Таблицы ключевых слов и разделителей - статические, таблицы идентификаторов и констант заполняются в процессе лексического и синтаксического анализа.

Статические таблицы лексем

4. Синтаксический анализатор

Синтаксический анализ, основанный на простом предшествовании, использует для выделения основы правовыводимой цепочки бвw три отношения предшествования (<), (=) и (>) следующим образом:

· если в - основа, то между всеми смежными символами цепочки б выполняется либо отношение (<), либо (=);

· между последним символом цепочки б и первым символом цепочки в выполняется отношение (<);

· между смежными символами основы выполняется отношение (=);

· между последним символом цепочки в и первым символом цепочки w выполняется отношение (>).

Очевидно, что правый конец основы правовыводимой цепочки грамматики простого предшествования можно выделить, просматривая эту цепочку слева направо до тех пор, пока впервые не встретится отношение (>). Для нахождения левого конца основы надо просмотреть ее назад, пока не встретится отношение (<). Цепочка, заключенная между отношениями (<) и (>), будет основой. Если грамматика является обратимой, т.е. не содержит правил с одинаковой правой частью, то основу можно однозначно свернуть. Этот процесс продолжается до тех пор, пока входная цепочка не свернется к начальному символу (либо пока дальнейшие свертки окажутся невозможными).

Отношения предшествования для КС-грамматики G = (N, У, Р, S) определяются на множестве (N U У U {+}) Ч (N U У U {е}) следующим образом:

· X < У, если в множестве правил грамматики Р есть правило А -> бXBв и существует вывод В =>⁺ Yг;

· X = Y, если в Р содержится правило вида А -> бXYв;

· X > а, если в Р есть правило вида А -> бBYв и существуют выводы В =>⁺ гX и Y => ад (если У=>° ад, то Y= а);

· + < X для всех X, для которых S =>⁺ Хб;

· Y > е для всех Y, для которых S =>^* бY.

КС-грамматика G = (N, У, P, S) называется грамматикой предшествования, если она приведенная, не содержит е - правил и для любой пары символов из множества N U У выполняется не более одного отношения предшествования.

Обратимая грамматика предшествования называется грамматикой простого предшествования.

Построение грамматики по БНФ

S -> pro id; Def BOp.

S -> pro id; BOp.

S -> Def BOp.

S -> BOp.

Def -> DfL Def

Def -> DfL

Def -> DfC Def

Def -> DfC

Def -> DfT Def

Def -> DfT

Def -> DfV Def

Def -> DfV

DfL -> lab LLb

LLb -> M;

LLb -> M, LLb

DfC -> con LCn

LCn -> Cn1; LCn

LCn -> Cn1;

Cn1 -> id = Pex

DfT -> typ LTp

LTp -> Tp1; LTp

LTp -> Tp1;

Tp1 -> id = Typ

Tp1 -> id = id

Typ -> Cid. Cid

Typ -> int

Typ -> chr

Typ -> str

DfV -> var LVr

LVr -> DV1;

LVr -> DV1; LVr

Vr1 -> id

Vr1 -> Vr1, id

Vrs -> Vr1

DV1 -> Vrs: id

DV1 -> Vrs: int

DV1 -> Vrs: chr

DV1 -> Vrs: str

M -> id

M -> nat

Opl -> M: Op

Opl -> Op

Op -> BOp

Op -> O:=

Op -> OIO

Op -> OMn

BOp -> beg OPs end

OPs -> Op1

Op1 -> Opl

Op1 -> Opl; Op1

O:= -> id:= Pex

OIO -> OIn

OIO -> OOu

OIn -> rd (Vrs)

OOu -> wr (LWr)

W1 -> Pex

W1 -> Pex, W1

LWr -> W1

OMn -> ORu

OMn -> OGo

OMn -> OIf

ORu -> rpt Ops unt Lex

OGo -> got M

OIf -> if Lex thn Opl

OIf -> if Lex thn Opl els Opl

Lex -> Z1 F1

Lex -> Z1

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 -> >

Sgn -> =

Sgn -> <=

Sgn -> >=

Sgn -> <>

Pex -> T1 E1

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)

Fun -> int (Pex)

Fun -> str (Pex)

Fun -> lng (Pex)

Fun -> cnc (Pex, Pex)

Fun -> pos (Pex, Pex)

Fun -> sym (Pex, Pex)

Cid -> - nat

Cid -> nat

Scn -> ' Sms '

Scn -> ' '

Sms -> Sym

Sym -> Any

Sym -> Any Sym

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

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

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

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

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

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

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

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

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

Терминалы:

pro = program; id = идент; =;

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

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

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

Правила:

1) S -> pro id; Def BOp.

2) S -> pro id; BOp.

3) S -> Def BOp.

4) S -> BOp.

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

Терминалы:

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

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

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

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

Правила:

1) Def -> DfL Def

2) Def -> DfL

3) Def -> DfC Def

4) Def -> DfC

5) Def -> DfT Def

6) Def -> DfT

7) Def -> DfV Def

8) Def -> DfV

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

Терминалы:

lab = label; =;, =;

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

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

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

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

Правила:

1) DfL -> lab LLb

2) LLb -> M;

3) LLb -> M, LLb

4) M -> id

5) M -> nat

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

Терминалы:

con = const; =; = = =;

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

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

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

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

Правила:

1) DfC -> con LCn

2) LCn -> Cn1; LCn

3) LCn -> Cn1;

4) Cn1 -> id = Pex

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

Терминалы:

typ = type; =; = = =;

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

chr = char; =.; str = string;

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

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

Tp1 = ОписТипа 2; Typ = Тип 4;

Правила:

1) DfT -> typ LTp

2) LTp -> Tp1; LTp

3) LTp -> Tp1;

4) Tp1 -> id = Typ

5) Tp1 -> id = id

6) Typ -> Cid. Cid

7) Typ -> int

8) Typ -> chr

9) Typ -> str

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

Терминалы:

var = var; =;, =;

: =:; id = идент; int = integer;

chr = char; str = string;

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

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

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

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

Правила:

1) DfV -> var LVr

2) LVr -> DV1;

3) LVr -> DV1; LVr

4) Vr1 -> id

5) Vr1 -> Vr1, id

6) Vrs -> Vr1

7) DV1 -> Vrs: id

8) DV1 -> Vrs: int

9) DV1 -> Vrs: chr

10) DV1 -> Vrs: str

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

Терминалы:

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

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

M = *Метка 2;

Правила:

1) M -> id

2) M -> nat

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

Терминалы:

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

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

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

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

Правила:

1) Opl -> M: Op

2) Opl -> Op

3) Op -> BOp

4) Op -> O:=

5) Op -> OIO

6) Op -> OMn

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

Терминалы:

beg = begin; end = end; =;

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

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

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

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

Правила:

1) BOp -> beg OPs end

2) OPs -> Op1

3) Op1 -> Opl

4) Op1 -> Opl; Op1

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

Терминалы:

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

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

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

Правила:

1) O:= -> id:= Pex

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

Терминалы:

rd = readln; wr = writeln; (= (;

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

id = идент;

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

OIO = *ОпВв / Выв 2; OIn = ОперВвода 1;

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

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

Vr1 = Перемен 2;

Правила:

1) OIO -> OIn

2) OIO -> OOu

3) OIn -> rd (Vrs)

4) OOu -> wr (LWr)

5) W1 -> Pex

6) W1 -> Pex, W1

7) LWr -> W1

8) Vrs -> Vr1

9) Vr1 -> id

10) Vr1 -> id, Vr1

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

Терминалы:

rpt = repeat; unt = until; Opl = *Оператор;

Lex = *ЛогВыраж; got = goto; if = if;

thn = then; els = else; M = *Метка;

; =;

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

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

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

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

Правила:

1) OMn -> ORu

2) OMn -> OGo

3) OMn -> OIf

4) ORu -> rpt Ops unt Lex

5) OGo -> got M

6) OIf -> if Lex thn Opl

7) OIf -> if Lex thn Opl els Opl

8) Ops -> Op1

9) Op1 -> Opl;

10) Op1 -> Opl; Op1

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

Терминалы:

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

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

(= (;) =); or = or;

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

str = строка; sme = Same;, =;

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

Lex = *ЛогВыраж 2; Z1 = 2;

Z2 = 1; Z3 = 2;

Z4 = 3; F1 = 2;

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

Правила:

1) Lex -> Z1 F1

2) Lex -> Z1

3) Z1 -> Z2 F2

4) Z1 -> Z2

5) Z2 -> Z3

6) Z3 -> not Z3

7) Z3 -> Z4

8) Z4 -> sme (str, str)

9) Z4 -> Pex Sgn Pex

10) Z4 -> (Lex)

11) F1 -> or Z1 F1

12) F1 -> or Z1

13) F2 -> and Z2 F2

14) F2 -> and Z2

15) Sgn -> <

16) Sgn -> >

17) Sgn -> =

18) Sgn -> <=

19) Sgn -> >=

20) Sgn -> <>

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

Терминалы:

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

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

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

Fun = *функция;

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

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

E2 = 2; T1 = 2;

T2 = 5;

Правила:

1) Pex -> T1 E1

2) Pex -> T1

3) E1 -> + T1 E1

4) E1 -> + T1

5) E1 -> - T1 E1

6) E1 -> - T1

7) E2 -> * T2 E2

8) E2 -> * T2

9) E2 -> / T2 E2

10) E2 -> / T2

11) T1 -> T2 E2

12) T1 -> T2

13) T2 -> id

14) T2 -> Cid

15) T2 -> Scn

16) T2 -> Fun

17) T2 -> (Pex)

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

Терминалы:

int = integer; str = string; lng = length;

cnc = concat; pos = pos; sym = StrChar;

(= (;) =);, =;

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

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

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

Правила:

1) Fun -> int (Pex)

2) Fun -> str (Pex)

3) Fun -> lng (Pex)

4) Fun -> cnc (Pex, Pex)

5) Fun -> pos (Pex, Pex)

6) Fun -> sym (Pex, Pex)

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

Терминалы:

nat = ЦелБезЗнак; - = -;

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

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

Правила:

1) Cid -> - nat

2) Cid -> nat

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

Терминалы:

Any = Любой символ; ' = ';

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

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

Sym = символ 2;

Правила:

1) Scn -> ' Sms '

2) Scn -> ' '

3) Sms -> Sym

4) Sym -> Any

5) Sym -> Any Sym

4.3 Описание промежуточного языка

Для бинарных операций удобной формой представления программы после синтаксического анализа являются тетрады.

Формат тетрад:

<код операции>, <операнд_1>, <операнд_2>, <результат>,

где <операнд_1> и <операнд_2> специфицируют аргументы, а <результат> - временное имя для хранения результата выполнения операции (переменная из рабочей области).

В качестве операндов тетрад наряду с переменными и константами, определенными в исходной программе, могут выступать результаты ранее выполненных тетрад. Например, выражение a* b + с* d представляется в виде последовательности следующих тетрад:

*, a, b, t1

*, c, d, t2

+, t1, t2, t3

Последовательность тетрад представляет собой программу, инструкции которой обрабатываются последовательно. Операнды одной тетрады должны быть одинакового типа. Для преобразования типа операнда можно использовать тетрады преобразования типа с кодами операций ITOS (целый - в строкоый) и STOI (строковый - в целый). Поскольку операция преобразования типа одноместная, она записывается с пустым вторым операндом, например, STOI, а, t.

Для представления унарного минуса в тетрадах также можно не использовать второй операнд. Тетрада -, а, t интерпретируется как присвоение временной переменной t значения - а.

Тетрады удобно использовать для выполнения машинно-независимой оптимизации, в частности, исключения лишних операций. Основным недостатком тетрад является большой объем памяти, необходимый для их хранения. Несмотря на то, что во многих тетрадах имеются свободные поля, результат выполнения операции всегда записывается в четвертое поле.

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

синтаксис лексема анализатор язык

Размещено на Allbest.ru