编译原理习题-LL(1)分析

Tags

编译技术，LL分析

一道曾今的考题，当做复习了

考虑文法:

S→AaAb

S→BbBa

A→ε

B→ε

1）计算First和Follow集合

2）构造LL预测分析表

首先是First和Follow的计算：

[blockquote source=”FIRST”]

FIRST(X)：

可以从X推导得到的串的首符号的集合

算法：

1）如果X是一个终结符号，那么FIRST(X)=X

2）如果X是一个非终结符号，且X→Y1Y2….其中Y1…Yi-1 能推导出空串，则将FIRST(Yi)加入FIRST(X)中

3）如果X→∊,则∊也在FIRST(X)中

[/blockquote]

[blockquote source=”FOLLOW”]

FOLLOW(X):

可能在某些句型中紧跟在A右边的终结符号的集合

算法:

1）$在FOLLOW(S)中

2）如果存在一个产生式 A→αXb，那么FIRST(b)中除∊之外的所有终结符号都在FOLLOW(X)中

3）如果存在一个产生式 A→aX，或者A→aXb且FIRST(b)包含∊，那么FOLLOW(A)中的符号都在FOLLOW(X)中

[/blockquote]

于是

First(A) = First(B) = ∊

First(S)由于S能推导出Aa..和Bb..，故First(a)和First(b)包含在First(S)中，可得 First(S)=a,b

 

Follow(S) = $

由于S→AaAb，故Follow(A) = a,b

S→BbBa，故Follow(B) = a,b

然后是LL预测分析表构建

[blockquote source=”LL预测分析表构建算法”]

输入:文法G

输出:预测分析表M

算法:

对于每个G的产生式 A→X:

1)对于First(X)中得每个终结符号a,将A→X加入到M[A,a]中

2)如果∊在First(X)中，那么对于Follow(A)中的每个终结符号b，将A→X加入到M[A,b]中

如果∊在First(X)中，且$在Follow(A)中，也将A→X加入到M[A,$]中

[/blockquote]

由于S→AaAb,S→BbBa而

First(AaAb)=a，故有M[S,a]=S→AaBb

First(BbBa)=b，故有M[S,b]=S→BbBa

A→∊,B→∊, ∊在First(∊)中,Follow(A) = Follow(B)=a,b

故M[A,a]=M[A,b] = A→∊,M[B,a] = M[B,b] = B→∊