编译原理自上而下语法分析【PPT】共49页文档

S → AB|bc
B → a|c
B → a|c
A → Ad|Sbc|d
A → bcbcPQ|dPQ Q → BbcPQ|ε
直接左递归 间接左递归 P → dP|ε S → AB|bc S → AB|bc
B → a|c
B → a|c
A → SbcP|dP A → ABbcP|bcbcP|dP
P→dP|ε
P γP’ P’αP’|βP’|
P βP’|γP’ P’αP’|
程序设计语言与编译
一般地: 改写为:
A→Aα1|Aα2|…|Aαm|β1|β2|…|βn （ α i ≠ ε ， β j 不以A开头）
A→β1P’│ β2P’│. . . │ βnP’ P’→α1P’│α2P’│. .
.│αmP’│ε
xay的推导过程如右图
S
xAy aB ε
程序设计语言与编译
一般方法
产生式： A→αβ1|αβ2|…|αβn|δ
提取公共左因子α
A→αB|δ B→β1|β2|…|βn
程序设计语言与编译 四 . 消除左递归
1.消除直接左递归
P→Pα│β
改写为
P→P ’ P’→αP’│ε
PPα|Pβ|γ 改写为 PPα|β|γ 改写为
(4.3)
虽没有直接左递归，但S、Q、R都是左递归的
S⇒Qc⇒Rbc⇒Sabc
程序设计语言与编译
2.间接左递归的消除
例子：
A → Bc│a B → Ab
P ⇒+ Pα
⇒ A → Abc │a
改为：
A → aP’ P’→ bcP’│ ε
程序设计语言与编译
算法
1. 将文法G的所有非终结符按任一顺序排列，设为A1,…,An

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α使分析陷入无限循环 回溯的不确定性，要求我们将已经完成工作推倒重来 虚假匹配问题 难于知道出错位置 效率低，代价高，实践价值不大
END
③ 化简上述文法
11
例4.3：考虑文法：SQc|c
Q Rb|b
R Sa|a
消除左递归。
解：将终结符排序为R、Q、S。对于R不存在直接左递归。把R带入 到Q中有关的候选式： Q Sab|ab|b
现在Q同样不含直接左递归，把它带入S的有关候选式：
S Sabc|abc|bc|c 经消除S的直接左递归后我们们得到整个文法
❖ 下图表明了语法分析器在编译程序中的地位
源程序
词法分析器
单词符号 取下一
语法分析器
语法 分析树
单词符号
后续部分
符号表
❖ 按照语法分析树的建立方法，我们可以粗略地把语法分析方 法分为两类：一类是自上而下分析法，另一类为自下而上分 析法
3
例：自顶向下构造最左推导（aabbaa) SaASa A SbA SS ba
执行任务。这个候选就是那个终结首符集含a 的
14
❖ 如何把一个文法改造成任何终结首符集的所有候选首符集两 两不相交呢？其办法是提取公共左因子
❖ 假定关于A 的规则是 A1| 2| … |n| 1| 2|… |m （其中每个不以开头）
那末，可以把这些规则改写成： A A’| 1| 2|… |m A’ 1 | 2 | …| n

Yn；当Y1 Y2 … Yi-1都ε时，(其中1≤i≤n)，则FIRST(Y1){ε}、FIRST(Y2) -{ε} 、…、FIRST(Yi-1)- {ε}，FIRST(Yi) 都包含在FIRST(X)中
(e) 当(d)中所有Yi * ε,(i=1,2,…n)，则 FIRST(X)=FIRST(Y1)∪FIRST(Y2)∪…∪FIRST(Yn)∪{ε}
一 . 自上而下语法分析方法
给定文法G和源程序串$。从G的开始符 号S出发，通过反复使用产生式对句型中的 非终结符进行替换(推导)，逐步推导出$ 。
是一种产生的方法，面向目标的方法。 分析的主旨是选择产生式的合适的侯选 式进行推导，逐步使推导结果与$匹配。
Ch4 语法分析 4.1 语法分析程序综述 4.1.2 语法分析的方法
计算Select集：
B ε | aD C AD | b
每个产生式的Select集合计算为:D aS | c
Select(SAB)= (first (AB) -{ε}) ∪Follow(S)={b,a,#}
Select(S bC)= first (bC)={b}
因为A B
Select(Aε)=(first (ε) -{}) ∪Follow (A)={c,a,#}
A ε | b B ε | aD C AD | b D aS | c
first(C)={first(A)-{}} ∪first(D) ∪first(b)={a,b, c}
first(D)={a} ∪{c}={a,c}
➢求出每个文法符号的FIRST集合后也就不难求出一个符号 串的FIRST集合
✓若符号串α∈V*，α=X1 X2 … Xn,当X1不能
∪{ε}
ε*,则置 ∈

当预测失败时，需要回溯到之前的步骤并尝试其 他可能的分支，这可能导致效率低下。
3
对输入符号的依赖
自上而下的语法分析需要在分析过程中不断查看 输入符号，因此对输入符号的依赖较强。
编译原理的发展趋势与挑战
静态代码分析与优化
通过静态代码分析技术，编译器可以在编译时检测出更多的潜在错误，并进行 相应的优化。
非递归预测分析的基本思想
消除左递归
通过改写文法规则，消除直接和间接左递归，使得分析过程能够 顺利进行。
构造预测分析表
根据文法规则和非终结符的FOLLOW集，构造预测分析表，用于 指导分析过程。
栈和输入符号的同步处理
使用栈保存分析过程中的信息，并根据输入符号和栈顶信息进行同 步处理，实现语法分析。
非递归预测分析表的构造
介绍LL(1)文法的定义和判别方法，包括FIRST集和 FOLLOW集的构造。
递归下降分析算法设计
介绍递归下降分析算法的设计方法，包括递归子程序的 编写和错误处理机制。
02
CATALOGUE
语法分析基础
语法分析器的作用
识别语法错误
语法分析器能够检查源代码是否 符合语言的语法规则，识别出语 法错误并提供相应的错误信息。
在推导过程中，如果遇到非终 结符，则根据相应的产生式规 则进行替换，直到最终得到终
结符序列为止。
递归下降分析器的构造
分析函数根据当前输入符号和文 法规则判断应该执行的操作。
如果当前输入符号与文法规则中的某 个终结符相匹配，则消耗掉该输入符 号，并继续分析下一个输入符号。
如果当前输入符号与文法规则中 的某个非终结符相匹配，则调用 相应的分析函数进行递归分析。
预测分析算法的实现
初始化分析栈