第六章 自下而上的语法分析.pptVIP

第六章 自下而上的语法分析;自下而上语法分析概述 简单优先分析 算符优先分析 ;自下而上语法分析概述;自下而上语法分析概述;文法G[S]：(1) S → aAcBe(2) A → b(3) A → Ab(4) B → d;自下而上语法分析算法的一般描述;算法应考虑的问题;自下而上语法分析的策略：移进-规约分析； 移进就是将一个终结符推进栈 归约就是将0个或多个符号从栈中弹出，根据产生式将一个非终结符压入栈 移进-归约过程是自顶向下最右推导的逆过程（规范归约） ;规约T ? int;A Shift-Reduce Parse in Detail (1);A Shift-Reduce Parse in Detail (2);A Shift-Reduce Parse in Detail (3);A Shift-Reduce Parse in Detail (4);A Shift-Reduce Parse in Detail (5);A Shift-Reduce Parse in Detail (6);A Shift-Reduce Parse in Detail (7);A Shift-Reduce Parse in Detail (8);A Shift-Reduce Parse in Detail (9);A Shift-Reduce Parse in Detail (10);A Shift-Reduce Parse in Detail (11);我们如何决定什么时候??进，什么时候规约？ 考虑 int | * int + int 我们可以用 T ? int进行归约，而得到 T | * int + int 致命错误: 无法规约到开始符号 E 直觉: Want to reduce only if the result can still be reduced to the start symbol 一般的移进-归约策略： 若句柄在栈顶出现，则归约 否则移进 句柄（Handles）:句型的最左直接短语;短语、直接短语、句柄的定义： 文法G[S]， S αAδ且A b则称b是句型αbδ相对于非终结符A的短语。 若有A ? b则称b是句型αbδ相对于该规则A → b的直接短语。 一个句型的最左直接短语称为该句型的句柄。;Conflicts;Source of Conflicts;Conflict Example;One Shift-Reduce Parse;Another Shift-Reduce Parse;Conflict Solutions;自下而上的分析算法;简单优先分析法;文法G[S]：(1) S → bAb(2) A → (B|a(3) B → Aa);优先关系;简单优先文法的定义;算符优先分析;文法G[E]：E→E+E|E-E|E*E|E/E|E?E|(E)|i;如何确定算符优先关系？;算符文法的定义;算符优先关系的定义;算符优先文法的定义;算符优先关系表的构造;首先引入两个概念 FIRSTVT(B)={b|B b…或B Cb...} 对于非终结符B，其往下推导所可能出现的首个算符 LASTVT(B)={a|B a…或B aC...} 对于非终结符B，其往下推导所可能出现的最后一个算符;如何计算算符优先关系;文法G[E]：(0) E’→#E#(1) E→E+T(2) E→T(3) T→T*F(4) T→F(5) F→P?F|P(6) P→(E)(7) P→i;算符优先分析算法;算符文法的任一句型有如下形式：#N1a1N2a2......NnanNn+1#,若Niai......NjajNj+1为句柄，则有ai-1ai=ai=...= aj-1 = aj ai+1 对于算符优先文法，如果aNb(或ab)出现在句型r中 若ab，则在r中必含有b而不含a的短语存在 若ab，则在r中必含有a而不含b的短语存在 若a=b，则在r中含有a的短语必含有b，反之亦然 定义 cfg G 的句型的素短语是一个短语，它至少包含一个终结符，且除自身外不再包含其他素短语。处于句型最左边的素短语为最左素短语;文法G[E]：(1) E→E+T(2) E→T(3) T→T*F(4) T→F(5) F→P?F|P(6) P→(E)(7) P→i;优先函数;算符优先分析法的局限性;作业