предисловие

После того, как лексический анализ завершен ранее, получен поток маркеров, затем следующим шагом является реализация синтаксического анализатора для ввода потока маркеров для получения абстрактного синтаксического дерева.(Абстрактное синтаксическое дерево, AST). Однако при заполнении этого парсера, в отличие от лексического анализатора, вы можете просто сделать это вручную, и вам все равно потребуются некоторые предварительные знания.

Эти предварительные условия были упомянуты в предыдущих сообщениях в блоге.

Список предыдущих сообщений в блоге

Полный код проекта находится по адресуC2j-Compiler

Что такое синтаксический анализ?

Если представить лексический анализ как объединение слов и вывод потока слов, то грамматический анализ можно рассматривать как процесс проверки правильности грамматики этих слов. В лексическом анализе для проверки слов используются регулярные или ручные сравнения, а в грамматическом анализе используются контекстно-свободные грамматики.(контекстно-свободная грамматика, CFG).

Говорят, что формальная грамматика G = (N, Σ, P, S) имеет следующие продукционные правила: V -> w. где V∈N, w∈(N∪Σ). Контекстно-свободные грамматики называются «контекстно-свободными», потому что символ V всегда можно свободно заменить строкой w, независимо от контекста, в котором появляется символ V. Формальный язык является контекстно-свободным, если он порождается контекстно-свободной грамматикой*.

парадигма БНФ

Нормальная форма Бэкуса (BNF) — это язык для представления контекстно-свободных грамматик.

См. пример:

S –> AB
A –> aA | ε
B –> b | bB

При этом SAB называетсянетерминальный, что означает, что новые символы могут быть сгенерированы дедукцией, и эти нетерминальные символы также были определены в классе Token ранее; a b ε называетсятерминатор, что указывает на то, что он больше не может генерировать новые символы путем вывода, а ε означает пустой;

Каждая строка выше представляет собой продукционное правило, также называемое выводом, которое представляет метод передачи нетерминальных символов;

S — начальный символ.

Строка символов, содержащая только терминаторы, называетсяпредложение (предложение).

Например, по этим трем произведениям можно сделать вывод, что bbb соответствует грамматическим правилам.

Несколько методов грамматического анализа

Как упоминалось ранее, он в основном делится на верхний и нижний.

Прежде чем записывать в изучение немного этого несколькими способами, здесь не сказать

Рекурсивный спуск и разбор LL(1)

восходящий анализ

Давайте немного поговорим о методе, используемом в этом синтаксическом анализе, LALR(1), который также является алгоритмом восходящего анализа.

восходящий анализ

Процесс синтаксического анализа снизу вверх соответствует процессу построения книги синтаксического анализа для входной строки, он начинается с листового узла и постепенно достигает корневого узла посредством операций сдвига и сокращения.

Синтаксический анализ снизу вверх требует стека для хранения проанализированных символов, например, для следующей грамматики:

0.	statement -> expr
1.	expr -> expr + factor
2.	         | factor
3.	factor ->  ( expr )
4.	         | NUM

2 + 1 решить

stack	input
null	1 + 2
NUM	+ 2	Начните читать персонаж и поместите соответствующий токен в стек разборки, называемый операцией Shift
factor	+ 2	Согласно синтаксису, фактор -> ЧИСЛО, извлечь ЧИСЛО из стека и поместить фактор в стек.Эта операция называется уменьшением
expr	+ 2	Операция редукции здесь продолжается, но, поскольку вывод грамматики имеет две продукции, необходимо ожидать совпадения, чтобы определить, следует ли сдвигать или редуцировать, что является ЛА разбора грамматики.
expr +	2	сменная работа
expr + NUM	null	сменная работа
expr + factor	null	уменьшить в соответствии с производством фатора
expr	null	Уменьшить работу
statement	null	уменьшить операцию

В это время происходит сокращение до начального символа, а входная строка также пуста, что означает, что анализ грамматики прошел успешно.

Таким образом, ключом к реализации восходящего синтаксического анализа является определение того, следует ли выполнять операцию сдвига или сокращения в стеке.

• Выполните сопоставление методом грубой силы, найдите в стеке символы и все синтаксические включения, соответствующие x.
• Создайте конечный автомат, чтобы решить, следует ли выполнять операцию сокращения на основе состояния после того, как стек помещен в стек или извлечен из него.

Таким образом, естественной следующей задачей является создание конечного автомата, который может давать команды синтаксическому анализатору.

резюме

На самом деле, так называемые предварительные знания - понимать разборки, и, вероятно, как это сделать.

Синтаксический анализ — это процесс проверки того, является ли входной поток Token грамматическим, и алгоритм синтаксического анализа для завершения этого шага — восходящий, то есть процесс вывода из листовых узлов к вершине дерева.