Курс Основы построения трансляторов

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


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

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

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

множество терминальных символов 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

 

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


Содержание раздела