编译原理实验：消除文法的左递归

—

TE

'

E

'

—

+TE

'

/

?

T

—

FT

'

T

'

—

*FT

'

/

?

F

—（< /p>

E

）

/ I

考虑更一般的情况，假定关于非终结符

P

的规则为

P

—

P

al

/ P

o2

/??/

P

a

n

/

B

i

/

B

/??/

和

其中，

a

（

1

=

1

，

2

，…，

n

）都不为?而每个

B

（

j

=

1

，

2

，…，

m

）都不以

P

开

头，将上述规则改写为如下形式即可消除

P

的直接左递归：

P

—

B

i

P'

/ B

P'

/

??/

B

m

P

'

P

'

—

a

1

P

'

/

a

2

P

'

/

…

/

a

n

P

'

/

?

2

．间接左递归的消除

直接左递归见诸于表面，

利用以上的方法可以很容易将其消除，

即把直接左

递归改写成直接右递归。

然而文法表面上不存在左递归并不意味着该文法就不存

在

左递归了。有些文法虽然表面上不存在左递归，但却隐藏着左递归。 例如，设

有文法

G[S]

：

S

—

Qc/ c

Q

—

Rb/ b

R

—

Sa/ a

虽不具有左递归，但

S

、

Q

、

R

都是左递归的， 因为经过若干次推导有

S Qc Rbc Sabc

Q Rb Sab Qcab

R Sa Qca Rbca

就显现出其左递归性了，这就是间接左递归文法。

消除间接左递归的方法是，

把间接左递归文法改写为直接左递归文法，

然后

用消除直接左递归的方法改写文法。

如果一个文法不含有回路，即形如

P P

的推导，也不含有以

&

为右部的产< /p>

生式，那么就可以采用下述算法消除文法的所有左递归。

消除左递归算法：

(1)

把文法

G

的所有非终结符按任一顺序排列，例如，

A

n

。

(2)

for

(

i

=

1

；

i<=n

；

i++

)

for

(

j

=

1

;

j<=i

—

1

;

j++

)

{

把形如

A

i

f

A

j

Y

的产生 式改写成

A

i

f§

1

丫

/

62

丫

/

??/

&

丫

其中

A

j

f 6

1

/

6

/??/

&

是关于的

A

j

全部规则；

A

i

规则中的直接左 递

归；

}

A

i

, < /p>

A

2

,

…，

(3)

化简由

(

2

)

所得到的文法，即去掉多余的规则。

利用此算法可以将上

述文法进行改写，来消除左递归。

首先，令非终结符的排序为

R

、

Q

、

S

R

,

不存在直接左 递归。把

R

代

入

到

Q

中的相关规则中，贝

U

Q

的规则变为

Q< /p>

f

Sab/ ab/ b

。

代换后的

Q

不含有直接左递归，将其代入

S, S

的规则变为

S

f

Sabc/ abc/ bc/

c

。

此时，

S

存在直接左递归。在消除了

S

的直接左递归后，得到整个文法为：

S

f

abcS

'

/bcS'/ cS'

S'

f

abcS'/

&

Q

f

Sab/ ab/ b

R

f

Sa/ a

可以看到从文法开始符号

S

出发，永远无法达到

Q

和

R

,

< br>所以关于

Q

和

R

的规

则是多余的，将其删除并化简，最后得到文法

G[S]

为：

S

f

abcS'/ bcS

'

/cS'

S'

f

abcS'/

?

当然如果对文法非终结符排序的不 同，最后得到的文法在形式上可能不一

样，

< br>但它们都是等价的。例如，如果对上述非终结符排序选为

S

、

Q

、

R

,

那么最

后得到的文法

G[R]

为：

R

f

bcaR'/ caR'/ aR

R'

f

bcaR'/

?

容易证明上述两个文法是等价的。

3..

实验内容：

消除左递归算法：

(4)

把文法

G

的所有非终结符按任一顺序排列，例如，

A

n

。

(5)

for

(

i

=

1

；

i<=n

；

i++

)

A

1

,

A< /p>

2

,

…,

for

(

j

=

1

;

j<=i

—

1

;

j++

)

{

把形如

A

i

—

A

j

丫的产生式改写成

A

i

f

Si

Y & Y

??/

&

丫

其中

A

—

S

/

&

/??/

&

k

是关于的

A

j

全部规则；

消除

A

i

规则中的直接左递归；

}

(

6

)

化简由

(

2

)

所得到的文法，即去掉多余的规则。

利用此算法可以将上述文法进行改写，来消除左递归。

注意事项：

指明是否存在左递归，

以及左递归的类型。

对于直接左递归，

可将其改为直

接右递归；对于间接左 递归

(

也称文法左递归

)

，则应按照算法给出非终结符不

同排 列的等价的消除左递归后的文法。

(

应该有

n

!

种

)

4.

代码实现

(

C

语言

)

：

#include

#include<> #include<> #define N 20

char P[N][N];

char Q[N]; char

R[N][N];

int r;

//

规则集

//

规则集

,

存放间接左递归消除后的部分规则

//

用来存放规则的初始值

//

实际输入的规则的个数

int direct(char P[N][N]);

int indirect(char P[N][N]); void directRemove(char P[N][N]); void indirectRemove(char

//

直接左递归函数

P[N][N]);

//

间接左递归函数

int direct(char P[N][N])

//< /p>

定义直

//

消除直接左递归函数