Формальные языки, грамматики и основы построения трансляторов. Кревский И.Г - 57 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

57
Для нисходящего грамматического разбора характерно, что цель
анализа известна с самого начала. Эта цель – распознать предложение, т.е.
последовательность символов, которая может порождаться из начального
символа. Применение порождающего правила, т.е. замена одного символа
последовательностью символов, соответствует расщеплению одной цели на
некоторое число подцелей, которые должны следовать в определенном
порядке. Поэтому
нисходящий метод можно называть также
целеориентированным грамматическим разбором
. При построении
программы грамматического разбора можно воспользоваться этим
очевидным соответствием между нетерминальными символами и целями:
для каждого нетерминального символа строится своя процедура
грамматического разбора. Цель каждой такой процедуры – распознавание
части предложения, которая может порождаться из соответствующего
нетерминального символа. Поскольку мы хотим построить граф,
представляющий всю программу грамматического разбора, то каждый
нетерминальный символ будет отражаться в подграф.
Правила построения синтаксического графа:
А1. Каждый нетерминальный символ A с соответствующим
множеством порождающих правил
A::=β
1
| β
2
|...| β
n
отображается в синтаксический граф A, структура которого
определяется правой частью порождающего правила в соответствии с А2-А6.
А2. Каждое появление терминального символа x в β
i
соответствует
оператору распознавания этого символа во входном предложении. На графе
это изображается ребром, помеченным символом x, заключенным в кружок
или овал:
x
А3. Каждому появлению нетерминального символа B в β
i
соответствует обращение к процедуре распознавания B. На графе это 
                                                                                           57
      Для нисходящего грамматического разбора характерно, что цель
анализа известна с самого начала. Эта цель – распознать предложение, т.е.
последовательность символов, которая может порождаться из начального
символа. Применение порождающего правила, т.е. замена одного символа
последовательностью символов, соответствует расщеплению одной цели на
некоторое число подцелей, которые должны следовать в определенном
порядке.      Поэтому            нисходящий     метод       можно       называть       также
целеориентированным                грамматическим       разбором.       При      построении
программы       грамматического          разбора    можно         воспользоваться      этим
очевидным соответствием между нетерминальными символами и целями:
для   каждого        нетерминального          символа     строится      своя      процедура
грамматического разбора. Цель каждой такой процедуры – распознавание
части предложения, которая может порождаться из соответствующего
нетерминального         символа.       Поскольку     мы      хотим      построить      граф,
представляющий всю программу грамматического разбора, то каждый
нетерминальный символ будет отражаться в подграф.
      Правила построения синтаксического графа:
      А1.    Каждый          нетерминальный        символ    A     с    соответствующим
множеством порождающих правил
      A::=β1 | β2 |...| βn
      отображается           в    синтаксический    граф     A,     структура      которого
определяется правой частью порождающего правила в соответствии с А2-А6.
      А2. Каждое появление терминального символа x в βi соответствует
оператору распознавания этого символа во входном предложении. На графе
это изображается ребром, помеченным символом x, заключенным в кружок
или овал:

                 x



      А3.    Каждому             появлению    нетерминального          символа     B   в   βi
соответствует обращение к процедуре распознавания B. На графе это

Страницы