编译原理学习笔记---自上而下分析
语法分析---自上而下分析
面临的问题:
-
左递归性问题
例如:P→Pa
如果存在非终结符P含有左递归的文法将上述自上而下的分析过程陷入无限循环
-
回溯
???
LL(0)分析法
-
左递归的消除
P→Pα|β 改写为 P→β p’
P’→ α P’ | ε
消除左递归的做法:
-
把文法G的所有非终结符按人一种顺序排列成P1,P2……Pn,按此顺序执行;
-
FOR i:=1 TO n DO
BEGIN
FOR j:=1 TO i-1 DO
把形如Pi→Pjγ的规则改写成
Pi→δ1γ|δ2γ|………|δkγ。其中Pj→δ1|δ2|…….| δk是关于Pj的所有规则;
消除关于Pj规则的直接左递归性
END
-
化简由(2)所得的文法。即去除那些从开始符号出发永远无法到达的非终结符的产生规则。
(其实就是先展开再消除左递归)
-
消除回溯,提左因子
消除回溯的实质就是为了减少回溯所造成的不必要的资源浪费
方法有 提取公共左因子.
A→δβ1|δβ2|…………|δβn|γ1|γ2|………|γm
改写为:A→δ A’|γ1|γ2|………|γm
A’→ β1|β2|……|βn
LL(1)文法的判断:
-
文法不含有左递归
-
对于文法中的每一个非终结符A的各个产生式的候选首符集两两不相交。即,若
A→α1|α2|…….|αn
则 FIRST(αi) ∩ FIRST(αj) = Φ
-
对于文法中的每一个非终结符A,若它存在某个候选首符集包含ε,则FIRST(A) ∩ FOLLOW(A) = Φ
递归下降分析程序
预测分析程序:
-
预测分析表的构建:
首先求出各个非终结符的FIRST和FOLLOW。
-
对文法G的每个产生式A→α执行第二步和第三步;
-
对每个终结符a∈FIRST(α),把A→α加至M[A,a]中;
-
若ε∈FIRST(α),则对任何b∈FOLLOW(A)把A→α加至M[A,b]中;
-
把所有无定义的M[A,a]标上”出错标志“。
理解:
先求出各个非终结符号的FIRST和FOLLOW;
然后画数组,行为终结符,列为非终结符;
对应上下图可以看出:
先根据各个非终结符的FIRST填写数组
然后FIRST中含有ε的,根据其FOLLOW填写
然后利用分析表进行预测分析: