Разбиение грамматики на подграмматики

 

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

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

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

При разбиении грамматики на подграмматики нужно учитывать следующее:

1. Совокупности выделенных из грамматики взаимосвязанных правил должна представлять собой КС-грамматику.

2. Основной символ подграмматики становится (специальным) терминальным символом исходной грамматики.

3. Если множества нетерминальных символов подграмматики и модифицированной исходной грамматики не пересекаются, то синтаксический анализ для каждой из них может быть реализован при помощи отдельного процессора с магазинной памятью.

1. Базовая грамматика программы GR1 (Начальный символ S)

 

Терминалы:= program; id = идент; =;

Def = *БлокОпис; BOp = *БлокОпер; =.;

Нетерминалы:

S = НачСимвол 4;

Правила:

) S -> pro id; Def BOp.

) S -> pro id; BOp.

) S -> Def BOp.

4) S -> BOp.

 

. Грамматика раздела описаний GR2 (Начальный символ Def)

 

Терминалы:

DfL = ОписМеток; DfC = ОписКонст; DfT = ОписТипов;

DfV = ОписПерем;

Нетерминалы:

Def = *БлокОпис 8;

Правила:

) Def -> DfL Def

) Def -> DfL

) Def -> DfC Def

) Def -> DfC

) Def -> DfT Def

) Def -> DfT

) Def -> DfV Def

) Def -> DfV

 

3. Грамматика описания меток GR3 (Начальный символ D fL)

 

Терминалы:

lab = label; =;, =;

id = идент; nat = ЦелБезЗнак;

Нетерминалы:

DfL = *ОписМеток 1; M = Метка 2;

LLb = СписокМеток 2;

Правила:

) DfL -> lab LLb

2) LLb -> M;

) LLb -> M, LLb

) M -> id

5) M -> nat

 

. Грамматика описания констант GR4 (Начальный символ Df C)

 

Терминалы:

con = const; =; = = =;

id = идент; Pex = *выражение;

Нетерминалы:

DfC = *ОписКонстант 1; LCn = СписокКонстант 2;

Cn1 = ОписКонстанты 1;

Правила:

) DfC -> con LCn

) LCn -> Cn1; LCn

) LCn -> Cn1;

) Cn1 -> id = Pex

 

. Грамматика описания типов GR5 (Начальный символ Df T)

 

Терминалы:

typ = type; =; = = =;

id = идент; С id = *КонстИден; int = integer;

chr = char; =.; str = string;

Нетерминалы:

DfT = *ОписТипов 1; LTp = СписокТипов 2;= ОписТипа 2; Typ = Тип 4;

Правила:

) DfT -> typ LTp

) LTp -> Tp1; LTp

) LTp -> Tp1;

) Tp1 -> id = Typ

) Tp1 -> id = id

) Typ -> Cid. Cid

) Typ -> int

) Typ -> chr

9) Typ -> str

 

6. Грамматика описания переменных GR6 (Начальный символ Df V)

 

Терминалы:= var; =;, =;

: =:; id = идент; int = integer;= char; str = string;

Нетерминалы:

DfV = *ОписПеременных 1; LVr = СписокОписПерем 2;

Vr1 = Перемен 2; Vrs = СписокПеременных 1;

DV1 = 1ОписПеремен 4;

Правила:

) DfV -> var LVr

2) LVr -> DV1;

) LVr -> DV1; LVr

) Vr1 -> id

) Vr1 -> Vr1, id

) Vrs -> Vr1

) DV1 -> Vrs: id

) DV1 -> Vrs: int

) DV1 -> Vrs: chr

10) DV1 -> Vrs: str

 

. Грамматика меток GR7 (Начальный символ M)

 

Терминалы:= идент; nat = ЦелБезЗнак;

Нетерминалы:

M = *Метка 2;

Правила:

) M -> id

) M -> nat

 

. Грамматика описания операторов GR8 (Начальный символ opl)

 

Терминалы:

M = *метка;: =:; O:= = *ОпПрисв;

OIO = *ОпВв / Выв; OMn = *ОперУправ; BOp = *БлокОпер;

Нетерминалы:

Opl = *Оператор 2; Op = НепомечОпер 4;

Правила:

) Opl -> M: Op

) Opl -> Op

) Op -> BOp

) Op -> O:=

) Op -> OIO

) Op -> OMn

 

9. Грамматика блока операторов GR9 (Начальный символ BOp)

 

Терминалы:= begin; end = end; =;

Opl = *Оператор;

Нетерминалы:

BOp = *БлокОпер 1; OPs = Набор операторов 1;

Op1 = Оператор 2;

Правила:

) BOp -> beg OPs end

2) OPs -> Op1

) Op1 -> Opl

) Op1 -> Opl; Op1

10. Грамматика оператора присваивания GR10 (Начальный символ O :=)

 

Терминалы:= идент;:= =:=; Pex = *выражение;

Нетерминалы:

O:= = *ОпПрисв 1;

Правила:

) O:= -> id:= Pex

 

. Грамматика операторов ввода / вывода GR11 (Начальный символ OIO)

 

Терминалы:= readln; wr = writeln; (= (;

) =); Pex = *выражение;, =;

id = идент;

Нетерминалы:

OIO = *ОпВв / Выв 2; OIn = ОперВвода 1;= ОперВывода 1; W1 = Аргумент вывода 2;

LWr = СписВыраж 1; Vrs = СписПерем 1;

Vr1 = Перемен 2;

Правила:

) OIO -> OIn

) OIO -> OOu

) OIn -> rd (Vrs)

) OOu -> wr (LWr)

) W1 -> Pex

) W1 -> Pex, W1

) LWr -> W1

) Vrs -> Vr1

) Vr1 -> id

10) Vr1 -> id, Vr1

 

. Грамматика операторов управления GR12 (Начальный символ OMn)

 

Терминалы:= repeat; unt = until; Opl = *Оператор;

Lex = *ЛогВыраж; got = goto; if = if;= then; els = else; M = *Метка;

; =;

Нетерминалы:

OMn = *ОперУправ 3; ORu = ОперЦикла 1;

OGo = ОперПерехода 1; OIf = ОперУсловия 2;

Ops = Операторы 1; Op1 = Оператор 2;

Правила:

) OMn -> ORu

) OMn -> OGo

) OMn -> OIf

4) ORu -> rpt Ops unt Lex

) OGo -> got M

) OIf -> if Lex thn Opl

) OIf -> if Lex thn Opl els Opl

) Ops -> Op1

) Op1 -> Opl;

) Op1 -> Opl; Op1

 

13. Грамматика логических выражений GR13 (Начальный символ Le x)

 

Терминалы:

> = >; < = <; = = =;

>= = >=; <= = <=; <> = <>;

(= (;) =); or = or;= and; not = not; Pex = *выражение;= строка; sme = Same;, =;

Нетерминалы:

Lex = *ЛогВыраж 2; Z1 = 2;= 1; Z3 = 2;4 = 3; F1 = 2;

F2 = 2; Sgn = знак сравнения 6;

Правила:

) Lex -> Z1 F1

) Lex -> Z1

3) Z1 -> Z2 F2

) Z1 -> Z2

) Z2 -> Z3

) Z3 -> not Z3

) Z3 -> Z4

) Z4 -> sme (str, str)

) Z4 -> Pex Sgn Pex

) Z4 -> (Lex)

) F1 -> or Z1 F1

) F1 -> or Z1

) F2 -> and Z2 F2

) F2 -> and Z2

) Sgn -> <

) Sgn -> >

17) Sgn -> =

) Sgn -> <=

) Sgn -> >=

) Sgn -> <>

 

. Грамматика простых выражений GR14 (Начальный символ Pe x)

 

Терминалы:

+ = +; - = -; * = *,/;

(= (; / = /;) =);

id = идент; Cid = *КонстИден; Scn = *СтрокКонст;

Fun = *функция;

Нетерминалы:

Pex = *выражение 2; E1 = 2;= 2; T1 = 2;= 5;

Правила:

) Pex -> T1 E1

2) Pex -> T1

) E1 -> + T1 E1

) E1 -> + T1

) E1 -> - T1 E1

) E1 -> - T1

) E2 -> * T2 E2

) E2 -> * T2

) E2 -> / T2 E2

) E2 -> / T2

) T1 -> T2 E2

) T1 -> T2

) T2 -> id

) T2 -> Cid

) T2 -> Scn

) T2 -> Fun

) T2 -> (Pex)

 

15. Грамматика вызова фукций GR15 (Начальный символ Fun)

 

Терминалы:= integer; str = string; lng = length;= concat; pos = pos; sym = StrChar;

(= (;) =);, =;

Pex = *выражение;

Нетерминалы:

Fun = *функция 6;

Правила:

) Fun -> int (Pex)

) Fun -> str (Pex)

) Fun -> lng (Pex)

) Fun -> cnc (Pex, Pex)

) Fun -> pos (Pex, Pex)

) Fun -> sym (Pex, Pex)

 

16. Грамматика целых констант GR16 (Начальный символ Cid)

 

Терминалы:= ЦелБезЗнак; - = -;

Нетерминалы:

Cid = *КонстИден 2;

Правила:

) Cid -> - nat

) Cid -> nat

 

. Грамматика строковых констант GR17 (Начальный символ Scn)

 

Терминалы:= Любой символ; ' = ';

Нетерминалы:

Scn = *СтрокКонст 2; Sms = список символов 1;= символ 2;

Правила:

) Scn -> ' Sms '

2) Scn -> ' '

) Sms -> Sym

) Sym -> Any

5) Sym -> Any Sym