Разработка языка программирования, являющегося подмножеством заданного языка

Вход: лексема типа «однолитерный  разделитель» или «двулитерный разделитель»;.

 

6. Процедура AddLexem(Type, Lexem) – добавляет запись(pos) о лексеме в таблицу лексем заданного класса и вызывает процедуру WriteToken(Type,pos);

Вход: лексема и ее тип.

 

7. Процедура WriteToken(Type, Position) – формирует токен и записывает его в выходной поток токенов.

Вход: номер лексемы в соответствующей таблице лексем.

 

3.4. Таблицы лексем.

1. Таблица ключевых слов.

Таблица ключевых слов

имя ключевого слова

2. Таблица идентификаторов.

Таблица идентификаторов
имя	Тип	значение

3. Таблица целых констант.

Таблица целых констант

значение

4. Таблица разделителей.

Таблица разделителей

Разделитель

5. Таблица строковых констант.

Таблица строковых констант

значение

6. Таблица пользовательских типов. (Заполняется на этапе синтаксического анализа)

Таблица пользовательских типов
Имя	Начало	Конец

7. Таблица меток (Заполняется на этапе синтаксического анализа)

Таблица меток
Имя	Номер тетрады

8. Таблица строковых переменных. (Заполняется на этапе синтаксического анализа)

Таблица строковых переменных
Имя	Длина	Значение

9. Таблица промежуточных значений. (Заполняется на этапе синтаксического анализа)

Таблица промежуточных значений
Тип	Значение

 

 

3.5. Тестирование лексического  анализатора

 

Тестовая программа

Выходной поток токенов

program Test; const   C=10; type     TCounter=0..C; var   i:TCounter;   CurEl:integer;   summa:integer; begin   writeln(‘Hello World!!!’);   i:=0;   summa:=0;   repeat         read(CurEl);         summa:=summa+CurEl;         i:=i+1;   until i=C;   write(summa); end.

program 1 1 id 2 1 ; 4 1 const 1 2   id 2 2 = 4 2 nat 3 1 ; 4 1 type 1 15   id 2 3 = 4 2 nat 3 2 .. 4 19 id 2 2 ; 4 1 var 1 3   id 2 4 : 4 4 id 2 3 ; 4 1   id 2 5 : 4 4 integer 1 4 ; 4 1   id 2 6 : 4 4 integer 1 4 ; 4 1 begin 1 7   writeln 1 17 ( 4 9 scon 5 1 ) 4 10 ; 4 1   id 2 4 := 4 7 nat 3 2 ; 4 1   id 2 6 := 4 7 nat 3 2 ; 4 1   repeat 1 8     read 1 10 ( 4 9 id 2 5 ) 4 10 ; 4 1     id 2 6 := 4 7 id 2 6 + 4 12 id 2 5 ; 4 1     id 2 4 := 4 7 id 2 4 + 4 12 nat 3 3 ; 4 1   until 1 9 id 2 4 = 4 2 id 2 2 ; 4 1   write 1 11 ( 4 9 id 2 6 ) 4 10 ; 4 1 end 1 12 . 4 13

 

 

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

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

 

1. Таблица ключевых  слов			4. Таблица разделителей
1	program		1	;
2	const		2	=
3	var		3	,
4	integer		4	:
5	char		5	[
6	string		6	]
7	begin		7	:=
8	repeat		8	<=
9	until		9	(
10	read		10	)
11	write		11	*
12	end		12	+
13	and		13	.
14	label		14	<
15	type		15	>
16	readln		16	>=
17	writeln		17	<>
18	goto		18	/
19	if		19	..
20	then
21	else
22	length
23	concat
24	replace
25	pos
26	StrChar
27	copy
28	Same
29	or
30	not

 

Сформированные таблицы лексем:

 

 

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

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

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

4.1. Построение КС-грамматики входного языка

Для построения КС-грамматики входного языка необходимо:

1. Заменить металингвистические переменные БНФ обозначениями нетерминальных символов, используя короткие имена;
2. В качестве терминальных символов использовать токены;
3. Металингвистический символ «::=» заменить символом «à»;
4. Заменить одну металингвистическую формулу с n альтернативами на n правил грамматики с одинаковым символом в левой части правила вывода;
5. Исключить металингвистические символы [ ] и { }, включив в правила грамматики e-правила и рекурсивные правила.

 

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

 

Грамматика  простого предшествования

 

Синтаксический анализ, основанный на простом предшествовании, использует для выделения основы правовыводимой цепочки αβ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 = ОписПерем ;