Простой парсер

Автор: Камнев Георгий Павлович

Парсер — это сленговое слово от английского parse (сущ. анализ, разбор, производить структурный анализ). Так называют программы/библиотеки которые производят соответствующие действие, применяются во многих областях ИТ, в той или иной форме.


Эта статья предлагает рассмотрение общих принципов работы компиляторов и как они пишутся. Будет рассмотрен простой синтаксический анализ методом рекурсивного спуска — калькулятор математических выражений.


Основной упор хотелось бы сделать на примеры реализации кода, но без теории это сделать сложно. Примеры будут приводится на JAVA и код соответственно прилогается.

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

Задача перед синтаксическим анализатором (парсингом) — создание из последовательности символов дерева операций конечного языка:
 

В дальнейшем это дерево интерпретируется тем или иным способом.

Общая схема устройства

В большинстве случаев парсер состоит из двух основных механизмов: лексического и синтаксического анализатора.

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

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

---

Исходный код http://gocha.org/webstart/parser/01/lang-build.zip
PDF версия: http://gocha.org/webstart/parser/01/parser.pdf