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

Question

Как объясняется в Удаление левой рекурсии , существует два способа удаления левой рекурсии.

• Измените исходную грамматику, чтобы удалить левую рекурсию, используя некоторую процедуру
• Напишите грамматику изначально, чтобы не было левой рекурсии

Что люди обычно используют для удаления (не имея) левой рекурсии с помощью ANTLR? Я использовал flex / bison для парсера, но мне нужно использовать ANTLR. Единственное, что меня беспокоит при использовании ANTLR (или LL-парсера в целом), это удаление левой рекурсии.

• В практическом смысле, насколько серьёзно удаление левой рекурсии в ANTLR? Является ли это showtopper в использовании ANTLR? Или никто не заботится об этом в сообществе ANTLR?
• Мне нравится идея создания ANTLR AST. С точки зрения быстрого и простого получения AST, какой метод (из двух методов удаления левой рекурсии) предпочтительнее?

Добавлена ​​

Я провел некоторый эксперимент со следующей грамматикой.

E -> E + T|T
T -> T * F|F
F -> INT | ( E )

После удаления левой рекурсии я получаю следующий

E -> TE'
E' -> null | + TE'
T -> FT'
T' -> null | * FT'

Я мог бы придумать следующее представление ANTLR. Несмотря на то, что это относительно довольно просто и понятно, кажется, что грамматика, не имеющая левой рекурсии, должна быть лучшим путем.

grammar T;

options {
    language=Python;
}

start returns [value]
   : e {$value = $e.value};
e returns [value]
   : t ep  
     {
       $value = $t.value
       if $ep.value != None:
         $value += $ep.value
     }
   ;
ep returns [value]
   : {$value = None}
   | '+' t r = ep 
     {
       $value = $t.value
       if $r.value != None:
            $value += $r.value
     }
   ;
t returns [value]
  : f tp 
    {
      $value = $f.value
      if $tp.value != None:
        $value *= $tp.value
    }
  ;
tp returns [value]
  : {$value = None}
  | '*' f r = tp 
    {
      $value = $f.value;
      if $r.value != None:
        $value *= $r.value
    }
  ;
f returns [int value]
  : INT {$value = int($INT.text)}
  | '(' e ')' {$value = $e.value}
  ;

INT :   '0'..'9'+ ;
WS: (' '|'\n'|'\r')+ {$channel=HIDDEN;} ;

Answer 1

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

parameter_list: parameter
              | parameter_list ',' parameter
              ;

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

parameter_list: parameter more_params
              ;

more_params:
           | ',' parameter more_params
           ;

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

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

Answer 2

В практическом смысле, насколько серьезно удалить левую рекурсию в ANTLR? Является это showtopper в использовании 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, предназначенное только для демонстрационных целей по этому вопросу. В нем есть очевидные ошибки.)

Answer 3

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

A -> A B
  -> B

должен изменить это на:

A -> B+

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

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

A -> B B'

B' -> B B'
   -> 

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

Answer 4

Если вы пишете грамматику, то, конечно, вы пытаетесь написать ее, чтобы избежать ошибок вашего конкретного генератора синтаксического анализатора.

Обычно, по своему опыту, я получаю справочное руководство по (унаследованному) интересующему языку, и оно уже содержит грамматические или железнодорожные диаграммы, и это то, чем оно является.

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

В основном это удалениево многих случаях пот, и обычно его не бывает.Поэтому обычный подход - достать свой грамматический нож и взять его с собой.

Я не думаю, что удаление левой рекурсии меняет то, как ANTLR получает деревья.Сначала нужно выполнить левую рекурсию, иначе ANTLR (какой бы генератор LL-анализатора вы не использовали) просто не примет вашу грамматику.

Некоторые из нас не хотят, чтобы генератор синтаксического анализатора помещал какие-либосерьезные ограничения на то, что мы можем написать для контекстно-свободной грамматики.В этом случае вы хотите использовать что-то вроде генератора синтаксических анализаторов GLR, который легко обрабатывает левую или правую рекурсию.Необоснованные люди могут даже настаивать на автоматическом создании AST без каких-либо усилий со стороны автора грамматики.Информацию об инструменте, который может выполнять обе задачи, см. Инструментарий реинжиниринга программного обеспечения DMS .