Синтаксический анализ для самых маленьких. Часть 1

Здравствуй, дорогой друг!

Если перед тобой, как и передо мной, когда-либо стояла задача написания своего синтаксического анализатора - то нам с тобой по пути!

Не будем глубоко вдаваться в теорию, но интересующимся - могу посоветовать книгу, которую можно без зазрения совести назвать классикой: Книга дракона.

А тем, кто хочет перейти к делу прямо сейчас - прошу за мной!

Постановка задачи

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

• является однострочным (каждая строка - законченное выражение, перенос строк не поддерживается);
• поддерживает операции сложения, умножения, деления и вычитания;
• поддерживает приоритет операций;
• поддерживает скобки;

Немного теории

Вычисление любого выражения формального языка (а наш язык именно формальный) проходит несколько фаз. Чаще всего это следующие фазы:

• Лексический анализ;
• Синтаксический анализ;
• Семантический анализ;

На входе мы имеем последовательность символов. Лексический анализ превращает поток символов в поток лексем (значащих слов языка). Синтаксический анализ превращает поток лексем в абстрактное синтаксическое дерево, которое должно соответствовать грамматике языка - формально описанной структуре языка. Семантический анализ проверяет выражение на соответствие ограничениям, присущим данному языку, например запрет на объявление одной и той же переменной в одной области видимости и т.п.

К счастью, наш язык будет очень простой, поэтому составим какой-то план и будем ему следовать=)

Какой-то план

1. Описать грамматику языка;
2. Написать лексический анализатор;
3. Написать синтаксический анализатор;
4. Вычислить выражение, описанное абстрактным синтаксическим деревом;

Грамматика языка

Грамматика языка - это формальное описание структуры языка. Часто для описания грамматики языка используется так называемая форма Бэкуса-Наура или некое ее подобие. 

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

Итак, начнем. Грамматика нашего языка будет выглядеть так:

1. expression =  multExpression (('+'|'-') multExpression)*
2. multExpression = atom (('*'|'/') atom)*
3. atom = NUMBER | '(' expression ')'

Разберем подробнее описанную грамматику. Любое выражение нашего калькулятора представляет собой expression. Сам expression представляет собой один или более выражений multExpression, разделенных знаками '+ или '-'.
multExpression в свою очередь представляет собой один или более выражений atom, разделенных знаками '*' или '/'.
И наконец, atom - это или число - NUMBER, или expression в круглых скобках.

Терминалами в данной грамматике являются:

1. NUMBER - число с плавающей точкой;
2. '(' - открывающая круглая скобка;
3. ')' - закрывающая круглая скобка;
4. '+' - знак сложения;
5. '-' - знак вычитания;
6. '*'- знак умножения;
7. '/' - знак деления;

Введем в рассмотрение понятие токена. Токеном будем называть определенный класс лексем, объединенных общими признаками. В нашем случае список токенов такой:

1. NUMBER - дробное число;
2. BRACKET - '(' или ')';
3. OPERATOR - '+', '-', '*' или '/';

На примере реального математического выражения, рассмотрим, как будет происходить синтаксический анализ.
Допустим есть выражение: 12 - (1+23) / 56;

Шаг 1: лексический анализ

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

1. NUMBER ('12')
2. OPERATOR ('-')
3. BRACKET('(')
4. NUMBER ('1')
5. OPERATOR ('+')
6. NUMBER ('23')
7. BRACKET (')')
8. OPERATOR ('/')
9. NUMBER ('56')
10. EOF

EOF - специальная лексема, которая символизирует конец последовательности.
На этом фаза лексического анализа заканчивается.

Шаг 2: синтаксический анализ

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

В виде формул процесс синтаксического анализа можно изобразить так:

12 - (1+23) / 56 = expression1 = multExpression1 '-' multExpression2
multExpression1 = atom1 = NUMBER = '12'
multExpression2 = atom2 '/' atom3
atom2 = '(' expression2 ')'
expression2 = multExpression3 '+' multExpression4
multExpression3= atom4 = NUMBER = '1'
multExpression4= atom5 = NUMBER = '23'
atom3 = NUMBER = '56'

Абстрактное синтаксическое дерево, получившееся из нашего выражения, можно изобразить так:

Видно, что корнем дерева является нетерминал expression, а листьями - терминалы NUMBER, BRACKET и OPERATOR.

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

Шаг 3. Вычисление выражения

Теперь, когда все выражение разложено до элементарных составляющих - не составляет труда вычислить значение выражения.

Производя арифметические вычисления в порядке, обратном направлению синтаксического анализа - мы получим значение выражения expression1.

На этом хочу закончить статью. 

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

Ждите известий в следующей серии=)