орнеться до початкового символу (або поки подальші згортки виявляться неможливими). ??
Відносини передування для КС-граматики G=(N,?, Р, S) визначаються на безлічі (NU? U {?})? (NU? U {?}) Наступним чином:
· X < У, якщо в множині правил граматики Р є правило А -> ? XB? і існує висновок В => + Y? ;
· X=Y, якщо в Р міститься правило виду А -> ? XY? ;
· X> а, якщо в Р є правило виду А -> ? BY? і існують висновки В => +? X і Y => а? (Якщо У => ° а?, То Y=а);
·? < X для всіх X, для яких S => + Х? ;
· Y> ? для всіх Y, для яких S => *? Y.
КС-граматика G=(N,?, P, S) називається граматикою передування, якщо вона приведена, не містить?- Правил і для будь-якої пари символів з безлічі NU? виконується не більше одного відношення передування.
Поправна граматика передування називається граматикою простого передування.
Побудова граматики по БНФ
S -> pro id; Def BOp. -> pro id; BOp. -> Def BOp. -> BOp.
-> DfL Def-> DfL-> DfC Def-> DfC-> DfT Def-> DfT-> DfV Def-> DfV
-> lab LLb-> M; -> M, LLb
-> con LCn-> Cn1; LCn-> Cn1; -> id=Pex
-> typ LTp-> Tp1; LTp-> Tp1; -> id=Typ-> id=id-> Cid. Cid-> int-> chr-> str
-> var LVr-> DV1; -> DV1; LVr-> id-> Vr1, id-> Vr1-> Vrs: id-> Vrs: int-> Vrs: chr-> Vrs: str
-> id-> nat
-> M: Op-> Op-> BOp-> O:=-> OIO-> OMn
-> beg OPs end-> Op1-> Opl-> Opl; Op1
:=-> id:=Pex
-> OIn-> OOu-> rd (Vrs) -> wr (LWr) -> Pex-> Pex, W1-> W1
-> ORu-> OGo-> OIf-> rpt Ops unt Lex-> got M-> if Lex thn Opl-> if Lex thn Opl els Opl
-> Z1 F1-> Z1-> Z2 F2-> Z2-> Z3-> not Z3-> Z4-> sme (str, str) -> Pex Sgn Pex-> (Lex) -> or Z1 F1-> or Z1-> and Z2 F2-> and Z2-> <-> > -> =-> <= -> >=-> <>
-> T1 E1-> T1-> + T1 E1-> + T1->- T1 E1->- T1-> * T2 E2-> * T2->/T2 E2->/T2-> T2 E2-> T2-> id-> Cid-> Scn-> Fun-> (Pex)
Fun -> int (Pex) -> str (Pex) -> lng (Pex) -> cnc (Pex, Pex) -> pos (Pex, Pex) -> sym (Pex, Pex)
->- Nat-> nat
-> « Sms »-> « »-> Sym-> Any -> Any Sym
.2 Розбиття граматики на подграмматікі
За умовами завдання отримана граматика повинна належати до класу граматик простого передування, або складається з подграмматік простого передування.
Так як вихідна КС-граматика не є граматикою простого передування, то потрібно виділити з вихідної граматики подграмматікі таким чином, щоб кожна з отриманих граматик належала заданому класу.
Розбиття на подграмматікі дозволить використовувати заданий метод синтаксичного аналізу, але ускладнить опис та реалізацію цього перекладу, оскільки після розбиття переклад буде описуватися за допомогою декількох взаємопов'язаних атрібутних транслюють граматик.
