Я пытаюсь научиться делать компилятор. Для этого я много читал о языке без контекста. Но есть некоторые вещи, которые я пока не могу получить самостоятельно.
Поскольку это мой первый компилятор, есть некоторые приемы, о которых я не знаю. Мои вопросы задаются с целью создания генератора парсера, а не компилятора и лексера. Некоторые вопросы могут быть очевидны ..
Среди моих операций чтения: Разбор снизу вверх , Разбор сверху вниз , Формальные грамматики . Показанная картинка взята из: Разный анализ . Все из класса Stanford CS143.
Вот пункты:
0) Как (неоднозначный / однозначный) и (леворекурсивный / праворекурсивный) влияют на потребность в том или ином алгоритме? Существуют ли другие способы определения грамматики?
1) Неоднозначная грамматика - это такая, которая имеет несколько деревьев разбора. Но не должен ли выбор самого левого или самого правого вывода привести к единственности дерева разбора?
[РЕДАКТИРОВАТЬ: ответил здесь ]
2.1) Но все же, связана ли двусмысленность грамматики с k? Я имею в виду предоставление грамматики LR (2), является ли она неоднозначной для синтаксического анализатора LR (1) и не является неоднозначной для грамматики LR (2)?
[РЕДАКТИРОВАТЬ: Нет, грамматика LR (2) означает, что синтаксическому анализатору понадобится два токена, чтобы выбрать правильное правило для использования. С другой стороны, неоднозначная грамматика может привести к нескольким деревьям разбора. ]
2.2) Значит, парсер LR (*), если вы можете себе это представить, вообще не будет иметь двусмысленной грамматики и сможет затем анализировать весь набор языков без контекста?
[РЕДАКТИРОВАТЬ: Ответ Ира Бакстера, LR (*) является менее мощным, чем GLR, поскольку он не может обрабатывать несколько деревьев разбора. ]
3) В зависимости от предыдущих ответов последующее может быть противоречивым. Учитывая разбор LR, вызывают ли неоднозначные грамматики конфликт сдвиг-уменьшение? Может ли однозначная грамматика вызвать ее тоже? Точно так же, как насчет конфликтов уменьшить-уменьшить?
[РЕДАКТИРОВАТЬ: это так, неоднозначные грамматики приводит к конфликтам сдвиг-уменьшение и уменьшение-уменьшение С другой стороны, если нет конфликтов, грамматика однозначна. ]
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) Наконец, поскольку многие разные грамматики могут определять один и тот же язык, как выбрать грамматику и связанный с ней синтаксический анализатор? Является ли результирующее дерево разбора важным? Какое влияние оказывает дерево разбора?
Я спрашиваю много, и я действительно не ожидаю полного ответа, в любом случае любая помощь будет очень признательна.
Спасибо за чтение!