开发者

Removing Left Recursion with Terminals

开发者 https://www.devze.com 2023-01-30 09:08 出处:网络
How do I remove left recursion on the following rule: S -> aSAbb | aA I understand how to perfor开发者_如何学Gom it on S -> SA | A

How do I remove left recursion on the following rule:

S -> aSAbb | aA

I understand how to perfor开发者_如何学Gom it on S -> SA | A

which becomes S -> A | AS'; S' -> A | AS', but the terminals throw me off in this question.

EDIT:

Sorry, apparently I was confused as to what left recursion is. I should have asked how to remove the left hand symbol from the right hand side.


The rule

S -> aSAbb | aA

is not left recursive. A left recursive rule has the form

A -> Au

where u is a sequence of terminals and nonterminals. To remove the symbol S from the right side of the S rules, consider:

S => aSAbb
  => a(aSAbb)Abb
  => a^n(aA)(Abb)^n

The role of the recursion on S is to produce this sequence. An equivalent grammar is:

S -> aKAbb | aA
K -> aSAbb | aA

The grammars are equivalent, since any derivation

S => aSAbb
  => a(aSAbb)Abb
  => a(a(aSAbb)Abb)Abb

is now just a derivation

S => aKAbb
  => a(aSAbb)Abb
  => a(a(aKAbb)Abb)Abb

and each derivation is terminated by aA (I think: please correct me if I'm wrong).

0

精彩评论

暂无评论...
验证码 换一张
取 消