编译原理ch4 语法分析2

本文主要内容为计算First集和Follow集、递归和非递归预测分析法、预测分析中的错误处理等。

First集和Follow集的计算

计算文法符号X的FIRST(X )

回顾定义

FIRST ( X )：可以从X推导出的所有串首终结符构成的集合
如果 X -》*ε， 那么 ε∈FIRST ( X )

举例：

① E → TE'
② E' → +TE' |ε
③ T → FT '
④ T' → *FT ' |ε
⑤ F → (E)|id

First集求解：
FIRST ( E ) = { (， id } 
FIRST ( E' ) = { +， ε}
FIRST ( T ) = { (， id }
FIRST ( T' ) = { *， ε}
FIRST ( F ) = { (， id}

算法

不断应用下列规则，直到没有新的终结符或ε可以被加入到任何FIRST集合中为止

1. 如果X是一个终结符，那么FIRST ( X ) = { X }

2. 如果X是一个非终结符，且 X→Y1…Yk ∈ P (k≥1)，那么如果对于某个i， a在FIRST (Yi ) 中且ε 在所有的FIRST(Y1) , … , FIRST(Yi-1)中(即Y1…Yi-1 * ε )，就把a加入到FIRST( X )中。

   如果对于所有的 j = 1,2, . . . , k， ε在FIRST(Yj)中，那么将ε加入到FIRST( X )。

3. 如果 X→ε∈P，那么将ε加入到FIRST( X ) 。

计算串X 1X 2 …X n的FIRST 集合

1. 向FIRST(X1X2 …Xn)加入FIRST(X1)中所有的非ε符号
   理解：X1可推导出非ε的所有串首终结符加入FIRST(X1X2 …Xn)

2. 如果ε在FIRST(X1)中，再加入FIRST(X2)中的所有非ε符号；
   如果ε在FIRST(X1)和FIRST(X2)中，再加入FIRST(X3)中的所有非ε符号，以此类推

3. 最后，如果对所有的i， ε都在FIRST(Xi)中，那么将ε加入到FIRST(X1X2 …Xn) 中

计算非终结符A的FOLLOW(A)

回顾定义

FOLLOW(A)：可能在某个句型中紧跟在A后边的 终结符a 的集合
		FOLLOW(A)={ a| S -》 *αAaβ, a∈VT， α,β∈(VT∪VN)* }
如果A是某个句型的的最右符号，则将结束符“$”添加到FOLLOW(A)中

理解：

α,β为符号串

E → TE’ 中E、TE’ 即为两个句型

①E → TE'
② E' → +TE' |ε
③ T → FT'
④ T' → *FT' |ε
⑤ F → (E) | id

FIRST ( E ) = { ( id }
FIRST ( E' ) = { + ε }
FIRST ( T ) = { ( id }
FIRST ( T' ) = { * ε }
FIRST ( F ) = { ( id }

FOLLOW( E ) = { $ ) }
FOLLOW( E' )= { $ ) }
FOLLOW( T ) = { + $ ) }
FOLLOW( T' ) = { + $ ) }
FOLLOW( F ) = { * + $ ) }

算法

不断应用下列规则，直到没有新的终结符可以被加入到任何FOLLOW集合中为止 ：

S是开始符号，$是输入右端的结束标记

1. 将$放入FOLLOW( S )中

2. 如果存在一个产生式A→αBβ，那么FIRST ( β )中除ε 之外的所有符号都在FOLLOW( B )中

   紧跟在B后面除ε 之外的串首终结符，都在FOLLOW( B )中

3. 如果存在一个产生式A→αB，或存在产生式A→αBβ且FIRST ( β ) 包含ε，那么 FOLLOW( A )中的所有符号都在FOLLOW( B )中

理解：

α、β均是符号串

赏

谢谢你请我吃糖果

支付宝

微信