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


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


Такие грамматики являются основой построения синтаксиса любого языка. Сам нетерминал в левой части обозначает не что иное, как синтаксическую конструкцию, причем возможность ее замены на левую часть - описание этой конструкции, возможно в любой цепочке, где этот нетерминал встречается, то есть в любом контексте. В качестве примера приведем известную грамматику четырех арифметических действий. В дальнейшем по умолчанию все нетерминалы будут обозначаться большими латинскими буквами, все терминалы - знаками и маленькими латинскими буквами.

      .          

      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, то есть дерево синтаксического разбора.


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



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