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