Left Factoring & Remove Left Recursion JavaCC

Question

我有一个语法，我必须使用JJTree和JavaCC来创建一个符号表和一个AST。虽然我完全理解我的作业中创建表和树的部分，但我得到的语法是模糊的，包含左递归和间接左递归。它也需要考虑在内。我在互联网上搜索了所有的方法，试图找到适合我的方法。

例如：

A:：=Aα|β

可以更改为：

A:：=βA'
A'：：=αA'|ε

但我不知道如何把它应用到我的语法中
以下是我根据语法编写的生成规则的一部分，其中包含上述问题。

void statement() #STM : {}
{
   identifier() <ASSIGNMENT> expression()
   | identifier() <ASSIGNMENT> <STRING>
   | <EXCLAMATION> expression()
   | <QUESTION> identifier()
   | identifier() <LBR> arg_list() <RBR>
   | <BEGIN> (statement() <SEMIC>)+ <END>
   | matched()
   | unmatched()
   | <WHILE> <LBR> condition() <RBR> <DO> statement()
   | {}
}
void matched() #void : {}
{
    <IF> condition() <THEN> matched() <ELSE> matched()
}
void unmatched() #void : {}
{
    <IF> condition() <THEN> statement()
    |  <IF> condition() <THEN> matched() <ELSE> unmatched()
}
void expression() #EXPR : {}
{
    fragment() ((<PLUS>|<MINUS>|<MULT>|<DIV>) fragment())*
}
void fragment() #FRAG : {}
{
    (identifier() | <NUM> | (<PLUS>|<MINUS>) fragment() | expression())
}

Answer 1

这里有很多问题。大多数都在JavaCC常见问题解答的问题4.6中进行了处理。http://www.engr.mun.ca/~theo/JavaCC常见问题解答/

首先，有很多左因子分解要做。左因子分解试图将选择转移到稍后的解析中。例如，如果您有

void statement() #STM : {}
{
   identifier() <ASSIGNMENT> expression()
 | identifier() <ASSIGNMENT> <STRING>
 | identifier() <LBR> arg_list() <RBR>
}

如果解析器需要一个语句，而下一个输入项是一个标识符，那么解析器就无法做出选择。将左边的常见部分考虑在内，得到

void statement() #STM : {}
{
   identifier()
      (   <ASSIGNMENT> expression()
      |   <ASSIGNMENT> <STRING>
      |   <LBR> arg_list() <RBR>
      )
}

然后

void statement() #STM : {}
{
   identifier()
      (   <ASSIGNMENT> ( expression() | <STRING> )
      |   <LBR> arg_list() <RBR>
      )
}

其次，非词尾的"matched"是无用的，因为没有非递归的大小写。我怀疑你是在设法解决悬而未决的其他问题。这不是处理其他问题的好方法。请参阅JavaCC常见问题解答，了解明智的处理方法

第三，非终结符"fragment"one_answers"expression"之间存在相互的左递归。我不确定你想在这里完成什么。有几种方法可以处理不使用左递归的解析表达式。看见http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm了解详细信息。我的JavaCC教程介绍可能也会有所帮助。http://www.engr.mun.ca/~theo/JavaCC教程/

最后一句忠告。从一小部分语言的语法开始，然后一次添加一两个结构。这样你就不必同时处理很多问题了。