Рубрика «с нуля» - 2

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

Давайте подумаем, как обычно исполняются программы. В любой момент времени есть некоторые «точки контроля», которые указывает на то, какое выражение программа собирается выполнить дальше. Когда следующее выражение исполняется, оно модифицирует состояние программы, путем улучшения «точки контроля» и изменения значений переменных.
Читать полностью »

В предыдущей статье мы рассматривали сам язык IMP и основную структуру интерпретатора. Также, мы тщательно рассмотрели лексер. В этой статье мы будем писать небольшой парсер для нашего языка. Он будет извлекать AST (abstract syntax tree) из списка токенов, сгенерированных лексером. Библиотека комбинатора будет независимая, то есть с помощью нее можно будет написать парсер для любого языка.

Что такое комбинаторы парсеров?

Есть очень много способов написать парсер. Самым простым и быстрым способом сделать это являются комбинаторы.

Вы можете считать парсер функцией, которая принимает поток токенов. Если успешно, то парсер будет «съедать» немного токенов из потока. Функция вернет часть финального AST вместе с остальными токенами. Комбинатор — это функция, которая производит парсер, как его результат, обычно после приема одного или нескольких анализаторов (парсеров) в качестве входных данных, отсюда и название — «комбинатор». Вы можете использовать комбинаторы для создания законченного парсера для языка, как IMP, путем создания множества маленьких парсеров для каждой части языка.
Читать полностью »