编译原理语法2(推导与语法树).ppt
《编译原理语法2(推导与语法树).ppt》由会员分享,可在线阅读,更多相关《编译原理语法2(推导与语法树).ppt(26页珍藏版)》请在三一文库上搜索。
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 推导与语法树,举例:文法GE:E E + E | E * E | (E) | i (3.1) 句子i+i*i的最左推导和最右推导?,3.2.1 推导与短语 2、短语 设是文法GS的一个句型,如果有: 则称是句型关于非终结符A的一个短语,或称是的一个短语。特别是有A产生式时,为句型的一个直接短语或简单短语 短语的两个条件缺一不可。仅有A 未必意味着就是句型的一个短语,还需要有 加以限制;即短语属于句型的组成部分。,3.2 推导与语法树,3.2.1 推导与短语 3、句柄 一个句型的最左直接短语称为该句型的句柄。注意,一个句型的直接短语可能不只一个,但
3、最左直接短语则是惟一的。,3.2 推导与语法树,举例:文法GE:S AB A bB B Sb | a 句型“baSb”的短语和句柄?,解答: (1),句型本身是该句型关于开始符号的短语,最左推导,3.2.1 推导与短语,3.2 推导与语法树,解答: (2),句型baSb的子串Sb,是该句型相对于非终结符B的一个短语,而且是该句型的直接短语,(3),最右推导,句型baSb的子串a, 是该句型相对于非终结符B的一个短语,而且是该句型的直接短语、句柄,最左推导,3.2.1 推导与短语,3.2 推导与语法树,解答: (4),最右推导,句型baSb的子串ba, 是该句型相对于非终结符A的一个短语,注意:
4、短语、直接短语、句柄都是针对某一句型来说的,都是指句型中的哪些符号串能够构成短语、直接短语、句柄。脱离句型,谈论三者是无意义的。,例5.2 文法G E T | E +T T F | T * F F i |(E) i1*i2+i3 是文法G的一个句型吗? 如果是,求出其句柄。,3.2.1 推导与短语 4、素短语 含有终结符的短语,如果它不存在也具有同样性质的真子串(不能包含有另一个素短语),则该短语为素短语 (1)是短语 (2)至少包含一个终结符 (3)不再包含其它素短语 例如,在 中,i、E*i和E+E*i是句型E + E*i的三个短语;其中i为素短语;E*i虽为短语且含有终结符,但它的真子串
5、i是素短语,故E*i不是素短语;同样E+E*i也不是素短语。,3.2 推导与语法树,3.2.1 推导与短语 4、素短语(练习),3.2 推导与语法树,先找短语:,T、T*F 、 T+T*F 、 i 、 T+T*F+i,再找素短语:,T*F 、 i,先找短语:,i 、E*i 、 E+E*i,再找素短语:,i,3.2.2 语法树与二义性 对程序语言来说,有两个问题需要解决: (1)判别程序在语法上是否正确; (2)句子的识别或分析。 在编译方法中,为了便于识别或分析句子而引入了语法树这一重要的辅助工具 语法树以图示化的形式把句子分解成各个组成部分来描述或分析句子的语法结构,这种图示化的表示与所定义
6、的文法规则完全一致,但更为直观和完整,3.2 推导与语法树,3.2.2 语法树与二义性 1、语法树(定义) 对文法GS = (VT, VN, S, ),满足下列条件的树称为GS的语法树: (1) 每个结点用GS 的一个终结符或非终结符标记; (2) 根结点用文法开始符S标记; (3) 内部结点(指非树叶结点)一定是非终结符,如果某内部结点A有n个分支,它的所有子结点从左至右依次标记为x1、x2、xn,则A x1x2xn一定是文法GS的一条产生式; (4) 如果某结点标记为,则它必为叶结点且是其父结点的惟一子结点。,3.2 推导与语法树,图3-4 句子i+i*i的语法树,1、开始符S作为根结点,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 语法 推导
链接地址:https://www.31doc.com/p-2258610.html