[工学]编译原理第二章1.pptVIP

第二章 文法和语言的基本知识 第二章 文法和语言的基本知识 2.1 概 述 对程序设计语言的描述是从语法、语义和语用三个因素来考虑。 2.1 概 述 2.2 字母表和符号串的基本概念 2.2 字母表和符号串的基本概念 2.2 字母表和符号串的基本概念 2.2 字母表和符号串的基本概念 2.2 字母表和符号串的基本概念 说明: 2.2 字母表和符号串的基本概念 2.2 字母表和符号串的基本概念 2.2 字母表和符号串的基本概念 2.2 字母表和符号串的基本概念 2.2 字母表和符号串的基本概念 2.2 字母表和符号串的基本概念 2.2 字母表和符号串的基本概念 2.2 字母表和符号串的基本概念 2.2 字母表和符号串的基本概念 2.2 字母表和符号串的基本概念 2.3 文法和语言的形式定义 2.3 文法和语言的形式定义 2.3 文法和语言的形式定义 2.3 文法和语言的形式定义 2.3 文法和语言的形式定义 2.3 文法和语言的形式定义 2.3.2 文法的形式定义 2.3.2 文法的形式定义 2.3.2 文法的形式定义 2.3.2 文法的形式定义 2.3.2 文法的形式定义 2.3.2 文法的形式定义 2.3.2 文法的形式定义 2.3.2 文法的形式定义 2.3.2 文法的形式定义 2.3.2 文法的形式定义 2.3.2 文法的形式定义 2.3.2 文法的形式定义 2.3.2 文法的形式定义 2.3.2 文法的形式定义 2.3.2 文法的形式定义 2.3.2 文法的形式定义 2.3.2 文法的形式定义 2.3.2 文法的形式定义 2.3.2 文法的形式定义 2.3.2 文法的形式定义 2.3.3 语言的形式定义 2.3.3 语言的形式定义 例如，设有文法G[S]: 2.3.3 语言的形式定义 2.3.3 语言的形式定义 2.3.3 语言的形式定义 2.3.3 语言的形式定义 2.3.3 语言的形式定义 2.3.3 语言的形式定义 2.3.2 语言的形式定义 2.3.3 语言的形式定义 2.3.3 语言的形式定义 2.3.3 语言的形式定义 2.3.3 语言的形式定义 2.3.3 语言的形式定义 2.3.3 语言的形式定义 2.3.4 规范推导和规范归约 2.3.4 规范推导和规范归约 2.3.4 规范推导和规范归约 2.3.4 规范推导和规范归约 2.3.4 规范推导和规范归约 2.3.4 规范推导和规范归约 2.3.5 递归规则与文法的递归性 2.3.5 递归规则与文法的递归性 2.3.5 递归规则与文法的递归性 2.3.5 递归规则与文法的递归性 2.3.5 递归规则与文法的递归性 2.3.5 递归规则与文法的递归性 同一个句型(句子)可以通过不同的推导序列推导出来，这是因为在推导过程中与所选择非终结符的次序无关。 最左(最右)推导，是指对于一个推导序列中的每一步直接推导 α?β , 都是对α 中的最左(最右)非终结符进行替换。 最右推导也称为规范推导，用规范推导推导出的句型称为规范句型。 例 设有文法G[S]: 请给出句子101001的最右、最左推导。 S→AB A→A0 | 1B B→0 | S1 S ?AB ?AS1 ?AAB1 ?AA01 ?A1B01 ?A1001 ?1B1001 ?101001 句子101001的最右推导为: S→AB A→A0 | 1B B→0 | S1 句子101001的最左推导为： S ?AB ?1BB ?10B ?10S1 ?10AB1 ?101BB1 ?1010B1 ?101001 2.3.4 规范推导和规范归约 归约是与推导相对的概念，推导是把句型中的非终结符用规则的一个右部来替换的过程，而归约则是把句型中的某个子串用一个非终结符来替换的过程。 若用?表示归约，设A→α是文法G中的 一个规则，则我们有： . xAy?xαy xαy?xAy . 2.3.4 规范推导和规范归约 例如，例文法G[N1]中有规范推导： 则有规范归约： 规范推导的逆过程，称为最左归约，也称为规范归约。 N1 ?N ?ND ?N2 ?D2 ?12 12 ?D2 . ?N2 . ?ND . ?N . ?N1 . 递归规则 如果文法中有规则 A→A … 称为规则左递归。 如果文法中有规则 A→ … A 称为规则右递归。 如果文法中有规则 A→ …A… 称为规则递归。 文法的递归性 若文法中有推导A?A …称文法左递归。 + 若文法中有推导A? … A称文法右递归。 + 若文法中有推导A