左因子和删除左递归JavaCC [英] Left Factoring & Removing Left Recursion JavaCC

问题描述

我有一个语法，我必须使用JJTree和JavaCC创建一个符号表和AST。
虽然我完全理解我的分配创建表和树的部分，我给出的语法是不明确的，包含左递归和间接左回顾。它还需要被左乘因子。
我已经拖网到互联网，试图找到方法，为我工作。

I have a grammar which I have to use JJTree and JavaCC to create a symbol table and an AST. While I fully understand the sections of my assignment to create the table and tree, the grammar I was given is ambiguous, contains left recursion and indirect left recusion. It also needs to be left factored. I have trawled all over the internet to try find methods that would work for me.

例如：

A :: = β

A ::= Aα | β

可以更改为：

can be changed to:

A :: =βA'

A':: =αA'
| ε

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

但我不知道如何将它应用到我的语法。

这是我从包含上述问题的语法中写的生产规则的一部分。

But I don't know how to apply this to my grammar.
Here is a section of the production rules I wrote from the grammar that contains the problems aforementioned.

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())
}

推荐答案

这里有很多问题。大多数都在JavaCC FAQ的问题4.6中处理。 http://www.engr.mun.ca/~theo/JavaCC-FAQ/

You have a number of problems here. Most are dealt with in question 4.6 of the JavaCC FAQ. http://www.engr.mun.ca/~theo/JavaCC-FAQ/

首先，有很多遗留因素要做。左因子试图将选择移动到稍后的解析。例如。如果你有

First, there is a lot of left-factoring to do. Left factoring tries to move choices to later in the parse. E.g. if you have

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

，解析器正在等待语句，输入的下一个项目是标识符，那么解析器不能做出选择。排除左侧的公共部分以获取

and the parser is expecting a statement and the next item of input is an identifier, then the parser can't make the choice. Factor out the common parts on the left to get

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

然后

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

b $ b

其次，非终结符匹配是无用的，因为没有非递归的情况。我怀疑你正试图处理悬而未决的问题。这不是一个好的办法来处理悬而未决的问题。请参阅JavaCC常见问题解答，了解如何处理它。

Second, the nonterminal "matched" is useless, as there is no nonrecursive case. I suspect that you are trying to deal with the dangling else problem. This is not a good way to deal with the dangling else problem. See the JavaCC FAQ for a sensible way to deal with it.

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

Third, there is mutual left recursion between nonterminals "fragment" and "expression". I'm not sure what you are trying to accomplish here. There are several ways to deal with parsing expressions that don't use left recursion. See http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm for more information. My tutorial introduction to JavaCC might also help. http://www.engr.mun.ca/~theo/JavaCC-Tutorial/

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

Finally a word of advice. Start with a grammar for a small subset of your language and then add constructs one or two at a time. That way you won't have to deal with a lot of problems at once.

这篇关于左因子和删除左递归JavaCC的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！