LL1语法中的左递归消除 [英] Left recursion elimination in an LL1 grammar

问题描述

我试图从语法的以下提取中消除左递归 -

  expression：= fragment（（+ |  -  | * | /）fragment）* 
 
 fragment：= identifier |数字| （+ |  - ）片段|表达式
  

问题是表达式可以去片段，可以去表达式。我已经尝试了一堆方法来消除它，一些看起来像他们工作（在JavaCC），但我不能确定他们的正确性，和b）肯定我已经通过改变语法的结构打破了关联性。

我确定我需要一个表达式，并且有

  fragment：= identifier |数字| （+ |  - ）片段|表达式
  

更改为

  fragment：= identifier |数字| （+ |  - ）片段| expressionPrime 
  

但我不确定formPrime的形式。两者

  expressionPrime：= identifier |数字| （+ |  - ）片段| {} 
  

和

  expressionPrime：=（（+ |  -  | * | /）fragment）* 
  

似乎工作，但我知道它不能两者。

任何想法都会非常赞赏，甚至一个正确的方向。

解决方案

以

开头

  expression :: = fragment（（+ |  -  | * | /）fragment）* 
 fragment :: = identifier |数字| （+ |  - ）片段|表达式
  

定义

  frag1 :: = identifier |数字| （+ |  - ）fragment 
  

注意，fragment等效于 frag1 |表达式。替换前者由后者到处得到

  expression :: =（frag1 | expression）（（+ |  -  | * | /）（frag1 | expression））* 
 frag1 :: = identifier |数字| （+ |  - ）（frag1 | expression）
  


expression :: = frag1更多|表达式更多，


其中

  more :: =（（+ |  -  | * | /）（frag1 | expression））* 
  

现在你可以看到一个表达式是 frag1 后跟一个或多个更多 / p>

因此

  expression :: = frag1（more）+ 
  

您的语法仍然含糊不清 - 对于1 * - 2 * 3，有2个解析树。但至少它不再递归。

（如果你在你的作业中使用这个，一定要引用这个答案，所以你不会最终打破你的）

我仍然认为你的教练犯了一个错误，因为如果你改变

  fragment :: = identifier |数字| （+ |  - ）片段|表达式
  

到

 code> fragment :: = identifier |数字| （+ |  - ）片段| （expression），
  

你有一个明智的语法。

I'm trying to eliminate left recursion from the following extract of a grammar -

expression := fragment ( ( + | - | * | / )  fragment )*

fragment := identifier | number | ( + | - ) fragment | expression

The issue is that expression can go to fragment, can go to expression. I've tried a bunch of ways to eliminate it, some look like they work (in JavaCC) but I'm a)unsure of their correctness, and b) pretty sure I've broken associativity by changing the structure of the grammar.

I'm pretty sure I need an expression', and have

fragment := identifier | number | ( + | - ) fragment | expression

changed to

fragment := identifier | number | ( + | - ) fragment | expressionPrime 

But I'm unsure of the way to form expressionPrime. Both

expressionPrime := identifier | number | ( + | - ) fragment | {}

And

expressionPrime := ( ( + | - | * | / )  fragment )*

Seem to work, but I know it can't be both.

Any ideas would be much appreciated, even a point in the right direction.

解决方案

Start with

expression ::= fragment ( ( + | - | * | / )  fragment )*
fragment ::= identifier | number | ( + | - ) fragment | expression

Define

frag1 ::= identifier | number | ( + | - ) fragment

Note that fragment is equivalent to frag1 | expression. Replace the former by the latter everywhere to get

expression ::= (frag1 | expression) ( ( + | - | * | / )  (frag1 | expression) )*
frag1 ::= identifier | number | ( + | - ) (frag1 | expression)

fragment is no longer needed.

Distribute to get

expression ::= frag1 more | expression more   ,

where

more ::= ( ( + | - | * | / )  (frag1 | expression) )*

Now you can see that an expression is a frag1 followed by one or more more

So

expression ::= frag1 (more)+

Your grammar is still ambiguous -- there are 2 parse tress for "1 * - 2 * 3". But at least it is not left recursive anymore.

(If you use this in your assignment, be sure to cite this answer, so you don't end up breaking your institution's academic dishonesty rules.)

I still think your instructor made a mistake, since, if you change

fragment ::= identifier | number | ( + | - ) fragment | expression

to

fragment ::= identifier | number | ( + | - ) fragment | "(" expression ")"   ,

you have a sensible grammar for expressions.

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