编译原理语法2(推导与语法树)

《编译原理语法2(推导与语法树)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第5讲编译原理西北农林科技大学本科教程主讲教师：赵建邦第三章语法分析3.1文法和语言3.2推导与语法树3.3自顶向下的语法分析3.4自底向上的语法分析3.5规范规约的自底向上语法分析方法第三章《语法分析》3.2推导与语法树推导与短语语法树与二义性重点掌握短语、句柄的概念二义性的消除本讲目标3.2.1推导与短语1、规范推导在3.1.1节中，所给句子i+i*i推导序列中的每一步推导都是对句型中的最右非终结符用相应产生式的右部进行替换，这样的推导称为最右推导（规范推导），规范推导的逆过程称为规范规约如果每一步推导都是对句型中的最左非终结符用相应产生

2、式的右部进行替换，则称为最左推导3.2推导与语法树举例：文法G[E]：E→E+E

3、E*E

4、(E)

5、i(3.1)句子i+i*i的最左推导和最右推导？3.2.1推导与短语2、短语设αβδ是文法G[S]的一个句型，如果有：则称β是句型αβδ关于非终结符A的一个短语，或称β是αβδ的一个短语。特别是有A→β产生式时，β为句型αβδ的一个直接短语或简单短语短语的两个条件缺一不可。仅有A→β未必意味着β就是句型αβδ的一个短语，还需要有加以限制；即短语属于句型的组成部分。3.2推导与语法树3.2.1推导与短语3、句柄一个句型的最左直接短语称为该句型的句柄

6、。注意，一个句型的直接短语可能不只一个，但最左直接短语则是惟一的。3.2推导与语法树举例：文法G[E]：S→ABA→bBB→Sb

7、a句型“baSb”的短语和句柄？[解答]：（1）句型本身是该句型关于开始符号的短语最左推导3.2.1推导与短语3.2推导与语法树[解答]：（2）句型baSb的子串Sb,是该句型相对于非终结符B的一个短语，而且是该句型的直接短语（3）最右推导句型baSb的子串a,是该句型相对于非终结符B的一个短语，而且是该句型的直接短语、句柄最左推导3.2.1推导与短语3.2推导与语法树[解答]：（4）最右推导句型baSb的子串ba

8、,是该句型相对于非终结符A的一个短语注意：短语、直接短语、句柄都是针对某一句型来说的，都是指句型中的哪些符号串能够构成短语、直接短语、句柄。脱离句型，谈论三者是无意义的。例5.2文法GE→T

9、E+TT→F

10、T*FF→i

11、（E）i1*i2+i3是文法G的一个句型吗？如果是，求出其句柄。3.2.1推导与短语4、素短语含有终结符的短语，如果它不存在也具有同样性质的真子串（不能包含有另一个素短语），则该短语为素短语(1)是短语(2)至少包含一个终结符(3)不再包含其它素短语例如，在中，i、E*i和E+E*i是句型E + E*i的三个短语；其中i为

12、素短语；E*i虽为短语且含有终结符，但它的真子串i是素短语，故E*i不是素短语；同样E+E*i也不是素短语。3.2推导与语法树3.2.1推导与短语4、素短语(练习)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再找素短语：i3.2.2语法树与二义性对程序语言来说，有两个问题需要解决：(1)判别程序在语法上是否正确；(2)句子的识别或分析。在编译方法中，为了便于识别或分析句子而引入了语法树这一重要的辅助工具语法树以图示化的形式

13、把句子分解成各个组成部分来描述或分析句子的语法结构，这种图示化的表示与所定义的文法规则完全一致，但更为直观和完整3.2推导与语法树3.2.2语法树与二义性1、语法树(定义)对文法G[S] = (VT,VN,S,ξ)，满足下列条件的树称为G[S]的语法树：(1)每个结点用G[S]的一个终结符或非终结符标记；(2)根结点用文法开始符S标记；(3)内部结点(指非树叶结点)一定是非终结符，如果某内部结点A有n个分支，它的所有子结点从左至右依次标记为x1、x2、…、xn，则A → x1x2…xn一定是文法G[S]的一条产生式；(4)如果某结点标记为ε，

14、则它必为叶结点且是其父结点的惟一子结点。3.2推导与语法树图3-4句子i+i*i的语法树1、开始符S作为根结点3.2推导与语法树2、父亲节点是产生式左部，孩子节点对应产生式右部“E→ E+E”3、在一棵语法树生长过程中的任何时刻，所有那些没有后代的树叶结点自左至右排列起来就是一个句型。4、一棵已经完成的语法树无法判断是来自于最左推导还是最右推导，而使用文法规则的推导过程是有先后之分的。如果坚持使用最左(或最右)推导，那么一棵语法树就完全等价于一个最左(或最右)推导3.2.2语法树与二义性2、子树与短语语法树某个结点连同它的所有后代组成了一棵子

15、树。只含有单层分枝的子树称为简单子树。子树与短语的关系十分密切，根据子树的概念，句型的短语、直接短语、句柄和素短语的直观解释如下：(1)短语：子树的末端结点(即树叶