编译原理-西安交通大学(冯博琴)_自下而上语法分析__..100页PPT

*
S A
且
A
则称是句型相对于非终结符A的短语。 特别是，如果有A,则称是句型
相对于规则A的直接短语 一个句型的最左直接短语称为该句型
的句柄
5.1.7 规范归约例一
▪ 例：文法G[E]：
E→E+T|T
T→T*F|F F→(E)|–F|id
考虑文法G[E]上的句子id1+id2*id3 ➢ 其最右推导和分析树如图5.1(a)、(b)所示
第五章 语法分析—自下而上分析
内容
▪ 自下而上分析基本问题 ▪ 算符优先分析
5.1 自下而上分析基本问题
▪ 自下而上分析基本问题
➢ 归约 ➢ 规范归约 ➢ 符号栈的使用 ➢ 语法树的表示
▪ 算符优先分析
5.1.1 自下而上分析
▪ 自下而上分析
abbcde aAbcde (A b)
➢ 从输入字符的角度而言 aAcde (A Ab)
➢ 最左归约
规范推导
▪ 由规范推导推出的句型称为规范句型。
▪ 规范归约的中心问题：确定句型的句柄。
5.1.2 规范归约简述
▪ 最右推导，推导的每一步结果都是一个右句 型。该推导即分析树 “剪句柄”的全过程。
S
S
S
S
S
a A B ea A B ea A B ea A B e
Ab c d
Ab c d
d
图5.1 id1+id2*id3的最右推导、分析树与短语 (a) 最右推导；(b) 分析树；(c) 短语
5.1.7.1 归约的分析树
▪ 分析树的叶子与短语、直接短语和句柄有下述关系 ➢ 短语 以非终结符为根的子树中所有从左到右排列的 叶子 ➢ 直接短语 只有父子关系的树中所有从左到右排列的叶子 树高为2 ➢ 句柄 最左边父子关系树中所有从左到右排列的叶子 句柄是唯一的

23
❖ 例4.5：文法
E→E+T|T T→T*F|F F→(E)|i
可表示成
E→T{+T} T→F{*F} F→(E)|i
❖ 用语法图表示：
E
T
T
+
T
F
F
*
F
i
（
E
）
24
E→T{+T} T→F{*F} F→(E)|i
PROCEDURE E; BEGIN
T; WHILE SYM=’+’ DO
BEGIN ADVANCE; T END END;
5
❖ 例4.1：假定有文法(4.1) S→xAy A→**|*
分析输入串x*y（记为α）。
S
S
S
x Ay
x Ay x A y
*
*
*
(a)
(b)
(c)
6
❖ 由上例看到，自上而下分析法存在许多困难和缺点
文法的左递归性P+ Pα使分析陷入无限循环 回溯的不确定性，要求我们将已经完成工作推倒重来 虚假匹配问题 难于知道出错位置 效率低，代价高，实践价值不大
4 #E’T’ i i1+i2# 匹配
E→TE’ E’→+TE’|ε T→FT’ T’→*FT’|ε F→(E) | i
5 # E’T’ +i2# T’ –>
6 #E’
+i2# E’ –> +TE’
7 #E’T+ +i2# 匹配
I
+*
()#
8 # E’T i2# T –> FT’ E TE’
TE’
26
5.1预测分析程序工作过程

代码生成
编译器可以将高级语言编写的源代码转换成机器语言或低级语言，以便在特定的硬件平台上运行。编 译器还可以生成可执行文件或动态链接库等二进制文件。
编译器在人工智能领域的应用
机器学习编译器
机器学习编译器可以将机器学习模型转换成可执行代码，以便在嵌入式设备或边缘计算 设备上运行。这种编译器可以优化模型的计算性能和内存占用，提高模型的运行效率。
3
缺点
对于某些复杂文法，可能导致大量的无用推导和 状态爆炸。
自底向上的语法分析
分析步骤
从输入符号序列的最后一个符号开始，逐步向上构建语法树，直 到找到与文法中的某个产生式右部匹配的符号串。
优点
可以充分利用已知信息，避免不必要的推导和状态爆炸。
缺点
对于某些复杂文法，可能导致大量的无用归约和状态爆炸。
04
中间代码生成
中间代码生成的定义和任务
定义
中间代码生成是编译器的一个阶段，将源代码转换成中间代码的过程。
任务
将源代码转换成一种中间表示形式，以便进行后续的优化和目标代码生成。
三地址代码的生成
01
三地址代码是一种中间代码形 式，由一系列的三元式组成。
02
三元式的形式为(op, arg1, arg2)，表示执行一个操作(op) 并产生一个结果，操作数arg1 和arg2来自寄存器、常数或之 前的计算结果。
语义分析
检查AST是否有语义错误，如类型错 误、未定义的变量等。
中间代码生成
将AST转换为中间代码，通常是三地 址代码。
代码优化
对中间代码进行优化，提高执行效 率。
代码生成
将中间代码转换为机器语言代码， 能够在特定硬件上执行。
编译器的分类

E→E+a|a E⇒E+a ⇒E+a+a ⇒… L(G)={a,a+a,a+a+a,…}
5
上下文无关文法回顾
A→Aa|a A→aA|a
L(G)={an|n为整数，n≥1}
A→Aα|β A→αA|β
A→ε
β不以A开头 L(G)={βαn|n为整数，n≥0}
L(G)={ε,…}
A→Aa|ε A→aA|ε
10
Parse Trees and Abstract Syntax Trees
推导：从开始符号起构造特定句子的一个方法 推导：不能够唯一地表示所推到出的句子的结构
11
上下文无关文法回顾
exp→exp op exp|(exp) | number op →+|-|*
(number – number) * number
15
exp⇒exp op exp ⇒(exp) op exp ⇒(exp op exp) op exp ⇒(number op exp) op exp ⇒(number - exp) op exp ⇒(number - number) op exp ⇒(number - number) * exp ⇒(number - number) * number
typedef struct streenode
{ ExpKind kind;
OpKind op;
struct streenode *lchild, *rchild;
int val;
} StreeNode;
typedef StreeNode *SyntaxTree;
18
Yinliang Zhao （赵银亮）

• 约定：
• a、b代表任意终结符； • P、Q、R代表任意非终结符； • ‘…’代表由终结符和非终结符组成的任意序列，包括空字。
• 假定G是一个不含-产生式的算符文法。对于任 何一对终结符a、b，我们说： 1. a b 当且仅当文法G中含有形如P→…ab…
或P→…aQb…的产生式
2. a b 当且仅当G中含有形如P→…aR…的产
栈 输入 ＃S ＃
考虑文法G(E)： E T | E+T T F | T*F F (E) | I
输入串为i1*i2+i3 ，分析步骤为：
步骤 符号栈
0
#
1
#i1
2
#F
3
#T
4
#T*
输入串 i1*i2+i3# *i2+i3# *i2+i3# *i2+i3# i2+i3#
动作 预备 进 归，用F→i 归，用T→F 进
(1) E→E+T | T (2) T→T*F | F (3) F→P F | P (4) P→(E) | i
• 由第(4)条规则，有 ‘(’ ‘)’； • 由规则E→E＋T和TT*F， 有 ＋ *； • 由(2) T→T*F 和(3) F→P F ，可得* ↑； • 由(1)E→E＋T和E E+T，可得+ +； • 由(3)F→PF和F PF，可得↑ ↑。 • 由(4)P→(E)和 EE+TT+TT*F+TF*F+T
编译原理
第五章 语法分析—自下而上分析
• 自下而上分析法(Bottom-up)
• 基本思想：
• 从输入串开始，逐步进行“归约”，直到文法的开始符 号。所谓归约，是指根据文法的产生式规则，把产 生式的右部替换成左部符号。

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

❖ 由定义直接构造 ❖ 由关系图法构造算符优先关系表
20
（1）由定义直接构造
❖ 首先引入两个概念
FIRSTVT(B)={b|B b…或B Cb...}
❖对于非终结符B，其往下推导所可能出现的首个算符
LASTVT(B)={a|B … a或B ... aC}
>
>
11） #S
>=
#
接受
)
>
>
对输入串b(aa)#的简单优先分析过程
#< <
简单优先关系矩阵
12
❖ 自底向上优先分析法慨述 ❖ 简单优先分析 ❖ 算符优先分析
13
6.3 算符优先分析法
❖ 某些文法具有“算符”特性 表达式运算符（优先级、结合性） 人为地规定其算符的优先顺序，即给出优先级别 和同一级别的结合性
（4）括号‘(’,‘)’的优先级大 / > > > > < < > < >
于括号外的运算符，小于括号 内的运算符，内括号的优先性
>>>><<><>
(<<<<<<=<
)>>>>>
>
>
大于外括号
i>>>>>
>
>
（5）#的优先性低于与其相邻的 # < < < < < < < =
算符
算符优先关系表
15
文法G[E]：E→E+E|E-E|E*E|E/E|EE|(E)|i

• 例 4.4
4.4 递归下降分析程序构造
• 递归下降分析器：
这个分析程序由一组递归过程组成的，每个过程对应 文法的一个非终结符。 E→TE’ E’→+TE’| T→FT’ T’→*FT’| F→(E)|i
PROCEDURE E BEGIN T ; E’ END PROCEDURE E’ IF SYM=‘＋’THEN BEGIN ADVANCE ; T ; E’ END
4.2 自上而下分析面临的问题
• 例4.1 假定有文法
(1) SxAy (2)A**|*
对输入串x*y，构造语法树。 • 构造过程：
(1)把S作为根 (2)用S的产生式构造子树 (3)让输入串指示器IP指向输入串的第一个符号。
S x A y x
S
A y x
S
A y
*
*
*
(4)调整输入串指示器IP与叶结点进行匹配。 (5)如果为非终结符，用A的下一个产生式构建子树。 (6)如果匹配成功则结束；否则，回溯到步骤(4)。
• 一个反例：
– 文法：SQc|c；QRb|b；RSa|a虽然不是直接 左递归，但S、Q、R都是左递归。
• 消除左递归算法：
– 算法的思想是：
• • • • 首先构造直接左递归； 再利用一般转换规则，消除直接左递归 化简文法。 下面算法在不含PP，也不含在右部产生式时可以消除 左递归。
• 消除一个文法的左递归算法：
(1) 把文法 G 的所有非终结符按任一种顺利排列成 P1…Pn；按此顺序执行； (2) FOR i:=1 TO n DO
BEGIN FOR j:=1 TO i-1 DO 把形如Pj+1→Pj 的规则改写成 Pj+11|1|…k| 。其中 Pj1|1|…k 是关于 Pj 的 所有规则； 消除关于Pi规则的直接左递归性。 END 化简由（２）所得的文法。即去除那些从开始符号出发永 远无法到达的非终结符的产生规则。

二、算符优先文法和优先表的构造
1 算符优先文法（OPG文法）
两个非终结符相邻
（1）算符文法（OG文法）：设有一文法G，若G中没有形如
S→…QR…产生式，（S,Q,R∈VN）则称文法G为算符文 法。 （2）定义优先关系：设文法G是一个OG文法，令a,b是任意两 个终结符号，P , G , R 是非终结符号，定义： . ① a = b 当且仅当文法G中含有形如P→…ab…或 P→…aQb…规则。 ② a <. b 当且仅当文法G中含有形如P→…aR…的 规则， 其中：R=>b…或R=>Qb…。 ③ a .> b 当且仅当文法G中含有形如P→…Rb…的 规则， 其中：R=>…a 或 R=>…aQ。
3
S S→aAcBe A→b | Ab a A c B e B→d 问abbcde是不是该文法的句子？ A b d 步骤 符号栈 输入流 动作 0 # abbcde# b 1 #a bbcde# 移进 2 #ab bcde# 移进 3 #aA bcde# 归约，用A→b 4 #aAb cde# 移进 5 #aA cde# 归约，用A→Ab 6 #aAc de# 移进 7 #aAcd e# 移进 8 #aAcB e# 归约，用B→d 9 #aAcBe # 移进 10 #S # 归约，用S →aAcBe 4 11 #S # 成功 例：设文法G[S]:
10
优先关系的例子

文法：S→bAb
A→(B | a B→Aa) //S→bAb //A→(Aa)|a
语言：{bab, b(aa)b, b((aa)a)b, } 可以从语法树里面导出部分优先关系。

S b b<a A a b a>b
S
b