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


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


 

ПРЕДЛОЖЕНИЕ ЯЗЫКА -- цепочка терминальных символов.

 

НЕПОСРЕДСТВЕННЫЙ ВЫВОД -- замена в некоторой цепочки последовательности символов из правой части на последовательность символов из левой, то есть xAy -> xBy.

ПОСЛЕДОВАТЕЛЬНОСТЬ НЕПОСРЕДСТВЕННЫХ ВЫВОДОВ основана на том факте, что непосредственный вывод можно применять несколько раз, в том числе и повторно для одних и тех же правил (рекурсивно). Если для цепочки aaa существует такая последовательность непосредственных выводов, которая приводит к цепочке bbb, то говорят, что цепочка bbb выводится из aaa.

 

ПРАВИЛЬНОЕ ПРЕДЛОЖЕНИЕ -- цепочка терминальных символов, выводимая из начального нетерминального символа грамматики Z.

 

РЕКУРСИВНОЕ ПРАВИЛО -- правило, в правой части которого содержится его левая часть, то есть типа  A::=xAy.

Два правила образуют НЕПРЯМУЮ РЕКУРСИЮ, если они имеют вид:

 

B ::= xCy,      C ::= sBr.

 

Сразу же поясним смысл терминов и определений. Цепочка - это последовательность символов, возможно и пустая. Цепочка терминальных символов (предложение) языка обладает тем свойством, что из нее уже не может быть выведена никакая другая цепочка. Это происходит потому, что в левой части любого правила должен быть хотя бы один нетерминальный символ. Отсюда и происходит название ТЕРМИНАЛЬНЫЙ, то есть конечный символ. Таким образом, формальная грамматика своим набором правил определяет правила преобразования цепочек одного вида в другие. Естественно, если ограничить возможные варианты терминальных цепочек только выводимыми из начального символа грамматики Z,  то мы получим множество правильных предложений. Последовательность применений правил грамматики к начальному символу образуют  древовидную структуру, корнем которой является начальный символ  Z, а концевыми вершинами являются терминальные символы, образующие  при обходе дерева слева направо правильное предложение.

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

класс 2 - КОНТЕКСТНО-СВОБОДНЫЕ грамматики, имеющие в левой части любого правила единственный нетерминал.


Начало  Назад  Вперед



Книжный магазин