Разработка компилятора. Синтаксический анализатор

В первой версии нашего языка s4g синтаксический анализ не был полностью отдельным процессом, и был совмещен с лексическим анализом. Разбор осуществлялся без каких либо четких правил, он работал, но внести какие-то изменения или дополнения без риска сломать все было несколько проблематично. Понятно, что так продолжаться долго не может, и к версии 0.9.2 синтаксический анализатор был полностью переработан.

Вспомнить основные составляющие языка можно в этой статье

Синтаксический анализатор (парсер — parser) — процесс сопоставления последовательности лексем с грамматикой языка. На вход идут последовательно лексемы, на выходе — абстрактное синтаксическое дерево.

Рассматривать мы будем контекстно-свободные грамматики.
Контекстно-свободная грамматика (КС-грамматикабесконтекстная грамматика) — частный случай формальной грамматики, у которой левые части всех продукций являются одиночными нетерминалами (объектами, обозначающими какую-либо сущность языка (например: формула, арифметическое выражение, команда) и не имеющими конкретного символьного значения). Смысл термина «контекстно-свободная» заключается в том, что есть возможность применить продукцию к нетерминалу, причём независимо от контекста этого нетерминала.
Подробнее в википедии

Пример части грамматики из нашего языка s4g:

1 _PROGRAM = {STMT}
2 STMT = LVAL ASSIGN RVAL ';'
3 LVAL = word_user
4 RVAL = word_user | CONST
5 ASSIGN = '=' | '+='
6 CONST = int | uint | string | float

Здесь, слова в нижнем регистре, а так же в кавычках — являются терминалами — лексемами, которые парсер считывает из лексера.
Терминал — лексема, которую парсер считывает из лексера.
Слова в верхнем регистре — являются нетерминалами.
Нетерминал — символ грамматики, который выводится из других нетерминалов и терминалов по правилам грамматики. Каждый нетерминал должен однозначно выводится в цепочку терминалов.
Стартовый символ — символ грамматики, с которого начинается определение, при этом он не может встречаться в других правилах
_PROGRAM — стартовый символ для нашей грамматики.

Рассмотрим несколько подклассов КС-грамматик:

LL-грамматика — одна из самых простых грамматик для парсинга, однако не все языки можно описать с помощью LL грамматики. Первая буква L-left означает, что поток лексем считывается слева-направо. Вторая L-left говорит, что используется левосторонний вывод и синтаксическое дерево строится от корня к листьям.
При парсинге LL грамматик, парсер должен, начиная со стартового символа, производить раскрытие. Проще всего делать это рекурсивно: завести по функции на каждый нетерминал, и при пасинге вызывать функции тех символов, через которые он выводится. Такой парсер называется нисходящим.
Для примера выше — функция ParseProgram будет вызывать в цикле функцию ParseStmt, которая в свою очередь вызовет функции ParseLval, ParseAssign, ParseRval.
К сожалению, не все языки можно описать грамматикой этого класса, для s4g мне это сделать не удалось, и пришлось использовать LR-грамматику.

LR-грамматика — именно с помощью этой грамматики описан s4g. Первая буква L-left означает, что поток лексем считывается слева-направо. Вторая R-right говорит, что используется правосторонний вывод и синтаксическое дерево строится от листьев к корню. Для разбора используется восходящий парсер, использует алгоритм «сдвиг-свертка».
Алгоритм разбора является нерекурсивным и использует стек. При этом, на каждом шаге проверяется, что нужно сделать дальше — свернуть цепочку в нетерминал, или сделать очередной сдвиг.

сдвиг — вносит очередную лексему из парсера в стек
свертка — заменяет один или несколько символов с вершины стека на соответствующий нетерминал, следуя правилам грамматики

Пример работы парсера для следующего набора лексем: a = 7;

стек необработанные лексемы операция комментарий
‘a’ = 7; сдвиг Стек пуст,
LVAL = 7; свертка совпадает с правилом 3
LVAL ‘=’ 7; сдвиг совпадений нет
LVAL ASSIGN 7; свертка правило 5
LVAL ASSIGN ‘7’ ; сдвиг совпадений нет
LVAL ASSIGN CONST ; свертка правило 6
LVAL ASSIGN RVAL ; свертка правило 4
LVAL ASSIGN RVAL ‘;’ сдвиг совпадений нет
STMT свертка правило 2
_PROGRAM свертка правило 1, конец

Разбор прекращается, когда в стеке остается стартовый символ. Почему мы ожидаем стартовый символ, когда казалось бы, что с него должно все начинаться? Потому что этот алгоритм является восходящим парсером — строит дерево от листьев к корню, и появление стартового символа как раз означает, что мы дошли до корня. Если поток лексем кончился, но стартовый символ не появился — значит входной поток не соответствует грамматике — следовательно ошибочен.

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

Поделиться:

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

*

*

code