существует ли генератор синтаксического анализатора, способный генерировать синтаксический анализатор, который может анализировать это: S → 'x' S 'x' |'Икс'

Question

Некоторое время назад я заинтригован тем фактом, что ANTLR не способен анализировать следующее контекстно-свободное грамматическое правило: S → 'x' S 'x' |'x'.

Мне это не казалось сложным.

Насколько я знаю, ANTLR - самый мощный из доступных анализаторов LL.Существуют ли другие генераторы синтаксических анализаторов (LR или другие), способные генерировать для этого синтаксический анализатор?

gr,

Coen

Answer 1

Я не думаю, что ваша грамматика LL (n) или LALR (n) или LR (n) для любого n. Доказательство: исправить любое n. Ваш входной поток начинается с n x символов, за которыми следует еще один. На данный момент, без дальнейшего просмотра, вам нужно идти вверх или вниз?

Поскольку стандартные генераторы синтаксического анализатора работают только с языками в одном из этих классов (и многие только для небольших значений n), неудивительно, что вы не найдете тот, который обрабатывает ваш ввод. Возможно, вы захотите пересмотреть, действительно ли ваша грамматика должна выглядеть так, как она есть; для приведенного примера, который вы привели, вы также можете иметь S → 'x' 'x' S | «х», например.

Answer 2

В Antlr вам нужно добавить синтаксический предикат для устранения неоднозначности, например:

grammar fred;

sentence : ( 'x' 'x' 'x' ) => 'x' sentence 'x'
         |                    'x'
         ;

Я думаю, что для этого не нужно более 1 дополнительного токена упреждения.Семантический предикат говорит: «Если вы видите« x », за которым следует другой« x », попробуйте первый вариант».

Antlr 3.3 / Antlrworks 1.4.2 доволен им:

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

grammar fred;

start    : sentence
         ;

sentence : 'x'  'x'('x' 'x')*  'x'
         |      'x'
         ;

Это, я полагаю, даст вам такое же дерево разбора (или закрыть) в качестве исходной грамматики.