Удаление левой рекурсии в ANTLR

Рассмотрим что-то вроде типичного списка параметров:

parameter_list: parameter
              | parameter_list ',' parameter
              ;

Поскольку вас не волнует ничего вроде приоритета или ассоциативности параметров, это довольно легко преобразовать в правую рекурсию за счет добавления дополнительной продукции:

parameter_list: parameter more_params
              ;

more_params:
           | ',' parameter more_params
           ;

В наиболее серьезных случаях вы можете потратить некоторое время на Книгу Дракона. Если сделать быструю проверку, это в основном рассматривается в главе 4.

Что касается серьезности, я почти уверен, что ANTLR просто не примет грамматику, содержащую левую рекурсию, которая поставила бы ее в «абсолютную необходимость». категория.

Я не могу говорить об ANTLR, но в целом шаги по устранению левой рекурсии формы:

A -> A B
  -> B

заключаются в изменении ее на:

A -> B+

(обратите внимание, что B должен появиться хотя бы один раз)

или, если ANTLR не поддерживает закрытие Клини, вы можете сделать:

A -> B B'

B' -> B B'
   -> 

Если вы предоставите пример ваших правил, у которых есть конфликты, я могу предоставить лучший, более конкретный ответ.

В практическом смысле, насколько серьезно удаление левой рекурсии в ANTLR? Является это препятствие в использовании ANTLR?

Я думаю, что вы неправильно понимаете левую рекурсию. Это свойство грамматики, а не генератора синтаксического анализатора или взаимодействия между генератором синтаксического анализатора и спецификацией. Это происходит, когда первый символ в правой части правила равен нетерминалу, соответствующему самому правилу.

Чтобы понять присущую здесь проблему, вам нужно кое-что знать о том, как работает синтаксический анализатор с рекурсивным спуском (LL). В анализаторе LL правило для каждого нетерминального символа реализуется функцией, соответствующей этому правилу. Итак, предположим, что у меня есть такая грамматика:

S -> A B
A -> a
B -> b

Тогда синтаксический анализатор будет выглядеть (примерно) следующим образом:

boolean eat(char x) {
  // if the next character is x, advance the stream and return true
  // otherwise, return false
}

boolean S() {
  if (!A()) return false;
  if (!B()) return false;
  return true;
}

boolean A(char symbol) {
  return eat('a');
}

boolean B(char symbol) {
  return eat('b');
}

Однако что произойдет, если я изменю грамматику на следующую?

S -> A B
A -> A c | null
B -> b

Предположительно, я хочу это грамматика для представления языка вроде c * b . Соответствующая функция в анализаторе LL будет выглядеть так:

boolean A() {
  if (!A()) return false;  // stack overflow!  We continually call A()
                           // without consuming any input.
  eat('c');
  return true;
}

Итак, у нас не может быть левой рекурсии. Перепишите грамматику как:

S -> A B
A -> c A | null
B -> b

, и синтаксический анализатор изменится как таковой:

boolean A() {
  if (!eat('c')) return true;
  A();
  return true;
}

(Отказ от ответственности: это мое примитивное приближение анализатора LL, предназначенное только для демонстрационных целей по этому вопросу. В нем есть очевидные ошибки.)