Разработка и отладка формального языка

Введение

В современном программировании большой
популярностью пользуются языки высокого уровня. Это вызвано тем, что
программировать на этих языках существенно проще и программы, написанные с их
помощью нагляднее, чем эквивалентные им программы, выполненные на языках
низкого уровня. Именно поэтому в данной работе необходимо разработать свой
небольшой язык и осуществить его подготовку к написанию компилятора к данному
языку. Этот язык должен показать некоторые возможности современных языков
программирования и позволить разработчику данного языка укрепить знания,
полученные ранее и более глубоко изучить предмет «Теория трансляции».

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

Данная
курсовая работа имеет большое учебное значение, так как в настоящее время всё
больше внимания уделяют языкам программирования высокого уровня, потому что
писать программы на них намного проще (программы стали большими) и удобнее. В
будущем эти знания могут пригодиться нам в разработке собственных языков или
участвовать в разработке мощного языка высокого уровня. Именно поэтому большое
практическое значение имеет разработка собственного языка, пусть не слишком
мощного, но высокоуровневого, на котором будут видны все возможности языков
современных.

Чтобы создать
подобный язык в рамках данной курсовой работы необходимо в соответствии с
требованиями к языку разработать грамматику, в которой будет описан синтаксис
языка, а затем отладить её с помощью методов простого и параллельного
предшествований.

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

Назначение и область применения

Разработка языка C++ несет исключительно обучающую цель и производится с целью
углубить и расширить познания автора в дисциплине «Теория трансляций», а также
в приобретении навыков разработке учебного языка и проведения работы,
подготавливающей язык к построению транслятора.

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

 

Технические характеристики

Постановка
задачи на разработку

Перечень
требований к разрабатываемому языку программирования:

Процедура Sub.

Оператор
объявления констант.

Описание
типа переменных с помощью суффикса: Sin 99gle, Integer.

Массивы
фиксированного размера с макс. размерностью 2

Операторы
ввода / вывода MsgBox, InputBox.

Арифметические
операции: + ^.

Логические
операции: Not, And, Or.

Операции
сравнения.

Условный
оператор типа If…Then

Оператор
цикла типа For… Next.

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

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

Функции: конкатенация
строк, Cbool, Format, GetAllSettings.

Элементы управления: TextBox,
CommandButton, CheckBox, PictureBox.

Описание
применяемых математических методов

Введём несколько определений:

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

G = {Vт, Vn, P, S}, где

Vт – словарь
терминальных символов грамматики;

Vn – словарь
нетерминальных символов грамматики;

P – множество
правил грамматики:

P = {(A, )|A-> &
AVn & V*}

S – начальный
символ грамматики (SVт);

V* – множество
строк, составленных из символов полного словаря

V (V=Vт 
Vn);

V* = {|=
п  ( xV) ( QV*)=Qx}

п – пустая
цепочка.

Определение
2.
Цепочка o порождает нетривиальным образом цепочку o (записывают
o=>+W), если существует последовательность непосредственных выводов:

o
=>1 =>… n, n>=1.

Определение
3.
Цепочка  порождает цепочку Q (записывают =>*Q), если =>+Q,
или =Q.

Определение
4.
Цепочка называется сентенциальной формой грамматики G, если она выводится из
начального символа грамматики, т.е. если S->*.

Определение
5. Предложение языка – это
сентенциальная форма, состоящая только из терминальных символов.

Определение
6. Язык L(G) – это
множество предложений

L(G) = {|
S->+  Vт*}.

 

Определение
7. Символы A, B
контекстно-свободной грамматики связаны отношением FIRST, если выполняется
условие

A->B,

где AVn, BV, V*.

Определение
8. Символы A и B грамматики
связаны отношением.=., если в грамматике имеется правило вида:

WAВ.

Определение
9. Отношение >.
Между символами A и B грамматики находится из правила:

(>.)=(LAST+)T (.=.).

Определение
10. Отношение <.
Между символами A и B грамматики находится из правила:

(<.)=(.=.)
(FIRST+).

Разработка
грамматики по неформальному описанию языка

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

Чтобы
проверить ее корректность составим контрольный пример:

Sub D11 ()

Dim A As
Integer,

B% As
Integer

Const D As
Single

Dim M (2)
As Integer A = (B*2 + 9)^10

If ((IsNumeric
(A) <>0 and A>0) Then

MsgBox («A
is number», vbOkOnly) EndI

Text. Text
= A

End Sub

Дерево к
данному примеру приведено на листе А1.

Разработка
сканера

Лексический
анализ проводится сканером (лексическим анализатором). Сканер выделяет
простейшие языковые конструкции (лексемы) и классифицирует их тип.

Сканер
работает с таблицами, которые являються базой данных сканера.

Таблицы
делятся на постоянные и временные.

Постоянные
таблицы создаются разработчиком сканера и включают в себя:

ТТС1 –
таблица терминальных символов (однолитерных).

ТТС2 –
таблица терминальных символов (двулитерных).

ТКС – таблица
ключевых слов.

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

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

ТК – таблица
констант.

ТФ – таблица
функций.

ТСС – таблица
стандартных символов.

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

Формальное
определение лексем.

Лексические
единицы:

арифметические
операции:
«+», «/», «^».

операции
сравнения:
«>», «<», «=», «>=», «<=», «<>»

операция присваивания: «=»

скобка открывающая «(«

скобка закрывающая «)»

служебные
слова:

«Dim»,
«As», «Private», «Public», «Sub», «End», «goto», «Optional», «MsgBox», «InputBox».

условный
оператор:
«If», «Then»

оператор
цикла: «For», «Next»

типы данных: «Single», «Byte»,» Date», «Integer», «Boolean», «String», «Variant»,
«Object».

элементы управления: «TextBox», «ComandButton»,
«CheckBox», «PictureBox»

свойства элементов управления: «Caption», «Text»,
«With», «Height», «Visible»

специальные константы: «VbOkOnly», «VbOkCansel»,
«VbAbortRetryIgnore»,

«VbCritical»

логические функции: «Not», «And»,
«Or»

функции: «Format», «CBool», «GetAllSettings». нижнее
подчеркивание: «_»

точка: «.»

кавычки: «@»

десятичные целые константы

идентификатор

 

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

Таблица 1.
Однолитерные терминальные символы TTC1:

>

Адрес	Символ	KTL
1 26 27 54	a … z A … Z	1
55 … 64	0 … 9	2
65	=	3
66	>	3
67	<	3
68	^	3
69	*	3
70	-	3
71		3
72	#	3
73	%	3
74	.	3
75	_	3
76	@	3
77	(	3
78	)	3

Таблица 2.
Двулитерные терминальные символы

>

Адрес	Символ	KTL
1	<=	3
2	>=	3
3	<>	3

Таблица 3.
Классы текущих литер

>

Символ	Класс
Буква	1
Цифра	2
Допустимый символ	3

Таблица 4.
Функции

>

Логические ф-и (адрес)

Not(1)

And(2)

Or(3)

Функции (адрес)

CBool (5)

Format (6)

GetAllSettings (7)

Concat (8)

Таблица 5. Тип лексической единицы

>

Лексическая единица	Тип
операция «=»	1
операция «–»	2
операция «*»	3
операция «^»	4
операция «»	5
операция «mod «	6
разделители «.»,», «	7
нижнее подчеркивание «_»	8
кавычки «@»	9
операции сравнения	10
служебные слова	11
условный оператор	12
оператор цикла	13
тип данных	14
элементы управления	15
оператор цикла	16
события элементов управления	17
свойства элементов управления	18
специальные константы	19
логические функции	20
функции	21
десятичная целая константа	22
идентификатор	23
название функции	24
псевдоним функции	25
библиотек	26
открывающая скобка «(«	27
закрывающая скобка «)»	28

Для каждой
лексической единицы составляем автоматную грамматику.

Идентификатор:

S = бK                                            

K = бK|цК|%F |#F                 

Десятичная целая константа:

S = «ц» D                    

D = «ц» D | e2 F

Степень:

S = «^» F            

Деление:

S = «» F

Cложение:

S = «+» F                     

Знаки
отношения:

e3

<

S = «<» A | «>» B |
«=» F

A

A = «=» D |«>«D| e3 F

e5

=/>

B = «=» D | e4 F

=

>

F

D

S

D = e5 F