《程序设计语言的语法描述.ppt》由会员分享，可在线阅读，更多相关《程序设计语言的语法描述.ppt（18页珍藏版）》请在金锄头文库上搜索。
1、第第3章章 程序设计语言的语法描述程序设计语言的语法描述3.1 文法的引入文法的引入3.2 上下文无关文法上下文无关文法3.3 文法举例（略）文法举例（略） 使用文法对程序设计语言的结构进行使用文法对程序设计语言的结构进行定义和描述。定义和描述。7/22/20243.1 文法的引入文法的引入 先讨论自然语言的文法。例：先讨论自然语言的文法。例：先讨论自然语言的文法。例：先讨论自然语言的文法。例：the big the big elephentelephent ate a banana ate a banana语法树语法树 根据英语的语法，上述句子的语法结构可用图（语法树）表示根据英语的语法，上
2、述句子的语法结构可用图（语法树）表示根据英语的语法，上述句子的语法结构可用图（语法树）表示根据英语的语法，上述句子的语法结构可用图（语法树）表示如下：如下：如下：如下： 非叶结点称为非叶结点称为非叶结点称为非叶结点称为语法单位，在形语法单位，在形语法单位，在形语法单位，在形式语言中称为非式语言中称为非式语言中称为非式语言中称为非终结符。终结符。终结符。终结符。处于根结点位处于根结点位处于根结点位处于根结点位置的结点又称为置的结点又称为置的结点又称为置的结点又称为开始符号。开始符号。开始符号。开始符号。叶结点称为单叶结点称为单叶结点称为单叶结点称为单词符号，在形式词符号，在形式词符号，在形式词符
3、号，在形式语言中称为终结语言中称为终结语言中称为终结语言中称为终结符。符。符。符。7/22/2024规则规则 可以通过建立一组规则，来描述上述句子的语法结构，规则在可以通过建立一组规则，来描述上述句子的语法结构，规则在可以通过建立一组规则，来描述上述句子的语法结构，规则在可以通过建立一组规则，来描述上述句子的语法结构，规则在形式语言中称为产生式。形式语言中称为产生式。形式语言中称为产生式。形式语言中称为产生式。1.1. 2.2. 3.3. the|athe|a4.4. bigbig5.5. elephant|bananaelephant|banana6.6. 7.7. 8.8. ateate由
4、规则推导句子由规则推导句子 可用规则来推导出句子。从开始符号出发，若能从规则推导可用规则来推导出句子。从开始符号出发，若能从规则推导可用规则来推导出句子。从开始符号出发，若能从规则推导可用规则来推导出句子。从开始符号出发，若能从规则推导出某符号串，则该符号串就是该文法的合法的句子，反之语法出某符号串，则该符号串就是该文法的合法的句子，反之语法出某符号串，则该符号串就是该文法的合法的句子，反之语法出某符号串，则该符号串就是该文法的合法的句子，反之语法错误。错误。错误。错误。上述英文句子可用下述规则来描述：上述英文句子可用下述规则来描述：上述英文句子可用下述规则来描述：上述英文句子可用下述规则来描
5、述：7/22/2024 the the the big the big the big elephant the big elephant the big elephant the big elephant the big elephant ate the big elephant ate the big elephant ate the big elephant ate the big elephant ate a the big elephant ate a the big elephant ate a bananathe big elephant ate a banana 上述推导可简单
6、表示为：上述推导可简单表示为：上述推导可简单表示为：上述推导可简单表示为： the big elephant ate a bananathe big elephant ate a banana。 值得注意的是用上述规则可推导出多个句子，因存在推导值得注意的是用上述规则可推导出多个句子，因存在推导值得注意的是用上述规则可推导出多个句子，因存在推导值得注意的是用上述规则可推导出多个句子，因存在推导 a big banana ate the elephanta big banana ate the elephant 所以，所以，所以，所以，a big banana ate the elephanta
7、 big banana ate the elephant也是文法的一个合法的句子。但意也是文法的一个合法的句子。但意也是文法的一个合法的句子。但意也是文法的一个合法的句子。但意义是荒谬的，也就是说句子的语义是错误的。义是荒谬的，也就是说句子的语义是错误的。义是荒谬的，也就是说句子的语义是错误的。义是荒谬的，也就是说句子的语义是错误的。 一个语法正确的句子不能保证一个语法正确的句子不能保证一个语法正确的句子不能保证一个语法正确的句子不能保证其语义是正确的，故一个句子是否正确，需要进行语法和语义两方面检查。其语义是正确的，故一个句子是否正确，需要进行语法和语义两方面检查。其语义是正确的，故一个句子
8、是否正确，需要进行语法和语义两方面检查。其语义是正确的，故一个句子是否正确，需要进行语法和语义两方面检查。综上所述，语言结构通常是用文法来定义和描述，文法是由终结符、非终结综上所述，语言结构通常是用文法来定义和描述，文法是由终结符、非终结综上所述，语言结构通常是用文法来定义和描述，文法是由终结符、非终结综上所述，语言结构通常是用文法来定义和描述，文法是由终结符、非终结符、开始符号（特殊非终结符）及产生式四个要素构成。从开始符号出发，根符、开始符号（特殊非终结符）及产生式四个要素构成。从开始符号出发，根符、开始符号（特殊非终结符）及产生式四个要素构成。从开始符号出发，根符、开始符号（特殊非终结符
9、）及产生式四个要素构成。从开始符号出发，根据产生式能推导出的句子全体称为文法所规定的语言据产生式能推导出的句子全体称为文法所规定的语言据产生式能推导出的句子全体称为文法所规定的语言据产生式能推导出的句子全体称为文法所规定的语言7/22/2024递归规则和递归文法递归规则和递归文法 递归是编译技术中的一个重要概念。递归是编译技术中的一个重要概念。递归是编译技术中的一个重要概念。递归是编译技术中的一个重要概念。递归定义：定义某事物，又用到该事物本身。递归定义：定义某事物，又用到该事物本身。递归定义：定义某事物，又用到该事物本身。递归定义：定义某事物，又用到该事物本身。递归规则（直接递归）：在规则的
10、左部和右部有相同的非终结递归规则（直接递归）：在规则的左部和右部有相同的非终结递归规则（直接递归）：在规则的左部和右部有相同的非终结递归规则（直接递归）：在规则的左部和右部有相同的非终结符。符。符。符。 例：例：例：例：UxUyUxUy，通常用大写字母表示非终结符，用小写字母表，通常用大写字母表示非终结符，用小写字母表，通常用大写字母表示非终结符，用小写字母表，通常用大写字母表示非终结符，用小写字母表示终结符。示终结符。示终结符。示终结符。 左递归规则：左递归规则：左递归规则：左递归规则：x=x=，UUyUUy（ 表示空串）表示空串）表示空串）表示空串） 右递归规则：右递归规则：右递归规则：右
11、递归规则：y=y=，UxUUxU间接递归：由规则推导产生。间接递归：由规则推导产生。间接递归：由规则推导产生。间接递归：由规则推导产生。 例：例：例：例：VUy|ZVUy|Z，UxVUxV 因存在推导因存在推导因存在推导因存在推导V VUyUyxVyxVy，故存在间接递归。，故存在间接递归。，故存在间接递归。，故存在间接递归。间接左递归：若间接左递归：若间接左递归：若间接左递归：若x=x=，则，则，则，则V V VyVy。间接右递归：若间接右递归：若间接右递归：若间接右递归：若y=y=，则，则，则，则V V xUxU。递归文法：含有递归规则和间接递归的文法，称为递归文法。递归文法：含有递归规则
12、和间接递归的文法，称为递归文法。递归文法：含有递归规则和间接递归的文法，称为递归文法。递归文法：含有递归规则和间接递归的文法，称为递归文法。 利用递归文法，可以用有穷的规则来描述无穷的语言，这不但利用递归文法，可以用有穷的规则来描述无穷的语言，这不但利用递归文法，可以用有穷的规则来描述无穷的语言，这不但利用递归文法，可以用有穷的规则来描述无穷的语言，这不但解决了语言的定义问题，而且使得对语言的语法检查成为可能。解决了语言的定义问题，而且使得对语言的语法检查成为可能。解决了语言的定义问题，而且使得对语言的语法检查成为可能。解决了语言的定义问题，而且使得对语言的语法检查成为可能。7/22/2024
13、3.2 上下文无关文法上下文无关文法 形式语言的奠基人乔姆斯基（形式语言的奠基人乔姆斯基（形式语言的奠基人乔姆斯基（形式语言的奠基人乔姆斯基（ChomskyChomsky）将文法）将文法）将文法）将文法分为分为分为分为4 4种类型，它们是：种类型，它们是：种类型，它们是：种类型，它们是：短语文法（短语文法（短语文法（短语文法（0 0型文法）型文法）型文法）型文法）上下文有关文法（上下文有关文法（上下文有关文法（上下文有关文法（1 1型文法）型文法）型文法）型文法）上下文无关文法（上下文无关文法（上下文无关文法（上下文无关文法（2 2型文法）型文法）型文法）型文法）正规文法（正规文法（正规文法（
14、正规文法（3 3型文法）型文法）型文法）型文法） 这四种文法在形式语言中都有严格的定义。但对于这四种文法在形式语言中都有严格的定义。但对于这四种文法在形式语言中都有严格的定义。但对于这四种文法在形式语言中都有严格的定义。但对于程序设计语言来说，上下文无关文法已经够用了，上程序设计语言来说，上下文无关文法已经够用了，上程序设计语言来说，上下文无关文法已经够用了，上程序设计语言来说，上下文无关文法已经够用了，上下文无关文法有足够的能力描述大多数现今使用的程下文无关文法有足够的能力描述大多数现今使用的程下文无关文法有足够的能力描述大多数现今使用的程下文无关文法有足够的能力描述大多数现今使用的程序设计
15、语言的语法结构。以后，序设计语言的语法结构。以后，序设计语言的语法结构。以后，序设计语言的语法结构。以后，“ “文法文法文法文法” ”一词若无特一词若无特一词若无特一词若无特别说明，则指别说明，则指别说明，则指别说明，则指“ “上下文无关文法上下文无关文法上下文无关文法上下文无关文法” ”。7/22/2024文法和语言文法和语言文法和语言文法和语言 一个文法一个文法一个文法一个文法GG是一个四元式是一个四元式是一个四元式是一个四元式(V(VT T,V,VN N,S,P),S,P)，其中，其中，其中，其中V VT T是一个终结符的非空有限集，终结符通常用小写字母表示。是一个终结符的非空有限集，终
16、结符通常用小写字母表示。是一个终结符的非空有限集，终结符通常用小写字母表示。是一个终结符的非空有限集，终结符通常用小写字母表示。V VN N是一个非终结符的非空有限集，非终结符通常用大写字母是一个非终结符的非空有限集，非终结符通常用大写字母是一个非终结符的非空有限集，非终结符通常用大写字母是一个非终结符的非空有限集，非终结符通常用大写字母表示。表示。表示。表示。S S是一个特殊的非终结符（是一个特殊的非终结符（是一个特殊的非终结符（是一个特殊的非终结符（S SV VN N），称为开始符号。），称为开始符号。），称为开始符号。），称为开始符号。P P是一个产生式（规则）的有限集合，每个产生式的形
17、式是是一个产生式（规则）的有限集合，每个产生式的形式是是一个产生式（规则）的有限集合，每个产生式的形式是是一个产生式（规则）的有限集合，每个产生式的形式是AA ，其中，其中，其中，其中A AV VN N， (V(VT TV VN N)* )*。终结符是语言的基本符号，即程序设计语言的单词。语法分析终结符是语言的基本符号，即程序设计语言的单词。语法分析终结符是语言的基本符号，即程序设计语言的单词。语法分析终结符是语言的基本符号，即程序设计语言的单词。语法分析时，终结符用单词的种别表示。时，终结符用单词的种别表示。时，终结符用单词的种别表示。时，终结符用单词的种别表示。 根据前面约定：根据前面约定
18、：根据前面约定：根据前面约定：标识符（简单变量）：标识符（简单变量）：标识符（简单变量）：标识符（简单变量）：i i无符号整常数：无符号整常数：无符号整常数：无符号整常数：x x无符号实常数：无符号实常数：无符号实常数：无符号实常数：y y单字符单词：单字符单词：单字符单词：单字符单词：用单词本身表示（例单词用单词本身表示（例单词用单词本身表示（例单词用单词本身表示（例单词“ “+”+”的的的的种别用种别用种别用种别用+ +表示）表示）表示）表示）多字符单词：多字符单词：多字符单词：多字符单词：需特别指定（例需特别指定（例需特别指定（例需特别指定（例“ “+”+”用用用用$ $表示）表示）表示
19、）表示）7/22/2024非终结符表示抽象的语法单位非终结符表示抽象的语法单位非终结符表示抽象的语法单位非终结符表示抽象的语法单位. . 例例例例“ “算术表达式算术表达式算术表达式算术表达式” ”、“ “布尔表达式布尔表达式布尔表达式布尔表达式” ”、“ “赋值语句赋值语句赋值语句赋值语句” ”、“ “说明说明说明说明语句语句语句语句” ”和和和和“ “程序程序程序程序” ”等。非终结符通常用大写字母表示，也可以用等。非终结符通常用大写字母表示，也可以用等。非终结符通常用大写字母表示，也可以用等。非终结符通常用大写字母表示，也可以用带尖括号的汉字表示。带尖括号的汉字表示。带尖括号的汉字表示。
20、带尖括号的汉字表示。开始符号是一个特殊的非终结符，它代表我们最感兴趣的语法开始符号是一个特殊的非终结符，它代表我们最感兴趣的语法开始符号是一个特殊的非终结符，它代表我们最感兴趣的语法开始符号是一个特殊的非终结符，它代表我们最感兴趣的语法单位。单位。单位。单位。 例如讨论算术表达式，那么描述算术表达式文法的开始符号就例如讨论算术表达式，那么描述算术表达式文法的开始符号就例如讨论算术表达式，那么描述算术表达式文法的开始符号就例如讨论算术表达式，那么描述算术表达式文法的开始符号就是是是是 。在程序设计语言中，我们最感兴趣的语法单位。在程序设计语言中，我们最感兴趣的语法单位。在程序设计语言中，我们最感
21、兴趣的语法单位。在程序设计语言中，我们最感兴趣的语法单位是是是是“ “程序程序程序程序” ”。产生式是定义语法单位的一种书写规则。产生式是定义语法单位的一种书写规则。产生式是定义语法单位的一种书写规则。产生式是定义语法单位的一种书写规则。上下文无关文法产生式的左部必定是一个非终结符，该非终上下文无关文法产生式的左部必定是一个非终结符，该非终上下文无关文法产生式的左部必定是一个非终结符，该非终上下文无关文法产生式的左部必定是一个非终结符，该非终结符称为左部符号。结符称为左部符号。结符称为左部符号。结符称为左部符号。产生式的右部是终结符和非终结符经有限次连接构成的文法产生式的右部是终结符和非终结符
22、经有限次连接构成的文法产生式的右部是终结符和非终结符经有限次连接构成的文法产生式的右部是终结符和非终结符经有限次连接构成的文法符号串，可以是空字符号串，可以是空字符号串，可以是空字符号串，可以是空字 。四种文法的区别主要是对产生式的左部和右部的限制不同。四种文法的区别主要是对产生式的左部和右部的限制不同。四种文法的区别主要是对产生式的左部和右部的限制不同。四种文法的区别主要是对产生式的左部和右部的限制不同。若干个左部符号相同的产生式，可合并为一个，例：若干个左部符号相同的产生式，可合并为一个，例：若干个左部符号相同的产生式，可合并为一个，例：若干个左部符号相同的产生式，可合并为一个，例：AA1
23、 1|2 2| n n，其中，其中，其中，其中 i i 称为称为称为称为A A的候选式的候选式的候选式的候选式(1(1 i i n)n)。7/22/2024 例例例例1 1：描述算术表达式文法：描述算术表达式文法：描述算术表达式文法：描述算术表达式文法G=(VG=(VT T,V,VN N,S,P),S,P)，其中，其中，其中，其中V VT T=+,-,*,/,=+,-,*,/,i,x,yi,x,y,(,),(,)V VN N = =,S = S = P = P = + - * / () ii/ /标识符标识符标识符标识符 xx/ /无符号整常数无符号整常数无符号整常数无符号整常数 yy/ /无
24、符号实常数无符号实常数无符号实常数无符号实常数 根据上述文法，可推导出任何仅包含加减乘除的算术表达式。根据上述文法，可推导出任何仅包含加减乘除的算术表达式。根据上述文法，可推导出任何仅包含加减乘除的算术表达式。根据上述文法，可推导出任何仅包含加减乘除的算术表达式。7/22/2024 因已约定非终结符和终结符的书写方式，非终结符和终结符在产生式中一目因已约定非终结符和终结符的书写方式，非终结符和终结符在产生式中一目因已约定非终结符和终结符的书写方式，非终结符和终结符在产生式中一目因已约定非终结符和终结符的书写方式，非终结符和终结符在产生式中一目了然，故终结符集了然，故终结符集了然，故终结符集了然
25、，故终结符集V VT T和非终结符集和非终结符集和非终结符集和非终结符集V VN N无需再显式列出。无需再显式列出。无需再显式列出。无需再显式列出。 若规定左部符号为开始符号的产生式写在所定义文法的第一行，上述文法若规定左部符号为开始符号的产生式写在所定义文法的第一行，上述文法若规定左部符号为开始符号的产生式写在所定义文法的第一行，上述文法若规定左部符号为开始符号的产生式写在所定义文法的第一行，上述文法GG又又又又可简单表示为如下形式：可简单表示为如下形式：可简单表示为如下形式：可简单表示为如下形式： + - * / () ii xx yy 若用若用若用若用E E表示表示表示表示 、T T表示
26、表示表示表示 、F F表示表示表示表示 ，借助符号，借助符号，借助符号，借助符号|，算术表，算术表，算术表，算术表达式文法达式文法达式文法达式文法GG可表示成如下最简形式：可表示成如下最简形式：可表示成如下最简形式：可表示成如下最简形式：EE+TEE+TETETT TTT*FTT*FT /FT /FF FF(E)F(E)i ix xy y7/22/2024 例例例例2 2：描述算术表达式文法：描述算术表达式文法：描述算术表达式文法：描述算术表达式文法G=(VG=(VT T,V,VN N,S,P),S,P)，其中，其中，其中，其中V VT T=+,-,*,/,=+,-,*,/,i,x,yi,x,
27、y,(,),(,)V VN N = =算术表达式算术表达式算术表达式算术表达式 S = S = P = P = + - * / ( () i i/ /标识符标识符标识符标识符 x x/ /无符号整常数无符号整常数无符号整常数无符号整常数 y y/ /无符号实常数无符号实常数无符号实常数无符号实常数 根据上述文法，同样可推导出任何仅包含加减乘除的算术表达根据上述文法，同样可推导出任何仅包含加减乘除的算术表达根据上述文法，同样可推导出任何仅包含加减乘除的算术表达根据上述文法，同样可推导出任何仅包含加减乘除的算术表达式。式。式。式。 用用用用E E表示表示表示表示 ，上述文法可简记为：，上述文法可简
28、记为：，上述文法可简记为：，上述文法可简记为：EE+E|E-E|E*E|E/EE+E|E-E|E*E|E/E|(E)|i|x|yE|(E)|i|x|y7/22/2024基本术语基本术语 以文法以文法以文法以文法GG：EE+E|E*EE+E|E*E|(E)|iE|(E)|i为例，进行下述讨论。为例，进行下述讨论。为例，进行下述讨论。为例，进行下述讨论。直接推出和直接归约直接推出和直接归约直接推出和直接归约直接推出和直接归约推导和归约推导和归约推导和归约推导和归约 若若若若 1 1 2 2 n n，则称该直接推出序列是从，则称该直接推出序列是从，则称该直接推出序列是从，则称该直接推出序列是从 1
29、1到到到到 n n的一个推的一个推的一个推的一个推导，记作导，记作导，记作导，记作 1 1 n n或或或或 n n。 1 1 n n：从：从：从：从 1 1始，经一步或一步以上可推导出始，经一步或一步以上可推导出始，经一步或一步以上可推导出始，经一步或一步以上可推导出 n n。 1 1 n n：从：从：从：从 1 1始，经步或步以上可推导出始，经步或步以上可推导出始，经步或步以上可推导出始，经步或步以上可推导出 n n，即，即，即，即 1 1 n n或或或或 1 1= = n n。 也可称直接归约序列也可称直接归约序列也可称直接归约序列也可称直接归约序列 n n,n-1n-1,1 1为为为为
30、n n到到到到 1 1的一个归约。的一个归约。的一个归约。的一个归约。句型句型句型句型 若存在推导若存在推导若存在推导若存在推导S S （S S为文法的开始符号），则称为文法的开始符号），则称为文法的开始符号），则称为文法的开始符号），则称 是文法的一个是文法的一个是文法的一个是文法的一个句型。句型。句型。句型。句子句子句子句子 仅包含终结符的句型称为句子。仅包含终结符的句型称为句子。仅包含终结符的句型称为句子。仅包含终结符的句型称为句子。7/22/2024语言语言语言语言 文法所能推导出的句子全体称为该文法的语言，记为：文法所能推导出的句子全体称为该文法的语言，记为：文法所能推导出的句子全体
31、称为该文法的语言，记为：文法所能推导出的句子全体称为该文法的语言，记为：L(G)=L(G)=|(S|(S )(V VT T * *) )等价文法等价文法等价文法等价文法 1 1和和和和2 2是二个不同的文法，若是二个不同的文法，若是二个不同的文法，若是二个不同的文法，若L(GL(G1 1)=L(G)=L(G2 2) )， 则称则称则称则称GG1 1和和和和GG2 2是等是等是等是等价文法。价文法。价文法。价文法。 等价文法的存在，使我们能够在不改变文法所规定的语言的前等价文法的存在，使我们能够在不改变文法所规定的语言的前等价文法的存在，使我们能够在不改变文法所规定的语言的前等价文法的存在，使我
32、们能够在不改变文法所规定的语言的前提下，为了某种目的改造文法。提下，为了某种目的改造文法。提下，为了某种目的改造文法。提下，为了某种目的改造文法。最左推导和最右推导最左推导和最右推导最左推导和最右推导最左推导和最右推导 在各种推导中，考虑今后语法分析的需要，我们仅对两种推导在各种推导中，考虑今后语法分析的需要，我们仅对两种推导在各种推导中，考虑今后语法分析的需要，我们仅对两种推导在各种推导中，考虑今后语法分析的需要，我们仅对两种推导感兴趣。感兴趣。感兴趣。感兴趣。1 1）最左推导）最左推导）最左推导）最左推导 在推导过程中始终对最左面的非终结符进行替换，记为在推导过程中始终对最左面的非终结符进
33、行替换，记为在推导过程中始终对最左面的非终结符进行替换，记为在推导过程中始终对最左面的非终结符进行替换，记为。2 2）最右推导）最右推导）最右推导）最右推导 在推导过程中始终对最右面的非终结符进行替换，记为在推导过程中始终对最右面的非终结符进行替换，记为在推导过程中始终对最右面的非终结符进行替换，记为在推导过程中始终对最右面的非终结符进行替换，记为。7/22/2024文法的二义性文法的二义性语法树语法树语法树语法树 我们可以用一个有向图表示一个句型的推导，这种表示称为语我们可以用一个有向图表示一个句型的推导，这种表示称为语我们可以用一个有向图表示一个句型的推导，这种表示称为语我们可以用一个有向
34、图表示一个句型的推导，这种表示称为语法树。语法树有助于理解一个句子语法结构的层次。法树。语法树有助于理解一个句子语法结构的层次。法树。语法树有助于理解一个句子语法结构的层次。法树。语法树有助于理解一个句子语法结构的层次。 在一般情况下，某一句型不论其推导过程如何，其最终形成的在一般情况下，某一句型不论其推导过程如何，其最终形成的在一般情况下，某一句型不论其推导过程如何，其最终形成的在一般情况下，某一句型不论其推导过程如何，其最终形成的语法树是相同的，故语法树是不同推导过程的共性抽象。若仅进语法树是相同的，故语法树是不同推导过程的共性抽象。若仅进语法树是相同的，故语法树是不同推导过程的共性抽象。
35、若仅进语法树是相同的，故语法树是不同推导过程的共性抽象。若仅进行最左（右）推导，则语法树和最左（右）推导等价。行最左（右）推导，则语法树和最左（右）推导等价。行最左（右）推导，则语法树和最左（右）推导等价。行最左（右）推导，则语法树和最左（右）推导等价。二义文法二义文法二义文法二义文法 若一个文法所产生的语言中，只要存在一个句子，它有二个最若一个文法所产生的语言中，只要存在一个句子，它有二个最若一个文法所产生的语言中，只要存在一个句子，它有二个最若一个文法所产生的语言中，只要存在一个句子，它有二个最左推导，或有二个最右推导，或句子的推导对应两棵语法树，则左推导，或有二个最右推导，或句子的推导对
36、应两棵语法树，则左推导，或有二个最右推导，或句子的推导对应两棵语法树，则左推导，或有二个最右推导，或句子的推导对应两棵语法树，则称该文法为二义文法。称该文法为二义文法。称该文法为二义文法。称该文法为二义文法。二义文法的利用和处理二义文法的利用和处理二义文法的利用和处理二义文法的利用和处理 1)1)根据条件修改文法，语言不变。根据条件修改文法，语言不变。根据条件修改文法，语言不变。根据条件修改文法，语言不变。算符优先性：规定算符优先性：规定算符优先性：规定算符优先性：规定* *优先于优先于优先于优先于+ +，i+ii+i*i *i等价于等价于等价于等价于i+(ii+(i*i)*i)。算符结合性：
37、规定同级运算服从左结合，算符结合性：规定同级运算服从左结合，算符结合性：规定同级运算服从左结合，算符结合性：规定同级运算服从左结合，i+i+ii+i+i等价于等价于等价于等价于( (i+i)+ii+i)+i。 2)2)根据条件修改编译程序的语法分析表，文法保持不变（详见根据条件修改编译程序的语法分析表，文法保持不变（详见根据条件修改编译程序的语法分析表，文法保持不变（详见根据条件修改编译程序的语法分析表，文法保持不变（详见第四、五章）。第四、五章）。第四、五章）。第四、五章）。7/22/2024 1 1）根据条件修改文法，语言不变。）根据条件修改文法，语言不变。）根据条件修改文法，语言不变。）
38、根据条件修改文法，语言不变。 算符优先性：规定算符优先性：规定算符优先性：规定算符优先性：规定* *优先于优先于优先于优先于+ +，i+ii+i*i *i等价于等价于等价于等价于i+(ii+(i*i)*i)。 算符结合性：规定同级运算服从左结合，算符结合性：规定同级运算服从左结合，算符结合性：规定同级运算服从左结合，算符结合性：规定同级运算服从左结合，i+i+ii+i+i等价于等价于等价于等价于( (i+i)+ii+i)+i。 例文法例文法例文法例文法GG G G：EE+E|E*EE+E|E*E|(E)|iE|(E)|i是一个二义文法。是一个二义文法。是一个二义文法。是一个二义文法。 根据上述
39、条件将文法根据上述条件将文法根据上述条件将文法根据上述条件将文法GG修改成修改成修改成修改成GG，如下所示，如下所示，如下所示，如下所示 GG：EE+T|TEE+T|T TT*F|F TT*F|F F(E) |i F(E) |i显然显然显然显然GG不是二义文法，但不是二义文法，但不是二义文法，但不是二义文法，但L(G)=L(G)L(G)=L(G)，故，故，故，故GG和和和和GG等价。等价。等价。等价。例句子例句子例句子例句子i+ii+i*i *i的最右推导：的最右推导：的最右推导：的最右推导： E EE+TE+TE+T*FE+T*FE+T*E+T*i iE+FE+F* *i iE+iE+i*
40、*i iT+iT+i* *i iF+iF+i* *i ii+ii+i*i *i E ET TT*FT*F?+?*? ?+?*? 先形成先形成先形成先形成+ +，才有可能形成，才有可能形成，才有可能形成，才有可能形成* *。若先形成。若先形成。若先形成。若先形成* *，只有带括号才可能形成，只有带括号才可能形成，只有带括号才可能形成，只有带括号才可能形成+ +。7/22/2024 2 2）根据条件修改编译程序的语法分析表，文法保持不变。）根据条件修改编译程序的语法分析表，文法保持不变。）根据条件修改编译程序的语法分析表，文法保持不变。）根据条件修改编译程序的语法分析表，文法保持不变。例文法例文法
41、例文法例文法GG： if if 标识符标识符标识符标识符 thenthen else else SfitSeSSfitSeS if if 标识符标识符标识符标识符 thenthen SfitSSfitS 标识符标识符标识符标识符= = SiSi=E=E 无符号整常数无符号整常数无符号整常数无符号整常数ExEx程序段程序段程序段程序段a=2a=2if x then if y then a=4 else a=6if x then if y then a=4 else a=6相应的语法结构表示为相应的语法结构表示为相应的语法结构表示为相应的语法结构表示为i=xi=xfitfitifitfiti= =
42、xeixei=x=x句子句子句子句子fitfitifitfiti= =xeixei=x=x的最左推导序列有二个，如下所示：的最左推导序列有二个，如下所示：的最左推导序列有二个，如下所示：的最左推导序列有二个，如下所示：S SfitSeSfitSeSfitfitSeSfitfitSeSfitfitifitfiti= =EeSEeSfitfitifitfiti= =xeSxeSfitfitifitfiti= =xeixei= =E Efitfitifitfiti= =xeixei=x=xS SfitSfitSfitfitSeSfitfitSeSfitfitifitfiti= =EeSEeSfitf
43、itifitfiti= =xeSxeSfitfitifitfiti= =xeixei= =E Ef fifiiifii= =xeixei=x=x因句子因句子因句子因句子fitfitifitfiti= =xeixei=x=x存在二个最左推导，故文法存在二个最左推导，故文法存在二个最左推导，故文法存在二个最左推导，故文法GG为二义文法。为二义文法。为二义文法。为二义文法。7/22/2024这样对于该程序段有二个解释：这样对于该程序段有二个解释：这样对于该程序段有二个解释：这样对于该程序段有二个解释：假设假设假设假设elseelse和最近的和最近的和最近的和最近的if if结合，即结合，即结合，即结
44、合，即 a=2a=2 if x then if x then begin begin if y then a=4 else a=6 if y then a=4 else a=6 end end 当当当当x x和和和和y y为下列值时，相应为下列值时，相应为下列值时，相应为下列值时，相应a a的值为：的值为：的值为：的值为：x xy ya atruetruetruetrue4 4truetrueflaseflase6 6flaseflase2 2假设假设假设假设elseelse和最远的和最远的和最远的和最远的if if结合，即结合，即结合，即结合，即 a=2a=2 if x then if x
45、then begin begin if y then a=4 if y then a=4 end end else else a=6a=6x xy ya atruetruetruetrue4 4truetrueflaseflase2 2flaseflase6 6 实际的编译程序不可能、也不允许有两种解释，通常按第一实际的编译程序不可能、也不允许有两种解释，通常按第一实际的编译程序不可能、也不允许有两种解释，通常按第一实际的编译程序不可能、也不允许有两种解释，通常按第一种方式进行翻译执行，即种方式进行翻译执行，即种方式进行翻译执行，即种方式进行翻译执行，即“ “elseelse和最近的和最近的和最近的和最近的if if结合结合结合结合” ”。7/22/2024结束结束7/22/2024
