消除文法的左递归

简介

1.直接左递归的消除

消除产生式中的直接左递归是比较容易的。例如假设非终结符P的规则为

P→Pα / β

其中,β是不以P开头的符号串。那么,我们可以把P的规则改写为如下的非直接左递归形式:

P→βP’

 P’→αP’ / ε

这两条规则和原来的规则是等价的,即两种形式从P推出的符号串是相同的。

设有简单表达式文法G[E]:

E→E+T/ T

T→T*F/ F

F→(E)/ I

经消除直接左递归后得到如下文法:

E→TE’

E’ →+TE’/ ε

T→FT’

T’ →*FT’/ ε

F→(E)/ I

考虑更一般的情况,假定关于非终结符P的规则为

P→Pα1 / Pα2 /…/ Pαn / β1 / β2 /…/βm

其中,αi(I=1,2,…,n)都不为ε,而每个βj(j=1,2,…,m)都不以P开头,将上述规则改写为如下形式即可消除P的直接左递归:

P→β1 P’ / β2 P’ /…/βm P’

P’ →α1P’ / α2 P’ /…/ αn P’ /ε

2.间接左递归的消除

消除间接左递归的方法是,把间接左递归文法改写为直接左递归文法,然后用消除直接左递归的方法改写文法。

如果一个文法不含有回路,即形如PP的推导,也不含有以ε为右部的产生式,那么就可以采用下述算法消除文法的所有左递归。

消除左递归算法:

  • 把文法G的所有非终结符按任一顺序排列,例如,A1,A2,…,An

for (i=1;i<=n;i++)

for (j=1;j<=i-1;j++)

{   把形如Ai→Ajγ的产生式改写成Ai→δ1γ /δ2γ /…/δkγ

其中Aj→δ12 /…/δk是关于的Aj全部规则;

消除Ai规则中的直接左递归;

}

  • 化简由(2)所得到的文法,即去掉多余的规则。

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

首先,令非终结符的排序为R、Q、S。对于R,不存在直接左递归。把R代入到Q中的相关规则中,则Q的规则变为Q→Sab/ ab/ b。

代换后的Q不含有直接左递归,将其代入S,S的规则变为S→Sabc/ abc/ bc/ c。

此时,S存在直接左递归。在消除了S的直接左递归后,得到整个文法为:

S→abcS’/ bcS’/ cS’

S’ →abcS’/ ε

Q→Sab/ ab/ b

R→Sa/ a

可以看到从文法开始符号S出发,永远无法达到Q和R,所以关于Q和R的规则是多余的,将其删除并化简,最后得到文法G[S]为:

S→abcS’/ bcS’/ cS’

S’ →abcS’/ ε

当然如果对文法非终结符排序的不同,最后得到的文法在形式上可能不一样,但它们都是等价的。例如,如果对上述非终结符排序选为S、Q、R,那么最后得到的文法G[R]为:

R→bcaR’/ caR’/ aR’

R’ →bcaR’/ ε

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

指明是否存在左递归,以及左递归的类型。对于直接左递归,可将其改为直接右递归;对于间接左递归(也称文法左递归),则应按照算法给出非终结符不同排列的等价的消除左递归后的文法。(应该有n!种)

c++代码

C++编写,共三个模块,第一个模块是将简介左递归转换为直接左递归,第二个模块是将直接左递归消除,最后一个模块是主函数模块。

 

测试数据

测试数据1:

  1. A->aB
  2. A->Bb
  3. B->Ac
  4. B->d

测试数据2:

  1. S->Qc|c
  2. Q->Rb|b
  3. R->Sa|a

测试数据3:

  1. Q->Rb|b
  2. S->Qc|c
  3. R->Sa|a

测试数据4:

  1. R->Sa|a
  2. Q->Rb|b
  3. S->Qc|c

结果

测试数据1:

测试数据2:

测试数据3:

测试数据4:

遇到的难点和解决方案

由于文法的形式多种多样,在消除递归时要考虑到各种情况,一般来说,首先要解决统一文法格式,因此需要将具有相同非终结符左部的文法用|符号合并。接着,要解决间接左递归问题,因此将间接左递归转换成直接左递归。最后将消除直接左递归。在消除过程中要判断两个量,一个是|的位置,另一个是非终结符的位置,由于合并的文法串中有多个|,并且会生成新的转换的文法,因此需要用while语句进行处理,直到所有文法的形式不再变化为止。

第二个问题,消除左递归文法后有一部分的非终结符及其产生式无用,因此需要将其去处,使用DFS从开始符S开始检测非终结符,最终可以解决此种问题。

读者评分
[评分人数: 0 平均分: 0]

评论

OmegaXYZ