Vyaakaran — это браузерный инструмент для визуализации грамматик в виде автоматов, таблиц синтаксического анализа и других понятий, встречающихся в теории формального языка. Я начал работать над Vyaakaran, чтобы лучше изучить компиляторы и написание языков, а также создать полезный проект, чтобы другие могли изучить то же самое.
В этой статье я расскажу, как работает ядро Вьяакарана. Я считаю это одной из лучших областей информатики, и к концу этой статьи я надеюсь, что вы думаете так же 🙂
Понимание слоев в Вьяакаране
Ядро Vyaakaran делает много вещей для преобразования вашей грамматики в соответствующие таблицы автоматов и синтаксического анализа. Весь процесс разбит на кучу слоев, отвечающих за выполнение конкретной операции.
- Lexer — разбивает входную грамматику на набор отдельных токенов.
- Синтаксический анализатор — использует маркеры от Lexer для проверки синтаксиса входной грамматики и создает дерево синтаксического анализа на основе входной грамматики.
- Анализатор — анализирует дерево синтаксического анализа, чтобы найти и выполнить различные проверки грамматики. Это может включать поиск недостижимых или неопределенных символов и т. д.
- Преобразователи — специальные алгоритмы, преобразующие дерево синтаксического анализа в требуемые выходные данные (например, конечные автоматы, таблицы синтаксического анализа, регулярные выражения и т. д.).
Это похоже на компоненты, изучаемые в курсах Дизайн компилятора CS. И да, это так! Помните, я упоминал, что изучал компиляторы, когда начал работать над Vyaakaran. Таким образом, большая часть архитектуры более высокого уровня похожа на ту, что преподается в моем курсе. Давайте подробно разберем каждый из вышеперечисленных слоев в следующих разделах.
1. Лексер
Работа Лексера состоит в том, чтобы просто разбить входную программу на набор небольших неделимых наборов символов. Я думаю, что это лучше всего поясняется следующей диаграммой.
Ввод в этом изображении был одной строкой грамматического производства. Лексер принимает ввод и разбивает его на массив отдельных токенов. Эти токены не всегда являются одним символом. Маркером также может быть группа символов. ->
состоит из двух символов, но является одним токеном.