42自底向上的语法分析 口自底向上的语法分析是从给定的符号串出发试图将它归 约为文法的开始符号 两种自底向上分析方法 优先分析法:在文法符号之间确定优先关系,根据优先关 系确定句型的句柄,进行语法分析。 LR分析法:向前查看若千个输入符号以确定下一步应采 取的语义动作 口自底向上分析也需要一个分析栈用于存放分析过程中所 得的文法符号,开始时,先将#入栈,然后逐步地将输入符 号移进栈当在栈顶形成句柄时,则进行归约否则移进下 符号如果最后所有的符号都移进分析栈并且分析栈中 只剩下井和文法的开始符号,则表明分析成功
1 4.2 自底向上的语法分析 自底向上的语法分析是从给定的符号串出发,试图将它归 约为文法的开始符号. 两种自底向上分析方法: –优先分析法：在文法符号之间确定优先关系，根据优先关 系确定句型的句柄，进行语法分析。 –LR分析法：向前查看若干个输入符号以确定下一步应采 取的语义动作。 自底向上分析也需要一个分析栈用于存放分析过程中所 得的文法符号,开始时,先将#入栈,然后逐步地将输入符 号移进栈,当在栈顶形成句柄时,则进行归约,否则移进下 一符号.如果最后所有的符号都移进分析栈并且分析栈中 只剩下#和文法的开始符号，则表明分析成功
自底向上语法分析的例子 文法:S→ABl;A-bAa;B→> asbc,输入为 baac 步骤 分析栈内容 余留符号串 下步动作 bbaacb#移进 bacb#移进 0123456789 #bb aac b#移进 #bba aco 按A→a归约 #bbA acb#按A→bA归约 #ba acb#按A→bA归约 #A acb#移进 # Aa cb#|移进 Aac b#按S→c归约 #AaS b#移进 10 AaSb 按B→aSb归约 11 #AB 按S→AB归约 #S #分析成功
2 步 骤 分析栈内容 余留符号串 下步动作 0 # bbaacb# 移进 1 #b baacb# 移进 2 #bb aacb# 移进 3 #bba acb# 按 A→a 归约 4 #bbA acb# 按 A→bA 归约 5 #bA acb# 按 A→bA 归约 6 #A acb# 移进 7 #Aa cb# 移进 8 #Aac b# 按 S→c 归约 9 #AaS b# 移进 10 #AaSb # 按 B→aSb 归约 11 #AB # 按 S→AB 归约 12 #S # 分析成功 文法: S→AB|c；A→bA|a；B→aSb|c, 输入为bbaacb 自底向上语法分析的例子
关于自底向上分析 分析动作有移进,归约报错,接受在分析的每一步,分析 动作都是由当前栈里的内容和扫描到的符号确定的 分析过程采用最左归约(规范归约),句柄肯定出现在栈 顶位置,应注意,一旦句柄在栈顶形成,则立即归约 问题1:如何确定句型的句柄?栈顶出现的某产生式右部 不一定是句柄,如前例中第7步栈顶的a不是句柄 问题2:出现句柄时选择哪一个产生式?如前例中第8步, 对于句柄c,选择S→)c还是B→>c?
3 关于自底向上分析 分析动作有:移进,归约,报错,接受.在分析的每一步,分析 动作都是由当前栈里的内容和扫描到的符号确定的. 分析过程采用最左归约(规范归约)，句柄肯定出现在栈 顶位置，应注意，一旦句柄在栈顶形成,则立即归约。 问题1: 如何确定句型的句柄？栈顶出现的某产生式右部 不一定是句柄，如前例中第7步,栈顶的a不是句柄 问题2：出现句柄时选择哪一个产生式？ 如前例中第8步, 对于句柄c，选择S→c还是B→c？
自底向上分析潜在构造了语法树 分析过程隐含地自底向上建立了一棵语法树 (1)往分析栈移入一个终结符a时,则在语法树中添加 个以a为标记的末端结点 (2)每当将栈顶符号串XX2.Xm归约为非终结符A时, 则在语法树中添加一个结点A,并将串中的符号X, X2,.Xm按自左向右的顺序作为A的孩子结点 当分析过程结束时,如果接受了输入的符号串,则一棵 完整的语法树构造成功
4 自底向上分析潜在构造了语法树 分析过程隐含地自底向上建立了一棵语法树: （1）往分析栈移入一个终结符a时，则在语法树中添加 一个以a为标记的末端结点。 （2）每当将栈顶符号串X1X2…Xm归约为非终结符A时， 则在语法树中添加一个结点A，并将串中的符号X1, X2 ,…,Xm按自左向右的顺序作为A的孩子结点。 当分析过程结束时，如果接受了输入的符号串，则一棵 完整的语法树构造成功
42.1简单优先分析法 确定句型的句柄:在文法的各个符号(包括终结符和非 终结符)之间建立优先关系,先从左到右扫描句型中的 符号,根据优先关系确定句柄的尾部(相邻的两个符号 之间具有优先关系“>”),再反向扫描确定句柄的头部 (相邻的两个符号之间具有优先关系“<”)。 、简单优先关系的定义:若文法G中存在规范句型 =。St. s,t∈V,则s,t与a的句柄之间的关系必有下述情 况之 A s t s t s t 1.s句柄中,而t2.s与均在句3s不在句柄中, 不在句柄中 柄中 而t在句柄中
5 4.2.1 简单优先分析法 确定句型的句柄：在文法的各个符号（包括终结符和非 终结符）之间建立优先关系，先从左到右扫描句型中的 符号，根据优先关系确定句柄的尾部（相邻的两个符号 之间具有优先关系“>”），再反向扫描确定句柄的头部 （相邻的两个符号之间具有优先关系“<”） 。 A … … s t ... 1. s在句柄中,而t 不在句柄中 A … … s t … ... 2. s与t均在句 柄中 A … … s t … ... 3. s不在句柄中, 而t在句柄中 一、简单优先关系的定义: 若文法G中存在规范句型 =…st…, s,tV,则s,t与的句柄之间的关系必有下述情 况之一: