4.2自底向上的语法分析 ·自底向上()的语法分析是从给定的符号串出发，试图逐步 将它们归约为文法的开始符号 ·个的语法分析采用的是最左（规范）归约 ·本节中介绍两种个分析方法，即优先分析法和LR分析法； 。 ↑分析也需要一个分析栈用于存放分析过程中所得的文法 符号，开始时，先将#入栈，然后逐步地将输入符号移进栈，当 句柄在栈顶形成时，则进行归约，否则移进下一符号在分析 的每一步，分析动作都是由当前栈里的内容和扫描到的符 号确定的 ·分析动作有：移进，归约，报错，接受
4.2 自底向上的语法分析 • 自底向上()的语法分析是从给定的符号串出发,试图逐步 将它们归约为文法的开始符号. • 的语法分析采用的是最左(规范)归约 • 本节中介绍两种分析方法,即优先分析法和LR分析法; • 分析也需要一个分析栈用于存放分析过程中所得的文法 符号,开始时,先将#入栈,然后逐步地将输入符号移进栈,当 句柄在栈顶形成时,则进行归约,否则移进下一符号.在分析 的每一步,分析动作都是由当前栈里的内容和扫描到的符 号确定的. • 分析动作有:移进,归约,报错,接受
自底向上语法分析的例子 文法：S-→ABc A→bAaB→aSblc,输入为bbaacb 步骤 分析栈内容 余留符号串 下步动作 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 自底向上语法分析的例子 步 骤 分析栈内容 余留符号串 下步动作 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 # 分析成功
关于自底向上分析 ·分析过程是最左归约的（规范的）： ·注意，在分析过程中，一旦句柄在栈顶形成，则立即 归约； ·有时栈顶出现了某产生式的右部，但它不一定是句 柄（如前例中第七步，栈顶的a并不是句柄）； 从分析过程可容易地建立一棵语法树，可用作语法 分析的输出.建立树的方法见P127,这里从略
关于自底向上分析 • 分析过程是最左归约的(规范的); • 注意,在分析过程中,一旦句柄在栈顶形成,则立即 归约; • 有时栈顶出现了某产生式的右部,但它不一定是句 柄(如前例中第七步,栈顶的a并不是句柄); • 从分析过程可容易地建立一棵语法树,可用作语法 分析的输出.建立树的方法见P127,这里从略
4.2.1简单优先分析法 ·方法：在文法的符号之间建立一套（实际是三 种)优先关系RcV×V,在分析的过程中，利用 优先关系的比较，来确定当前句型的句柄： ·在找到句柄后按相应的产生式归约之，并将 归约出的V符号压入栈，再进行新的比较，如 此工作下去，直到出错或分析成功：
4.2.1 简单优先分析法 • 方法:在文法的符号之间建立一套(实际是三 种)优先关系RVV,在分析的过程中,利用 优先关系的比较,来确定当前句型的句柄; • 在找到句柄后按相应的产生式归约之,并将 归约出的VN符号压入栈,再进行新的比较,如 此工作下去,直到出错或分析成功
(一)简单优先关系的定义 设G是已化简的文法，s,teV,若G中存在规范句型o=.st.,则 s,t与的句柄之间的关系必有下述情况之一： .S t 。，。 。。。 st.. 1.s在句柄中， 2.s与t均在句 3.s不在句柄中，而t 而不在句柄中 柄中 在句柄中 对于上述情况，我们规定，情况1：s>t;情况2：s=t; 情况3：s<t 另外，还有一种情况，就是s和均不在句柄中，那么一定存在某个 句型使得它们进入上述三种情况之一. 若s和在任何句型中都不可能相邻出现，则我们规定二者无关系 注意，这种优先关系是不对称的：
(一)简单优先关系的定义 • 设G是已化简的文法,s,tV,若G中存在规范句型 =…st…, 则 s,t与的句柄之间的关系必有下述情况之一: A … … s t ... 1. s在句柄中, 而t不在句柄中 A … … s t … ... 2. s与t均在句 柄中 A … … s t … ... 3. s不在句柄中,而t 在句柄中 对于上述情况,我们规定,情况1: s>t; 情况2: s=t; 情况3: s<t 另外,还有一种情况,就是s和t均不在句柄中,那么一定存在某个 句型使得它们进入上述三种情况之一. 若s和t在任何句型中都不可能相邻出现,则我们规定二者无关系. 注意,这种优先关系是不对称的!