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

В этой статье я расскажу, как работает ядро ​​Вьяакарана. Я считаю это одной из лучших областей информатики, и к концу этой статьи я надеюсь, что вы думаете так же 🙂

Понимание слоев в Вьяакаране

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

  • Lexer — разбивает входную грамматику на набор отдельных токенов.
  • Синтаксический анализатор — использует маркеры от Lexer для проверки синтаксиса входной грамматики и создает дерево синтаксического анализа на основе входной грамматики.
  • Анализатор — анализирует дерево синтаксического анализа, чтобы найти и выполнить различные проверки грамматики. Это может включать поиск недостижимых или неопределенных символов и т. д.
  • Преобразователи — специальные алгоритмы, преобразующие дерево синтаксического анализа в требуемые выходные данные (например, конечные автоматы, таблицы синтаксического анализа, регулярные выражения и т. д.).

Это похоже на компоненты, изучаемые в курсах Дизайн компилятора CS. И да, это так! Помните, я упоминал, что изучал компиляторы, когда начал работать над Vyaakaran. Таким образом, большая часть архитектуры более высокого уровня похожа на ту, что преподается в моем курсе. Давайте подробно разберем каждый из вышеперечисленных слоев в следующих разделах.

1. Лексер

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

Ввод в этом изображении был одной строкой грамматического производства. Лексер принимает ввод и разбивает его на массив отдельных токенов. Эти токены не всегда являются одним символом. Маркером также может быть группа символов. -> состоит из двух символов, но является одним токеном.