parsing - 左分解和删除左递归 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 FAQ 的问题 4.6 中处理。 http://www.engr.mun.ca/~theo/JavaCC-FAQ/

首先，有很多左因式分解。左因式分解试图将选择移到解析的后面。例如。如果你有

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

并且解析器期待一个语句，而下一个输入项是一个标识符，那么解析器就无法做出选择。分解出左边的公共(public)部分得到

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

然后

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

其次，非终结符“匹配”是无用的，因为不存在非递归情况。我怀疑您正在尝试处理悬空的 else 问题。这不是处理悬空 else 问题的好方法。请参阅 JavaCC 常见问题解答以了解处理它的明智方法。

第三，非终结符“片段”和“表达式”之间存在相互左递归。我不确定您要在这里完成什么。有几种方法可以处理不使用左递归的解析表达式。参见 http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm了解更多信息。我的 JavaCC 教程介绍也可能有所帮助。 http://www.engr.mun.ca/~theo/JavaCC-Tutorial/

最后提个建议。从您语言的一小部分语法开始，然后一次添加一个或两个结构。这样您就不必一次处理很多问题。