А как насчет этих грамматик и минимального синтаксического анализатора для их распознавания?

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

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

Среди моих чтений: Анализ снизу вверх , Анализ сверху вниз , Формальные грамматики . Показанное изображение взято из: Различный синтаксический анализ . Все идет из Стэнфордского класса CS143.

Вот пункты:

0) Как (неоднозначность / однозначность) и (леворекурсивная / праворекурсивная) влияют на потребности в том или ином алгоритме? Есть ли другие способы уточнения грамматики?

1) Неоднозначная грамматика - это грамматика, имеющая несколько деревьев разбора. Но не должен ли выбор крайнего левого или крайнего правого вывода вести к единственности дерева синтаксического анализа?

[РЕДАКТИРОВАТЬ: ответили здесь ]

2.1) Но все же, связана ли неоднозначность грамматики с k? Я имею в виду грамматику LR (2), неоднозначно ли она для парсера LR (1) и не неоднозначна для LR (2)?

[EDIT: нет, грамматика LR (2) означает, что синтаксическому анализатору потребуется два токена просмотра вперед, чтобы выбрать правильное правило для использования. С другой стороны, неоднозначная грамматика может привести к нескольким деревьям синтаксического анализа. ]

2.2) Итак, синтаксический анализатор LR (*), насколько вы можете его себе представить, не будет иметь двусмысленной грамматики вообще и сможет затем проанализировать весь набор контекстно-свободных языков?

[РЕДАКТИРОВАТЬ: Ответил Ира Бакстер, LR (*) менее мощный, чем GLR, поскольку он не может обрабатывать несколько деревьев синтаксического анализа. ]

3) В зависимости от предыдущих ответов нижеследующее может быть противоречивым. Принимая во внимание синтаксический анализ LR, вызывает ли неоднозначная грамматика конфликт сдвиг-уменьшение? Может ли сработать и однозначная грамматика? Таким же образом, как насчет конфликтов сокращения-уменьшения?

[EDIT: вот и все, неоднозначная грамматика приводит к конфликтам сдвиг-уменьшение и уменьшение-уменьшение. Напротив, если нет конфликтов, грамматика однозначна. ]

4) Способность анализировать леворекурсивную грамматику является преимуществом парсера LR (k) перед LL (k), это единственное различие между ними?

[РЕДАКТИРОВАТЬ: да. ]

5) Давать G1:

G1 :
S -> S + S
S -> S - S
S -> a

5.1) G1 является одновременно леворекурсивным, праворекурсивным и неоднозначным, я прав? Это грамматика LR (2)? Можно было бы сделать однозначным:

G2 :
S -> S + a
S -> S - a
S -> a

5.2) G2 все еще неоднозначен? Нужны ли синтаксическому анализатору для G2 два просмотра вперед? Путем факторизации мы получаем:

G3 :
S -> S V
V -> + a
V -> - a
S -> a

5.3) Теперь, нужен ли синтаксическому анализатору для G3 только один просмотр вперед? Каковы составляющие этих преобразований? Требуется ли LR (1) минимальный синтаксический анализатор?

5.4) G1 является леворекурсивным, чтобы проанализировать его с помощью LL-синтаксического анализатора, необходимо преобразовать его в праворекурсивную грамматику:

G4 :
S -> a + S
S -> a - S
S -> a

затем

G5 :
S -> a V
V -> - V
V -> + V
V -> a

5.5) Нужен ли G4 хотя бы парсер LL (2)? Только G5 может быть проанализирован парсером LL (1), G1-G5 действительно определяют тот же язык, и этот язык (a (+/- a) ^ n). Это правда?

5.6) Для каждой грамматики от G1 до G5, какому минимальному набору она принадлежит?

6) Наконец,поскольку многие разные грамматики могут определять один и тот же язык, как выбрать грамматику и соответствующий синтаксический анализатор? Имеет ли значение получившееся дерево разбора? Каково влияние дерева синтаксического анализа?

Я много спрашиваю и не жду полного ответа, в любом случае любая помощь будет очень признательна.

Спасибо за чтение!