Определение 7

Определение 6.

Определение 5.

Определение 4.

Входной грамматикой называется четверка

Gin = (V _N, V _T, P, S).

В качестве входной грамматики Гр языка Le выберем КС-грамматику.

Процесс нахождения синтаксической структуры предложения называется синтаксическим анализом.

Синтаксический анализ выполняется на основе МП-автоматов.

Регулярной последовательностью символов называется упорядоченное множество символов с заданными семантическими атрибутами слов Le.

Пример

Слово	САМОЛЕТ	ЛЕТИТ	ВОЗДУХ
Атрибут	О	Р11	О

Атрибутной грамматикой называется шестерка

G = (V _N, V _T, P, S, At, μ),

где V _N, V _T— алфавиты (словари) нетерминалов и терминалов соответственно, причём

V _N Ç V _T = Æ;

P — конечное множество правил, каждое из которых имеет вид

,

где aÎ V^*V _N V^*, bÎ V^*, V = V _N È V _T— объединённый алфавит (словарь) грамматики; S — начальный нетерминал; At – конечное множество атрибутов; μ - отображение из

Свойства синтаксических анализаторов

· Эффективность трансляции – время, необходимое для обработки входной цепочки;

· Простота определения того, что входная цепочка принадлежит данной грамматике;

· Прямо по определению грамматики механически строить эффективный анализатор.

Указанным свойствам удовлетворяет LR-грамматика.

В частности, ее разновидность SLR(1).

LR – грамматика

Определение 8.

КС – грамматика является LR – грамматикой, если для любых цепочек выполняются следующие условия:

если

и если

и = , =.

Здесь выражение определяет цепочку первых литер из цепочки .

Определение 9.

Выводимой цепочкой в грамматике Ге называется цепочка

Пример

САМОЛЕТ O ЛЕТИТ P₁₁ ВОЗДУХ O

Отображение μ реализуется процедурами семантического анализа предложения, которые используют атрибуты членов предложения и формируют формулы внутреннего языка Lв. Атрибутами являются: род, число, падеж, сорт, признак словосочетания, признак математического выражения. Терминалами являются: части речи, ключевые слова, математические знаки. Нетерминалы – члены предложения.

Пример

μ: САМОЛЕТ O ЛЕТИТ P₁₁ ВОЗДУХ O −> P11(САМОЛЕТ^O, ВОЗДУХ^O)

SLR(1) – грамматика языка системы <<Доуэль>>

<Предложение>:: = <Гр_подлежащего> <Гр_сказуемого> <Предлог> <Гр_дополнения> <M> |

Параметр - <Гр_подлежащего> |

ДАЙ ОБЛИК <Гр_дополнения>|

...

<Гр_подлежащего>:: = <ОпределениеИ> <Подлежащее> <Подлежащее_1>;

<Подлежащее>:: = СуществительноеИ <Слов_1>;

<Подлежащее_1>:: = <Знак_пункт> <Гр_подлежащего> | ε;

Всего - 42 правила.