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

 

 

Конструкции входного языка

 

Оператор цикла  с постусловием repeat-until.

<цикл с постусловием>::= repeat <последовательность операторов> until <условие>

 

1. Выполняется оператор (Тело цикла).
2. Вычисляется условие.
3. Выполняется переход на пункт 1 в случае, если условие не выполнилось.

 

Оператор присваивания :=

<оператор присваивания>::=<переменная> := <простое выражение>

 

1. Вычисляется выражение, стоящее справа от знака присваивания
2. В случае, если результат получился того же типа, что и переменная, в нее заносится новое значение, иначе результат преобразуется к заданному типу и заносится в переменную

 

Каждая переменная, используемая в  программе, должна быть предварительно описана.

В программе не могут объявляться переменные с одинаковым именем.

Имя переменной не может совпадать  с ключевыми словами.

 

Оператор безусловного перехода goto.

<оператор безусловного перехода>::=goto <метка>

Выполняется переход на метку

Метка должна быть объявлена в разделе label, и встречаться в теле программы один раз.

 

Условный оператор if-then-else:

<условный оператор>::=if <условие> then <оператор1> [else <оператор2>]

Вычисляется значение логического  выражения и выполняется в переход на оператор2, если условие не выполнилось. Иначе выполняется оператор1 и происходит безусловный переход на конец оператора if-then-else.

 

Оператор ввода read.

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

 

Оператор  вывода write.

Оператор write вычисляет значение первого выражения в строке вывода и выводит его на экран. Затем то же самое производится со всеми последующими выражениями.

 

3. Лексический анализатор.

3.1. Описание типов лексем

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

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

 

Соотношение между токенами и лексемами для различных языковых конструкций иллюстрируется следующей таблицей:

 

Токен	Лексемы	Языковая конструкция
id	count, index	Идентификатор
scon	‘Hello’, ‘World’	Строка
nat	0, 1, 3, 943	Целое число без знака
program, begin, end, label, const, var, type, integer, char, string, read, readln, write, writeln, goto, if, then, else, repeat, until, length, concat, replace, pos, StrChar, copy, Same, and, or, not	program, begin, end, label, const, var, type, integer, char, string, read, readln, write, writeln, goto, if, then, else, repeat, until, length, concat, replace, pos, StrChar, copy, Same, and, or, not	Ключевые слова program, begin, end, label, const, var, type, integer, char, string, read, readln, write, writeln, goto, if, then, else, repeat, until, length, concat, replace, pos, StrChar, copy, Same, and, or, not
:=	:=	Оператор присваивания
=	=	Операция “равно”
<	<	Операция “меньше”
>	>	Операция “больше”
<=	<=	Операция “меньше равно”
>=	>=	Операция “больше равно”
<>	<>	Операция “неравно”
+	+, -	Операция типа «сложение»
*	*, /	Операция типа «умножение»
(	(	Открывающая круглая скобка
)	)	Закрывающая круглая скобка
[	[	Открывающая квадратная скобка
]	]	Закрывающая квадратная скобка
;	;	Символ «;»
,	,	Символ «,»
:	:	Символ «:»
.	.	Символ конца программы

 

 

3.2. Определение синтаксиса  лексем.

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

3.2.1. Классы литер, с помощью  которых записываются программы  на входном языке:

 

• класс «буква»: a A … z Z
• класс «цифра»: 0 1 2 3 4 5 6 7 8 9
• класс «однолитерные разделители»: ; , + - * / = ( ) [ ]
• класс «литеры однолитерных и двулитерных разделителей»: < > = : .

3.2.2. Составление автоматных грамматик, описывающих синтаксис лексем.

 

Терминальными символами грамматики являются классы литер, а начальным символом грамматики – символ S.

1. Автоматная грамматика, описывающая синтаксис лексем «идентификатор» и «ключевое слово». Здесь “Буква” – класс «буква», “Цифра” – класс «цифра», “e1” – класс, включающий все литеры, за исключением букв, цифр и знака подчеркивания.

Правила грамматики:

S	à	Буква Id
S	à	_ Id
Id	à	Буква Id
Id	à	Цифра Id
Id	à	_ Id
Id	à	e1

 

2. Автоматная грамматика, описывающая синтаксис лексемы «целая константа без знака». Здесь “Цифра” – класс «цифра», “e3” – класс, включающий все литеры, за исключением цифр.

Правила грамматики:

S	à	Цифра C
C	à	Цифра C
C	à	e3

 

3. Автоматная грамматика, описывающая синтаксис лексемы «строковая константа». Здесь “НE ‘” – любой символ, кроме ’.

Правила грамматики:

S	à	‘ T
T	à	НЕ ‘ T
T	à	‘

 

4. Автоматные грамматики, описывающие синтаксис лексем «однолитерный разделитель» и «двулитерный разделитель». Здесь “Знак” – классы «однолитерные разделители» и «литеры однолитерных и двулитерных разделителей», “e4” – класс, включающий все литеры.

Правила грамматики:

однолитерные разделители:	S	à	Знак L
	L	à	e4

 

лексема «:=»	S	à	: Next
	Next	à	= E
	E	à	e4

 

лексема «<=»	S	à	< Next
	Next	à	= E
	E	à	e4

 

лексема «>=»	S	à	> Next
	Next	à	= E
	E	à	e4

 

лексема «<>»	S	à	< Next
	Next	à	> E
	E	à	e4

 

лексема «..»	S	à	. Next
	Next	à	. E
	E	à	e4

 

 

3.3. Построение диаграммы  лексического анализатора.

3.3.1. Построение графов конечных автоматов для распознавания лексем.

 

Здесь S – начальное состояние конечного автомата, F- конечное состояние, соответствующее концу разбора лексемы.

 

1. Граф конечного автомата для распознавания лексем «идентификатор» и «ключевое слово».

2. Граф конечного автомата для распознавания лексемы «целая константа без знака».

3. Граф конечного автомата для распознавания лексемы «строковая константа».

4. Графы конечных автоматов для распознавания лексем «однолитерный разделитель» и «двулитерный разделитель». Здесь “Знак1” – включает литеры класса «однолитерные разделители».

 

3.3.2. Диаграмма лексического анализатора.

 

Здесь “Пробел” – класс, включающий пробелы, символы табуляции и перевода строки, “Не }” – класс, включающий все литеры кроме литеры «}».

 

3.3.3. Спецификации функций лексического анализатора.

1. Процедура ReadLexem(Text) – считывает лексему из входного потока и распознает ее тип.

Вход: входной поток литер текста программы.

 

2. Процедура GetLexem(Type,Lexem) – в зависимости от типа переданной лексемы вызывает одну из процедур:

• GetId(Lexem) – для лексем «идентификатор» и «ключевое слово»;

• GetNum(Lexem) – для лексем «целая константа без знака»;
• GetSCon(Lexem) – для лексем «строковая константа»;
• GetLet(Lexem) – для лексем «однолитерный разделитель» и «двулитерный разделитель»;

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

 

3. Процедура GetId(Lexem) – если переданная лексема является ключевым словом, определяет ее адрес(pos) в таблице ключевых слов и вызывает процедуру WriteToken(Key,pos);

в противном случае ищет запись(pos) об этой лексеме в таблице идентификаторов, если  находит, то вызывает процедуру WriteToken(Id, pos), иначе вызывает процедуру AddLexem(Id,Lexem);

Вход: лексема типа «идентификатор»  или «ключевое слово».

 

4. Процедура GetNum(Lexem) – ищет запись(pos) о переданной лексеме в таблице констант, если находит, то вызывает процедуру WriteToken(Num,pos), иначе вызывает процедуру AddLexem(Num,Lexem);

Вход: лексема типа «целая константа  без знака».

 

5. Процедура GetLet(Lexem) – определяет адрес(pos) лексемы в таблице разделителей и вызывает процедуру WriteToken(Let,pos);