左分解非左递归语法使其成为LL（1）

我已经从给予我的左递归语法中删除了左递归。原来的语法如下：左分解非左递归语法使其成为LL（1）

SPRIME :: = Expr的EOF
Expr的:: =条款| Expr +期限| Expr - Term
Term :: = Factor |术语*因子|术语/因子|术语mod因子|术语div因子
因子:: = ID | {Expr} | num | Funcall |
Funcall :: = id [Arglist]
Arglist :: = Expr | EXPR，ARGLIST

当移除左递归，这是我公司生产的语法：

SPRIME :: = EXPR EOF
EXPR :: =期限EXPR '
EXPR' :: = È | + Term Expr'| - Term Expr'
Term :: = Factor Term'
Term':: = e | *因子术语'| /因子术语'| mod因子术语'| div因子项'
因子:: = ID | {Expr} | num | Funcall
Funcall :: = ID[ ARGLIST ]
ARGLIST :: = Expr的ARGLIST '
ARGLIST' :: = ， ARGLIST | e

我的下一个任务是对该语法执行左分解以使其成为LL（1）。阅读了龙书中的相关章节后，我不确定是否需要对该语法做任何事情。我的问题是：这是LL（1）形式的语法吗？如果不是，我需要在哪里执行左分解以使其成为LL（1）？

编辑：在将@ suddnely_me的回答考虑在内后，我编辑了Arglist非终端以便将其生成的因素留下。我现在的语法是LL（1）语法吗？

来源

2011-04-09 Richard Stokes

不，这个语法不是LL（1）。至少，由于FIRST（Expr）和FIRST（Expr，Arglist）进行了互动，因此最后的规则组不会被留下因素。

来源

2011-04-09 13:14:27 iehrlich

所以会修改语法在以下方式将其转换为LL（1）？ – 2011-04-10 11:39:01

乍一看，是的。正如我记得我的学年，检查语法是否为LL（1）的最好方法是构建LL（1）分析器。有一些常见的算法可以做到这一点。 – iehrlich 2011-04-10 12:27:44

     if it is in the form of  A->A.ALPHA|BETA 
         REMOVING LEFT RECURSION  A->BETA A'| 
         A'->ALPHA A'|NULL   
         EXAMPLE:::A->A+B|a 
         IN THIS A=A A'=A' 
         ALPHA=+B 
         BETA=a 
        REMOVING LEFT RECURSION : A=aA' 
         A'=+BA'|NULL

来源

2012-01-17 05:00:05 srija

如果你解释了你发布的代码，它会更好。 – 2012-10-28 00:39:12

不，还是（甚至一年后！）不是LL（1）。我的oracle说：

Can't choose between two rules of 'Factor' 
    -> id 
    -> Funcall 

'Funcall' can start with id. For example: 
    Funcall -> id ...

来源

2013-02-05 05:13:40

左分解非左递归语法使其成为LL（1）

回答

相关问题