Курсовая работа: Разработка и отладка формального языка

Vт – словарь терминальных символов грамматики;

Vn – словарь нетерминальных символов грамматики;

P – множество правил грамматики:

P = {(A, )|A-> & AVn & V*}

S – начальный символ грамматики (SVт);

V* – множество строк, составленных из символов полного словаря

V (V=Vт  Vn);

V* = {|= п  ( xV) ( QV*)=Qx}

п – пустая цепочка.

Определение 2. Цепочка o порождает нетривиальным образом цепочку o (записывают o=>+W), если существует последовательность непосредственных выводов:

o =>1 =>… n, n>=1.

Определение 3. Цепочка  порождает цепочку Q (записывают =>*Q), если =>+Q, или =Q.

Определение 4. Цепочка называется сентенциальной формой грамматики G, если она выводится из начального символа грамматики, т.е. если S->*.

Определение 5 . Предложение языка – это сентенциальная форма, состоящая только из терминальных символов.

Определение 6 . Язык L(G) – это множество предложений

L(G) = {| S->+  Vт*}.

Определение 7 . Символы A, B контекстно-свободной грамматики связаны отношением FIRST, если выполняется условие

A->B,

где AVn, BV, V*.

Определение 8 . Символы A и B грамматики связаны отношением.=^. , если в грамматике имеется правило вида:

WAВ.

Определение 9 . Отношение >^. Между символами A и B грамматики находится из правила:

(>^. )=(LAST⁺ )^T (^. =^. ).

Определение 10 . Отношение <^. Между символами A и B грамматики находится из правила:

(<^. )=(^. =^. ) (FIRST⁺ ).

Разработка грамматики по неформальному описанию языка

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

Чтобы проверить ее корректность составим контрольный пример:

Sub D11 ()