左递归消除 [英] Left recursion elimination

问题描述

我尝试通过消除间接递归，然后直接递归来消除CFG中的左递归，因为此算法显示。

我会用这个语法：

  A = A a | A B C | B C | DD 
  

当 i = 1 和 j = 1 我们正在寻找将 A - > A r 格式的所有作品替换为：

A - >δ 1 γ | δ ₂ γ | .. | δ _k γ

所以当我看看匹配的 A - > A a 它与

  A  - > A a a | A B C a a | B C a | DD a 
  

这确实错了。

注意：我只会停留在第一个

[UPDATE] Found as close是什么意思？到原始的希腊符号，我可以。另外，我可能是在错误的方向接近这个。当 i = 1 和 j = 1 时，A _j - > A a | A B C | B C | D D，BUT应该使用A _{j <> - > B C | D D
如果是，那么我会得到：}

  A  - > B C A | B C B C | D D A | D D B C | B C | D D 
  

这样会消除该生产中的递归。

解决方案

这是食谱：

  A→Aα1| ... | Aαm| β1| ... | βn
  

应转换为

  A→β1A'| ... | βnA'
 A'→α1A'| ... | αmA'| ε
  

即：

1. 将递归生成替换为递归位于右侧的新生成。


2. 将新的非终端符号添加到新的非终端符号。
添加新的非终端符号。



对于您的语法：

  A = A a | A B C | B C | DD 
  

您将获得：

  A = BC A'| D D A'
 A'= a A'| B C A'| ε
  




I'm attempting to eliminate left recursion from a CFG by eliminating indirect recursion then direct recursion as this algorithm shows.

I'll be using this grammar:

A = A a | A B C | B C | D D

When i = 1, and j = 1 we are looking at replacing all productions of the form A -> A r with:

A -> δ₁ γ | δ₂ γ | .. | δ_k γ

So when I look at A -> A a which matches, i should replace it with

A -> A a a | A B C a a | B C a | D D a  

which im sure is wrong

Can anyone point me in the right direction for how to replace productions when your replacing it with the production itself?

NOTE : Also, I'm only stuck on the first rule so have omitted the others for simplicity

Any help would be greatly appreciated

[UPDATE]Found as close to the original greek symbols as I could. Also, am I perhaps approaching this in the wrong direction. When i=1 and j=1, A_j -> A a | A B C | B C | D D, BUT should I be using A_j -> B C | D D If so then I would get:

A -> B C A | B C B C | D D A | D D B C | B C | D D

As that would then eliminate the recursion in that production. This a better direction?

解决方案

This is the recipe:

A → Aα1 | ... | Aαm | β1 | ... | βn

should be transformed to:

A → β1 A' | ... | βn A'
A' → α1 A' | ... | αm A' | ε

That is:

1. Replace the recursive productions with new productions in which recursion is on the right. Use a new non-terminal symbol for that.
2. Add a production with an empty right side to the new non-terminal.
3. Append the new non-terminal symbol to the right of the non-recursive productions.

For your grammar:

A = A a | A B C | B C | D D

you would obtain:

A  = B C A' | D D A'
A' = a A' | B C A' | ε

这篇关于左递归消除的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！