第5章语法分析(2)自下而上分析 (编译原理陈火旺)

格式：ppt
大小：1011.00 KB
文档页数：72

下载文档原格式

第5章语法分析(2)自下而上分析

则成功，达不到这种格局则输入串有错误。

栈中符号串+剩余输入串 = 规范句型。
26
规范归约分析算法
1. 在栈底放入# ，在输入串尾附上#; 2. 逐个移入输入符号,当栈顶形成句柄时，进行归约; 3. 重复2 直到输入串已全部进栈，仅剩#, 4. 若栈中归约为#S, 表示分析成功，输入串为合法的句子,否则为非法句子.
2
5.1 自下而上分析的基本问题

自下而上分析法的基本思想：
从输入串出发，反复利用产生式逐步进行 ‚归约‛，如果最后能归约到文法的开始符号，则输入串是句子，否则输入串有语法错误。

各种不同自下而上分析法一个共同特点是：
边输入单词符号（移进栈），边归约；
3
5.1 自下而上分析的基本问题

自下而上分析的基本技术是采用归约栈,如下图所示: #

或者说从文法的开始符号产生句子。

自下而上分析采用的方法是归约，从叶子到根构造分析树。

或者说从句子开始归约出文法的开始符号。

语法树的一个子树：由该树的某个结连同它的所有子孙组成。在自下而上分析过程中，每一步归约都可画出一棵子树。
例如,上例中的归约过程可描述为如下分析树:
9
例5.2：文法G[S], 其4条产生式如下： ① S→aABe ② A→b ③ A→Abc ④ B→d 对句子abbcde的分析最右推导 SaABeaAdeaAbcdeabbcde 最左归约 abbcde，aAbcde ，aAde，aABe ，S S S aABe aAde aAbcde abbcde
S （2）每次归约用的句柄：， (a,(a))，，，，，， ( (L,(S)) (L,(L)) (L,S) (L) S (S,(a)) (L,(a)) L )

编译原理之语法分析-自下而上分析（二）

编译原理之语法分析-⾃下⽽上分析（⼆）、（⼀）LR分析法 LR分析定义：从左到右扫描(L)输⼊串，构造最右推导的逆过程(R)，是⾃下⽽上分析法的核⼼。

LR分析法特点：严格的规范规约。

⽐递归下降分析法、LL(1)分析法对⽂法的限制要少得多，适⽤范围⼴，适⽤于⼤多数上下⽂⽆关⽂法描述的语⾔。

分析速度快，能准确定位错误。

LR分析法缺点：⼿⼯构造分析程序⼯作量相当⼤。

LR分析器的组成：总控程序：执⾏分析表所规定的动作，对进⾏操作。

所有的LR分析器相同。

分析栈：⼜分为符号栈和状态栈。

符号栈：存放分析过程中移进或归约的符号。

状态栈：状态栈存放的是状态(标记号)，记录分析过程中从开始的某⼀归约阶段的整个分析历史或预测扫描了能遇到的分析符号分析表：LR分析器的核⼼。

其功能指⽰分析器是移进还是规约，根据不同的⽂法类要采⽤不同的构造⽅法。

(后边会具体描述) LR分析器模型：根据上图可以看出LR分析程序依次将输⼊串以及当前状态移⼊分析栈，然后根据分析栈和当前输⼊串去查找分析表去判断下⼀步应该进⾏什么操作。

我们最终的⽬的是通过⼀系列操作去构造这个LR分析表。

四种LR分析⽅法以及范围：在后续博客中我们会依次讲解LR(0)、SLR(1)、LR(1)。

图中看出⼀个LR(0)⽂法必定是SLR(1)、LALR(1)和LR（1）⽂法；LALR(1)⽂法必定是LR(1)⽂法。

(⼆)LR(0)分析法基本概念 LR(0)定义：从左到右扫描(L)输⼊串，构造最右推导的逆过程(R)，0代表不向前看任意符号即不进⾏展望或预测。

LR(0)分析法流程（移进-归约）：识别活前缀（⽬的是为了寻找句柄）NFA->DFA->项⽬集规范族(DFA的元素)CLOSURE（求规范族）->GO（DFA边）构造LR（0）分析表同样先讲解⼏个定义:活前缀、增⼴⽂法(拓⼴⽂法)、LR(0)项⽬。

活前缀(可归前缀)：⽬的是为了寻找LR分析中可归约串(句柄)，采取归约过程前符号栈中的内容，称为可归前缀。

《编译原理》第5章自上而下语法分析

编译原理武汉大学计算机学院编译原理课程组第5章自上而下语法分析·基本思想·存在的问题·解决方法·LL(1)方法·递归子程序法5.0 语法分析的功能及基本思想依据语法规则，逐一分析词法分析时得到的单词，把单词串分解成各类语法单位，即确定它们是怎样组成说明和语句，以及说明和语句又是怎样组成程序的。

分析时如发现有不合语法规则的地方，便将出错的位置及出错性质打印报告给程序员；如无语法错误，则用另一种中间形式给出正确的语法结构，供下一阶段分析使用。

1. 语法分析的功能5.0 语法分析的功能及基本思想2．自上而下语法分析的基本思想从识别符号出发，不断建立直接推导，试图构造一个最左推导序列，最终由它推导出与输入符号串相同的符号串。

从语法树的角度看，自顶向下分析过程将以识别符号为根结点，试图向下构造一棵语法树，其末端结点符号串正好与输入符号串相同。

相应于高级语言的编译过程，自上而下语法分析就是从该高级语言文法的开始符号——<程序>出发，试图推导得到该文法的句子——源程序或与其等价的单词串。

3. 自上而下语法分析遇到的问题5.0 语法分析的功能及基本思想在分析的过程中，匹配失败后，必须退回到出错点，选择其它可能的产生式重新推导，这个过程称为回溯。

如果文法中存在如下形式的产生式A →α1|α2|…|αn那么在自上而下的语法分析过程中，当要对A 展开时，应按哪一个后选式展开呢？即如何确定替换A 的αi 。

如果选择错误，将导致回溯。

5.0 语法分析的功能及基本思想3. 自上而下语法分析遇到的问题当文法中出现左递归时（存在非终结符号U，对于它有+⇒U→U…或U U…），会使分析过程陷入无限循环。

例如对文法G[S]：S→ABA→bB|AaB→Sb|a5.0 语法分析的功能及基本思想4.自上而下语法分析中问题的解决方法·避免回溯·消除左递归5.1 消除左递归的方法1．直接左递归的消除•采用扩充BNF表示[x]——x可以出现零次或一次{x}——x可以出现零次到多次x(y|z)——等价于xy或xz5.1 消除左递归的方法1．直接左递归的消除•采用扩充BNF表示•引进新的非终结符号，将左递归改写为右递归。

软件工程编译原理第五章自顶向下的语法分析方法

P→1P | 2P |… | mP |
（2）消除间接左递归
对于间接左递归的消除需先将间接左递归变为直接左递归，然后再按a)消除直接左递归。
例：文法G为例： (1) A→aB (2) A→Bb (3) B→Ac (4) B→d 用产生式(1)、(2)的右部代替产生式(3)中的非终结符A得到左部为B的产生式为： (1) B→aBc (2) BG的产生式为： (1) S→aSb (2) S→aS (3) S→ε 请提取文法中的左公因子
对产生式(1)、(2)提取左公因子后得： S→ aS(b|ε) S→ε 进一步变换为文法G′： S→aSA A→b A→ε S→ε
例2：若文法G的产生式为： (1) A→ad (2) A→Bc (3) B→aA (4) B→bB 请提取文法中的隐式左公因子。对文法G2分别用(3)、(4)的右部替换(2)中的B，可得：提取产生式(1)、(2)的左 (1) A→ad 公共因子得： (2) A→aAc A→a(d|Ac) (3) A→bBc A→bBc (4) B→aA B→aA (5) B→bB B→bB
由上面所举例子可以说明以下问题：
① 不一定每个文法的左公共因子都能在有限的步骤内替换成无左公共因子的文法，上面文法G4就是如此。 ② 一个文法提取了左公共因子后，只解决了相同左部产生式右部的FIRST集不相交问题，当改写后的文法不含空产生式，且无左递归时，则改写后的文法是 LL(1)文法，否则还需用LL(1)文法的判别方式进行判断才能确定是否为LL(1)文法。
例:文法G(E):
E→TE E→+TE | T→FT T→*FT | F→(E) | i
每个非终结符有对应的子程序的定义，首先在分析过程中，当需要从某个非终结符出发进行展开(推导)时，就调用这个非终结符对应的子程序。

第5章语法分析——自下而上

B d
e
SaAcBeaAcdeaAbcdeabbcde SS→aAcBeB→d A→Ab A→b
每次归约的都是句型中的句柄。
22
算符优先分析法
LR分析法
23
1. LR分析法介绍
2. LR(0)分析表的构造
3. SLR分析表的构造
24
从左（Left,L）向右扫描输入串，构造一个最右推导（Rightmost,R）的逆过程进行规范归约（最左归约），每次归约的都是真正的句柄；对文法限制最少，是识别效率较强的方法；出错处理能力较强；采用自动构造技术（构造LR分析表）
B
e
A
b
d
S → aAcBe A → Ab A→b B→d
b
分析树
输入串：abbcde
7
短语直接短语句柄
8
定义：设文法G的开始符号为S，是文法 *则称β是的一个句型，若有SA且Aβ, + 相对于非终结符A的一个短语。句型
短语是指句型中的某个部分，这部分可以由某个非终结符推出。可以利用语法树来找出句型中的所有短语。
查表 A[0,a]=s2，进栈 A[2,a]=s2，进栈 A[2,b]=s5，进栈 A[5,b]=r2，按第2条产生式归约 G[2,A]=3，进入状态3 A[3,b]=s4，进栈 A[4,#]=r1，归约 G[0,A]=1，进入状态1 A[1,#]=acc 31
对于一个文法，如果能够构造一张分析表，使得它的每个入口均是唯一确定的，则我们把这个文法称为LR文法。
33
前缀：字的任意首部。即移去符号尾
部零个或多于零个符号得到的一个符
号串。例：abc的前缀有ε,a, ab, abc

编译原理第五章答案

第5章自顶向下语法分析方法第1题对文法G[S]S→a||(T)∧T→T,S|S(1) 给出(a,(a,a))和(((a,a),,(a)),a)∧的最左推导。

(2) 对文法G，进行改写，然后对每个非终结符写出不带回溯的递归子程序。

(3) 经改写后的文法是否是LL(1)的?给出它的预测分析表。

(4) 给出输入串(a,a)#的分析过程，并说明该串是否为G的句子。

答案：也可由预测分析表中无多重入口判定文法是LL(1)的。

可见输入串（a,a）#是文法的句子。

第3题已知文法G[S]：S→MH|aH→LSo|εK→dML|εL→eHfM→K|bLM判断G是否是LL(1)文法，如果是，构造LL(1)分析表。

第7题对于一个文法若消除了左递归，提取了左公共因子后是否一定为LL(1)文法?试对下面文法进行改写，并对改写后的文法进行判断。

第2种改写：用S的产生式右部代替A的产生式右部的S得：S→Aa|b A→AaB|bB B→ab消除左递归后文法变为：0) S→A a1) S→b2) A→b B N3) N→a B N4) N→ε5) B→a b预测分析表：。

第五章语法分析(自上而下分析法)

解：这里P=exp , α 1=+term , α 2=-term, β =term 改写： exp → term exp' , exp' → +term exp' | - term exp' | ε
(3)间接左递归的消除例如文法G(S): S→Qc|c Q→Rb|b R→Sa|a
虽没有直接左递归，但S、Q、R都是左递归的
例：简单的表达式文法 exp → exp addop term | term 消除其左递归。解：属于格式P → Pα | β 这里 P=exp , α =addop term , β =term 改写： exp → term exp' exp' → addop term exp' | ε
例文法G(E): E→E＋T | T T→T*F | F F→(E) | i 经消去直接左递归后变成： E→TE′ E′→+TE′ | ε T→FT′ T′→*FT′ | ε F→(E) | i 不变
例1 假定有文法G(S): (1) S→xAy (2) A→** | * 分析输入串x*y(记为α)。 ① 按文法的开始符号产生语法树的根节点S,根据规则，S有三个子孙，于是此时的语法树如图所示；并把指示器IP指向串α的第一个符号x x*y IP S x*y IP S x A y
把语法树的子节点从左至右对IP所指向的符号进行匹配。第一符号匹配，于是，IP向后移动一个符号。
是递归下降分析法和预测分析法的基础
LL(1)分析法
构造不带回溯的自上而下分析算法要消除文法的左递归性克服回溯
1 左递归的消除
（1）简单直接左递归直接消除见诸于产生式中的左递归：假定关于非终结符P的规则为

编译原理-第五章习题答案

上一页
下一页
11
例：5.3 文法：SaAcBe A bAb B d 句子：abbcde
步骤（1）（2）（3）（4）（5）（6）
栈
＃＃a ＃ab ＃aA ＃aAb ＃aA ＃aAc ＃aAcd ＃aAcB ＃aAcBe ＃S
输入 abbcde＃ bbcde＃ bcde＃ bcde＃ cde＃ cde＃
上一页
下一页
20
5）构造算符优先文法G的优先表的算法
思路：对文法中的每一个产生式的候选式检查，判断句型中相邻符号之间的关系来构造优先表；具体算法： FOR 每条产生式P→X1X2…Xn FOR i＝1 TO n－1 IF Xi，Xi+1∈VT，THEN Xi＝Xi+1； IF i ≤n-2且Xi，Xi+2∈VT，Xi+1∈VN THEN Xi＝Xi+2； IF Xi∈VT，Xi+1∈VN THEN FOR FIRSTVT(Xi+1)中的每个a Xi <. a； NEXT IF Xi∈VN，Xi+1∈VT THEN FOR LASTVT(Xi)中的每个a DO a .> Xi＋1； NEXT NEXT NEXT

上一页
下一页
8
例：5.1 P85 文法： E→T|E＋T T→F|T*F F→i|（E）句型：i1*i2＋i3其中：短语有i1、i2、i3、i1*i2、 i1*i2＋i3 直接短语：i1、i2、i3；句柄：i1 例：5.2 P85 文法如上 E 句型：E+T*F+i 短语：E+T*F+i，E+T*F，T*F，i 直接短语：T*F和i E + 句柄：T*F

编译原理第三版第五章自下而上语法分析

3. 归 (2) 4. 进 b 5. 归 (3) 6. 进 c 7. 进 d 8. 归 (4) 9. 进 e 10. 归 (1)
a
b a
A a
b A A a a
c A a
d c A a
e B B c c A A a a
S
(2) 分析树: 用树表示“移进 - 归约 ”过程
A A B S
b
A
b
b
d
a
A
直接短语
T i F
句柄
T
T * F F ( E ) i
E + T T F
规范归约
设α是文法G的一个句子, 若序列αn, αn-1, …, α0，满足： (1)αn = α； (2) α0 = S； (3)对任意i , 0< i ≤n , αi-1 是从αi 将句柄替换成相应产生左部符号而得到的；则称该序列是一个规范归约。
1、归约与分析树
(1)移进-归约法: 使用符号栈, 把输入符号逐一移进栈, 栈顶出现某个产生式右部时归约为左部。
例：给定文法 G： (1) S→aAcBe (2) A→b (3) A→Ab (4) B→d 输入串 abbcde是否为句子？归约过程如下：步骤： 1. 2. 进进动作： a b
例：文法G: G[E]: E→E＋E|E*E |(E) |i (1) E→E+T│T (2) T→T*F│F (3) F→P↑F│P (4) P→(E)│i 算符优先关系为：由(4): P→(E) ∴( =) 由(1) (2): E→E+T, T => T*F ∴+<* 由(2) (3): T→T*F, F => P↑F ∴ *<↑ 由(1): E→E+T, E => E+T ∴ +>+ 由(3): F→P↑F, F=> P↑F ∴ ↑ <↑ 由(4): P→(E), E => E+T ∴ ( < +, +>) ... ∴ G为算符优先文法（优先关系表如表5.1所示,P90）＃看作终结符号

编译原理第五章语法分析-自下而上分析

5.2.2 算符优先分析算法
• 素短语：
–是一个短语，它至少含有一个终结符，并且，除它自身之外不再含任何更小的素短语。
• 最左素短语：
–最左边的素短语是最左素短语。
• 例子：
– 对文法(5.3)p*p和i是句型p*p+i的素短语，而p*p+i 本身也是素短语。
பைடு நூலகம்
• 算符优先文法：
算符优先文法，我们把句型（括在两个＃之间）的一般形式写成：＃N1a1N2a2…NnanNn+1# 其中，每个ai都是终结符，Ni是可有可无的非终结符。文法G的任何短语是满足如下条件的最左子串 Njaj…NiaiNi+1 aj-1⋖ aj aj ≖ aj+1 , …,aj-1 ≖ ai ai ⋗ ai+1
– 对于每个终结符a（包括＃）令其对应两个符号fa 和ga ，画一张以fa 和ga 所有符号为结点的方向图，如果 a⋗≖b, 那么，就从 fa 画一箭弧至 gb ；如果 a ⋖≖b，就画一条从gb到fa的箭弧。 – 对每个结点都赋予一个数，此数等于从该结点能到达结点（包括出发结点自身在内）的个数。赋给fa的数作为f(a)，赋给gb的数作为g(b)。 –检查所构造出来的函数f和g，看它们同原来的关系表是否有矛盾。如果没有矛盾，则f和g就是所要的优先函数。如果有矛盾，那么，就不存在优先函数。
• 例子：假定文法G
S→aAcBe A→b A→Ab B→d 输入串abbcde归约到S过程。
图5.1 规约中符号栈的变迁
步骤动作
1 进 a
2 进 b
3 归 (2)
4 进 b
5 归 (3)
6 进 c
7 进 d d

编译原理讲义(第五章语法分析--自底向上分析技术)

优先关系
• 和书上的写法不一样，凑合用。 SiSj Si Sj Si Sj • 注意：，，之间不同于=，>和<。由Si Sj不能导出Sj Si。
优先关系的例子
• 文法：Z::=bMb M::=(L|a L::=Ma) • 语言：{bab, b(aa)b, b((aa)a)b, …} • 可以从语法树里面导出部分优先关系。
关系闭包和Warshall算法
• Warshall算法是利用矩阵计算关系传递闭包的方法。计算B的传递闭包的算法伪代码如下：对于外层循环，当 A = B; i=K的循环结束的时 for (i = 1; i<=n; i++) 候，满足：如果Si和 for (j=1; j<=n; j++) Sj满足Si R Si1, Si1 R { Si2, … Sin R Sj，并 if (A[j,i]==1) 且im<K, 那么现在 for(k=1; k<=n; k++) A[i,j] = 1; A[j,k] = A[j,k]+A[i,k] }
基本方法（续）
• 归约中的动作有4类
– 移入：读入一个符号并把它归约入栈。 – 归约：当栈中的部分形成一个句柄（栈顶的符号序列）时，对句柄进行归约。 – 接受：当栈中的符号仅有#和识别符号的时候，输入符号也到达结尾的时候，执行接受动作。 – 当识别程序觉察出错误的时候，表明输入符号串不是句子。进行错误处理。
计算优先关系的例子P136
• 文法：S::=Wa W::=Wb W::=a • 将文法中的符号按照S，W，a，b排列。
0100 BHEAD= 0110 0000 0000
0010 0011 0000 0000

编译原理作业集-第五章-修订

第五章语法分析—自下而上分析本章要点1. 自下而上语法分析法的基本概念：2. 算符优先分析法；3. LR分析法分析过程；4. 语法分析器自动产生工具Y ACC；5. LR分析过程中的出错处理。

本章目标掌握和理解自下而上分析的基本问题、算符优先分析、LR分析法及语法分析器的自动产生工具YACC等内容。

本章重点1．自下而上语法分析的基本概念：归约、句柄、最左素短语；2．算符优先分析方法：FirstVT, LastVT集的计算，算符优先表的构造，工作原理；3．LR分析器：（1）LR(0)项目集族，LR(1)项目集簇；（2）LR(0)、SLR、LR(1)和LALR(1)分析表的构造；（3）LR分析的基本原理，分析过程；4．LR方法如何用于二义文法；本章难点1. 句柄的概念；2. 算符优先分析法；3. LR分析器基本；作业题一、单项选择题：1. LR语法分析栈中存放的状态是识别________的DFA状态。

a. 前缀；b. 可归前缀；c. 项目；d. 句柄；2. 算符优先分析法每次都是对________进行归约：(a)句柄（b）最左素短语(c)素短语(d)简单短语3. 有文法G＝（｛S｝，｛a｝，｛S→SaS，S→ε｝，S），该文法是________。

a. LL(1)文法；b.二义性文法；c.算符优先文法；d.SLR(1)文法；4. 在编译程序中，语法分析分为自顶向下分析和自底向上分析两类，和LL(1)分析法属于自顶向下分析；a. 深度分析法b. 宽度优先分析法c. 算符优先分析法d. 递归下降子程序分析法5. 自底向上语法分析采用分析法，常用的是自底向上语法分析有算符优先分析法和LR分析法。

a. 递归b. 回溯c. 枚举d. 移进－归约6. 一个LR(k)文法，无论k取多大，。

a. 都是无二义性的；b. 都是二义性的；c. 一部分是二义性的；d. 无法判定二义性；7. 在编译程序中，语法分析分为自顶向下分析和自底向上分析两类，和LR分析法属于自底向上分析。

编译原理语法分析—自上而下分析

对文法G的任何符号串=X1X2…Xn构造集合FIRST()。
1. 置FIRST()＝FIRST(X1)\{}；
2. 若对任何1ji-1，FIRST(Xj)，则把FIRST(Xi)\{}加至FIRST()中；特别是，若所有的FIRST(Xj)均含有， 1jn，则把也加至FIRST()中。显然，若＝则FIRST()＝{}。
T→T*F | F
F→(E) | i
经消去直接左递归后变成：
E→TE E→+TE | T→FT T→*FT | F→(E) | i
(4.2)
例如文法G(S): S→Qc|c Q→Rb|b R→Sa|a
虽没有直接左递归，但S、Q、R都是左递归的
SQcRbcSabc
(4.3)
一个文法消除左递归的条件：不含以为右部的产生式不含回路。
即A的任何两个不同候选 i和 j FIRST(i)∩FIRST( j)＝
当要求A匹配输入串时，A就能根据它所面临的第
一个输入符号a，准确地指派某一个候选前去执
行任务。这个候选就是那个终结首符集含a的。
提取公共左因子:
假定关于A的规则是 A→ 1 | 2 | …| n | 1 | 2 | … | m (其中，每个不以开头)
*
特别是，若S A ，则规定
＃FOLLOW(A)
构造不带回溯的自上而下分析的文法条件
1. 文法不含左递归，
2. 对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即，若
A→ 1| 2|…| n 则 FIRST( i)∩FIRST( j)＝ (ij)
3. 对文法中的每个非终结符A，若它存在某个候选首符集包含，则
1)算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。

编译原理-自下而上的语法分析

自上而下的语法分析
特点
从高层次的文法规则开始，通过不断展开和推导，直到生成目标字符串。
优点
易于理解和实现，可以生成详细的错误报告。
自下而上的语法分析
1
自底向上的语法分析方法概述
通过以输入的标记为起点，逐步推导文法规则，直到生成目标字符串。
2
LR语法分析
一种常用的自底向上的语法分析方法，通过构建一个LR分析表进行推导。
3
LALR语法分析
是LR语法分析的一种变体，通过合并相同状态来降低分析表的复杂度。
自下而上的语法分析的优点和局限性
优点
适用于大型文法，能够处理更广泛的语言结构。
局限性
分析过程复杂，容易产生冲突，需要较大的存储空间。
自下而上的语法分析的实现
词法分分析器的生成
根据文法规则，构建分析表或语法分析器的数据结构。
语法制导翻译的实现
在语法分析过程中，将源代码转换为目标代码。
自下而上的语法分析的应用
1
编译器中的语法分析
语法分析是编译器中的重要组成部分，用于将源代码转换为中间代码或目标代码。
2
解析器生成器
自下而上的语法分析技术被广泛应用于解析器生成器中，用于自动生成语法分析器。
结论
自下而上的语法分析是编译原理中重要的一环，虽然实现复杂，但却具有广泛的应用价值。
编译原理-自下而上的语法分析
编译原理是研究程序在计算机上的自动翻译过程，语法分析是其中的重要步骤。自下而上的语法分析是一种常用的语法分析方法。
语法分析的定义和目的
1 定义
语法分析是编译器中的一个阶段，用于验证和分析程序语法的正确性。
2 目的
语法分析的目的是将源代码转换为语法树，为后续的编译过程提供基础。

编译原理第五章语法分析——自下而上分析

第五章语法分析——自下而上分析要紧内容:[1]自下而上分析的大体问题[2]算符优先分析法[3]算符优先分析表和优先函数的构造[4]LR分析器的大体原理大体要求:[1]明白得自下而上分析法的大体思想[2]明白得有关归约、短语、句柄、标准归约等概念[3]把握算符优先分析法[4]了解算符优先表和优先函数的构造技术[5]了解LR 分析器大体原理和工作方式教学要点：本章介绍自下而上语法分析方式。

所谓自下而上分析法确实是从输入串开始，慢慢进行“归约”，直至归约到文法的开始符号；或说，从语法树的结尾开始，步步向上“归约”，直到根结。

讲义摘要：5.1 自下而上分析大体问题自下而上分析法的大体思想：从输入串开始，慢慢进行“归约”，直到文法的开始符号。

即从树结尾开始，构造语法树。

所谓归约，是指依照文法的产生式规那么，把产生式的右部替换成左部符号。

自上而下分析的核心问题是：如何判定符号串的可归约性，和如何归约。

即，识别可归约串的问题。

归约自下而上分析法事实上确实是一种“移进－归约”法，即，采纳“移进－归约”思想进行。

实现思想是：对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄时，（该句型对应某产生式的右部，即栈顶生成了某产生式的右部的文法符号串），就将栈顶的这一部份替换成 (归约为) 该产生式的左部符号，这称为归约。

重复这一进程直到归约到栈中只剩文法的开始符号时那么为分析成功，也就确认输入串是文法的句子。

现举例说明。

例1：设文法G[S]为：(1) S→aAcBe(2) A→b(3) A→Ab(4) B→d试对abbcde进行“移进－归约”分析。

步骤: 1 2 3 4 5 6 7 8 9 10解：动作: 进a 进b 归(2) 进b 归(3) 进c 进d 归(4) 进e 归(1)表1符合栈的转变进程自下而上语法分析的进程也可看成自底向上构造语法树的进程，每步归约都是构造一棵子树，最后当输入串终止时恰好构造出整个语法树，如图1所示。

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

5
例5.1 G[S]: S→aAcBe A→b|Ab B→d 分析句子 abbcde 是否为合法的句子
分析栈
#a ab aA aAb aA
动作
移入
移入
源串分析栈 bbcde aAc bcde bcde
aAcd aAcB aAcBe #S
动作
移入
移入
源串 de e e
归约移入归约
归约移入
cde
7
5.1.1

归约
自下而上分析的核心问题：就是寻找句型中的“可归约串”进行归约。

对“可归约串”概念的不同定义，就形成了不同的自下而上的分析方法。在“规范归约”中，则用“句柄”来刻画“可归约串” 在“算符优先分析法”用“最左素短语” 来刻画”可归约串”
8
5.1.1

归约
语法分析树: 一棵倒立的树,可用于描述语法分析的过程；自上而下分析采用的方法是推导，从根到叶子构造分析树。

5.4 语法分析器的自动产生工具 YACC---了解
2
5.1 自下而上分析的基本问题

自下而上分析法的基本思想：
从输入串出发，反复利用产生式逐步进行 ‚归约‛，如果最后能归约到文法的开始符号，则输入串是句子，否则输入串有语法错误。

各种不同自下而上分析法一个共同特点是：
边输入单词符号（移进栈），边归约；
32
5.2 算符优先分析

算符优先分析的基本思路:

(1) 解决谁先归约: 规定算符(终结符)的优先关系和结合性质
表示算符优先文法及优先表的构造 (5.2.1) 便于计算机实现优先函数及构造 (5.2.3)
S （2）每次归约用的句柄：， (a,(a))，，，，，， ( (L,(S)) (L,(L)) (L,S) (L) S (S,(a)) (L,(a)) L )
L , S
S ( a L )
S a
23
5.1.3 符号栈的使用与语法树的表示
符号栈的使用

自下而上分析法要使用一个符号栈(语法分析的一种基本数据结构),分析中根据符号栈顶是否形成句柄决定是移进还是归约。符号栈输入串分析开始： # ω# 分析中： #α β# 分析结束时： # S # 分析中任何时候：
cde
归约
6
经分析,判定该句子是G合法的句子.
5.1.1
归约
归约串分为：可归约串、非可归约串
在上例中,当栈中为aAb时,存在两个归约串:b及Ab,都可以归约为A；
若使用b进行归约，栈中得到aAA,导致最终不能归约为S,因此，判定输入字符串非法；这是一种错误归约, 原因在于栈中同时存在多个归约串,而只有一个归约串的选择是正确的,如Ab；把Ab称为可归约串，而b为非可归约串
• 自上而下从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导（最左推导），若能推导出与输入字串相同的句子,则表示输入字符串是合法的； • 特点从文法开始符开始；推导中始终使用产生式的右部替换左边的非终结符； • 自下而上根据文法,对输入符号串进行归约,若能正确地归约为文法的初始符号,则表示输入字串是合法的。 • 归约：在输入串中，寻找一条产生式的右部，如果找到用产生式的左边的非终结符替换右部。 • 特点从输入串开始；归约中始终使用产生式的左部替换右边的候选式；
– E＋E+T*F+i – E＋E+T*F – TT*F + – T i – Fi
–短语有4个：E+T*F+i (相对于E)； E+T*F(相对于E)； T*F(相对于T)；i (相对于T、F) 。 –T*F 和 i 为直接短语 –T*F为句柄。
14
5.1.2

规范归约简述

语法树的一个子树的所有叶结点的自左至右排列形成一个相对于子树根的短语。P86 有多少棵子树就有多少个相对于子树根结 (非终结符)的短语, 短语由某子树的全部叶结点组成。若短语是由某子树根经过1步推导得到的，则称之为该子树根的直接短语。
L , S (
S
a
17
5.1.2

规范归约简述
一个句型只有一个句柄，不同句型一般有不同句柄，每次归约都对句柄进行归约 --- 这就是规范归约。规范归约假定是文法G的一个句子, 称序列 n , n-1 , n-2, ……, 0 是的一个规范归约，如果此序列满足： (1) n = ; (2) 0 为文法的开始符,即 0 =S; (3) 对于任何的i，0<i ≤n, i-1 是从 i 经把句柄替换为相应产生式的左部符号而得到的。

或者说从文法的开始符号产生句子。

自下而上分析采用的方法是归约，从叶子到根构造分析树。

或者说从句子开始归约出文法的开始符号。

语法树的一个子树：由该树的某个结连同它的所有子孙组成。在自下而上分析过程中，每一步归约都可画出一棵子树。
例如,上例中的归约过程可描述为如下分析树:
9
例5.2：文法G[S], 其4条产生式如下： ① S→aABe ② A→b ③ A→Abc ④ B→d 对句子abbcde的分析最右推导 SaABeaAdeaAbcdeabbcde 最左归约 abbcde，aAbcde ，aAde，aABe ，S S S aABe aAde aAbcde abbcde
A
A a b b c B d e
5.1.1

归约
归约与推导关系：

推导与归约互逆关系最右推导称为规范推导
最右推导得到的句型称为规范句型
最左归约称为规范归约
12
5.1.2
规范归约简述
令G是一个文法，S是文法的开始符号短语假定是文法G的一个句型，如果有：
S*A 且 A +
21
例5.6
① S→aABe ③ A→Abc 句子abbcde的规范归约。
文法G[S],
② A→b ④ B→d 求对
规范归约为： abbcde，aAbcde，aAde，aABe，S
归约--剪子树
S A
句型abbcde的句柄是b ，把句柄剪去（归约）就形成了句型 S aAbcde的语法树。
A
a b b c
18
例5.5文法G[S],
① S→aABe ② A→b ③ A→Abc ④ B→d 求句子 abbcde的规范归约。
abbcde aAbcde aAde aABe S
abbcde的规范归约为： abbcde，aAbcde，aAde，aAB，S
5.1.2

规范归约简述

规范归约是一种较常用的自下而上分析方法。规范归约：是关于句子α的一个最右推导的逆过程。 ■也称最左归约。 �� 规范归约采用句柄来刻画可归约串。�� 每次归约总是句型的句柄归约。
T * F + i3 T + i3 E + i3
E+F E+T E 开始符号
回顾：

自下而上语法分析方法 --- ‚移进-归约‛法
符号栈顶没有形成可归约串, 决定是形成移进归约

定义可归约串要解决：

1. 定义什么样的符号串是可归约串； 2. 在分析时怎样判定符号栈顶出现了可归约串； 3. 如何归约。
步骤
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
符Байду номын сангаас栈
# #i1 #F #T #T* #T* i2 #T*F #T #E # E+ #E+ i3 #E+F #E+T #E #E
输入串
i1 * i2 + i3# * i2 + i3 # * i2 + i3 # * i2 + i3 # i2 + i3 # + i3 # + i3# + i3 # + i3 # i3 # # # # # #
动作
预备读入 i1 , i1进栈归约，Fi 归约，T F 读入* , *进栈读入 i2 , i2进栈归约，F i 归约，T T*F 归约，E T 读入+ , +进栈读入 i3 , i3进栈归约, F i 归约, T F 归约，E E+T 接受
句型和句柄
i1 * i2 + i3 F * i2 + i3 T * i2 + i3
16
练习 • 文法G(S): S (L)|aS|a
L L , S |S
(1)
(
• (1) 画出句型 (S,(a)) 的语法树。 • (2) 写出上述句型的所有短语、直接短语和句柄。 (2) 短语: S、a、(a)、S,(a)、(S,(a)) 直接短语: a、S 句柄：S
S
L S L ) )

4
5.1 自下而上分析的基本问题

定义：栈顶形成的某产生式的候选称为归约串。自底向上分析方法，也称移进－归约分析法，粗略地说它的实现思想是对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个归约串时，（某产生式的右部），就用该产生式的左部非终结符代替相应右部的文法符号串，这称为归约。重复这一过程直到归约到栈顶中只剩文法的开始符号时则为分析成功，也就确认输入串是文法的句子。
3
5.1 自下而上分析的基本问题

自下而上分析的基本技术是采用归约栈,如下图所示: #
a1a2......an

归约栈字符串把输入符号依次移入栈内,当栈顶符号串形成某产生式的右部时，就归约为产生式左部非终结符; 继续移入输入字串，直到栈中归约为文法初始符号S. 这种方法也称为‚移进－归约法‛.

第5章语法分析(2)自下而上分析 (编译原理陈火旺)

合集下载