КС грамматики традиционно служат основой для синтаксического анализа компиляции. Описание входного языка включают правила синтаксиса, в соответствии с которыми порождаются тексты

программ. Каждому синтаксическому правилу в КС-грамматике соответствует правило вывода грамматики. Обычно множество выводов КС-грамматики ограничивается, и рассматриваются не все ее возможные выводы,

а лишь так называемые левосторонние и правосторонние выводы.

 

ОПР) Вывод в КС-грамматике называют левосторонним (правосторонним), если правила вывода применяются к самому левому(правому) вхождению нетерминального символа каждой цепочки вывода.

G=<N,T,P,S>

N={E,R,F}, T={i,+,*,(,)} S=E

E::=E+R|R

R::=R*F|F

F::=(E)|i

Порождаемые арифметические выражения

Построим левосторонний вывод:

E->E+R->R+R->F+R->i+R->i+R*F->i+F*F->i+i*F->i+i*i

Построим правосторонний вывод:

E->E+R->E+R*F->E+R*i->E+F*i->E+i*i->R+i*i->F+i*i->i+i*i

Наиболее наглядным является представление в виде дерева вывода

ОПР) Под деревом синтаксического разбора будем понимать конечный ориентированный граф,обладающий след. свойствами.

 

1) у него имеется одна вершина, в которую не входит ни одна дуга. Эту вершину будем называть корнем дерева. Корень дерева соответсвует начальному символу грамматики.

2) в каждую из его остальных вершин входит лишь одна дуга. Вершины не имеющие выходящих из них дуг, называются заключительными вершинами дерева или листьями.

В КС-грамматике им соответствуют терминальные символы грамматики. Не заключительным вершинам дерева соответствуют нетерминальные символы грамматики.

3) Он не содержит контуров(замкнутых символов)

 

ОПР) Деревья вывода - это некоторые упорядоченые деревья, вершины которых помечены символами алфавита N U T. Корень дерева отвечает начальному символу S. Каждому символу слова w1,

на который заменяется начальный символ на первом шаге вывода ставится в соответствие вершина дерева, и к ней проводится дуга из корня.Полученные таким образом непосредственные потомки

 корня упорядочены согласно порядку их меток в слове w1. Для тех из полученных вершин,которые помечены символами из множества N, делается аналогичное построение.

 

ОПР) Кроной дерева вывода называется слово, записанное в вершине помеченных символами из алфавита Е.