LL (*) и PEG парсеры: в чем разница? - PullRequest
Новая
       2

LL (*) и PEG парсеры: в чем разница?

10 голосов
/ 11 января 2012

Мне интересно, если ANTLR v3, который представляет свой внутренний алгоритм синтаксического анализа как "LL (*)", полностью представляет PEG (грамматику синтаксического анализа выражения).

Есть ли разница?

Ответы [ 4 ]

4 голосов
/ 14 октября 2017

Статья ANTLR была неверна в отношении PEG.

LL (*) является подмножеством DCFG (детерминированной контекстной свободной грамматики), которая является подмножеством CFG (Context Free Grammar).

PEG может выражать контекстно-зависимые грамматики, такие как A{n}B{n}C{n}, в которых A и B и C все встречаются n раз.Вот определение: 

s := &(x C) A+ y / ε
x := A x B / A B
y := B y C / B C

Но нет способа определить такую ​​грамматику в CFG (доказательство включает в себя лемму насоса).Таким образом, PEG не является подмножеством CFG.Является ли ПЭГ надмножеством CFG?Я не знаю.

Два ключевых различия между LL (*) и PEG:

  1. LL (*) могут только смотреть на паттерн DFA, тогда как PEG может смотреть впередрекурсивный паттерн.Например, в PEG вы можете посмотреть вложенные парены, в то время как LL (*) не может.

  2. Оператор выбора / в PEG - это приоритетный выбор (или «притяжательный»), которыйозначает, что если у вас есть правило A / AB, оно никогда не достигнет правой стороны AB.В LL (*) для правила A | AB можно сопоставить AB.

Если у вас есть грамматика PEG без прогнозирования, или ваш шаблон прогнозирования может быть уменьшенв DFA, затем он может быть переведен в LL (*).Если нет, то это невозможно.

4 голосов
/ 11 января 2012

В ANTLR вы можете включить глобальное отслеживание всех правил производства в вашей грамматике, так что для k >= 1 вы можете анализировать почти так же, как PEG. Конечно, из-за возможного обратного отслеживания время выполнения синтаксического анализатора ухудшается. За счет (некоторой) памяти вы также можете включить запоминание, заставляя его вести себя как Packrat-парсер, способный анализировать ввод за линейное время.

Так что нет, нет большой разницы с ANTLR и PEG / Packrat (с включенными правильными опциями!).

3 голосов
/ 13 января 2012

ANTLR и PEG не совпадают. Это довольно теоретический вопрос, и я думаю, что вам лучше всего обратиться к этой статье, написанной Терренсом Парром, где он точно указывает на различия между ANTLR и PEG и некоторые преимущества ANTLR LL (*) Стратегия разбора. Я не хочу давать себе свободу перефразировать то, что он там написал, но вам лучше прочитать всю статью.

1 голос
/ 11 января 2012

В соответствии с перечисленными инструментами здесь ANTLR является полным представителем анализатора PEG:

ANTLR, хорошо зарекомендовавший себя генератор парсеров Terence Parr, поддерживает широкие возможности PEG и сочетает в себе синтаксический анализ пакетов с методами LL.

...