《编译原理第5讲汇总》由会员分享，可在线阅读，更多相关《编译原理第5讲汇总（37页珍藏版）》请在金锄头文库上搜索。
1、1 of 36,内容提纲,语法分析的任务 规范推导 短语 句柄 素短语 语法树与二义性 语法树 子树和短语 文法的二义性 文法二义性的消除 自上而下分析方法,2 of 36,内容提纲,语法分析的任务 规范推导 短语 句柄 素短语 语法树与二义性 语法树 子树和短语 文法的二义性 文法二义性的消除 自上而下分析方法,3 of 36,语法分析的任务,问题： 词法分析中讲解了如何判断源程序中单词的正确性，并输出正确的单词符号。那么如何知道这些正确的单词是否能构成正确的表达式、语句或程序呢？这就是语法分析的任务 语法分析的任务 在词法分析识别出正确的单词符号串的基础上，分析并判定程序的语法结构是否符合
2、语法规则。,4 of 36,语法分析在编译系统中所处的位置,5 of 36,语法分析器的输入 Token序列：词法分析的输出，是各个单词都正确的源程序的变换形式，是一个有限序列 语法分析器的输出 分析树：表示方法？ 错误处理信息：定位、继续编译,语法分析的接口设计,6 of 36,语法分析器的功能 按照语言的语法构成规则, 识别输入的符号串能否构成一个句子。这些规则是用文法的产生式来定义的。 问题 对给定的一个输入串，如何判定它是不是一个句子？ 方法 根据文法的产生式规则，从开始符号出发，看能否推导出与这个输入串匹配的句子。这需要建立与输入串匹配的语法分析树。,7 of 36,内容提纲,语法分
3、析的任务 规范推导 短语 句柄 素短语 语法树与二义性 语法树 子树和短语 文法的二义性 文法二义性的消除,8 of 36,规范推导,最右推导：每一步推导都是对句型中的最右非终结符用相应产生式的右部进行替换。,最左推导：每一步推导都是对句型中的最左非终结符用相应产生式的右部进行替换。,称最右推导为规范推导。 规范规约：规范推导的逆过程。,9 of 36,G = ( i, +, *, (, ) , E , E, P) P： E E + E E E * E E ( E ) E i,解：使用最左推导： E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)
4、*i,例：判定输入串(i+i)*i是否是下述文法的句子？,结论：能够从开始符号出发推导出给定的输入串， 是句子。,10 of 36,短语,定义：令G是一个文法，S是文法的开始符号，假定是文法G的一个句型，如果有 且,则称是句型相对于非终结符A的短语。 如果还有A,则称是句型的直接短语。 一个句型的最左直接短语称为该句型的句柄。,11 of 36,考虑文法G(E): E T | E+T T F | T*F F (E) | i 和句型i1*i2+i3： E E+T E+F E+i3 T+i3 T*F+i3 T*i2+i3 F*i2+i3 i1*i2+i3 短语： i1，i2，i3， i1*i2，
5、i1*i2+i3 直接短语： i1，i2，i3 句柄： i1,12 of 36,句型 归约规则 abbcde (2) A b aAbcde (3) A Ab aAcde (4) B d aAcBe (1) S aAcBe S,用句柄对句子进行归约,13 of 36,素短语,素短语：含有终结符的短语，如果它不存在具有同样性质（含有终结符）的真子串。 例如，在 中，i、E*i和E+E*i是句型E+E*i的三个短语； i为素短语； E*i虽为短语且含有终结符，但它的真子串i是素短语，故E*i不是素短语； 同样，E+E*i也不是素短语。,14 of 36,内容提纲,语法分析的任务 规范推导 短语 句柄
6、 素短语 语法树与二义性 语法树 子树和短语 文法的二义性 文法二义性的消除,15 of 36,语法树,对程序语言来说，有两个问题需要解决： 判别程序在语法上是否正确 句子的识别或分析 编译方法中常用语法树来辅助识别或分析句子。 语法树是推导的形式化表示，有助于理解句子语法结构的层次,16 of 36,语法树定义,对文法G=(VT,VN,S,) ，满足下列条件的树称为GS的语法树： (1) 每个结点用GS的一个终结符或非终结符标记； (2) 根结点用文法开始符S标记； (3) 内部结点(指非树叶结点)一定是非终结符，如果某内部结点A有n个分支，它的所有子结点从左至右依次标记为x1、x2、xn，
7、则Ax1x2xn一定是文法GS的一条产生式； (4) 如果某结点标记为，则它必为叶结点且是其父结点的惟一子结点。,17 of 36,例：对文法G = ( i, +, *, (, ) , E, E , P) P： E E + E | E * E | ( E ) | i 句子(i+i)*i 的语法树：,以文法开始符E作为根结点； 当某个非终结符被它对应的产生式右部某个候选式所替换时产生下一代新结点，候选式中从左至右的每一个符号都依次顺序对应一个新结点，每个新结点与其父结点之间都有一条连线(树枝) 在语法树的推导过程中的任何时刻，没有后代的树叶结点自左至右排列起来就是一个句型 一棵语法树表示了一个句
8、型很多可能的不同推导过程。(包括最左推导和最右推导),18 of 36,例： G =( i, +, *, (, ) , E, E, P) P： E E + E | E * E | ( E ) | i 句子 ( i * i + i)的语法树： (1) E (E) (E + E) (E * E + E) (i * E + E) (i * i + E) (i *i + i),(2) E (E) (E * E) (i*E) (i * E + E) (i * i + E) (i *i + i),并非任何情况下一个句型就唯一地对应一棵语法树。,19 of 36,语法树与推导,如果坚持使用最左(或最右)推导
9、，那么一棵语法树就完全等价于一个最左(或最右)推导 这种等价性也包括语法树的每一步生长和推导的每一步展开的这种完全一致性。,20 of 36,子树和短语,语法树的某个结点连同它的所有后代组成了一棵子树,子树,简单子树,只含有单层分枝的子树称为简单子树。,21 of 36,子树与短语,(1) 短语：子树的树叶组成的符号串是相对于子树根的短语；,i*i是相对于E的短语,22 of 36,子树与短语,(2) 直接短语：简单子树的树叶组成的符号串是相对于简单子树根的直接短语；,i是相对于E的短语,23 of 36,子树与短语,(3) 句柄：最左简单子树的树叶组成的符号串为句柄；,i是句柄,24 of
10、36,子树与短语,(4) 素短语：子树的树叶组成的符号串含终结符，且该子树中不存在包含终结符的更小子树。 子树树叶组成的符号串是指由该子树根开始向下生长的所有树叶，该子树的部分树叶不是该子树的短语。,i是素短语,25 of 36,图35 E+E*i的语法树,对图35所示的关于句型E+E*i的语法树来说，它有3棵子树，即3个短语，分别为i、E*i和E+E*i；而直接短语、句柄和素短语均为i。,26 of 36,文法的二义性,文法GS的一个句子如果能找到两种不同的最左推导(或最右推导)，或者存在两棵不同的语法树，则称这个句子是二义性的。 一个文法如果包含二义性的句子，则这个文法是二义文法，否则是无
11、二义文法。,27 of 36,图36 句子i+i*i的两棵不同语法树,例如，文法G(E):EE+E|E*E|(E)|i，句子i+i*i存在着两种最左推导或最右推导，所形成的两棵不同的语法树如图36所示。,28 of 36,二义文法,例：条件语句的文法GS为： GS: Sif B S Sif B S else S SA /*A指其它语句*/ VN = B,S,A，VT = if , else， 句型if B if B S else S所对应的两棵不同语法树(见右图)。 故文法GS是二义文法。,29 of 36,文法二义性的消除,文法是二义性的，并不说明该文法所描述的语言也是二义性的。 对于一个二
12、义性文法GS，如果能找到一个非二义性文法GS，使得L(G)=L(G)，则该二义性文法的二义性是可以消除的。 如果找不到这样的GS，则二义性文法描述的语言为先天二义性的。,30 of 36,文法二义性的消除方法,方法一：不改变文法中原有的语法规则，仅加进一些语法的非形式规定。 如对文法G(E):EE+E|E*E|(E)|i ， 不改变已有的四条规则(即四个产生式) 仅加进运算符的优先顺序和结合规则： *优先于+，且*、+都服从左结合 则句子i+i*i就只有唯一一棵语法树(如右图),31 of 36,文法二义性的消除,方法二： 把排除二义性的规则合并到原有文法中，改写原有的文法，构造一个等价的无二
13、义性文法。 例如：将文法G(E):EE+E|E*E|(E)|i改写为无二义性的文法： GE: EE+TT TT*FF F(E)i 则句子i+i*i就只有唯一一棵语法树（右图）。,32 of 36,例题3.6,试将如下的二义性文法GS的二义性消除: GS: Sif b Sif b S else SA 解 方法一：不改变已有规则，仅加进一项非形式的语法规定：else与离它最近的if匹配(即最近匹配原则)，文法GS的句子if b if b A else A只对应惟一的一棵语法树(见右图)。,33 of 36,例题3.6,方法二：改写文法 GS: Sif b Sif b S else SA 为GS:
14、SS1S2 S1if b S1 else S1A S2if b Sif b S1 else S2 由于引起二义性的原因是if-else语句的if后可以是任意if型语句，所以改写文法时规定if和else之间只能是if-else语句或其它语句。改写后文法GS的句子if b if b A else A只对应惟一的一棵语法树(如图),34 of 36,文法的二义性不可判定：不存在一种算法，能够在有限步内判定一个文法是否为二义性的。 二义性文法有时也会带来一定的好处，如语法分析中二义性文法的应用。,说明,35 of 36,要点回顾,规范推导 短语 句柄 素短语 语法树与二义性 语法树 子树和短语 文法的二义性 文法二义性的消除,36 of 36,思考题,什么是最左推导、最右推导？ 什么是短语、直接短语？ 什么是句柄、素短语？ 什么是文法GS的语法树？ 什么是句子的二义性？ 如何消除文法的二义性？,37 of 36,谢谢！,
