第五章语法分析一自下而上分析 ■自上而下分析法(Top一down) ■自下而上分析法(Bottom-up) 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 第五章 语法分析——自下而上分析 ◼ 自上而下分析法(Top-down) ◼ 自下而上分析法(Bottom-up)
语法分析的方法： 口自下而上分析法(Bottom-up) 口自上而下分析法(Top-dowm) ■基本思想：它从文法的开始符号出发，反复 使用各种产生式，寻找“匹配“的推导。 ■递归下降分析法：对每一语法变量（非终结 符)构造一个相应的子程序，每个子程序识 别一定的语法单位，通过子程序间的信息反 馈和联合作用实现对输入串的识别。 预测分析程序 。优点：直观、简单和宜于手工实现。 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 ◼ 语法分析的方法： 自下而上分析法(Bottom-up) 自上而下分析法(Top-down) ◼基本思想：它从文法的开始符号出发，反复 使用各种产生式，寻找"匹配"的推导。 ◼递归下降分析法：对每一语法变量(非终结 符)构造一个相应的子程序，每个子程序识 别一定的语法单位，通过子程序间的信息反 馈和联合作用实现对输入串的识别。 ◼预测分析程序 优点：直观、简单和宜于手工实现
语法分析的方法： 口自下而上分析法(Bottom-up) ■基本思想：从输入串开始，逐步进行“担 约”，直到文法的开始符号。即从树末端开 始，构造语法树。所谓归约，是指根据文法的 产生式规则，把产生式的右部替换成左部符号。 ■算符优先分析法：按照算符的优先关系和结合 性质进行语法分析。适合分析表达式。 ■LR分析法：规范归约 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 ◼语法分析的方法： 自下而上分析法(Bottom-up) ◼基本思想：从输入串开始，逐步进行“归 约”，直到文法的开始符号。即从树末端开 始，构造语法树。所谓归约，是指根据文法的 产生式规则，把产生式的右部替换成左部符号。 ◼算符优先分析法：按照算符的优先关系和结合 性质进行语法分析。适合分析表达式。 ◼ LR分析法：规范归约
G(E):E->iE+E E-EI E*EE/E(E) i*i+i E*i+i E*E+i E+i E+E E E E E 米 i 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 G(E)： E → i| E+E | E-E | E*E | E/E | (E) i*i+i E*i+i E*E+i E+i E+E E i + * E i i E E E E
5.1.1归约 ■采用“移进一归约”思想进行自下而上分析。 ■ 基本思想：用一个寄存符号的先进后出栈， 把输入符号一个一个地移进到栈里，当栈顶 形成某个产生式的候选式时，即把栈顶的这 一部分替换成（约为）该产生式的左部符 号。 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 5.1.1 归约 ◼ 采用“移进－归约”思想进行自下而上分析。 ◼ 基本思想：用一个寄存符号的先进后出栈， 把输入符号一个一个地移进到栈里，当栈顶 形成某个产生式的候选式时，即把栈顶的这 一部分替换成(归约为)该产生式的左部符 号
■ 例：设文法G(S): (1)S→aAcBe (2)A→b (3)A-→Ab (4)B→>d 试对abbcde:进行“移进一归约”分析。 e B a e A 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 ◼ 例：设文法G(S)： (1) S → aAcBe (2) A → b (3) A → Ab (4) B → d 试对abbcde进行“移进－归约”分析。 a bbcde b bcde A b cde c de d abbcdee e B c A Sa B c A a e
步骤：123 5678910 动作：进a进b归(2)进b归(3)进c进d归(4)进e归(1) e d B B b b A A A A A A A a a a a a a a a a S 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 步骤: 1 2 3 4 5 6 7 8 9 10 动作: 进a 进b 归(2) 进b 归(3) 进c 进d 归(4) 进e 归(1) e d B B b c c c c b A A A A A A A a a a a a a a a a S
d b 分析树和语法树不一定一致。 自下而上分析过程：边输入单词符号，边 归约。 核心问题：识别可归约串 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 b b d a c e S A B A 分析树和语法树不一定一致。 自下而上分析过程：边输入单词符号，边 归约。 核心问题：识别可归约串
5.1.2规范归约 ■ 定义：令G是一个文法，S是文法的开始符 号，假定oBδ是文法G的一个句型，如果有 SS16且A÷B 则B称是句型oBδ相对于非终结符A的短语。 特别是，如果有A→B,则称B是句型Bδ相对 于规则A→B的直接短语。一个句型的最左 直接短语称为该句型的句柄。 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 5.1.2 规范归约 ◼ 定义：令G是一个文法，S是文法的开始符 号，假定是文法G的一个句型，如果有 S * A 且 + A 则称是句型相对于非终结符A的短语。 特别是，如果有A,则称是句型相对 于规则A→ 的直接短语。一个句型的最左 直接短语称为该句型的句柄
考虑文法G(E):E→T|E+T T→F|T*F F→(E)Ii 和句型11*i2+i3: E→E+T→E+F→E+i3→T+i3 →T*F+i3→T*i2ti3→F*i2ti3 →11*i2ti3 ■短语：i1,i2,3,1*i2,i1*i2ti3 ■直接短语：i1,i2,i3 ■句柄：i1 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 考虑文法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， i1 *i2+i3 ◼ 直接短语： i1，i2，i3 ◼ 句柄： i1