Сущность синтаксического анализа
Сущность синтаксического анализа программы достаточно сложна, чтобы излагать ее "на пальцах". Даже такое средство представления как конечный автомат является недостаточно "мощным" для этого. В первом приближении это можно доказать, ссылаясь на вложенный характер конструкций языка. Элементы лексики представляют собой линейные последовательности, анализ которых и производится конечными автоматами. Синтаксис же предложения не является линейной структурой. Если определения элементов синтаксиса языка (выражения, операторы) являются теми единицами, из которых строится программа, то взаимоотношение этих единиц в конкретной программе может быть представлено в виде дерева. А с деревом тесно связаны такие понятия, как рекурсия и стек. Таким образом, интуитивно становится ясным, что для определения и анализа синтаксиса языка необходим математический аппарат, который допускает рекурсивное определение и порождение своих элементов, а при их анализе используются деревья, рекурсивные функции и работа со стеком.
Формальные грамматики и языки
Формальные грамматики являются математическим аппаратом, который исследует свойства цепочек символов, порожденных заданным набором правил. Определение формальной грамматики (ФГ) включает в себя:
множество терминальных символов T;
множество нетерминальных символов N;
начальный нетерминальный символ Z из множества N;
множество порождающих правил вида A ::= B, где B - цепочка из любых символов грамматики (N U T), A-цепочка, содержащая хотя бы один нетерминальный символ.
В дальнейшем мы будем представлять правила грамматики в таком виде:
.
E ::= E + T
E ::= E - T или E ::= E + T | E – T
Где символ ::= разделяет правую и левую части. В дальнейшем любой символ, который используется для описания самих средств построения предложений языка (правил и т.д.), но не входит в множество символов, из которых они строятся , будем называть МЕТАСИМВОЛОМ. Если два и более правила имеют одинаковую левую часть, то они могут быть объединены, причем их правые части разделяются вертикальной чертой - тоже метасимволом.
ПРЕДЛОЖЕНИЕ ЯЗЫКА -- цепочка терминальных символов.
НЕПОСРЕДСТВЕННЫЙ ВЫВОД -- замена в некоторой цепочки последовательности символов из правой части на последовательность символов из левой, то есть xAy -> xBy.
ПОСЛЕДОВАТЕЛЬНОСТЬ НЕПОСРЕДСТВЕННЫХ ВЫВОДОВ основана на том факте, что непосредственный вывод можно применять несколько раз, в том числе и повторно для одних и тех же правил (рекурсивно). Если для цепочки aaa существует такая последовательность непосредственных выводов, которая приводит к цепочке bbb, то говорят, что цепочка bbb выводится из aaa.
ПРАВИЛЬНОЕ ПРЕДЛОЖЕНИЕ -- цепочка терминальных символов, выводимая из начального нетерминального символа грамматики Z.
РЕКУРСИВНОЕ ПРАВИЛО -- правило, в правой части которого содержится его левая часть, то есть типа A::=xAy.
Два правила образуют НЕПРЯМУЮ РЕКУРСИЮ, если они имеют вид:
B ::= xCy, C ::= sBr.
Сразу же поясним смысл терминов и определений. Цепочка - это последовательность символов, возможно и пустая. Цепочка терминальных символов (предложение) языка обладает тем свойством, что из нее уже не может быть выведена никакая другая цепочка. Это происходит потому, что в левой части любого правила должен быть хотя бы один нетерминальный символ. Отсюда и происходит название ТЕРМИНАЛЬНЫЙ, то есть конечный символ. Таким образом, формальная грамматика своим набором правил определяет правила преобразования цепочек одного вида в другие. Естественно, если ограничить возможные варианты терминальных цепочек только выводимыми из начального символа грамматики Z, то мы получим множество правильных предложений. Последовательность применений правил грамматики к начальному символу образуют древовидную структуру, корнем которой является начальный символ Z, а концевыми вершинами являются терминальные символы, образующие при обходе дерева слева направо правильное предложение.
Грамматики по ограничениям, накладываемым на правила, образуют несколько классов:
класс 2 - КОНТЕКСТНО-СВОБОДНЫЕ грамматики, имеющие в левой части любого правила единственный нетерминал.
Такие грамматики являются основой построения синтаксиса любого языка. Сам нетерминал в левой части обозначает не что иное, как синтаксическую конструкцию, причем возможность ее замены на левую часть - описание этой конструкции, возможно в любой цепочке, где этот нетерминал встречается, то есть в любом контексте. В качестве примера приведем известную грамматику четырех арифметических действий. В дальнейшем по умолчанию все нетерминалы будут обозначаться большими латинскими буквами, все терминалы - знаками и маленькими латинскими буквами.
.
N = {Z,E,R,F}, T = {+,-,/,*,(,),f}
Z ::= E
E ::= E + R | E - R | R
R ::= R * F | R / F | F
F ::= f | (E)
класс 1 - контекстно-зависимые грамматики, ограничение - длина цепочки в правой части правила не превышает длину цепочки в правой. Термин КОНТЕКСТНО-ЗАВИСИМАЯ характеризует частный случай правил в такой грамматике, имеющих вид xAy ::=xa...ay, когда замена нетерминала A на цепочку a...a возможна на только в окружении некоторых символов, то есть в контексте. Этот вид грамматик является достаточно сложным и обычно в синтаксическом анализе не используется.
класс 3 - регулярные грамматики, правила в которых могут иметь в правой части не более одного терминального. а при его наличии - и не более одного нетерминального символов, то есть
.
X ::= aY
X ::= Ya
X ::= a
X ::= e(пустая цепочка)
такие грамматики эквивалентны по своим свойствам конечным автоматам и используются для описания лексики при построении лексических анализаторов.
Теперь следует разобраться, в каких взаимоотношениях находятся формальные грамматики и синтаксический анализ. Синтаксис любого языка программирования определяется контекстно-свободной формальной грамматикой - системой терминальных и нетерминальных символов и множеством правил. Анализируемая программа представляется в такой грамматике предложением языка. Задача синтаксического анализа - определить, является ли это предложение правильным и построить для него последовательность непосредственных выводов из начального символа Z, то есть дерево синтаксического разбора.
Рассмотрим в качестве примера ту же самую грамматику и цепочку в ней вида i*(i+i)
.
Z
|
E
|
T
-----
T * F
| -------------
F ( E )
| -------
i E + T
| |
T F
| |
F i
|
i
Заметим, что последовательность непосредственных выводов при построении дерева однозначно соответствует вложенности данных синтаксических конструкций и обычно соответствует порядку их определения или выполнения (последнее качается уже семантического разбора и генерации кода или интерпретации).
