Как удалить левую рекурсию в JavaCC? - PullRequest
Новая
       51

Как удалить левую рекурсию в JavaCC?

0 голосов
/ 18 октября 2018

Я пытаюсь удалить левую рекурсию в JavaCC для expr, которая должна быть определена как: 

expr ::= statement binary_op statement
| **(** expr **)**
| identifier **(** arg **)**
| statement

Этот код вызывает левую рекурсию в моей программе: 

void expr() : { }
{

    < LPAREN > simpleExpr() < RPAREN >
    | < IDENTIFIER > <LPAREN > arg() < RPAREN >
    | statement()
}

void simpleExpr() : { }
{
    statement() binary_op() statement()
}

операторопределяется как: 

statement ::= id | - id | number | false | true | expr

void statement() : { }
{
    < ID > | < NOT_OP > < ID >
    | < DIGIT >
    | < TRUE >
    | < FALSE >
    | expr() 
}

Ошибка, которую я получаю в своей программе: 

Left recursion detected: "expr... --> statement... --> expr..."

Как бы это исправить?

Ответы [ 2 ]

0 голосов
/ 19 октября 2018

Согласно вашей грамматике, statement может быть expr, а expr может быть statement.Поэтому языки, генерируемые этими двумя нетерминалами, одинаковы.Вам не нужны оба нетерминала.Я бы предложил удалить определение statement и изменить определение expr на это 

void expr() : { }
{
      < ID >
    | < NOT_OP > < ID >
    | < DIGIT >
    | < TRUE >
    | < FALSE >
    | < LPAREN > simpleExpr() < RPAREN >
    | < IDENTIFIER > <LPAREN > arg() < RPAREN > 
}

Затем либо

  • заменить statement на expr вездев оставшейся грамматике (включая определение simpleExpr)

  • или добавьте это правило: 

    void statement() : { }
{
    expr()
}
0 голосов
/ 19 октября 2018
  1. Ваше использование идентификатора statement довольно необычно.Это больше похоже на literal.
  2. В вашем statement вы должны удалить строку | expr().В противном случае statement может быть expression, а expression может быть statement ... как тогда решит анализатор?
...