《编译原理语法2(推导与语法树).ppt》由会员分享，可在线阅读，更多相关《编译原理语法2(推导与语法树).ppt（26页珍藏版）》请在金锄头文库上搜索。
1、第第 5 5 讲讲西北农林科技大学本科教程西北农林科技大学本科教程 主讲教师：赵建邦主讲教师：赵建邦 第三章第三章 语法分析语法分析l3.1 3.1 文法和语言文法和语言l3.2 3.2 推导与语法树推导与语法树l3.3 3.3 自顶向下的语法分析自顶向下的语法分析l3.4 3.4 自底向上的语法分析自底向上的语法分析l3.5 3.5 规范规约的自底向上语法分析方法规范规约的自底向上语法分析方法u第三章第三章语法分析语法分析l3.2 3.2 推导与语法树推导与语法树l推导与短语推导与短语l语法树与二义性语法树与二义性u重点掌握重点掌握l短语、句柄的概念短语、句柄的概念l二义性的消除二义性的消除
2、本讲目标本讲目标 u3.2.1 推导与短语推导与短语1、规范推导、规范推导在在3.1.1节中，所给句子节中，所给句子i+i*i推导序列中的每一步推导都是对句推导序列中的每一步推导都是对句型中的型中的最右非终结符最右非终结符用相应产生式的右部进行替换，这样的用相应产生式的右部进行替换，这样的推导称为推导称为最右最右推导推导（规范推导），（规范推导），规范推导的逆过程称为规范推导的逆过程称为规规范规约范规约如果如果每一步推导都是对句型中的最左非终结符用相应产生式每一步推导都是对句型中的最左非终结符用相应产生式的右部进行替换，则称为的右部进行替换，则称为最左最左推导推导3.2 3.2 推导与语法树推
3、导与语法树举例：举例：文法GE：EE+E | E*E | (E) | i (3.1) 句子i+i*i的最左推导和最右推导？u3.2.1 推导与短语推导与短语2、短语、短语设设是文法是文法GS的一个句型，如果有：的一个句型，如果有：则称则称是句型是句型关于非终结符关于非终结符A的一个的一个短语短语，或称，或称是是的一的一个个短语短语。特别是有。特别是有A产生式时，产生式时，为句型为句型的一个的一个直接短语直接短语或或简单简单短语短语 短语短语的两个条件缺一不可。仅有的两个条件缺一不可。仅有A 未必意味着未必意味着就是句型就是句型的一个短语，还需要的一个短语，还需要有有 加以限制；即短语属加以限制
4、；即短语属于句型的组成部分。于句型的组成部分。3.2 3.2 推导与语法树推导与语法树u3.2.1 推导与短语推导与短语3、句柄、句柄一个句型的最左直接短语称为该句型的一个句型的最左直接短语称为该句型的句柄句柄。注意，一个句。注意，一个句型的直接短语可能不只一个，但型的直接短语可能不只一个，但最左直接短语则是惟一的最左直接短语则是惟一的。3.2 3.2 推导与语法树推导与语法树举例：举例：文法GE：SAB A bB B Sb | a 句型“baSb”的短语和句柄？解答解答：（1）句型本身是该句型关于开始符号的短语句型本身是该句型关于开始符号的短语最左推导u3.2.1 推导与短语推导与短语3.2
5、 3.2 推导与语法树推导与语法树解答解答：（2）句型baSb的子串Sb,是该句型相对于非终结符B的一个短语，而且是该句型的直接短语 （3）句型baSb的子串a, 是该句型相对于非终结符B的一个短语，而且是该句型的直接短语、句柄最左推导u3.2.1 推导与短语推导与短语3.2 3.2 推导与语法树推导与语法树解答解答：（4）句型baSb的子串ba, 是该句型相对于非终结符A的一个短语注意：注意：短语、直接短语、句柄短语、直接短语、句柄都是针对某一都是针对某一句型句型来说的，来说的，都是指句型中的哪些符号串能够构成短语、直接短语、句都是指句型中的哪些符号串能够构成短语、直接短语、句柄。柄。脱离句
6、型，谈论三者是无意义的。脱离句型，谈论三者是无意义的。例例5.2 文法文法G G E T | E +T T F | T * F F i |（E）i i1 1*i*i2 2+i+i3 3 是文法是文法G G的一个句型吗？的一个句型吗？如果是，求出其句柄。如果是，求出其句柄。u3.2.1 推导与短语推导与短语4、素短语、素短语含有终结符的短语，如果它不存在也具有同样性质的真子串含有终结符的短语，如果它不存在也具有同样性质的真子串（不能包含有另一个素短语），则该短语为（不能包含有另一个素短语），则该短语为素素短语短语 (1)是短语是短语 (2)至少包含一个终结符至少包含一个终结符 (3)不再包含其它
7、素短语不再包含其它素短语例如例如，在，在 中，对于句型句型中，对于句型句型“E E + + E*iE*i”: :短语短语: :i i、E*iE*i和和E+E*iE+E*i素短语素短语: :i i3.2 3.2 推导与语法树推导与语法树E=E+E = E+E*E = E+E*i u3.2.1 推导与短语推导与短语4、素短语、素短语(练习练习) 3.2 3.2 推导与语法树推导与语法树E+TE+TETF*FTi先找短语：先找短语：T、T*F 、 T+T*F 、 i 、 T+T*F+i 再找素短语：再找素短语：T*F 、 iE+EE*EEi先找短语：先找短语：i 、E*i 、 E+E*i 再找素短语
8、：再找素短语：iu3.2.2 语法语法树与二义性树与二义性对程序语言来说，有两个问题需要解决：对程序语言来说，有两个问题需要解决： (1)(1)判别程序在语法上是否正确；判别程序在语法上是否正确； (2)(2)句子的识别或分析。句子的识别或分析。在在编译方法中，为了便于识别或分析句子而引入了编译方法中，为了便于识别或分析句子而引入了语法树语法树这一重这一重要的辅助要的辅助工具工具语法树语法树以图示化的形式把句子分解成各个组成部分来描述或以图示化的形式把句子分解成各个组成部分来描述或分析分析句子的语法结构句子的语法结构，这种图示化的表示与所定义的文法规则完全一，这种图示化的表示与所定义的文法规则
9、完全一致，但更为直观和致，但更为直观和完整完整3.2 3.2 推导与语法树推导与语法树u3.2.2 语法树与二义性语法树与二义性1、语法语法树树(定义定义)对文法对文法GS=(VT, VN, S, )，满足下列条件的树称为，满足下列条件的树称为GS的的语语法树法树：(1) 每个结点用每个结点用GS的一个终结符或非终结符标记；的一个终结符或非终结符标记；(2) 根结点用文法开始符根结点用文法开始符S标记标记； (3) 内部结点内部结点(指非树叶结点指非树叶结点)一定是非终结符一定是非终结符，如果某内部结，如果某内部结点点A有有n个分支，它的所有子结点从左至右依次标记为个分支，它的所有子结点从左至
10、右依次标记为x1、x2、xn，则，则Ax1x2xn一定是文法一定是文法GS的一条产生式的一条产生式； (4) 如果某结点标记为如果某结点标记为，则它必为叶结点且是其父结点的惟一，则它必为叶结点且是其父结点的惟一子结点。子结点。3.2 3.2 推导与语法树推导与语法树图图3-4 句子句子i+i*i的语法树的语法树1、开始符S作为根结点3.2 3.2 推导与语法树推导与语法树2、父亲节点是产生式左部，孩子节点对应产生式右部“EE+E”3、在一棵语法树生长过程中的任何时刻，所有那些没有后代的树叶结点自左至右排列起来就是一个句型。4、一棵已经完成的语法树无法判断是来自于最左推导还是最右推导，而使用文法
11、规则的推导过程是有先后之分的。如果坚持使用最左(或最右)推导，那么一棵语法树就完全等价于一个最左(或最右)推导u3.2.2 3.2.2 语法树与二义性语法树与二义性2 2、子树与短语、子树与短语语法树某个结点连同它的所有后代组成了一棵语法树某个结点连同它的所有后代组成了一棵子树子树。只含有。只含有单层分枝的子树称为单层分枝的子树称为简单子树简单子树。子子树与短语的关系十分密切，根据子树的概念，句型的短语、树与短语的关系十分密切，根据子树的概念，句型的短语、直接短语、句柄和素短语的直观解释如下直接短语、句柄和素短语的直观解释如下： ( (1)1) 短语：短语：子树的末端结点子树的末端结点( (即
12、树叶即树叶) ) 组成组成的符号串是相对于子树根的短语的符号串是相对于子树根的短语； ( (2 2) ) 直接直接短语短语：简单子树的：简单子树的末端结点末端结点 组成组成的符号串是相对于简单子树根的符号串是相对于简单子树根的的 直接直接短语短语3.2 3.2 推导与语法树推导与语法树SABbBaSbu3.2.2 3.2.2 语法树与二义性语法树与二义性2 2、子树与短语、子树与短语 (3) (3) 句柄：句柄：最左简单子树的最左简单子树的末端末端 结点结点组成的符号串为句柄组成的符号串为句柄； (4) (4) 素素短语短语：子树的末端结点子树的末端结点组组 成成的符号串含终结符，且的符号串含
13、终结符，且在在 该该子树中不再有包含终结符的更小子子树中不再有包含终结符的更小子树树显然显然，从语法树出发寻找短语、直接短语、句柄和素短语要直观，从语法树出发寻找短语、直接短语、句柄和素短语要直观得多得多。注意。注意: :子树末端结点组成的符号串子树末端结点组成的符号串是指由该子树根开始向是指由该子树根开始向下生长的下生长的所有所有末端结点末端结点( (即树叶即树叶) )，该子树的部分末端结点并不是，该子树的部分末端结点并不是该子树的短语。该子树的短语。3.2 3.2 推导与语法树推导与语法树SABbBaSb图3-5 E+E*i的语法树3.2 3.2 推导与语法树推导与语法树图3-6 E+E+
14、E*i的语法树直接短语、句柄、素短语不是短语直接短语u3.2.2 3.2.2 语法树与二义性语法树与二义性3 3、语法的二义性、语法的二义性对于文法任一句型的推导序列，总能为其构造一棵语法树，对于文法任一句型的推导序列，总能为其构造一棵语法树，那么文法的某个句型是否只对应一棵唯一的语法树呢？那么文法的某个句型是否只对应一棵唯一的语法树呢？也就也就是它是否只有唯一的一个最左（最右）推导呢？是它是否只有唯一的一个最左（最右）推导呢？对于文法对于文法(3.1)，句子，句子i+i*i存在两种最左（最右）推导，形成两存在两种最左（最右）推导，形成两棵不同的语法树棵不同的语法树:3.2 3.2 推导与语法
15、树推导与语法树最左推导最左推导1 1 最左推导最左推导2 2 图3-7 句子i+i*i的两棵不同的语法树3.2 3.2 推导与语法树推导与语法树u3.2.2 3.2.2 语法树与二义性语法树与二义性3 3、语法的二义性、语法的二义性u3.2.2 3.2.2 语法树与二义性语法树与二义性3 3、语法的二义性、语法的二义性再如，条件语句的文法再如，条件语句的文法GSGS为为 GSGS: S: S if b Sif b S S S if b S else Sif b S else S S S a a定义：文法定义：文法GSGS的一个句子如果能找到的一个句子如果能找到两种不同的最左推导两种不同的最左推
16、导( (或最右推导或最右推导) )，或者或者存在两棵不同的语法树存在两棵不同的语法树，则称这个句子，则称这个句子是是二义性二义性的。一个文法如果包含二义性的句子，则这个文法的。一个文法如果包含二义性的句子，则这个文法是是二义文法二义文法，否则是无二义文法。，否则是无二义文法。3.2 3.2 推导与语法树推导与语法树句子句子 if b if b a else a if b if b a else a 的两棵不同语法树的两棵不同语法树, ,请画出对应的两棵语法树请画出对应的两棵语法树u3.2.2 3.2.2 语法树与二义性语法树与二义性4 4、文法二义性的消除、文法二义性的消除对于一个二义性文法对
17、于一个二义性文法GS，如果能找到一个非二义性文法，如果能找到一个非二义性文法GS，使得，使得L(G)=L(G)，则该二义性文法的二义性是，则该二义性文法的二义性是可以消可以消除的除的。如果找不到这样的。如果找不到这样的GS，则二义性文法描述的语言为，则二义性文法描述的语言为先天二义性先天二义性的的。文法二义性消除方法：文法二义性消除方法： (1)不改变文法中原有的语法规则，仅增加一些语法的非形式不改变文法中原有的语法规则，仅增加一些语法的非形式规定；规定； (2)构造一个等价的无二义性文法，把排除二义性的规则合并构造一个等价的无二义性文法，把排除二义性的规则合并到原有文法中，改写原有的文法。到
18、原有文法中，改写原有的文法。(增加新的非终结符增加新的非终结符)3.2 3.2 推导与语法树推导与语法树u3.2.2 3.2.2 语法树与二义性语法树与二义性4、文法二义性的消除、文法二义性的消除例：将例：将文法文法(3.1)改写为无二义性的文法改写为无二义性的文法GE如下如下： GE: EE+T | T TT*F | F F (E) | i此时此时，句子，句子 i+i*i 就就只有只有如图如图3-9所示的惟一一棵语法所示的惟一一棵语法树：树：3.2 3.2 推导与语法树推导与语法树例例3.6 试将如下的二义性文法试将如下的二义性文法GS的二义性消除：的二义性消除：GS: Sif b S |
19、if b S else S | a解答解答 消除GS的二义性可采用如下两种方法：(1) 不改变已有规则，仅加进一项非形式的语法规定：else与离它最近的if匹配(即最近匹配原则)，这样，文法GS的句子if b if b a else a只对应惟一的一棵语法树(见图3-10)。(2) 改写文法GS为GS: SS1 | S2 S1if b S1 else S1 | a S2if b S | if b S1 else S2 GS对应的语法树见图3-113.2 3.2 推导与语法树推导与语法树3.2 3.2 推导与语法树推导与语法树图3-11 GS的复合if语句的语法树aa图3-10 复合if语句的语
20、法树u3.2.2 3.2.2 语法树与二义性语法树与二义性特别说明特别说明应该指出的是文法的二义性和语言二义性是应该指出的是文法的二义性和语言二义性是两个不同的概念两个不同的概念 通常通常只只说文法的二义性，而不说语言的二义性，这是因为可说文法的二义性，而不说语言的二义性，这是因为可能有两个不同的文法能有两个不同的文法G和和G,其中一个是二义性的，另一个是无其中一个是二义性的，另一个是无二义性的，但却有二义性的，但却有L(G)=L(G)，即这两个文法所产生的语言是，即这两个文法所产生的语言是相同的；相同的； 讲一个语言称为二义性的，是指对它不存在无二义性的文法，讲一个语言称为二义性的，是指对它不存在无二义性的文法，这样的语言称为先天二义性的语言。这样的语言称为先天二义性的语言。3.2 3.2 推导与语法树推导与语法树课后习题：课后习题： 3.2 3.33.2 3.2 推导与语法树推导与语法树
