Сущность синтаксического анализа

Сущность синтаксического анализа программы достаточно сложна, чтобы излагать ее "на пальцах". Даже такое средство представления как конечный автомат является недостаточно  "мощным" для этого. В первом приближении это можно доказать, ссылаясь на вложенный характер конструкций языка. Элементы лексики представляют собой линейные последовательности, анализ которых и производится конечными автоматами. Синтаксис же предложения не является линейной структурой. Если определения элементов синтаксиса языка (выражения, операторы) являются теми единицами, из которых строится программа, то взаимоотношение этих единиц в конкретной программе может быть представлено в виде дерева. А с деревом тесно связаны такие понятия, как рекурсия и стек. Таким образом, интуитивно становится ясным, что для определения и анализа синтаксиса языка необходим математический аппарат, который допускает рекурсивное определение и порождение своих элементов, а при их анализе используются деревья, рекурсивные функции и работа со стеком.

Формальные грамматики и языки

Формальные грамматики являются математическим аппаратом, который исследует свойства цепочек символов, порожденных заданным набором правил. Определение формальной грамматики (ФГ) включает в себя:

множество терминальных символов T;

множество нетерминальных символов N;

начальный нетерминальный символ Z из множества N;

множество порождающих правил вида A ::= B, где B - цепочка из любых символов грамматики (N U T), A-цепочка, содержащая хотя бы один нетерминальный символ.

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

.                

      E ::= E + T

      E ::= E - T       или      E ::= E + T | E – T

Где символ ::=  разделяет правую и левую части. В дальнейшем любой символ, который используется для описания самих средств построения предложений языка (правил и т.д.), но не входит в множество символов, из которых они строятся , будем называть МЕТАСИМВОЛОМ. Если два и более правила имеют одинаковую левую часть, то они могут быть объединены, причем их правые части разделяются вертикальной чертой - тоже метасимволом.