По теории языков программирования и методов трансляции Разработка компилятора модельного языка
Содержание
Введение 3
1 Постановка задачи 4
2 Формальная модель задачи 5
3
Структура программы…………………………………………………..
3.1 Лексический анализатор 16
3.2 Синтаксический анализатор 18
3.3 Семантический анализатор 20
3.4 Генерация ПОЛИЗа программы 22
3.5 Интерпритация ПОЛИЗа программы 24
4
Структурная организация
4.1
Спецификация входной
4.2
Спецификация выходной
4.3
Спецификация процедур и
5 Разработка алгоритма решения задачи 32
5.1 Укрупненная схема алгоритма программного средства 32
5.2 Детальная разработка алгоритмов отдельных подзадач 33
6
Установка и эксплуатация
7
Работа с программным
Заключение 36
Список использованных источников 37
Приложение
А – Текст программы 38
Введение
Теория формальных языков, грамматик и автоматов составляет фундамент синтаксических методов. Основы этой теории были заложены Н. Хомским в 40–50-е годы XX столетия в связи с его лингвистическими работами, посвященными изучению естественных языков. Но уже в следующем десятилетии синтаксические методы нашли широкое практическое применение в области разработки и реализации языков программирования.
В настоящее время искусственные языки, использующие для описания предметной области текстовое представление, широко применяются не только в программировании, но и в других областях. С их помощью описывается структура всевозможных документов, трехмерных виртуальных миров, графических интерфейсов пользователя и многих других объектов, используемых в моделях и в реальном мире. Для того чтобы эти текстовые описания были корректно составлены, а затем правильно распознаны и интерпретированы, применяются специальные методы их анализа и преобразования. В основе данных методов лежит теория формальных языков, грамматик и автоматов.
Теория
формальных языков, грамматик и автоматов
дала новый стимул развитию математической
лингвистики и методам
Несмотря
на то, что к настоящему времени разработаны
тысячи различных языков и их компиляторов,
процесс создания новых приложений в этой
области не прекращается. Это связно как
с развитием технологии производства
вычислительных систем, так и с необходимостью
решения все более сложных прикладных
задач. Такая разработка может быть обусловлена
различными причинами, в частности, функциональными
ограничениями, отсутствием локализации,
низкой эффективностью существующих компиляторов.
Целью курсовой работы являться:
- закрепление теоретических знаний в области теории формальных языков, грамматик, автоматов и методов трансляции;
- формирование практических умений и навыков разработки собственного компилятора модельного языка программирования;
- закрепление практических навыков самостоятельного решения инженерных задач, развитие творческих способностей студентов и умений пользоваться технической, нормативной и справочной литературой.
1
Постановка задачи
Разработать компилятор модельного языка, выполнив следующие действия.
1) В соответствии с номером варианта составить формальное описание модельного языка программирования с помощью:
а) РБНФ;
б) диаграмм Вирта;
в) формальных грамматик.
2) Написать пять содержательных примеров программ, раскрывающих особенности конструкций учебного языка программирования, отразив в этих примерах все его функциональные возможности.
3)
Составить таблицы лексем и
диаграмму состояний с
4) По диаграмме с действиями написать функцию сканирования текста входной программы на модельном языке.
5)
Разработать программное
6)
Реализовать синтаксический
7) Построить цепочку вывода и дерево разбора простейшей программы на модельном языке из начального символа грамматики.
8)
Дополнить синтаксический
9)
Распечатать пример таблиц
10)
Показать динамику изменения
содержимого стека при
11) Записать правила вывода грамматики с действиями по переводу в ПОЛИЗ программы на модельном языке.
12)
Пополнить разработанное
13) Разработать интерпретатор ПОЛИЗа программы на модельном языке.
14) Составить набор контрольных примеров, демонстрирующих:
а) все возможные типы лексических, синтаксических и семантических ошибок в программах на модельном языке;
б) перевод в ПОЛИЗ различных конструкций языка;
в)
представить ход интерпретации синтаксически
и семантически правильной программы
с помощью таблицы.
2
Формальная модель
задачи
Процесс
компиляции включает два основных этапа:
анализ и синтез. На этапе анализа
выполняется распознавание
синтаксический анализ, синтаксический анализ, семантический анализ, подготовка к генерации кода, генерация кода.
Лексический анализатор производит чтение символов программы на исходном языке и строит из них слова (лексемы) исходного языка, которые передаются для дальнейшей обработки на этапе синтаксического анализа.
Синтаксический разбор - часть компилятора, выполняющая выделение синтаксических конструкций в тексте исходной программы, обработанной лексическим анализатором. На этой же фазе проверяется синтаксическая правильность программы.
Семантический анализ - часть компилятора, проверяющая правильность текста исходной программы с точки зрения семантики входного языка. Кроме непосредственно проверки выполняются преобразования текста, требуемые семантикой входного языка. В данной реализованной программе семантические проверки входят в состав синтаксического анализатора.
На
фазе подготовки к генерации кода
выполняются предварительные
На фазе генерации кода порождаются команды, составляющие предложения выходного языка и в целом текст результирующей программы.
Грамматика - это описание способа построения предложений некоторого языка. Для полного формального определения грамматики кроме правил порождения цепочек языка необходимо задать также алфавит языка.
Формально грамматика G определяется как четверка G(VT, VN,P,S), где
VT: множество терминальных символов;
VN: множество нетерминальных символов;
P: множество правил вывода
S:
начальный символ грамматики.
РБНФ в соответствии с вариантом:
<буква>::= A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z
<цифра> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<число>::= <целое> | <действительное>
<целое>::= <двоичное> | <восьмеричное> | <десятичное> |
<шестнадцатеричное>
<двоичное>::= {/ 0 | 1 /} (B | b)
<восьмеричное>::= {/ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 /} (O | o)
<десятичное>::= {/ <цифра> /} [D | d]
<шестнадцатеричное>::= <цифра> {<цифра> | A | B | C | D | E | F | a | b |
<действительное>::= <числовая_строка> <порядок> |
[<числовая_строка>] . <числовая_строка>[порядок]
<числовая_строка>::= {/ <цифра> /}
<порядок>::= ( E | e )[+ | -] <числовая_строка>
<идентификатор> ::= <буква> { <буква> | <цифра> }
<ключевое_слово> ::= or | and | not | integer | real | boolean| ass | if | then | else | for | to | do | while| read | write | true | false
<разделитель> ::= < > | = | < | <= | > | >= | + | - | * | / | ; | : | ( | ) | { | } | , | . |
<тип>::= integer | real | boolean
<описание>::= <тип> <идентификатор> { , <идентификатор> }
<оператор>::= <составной> | <присваивания> | <условный> | <фиксированного_цикла> | <условного_цикла> | <ввода> | <вывода>
<составной>::= <оператор> { ( : | перевод строки) <оператор> }
<операнд>::= <слагаемое> {<операции_группы_сложения> <операнд>}
<выражение>::=
<операнд>{<операции_группы_
<присваивания>::= <идентификатор> ass <выражение>
<условный>::= if <выражение> then <оператор> [ else <оператор>]
<фиксированного_цикла>::
<условного_цикла>::= while <выражение> do <оператор>
<ввода>::= read «(»<идентификатор> {, <идентификатор> } «)»
<вывода>::= write «(»<выражение> {, <выражение> } «)»
<программа>::= program var <описание> begin <оператор> {; <оператор>} end.
<операции_группы_
<операции_группы_
<операции_группы_
<унарная_операция>::= not
<слагаемое>::= <множитель> {<операции_группы_умножения> <множитель>}
<множитель>::= <идентификатор> | <число> | <логическая_константа> | <унарная_операция> <множитель> | «(»<выражение>«)»
<логическая_константа>::
Правила вывода грамматики модельного языка М:
P ® program var D1 begin S1 end.
D1 ® O;| D1;O;
O ® integer I1 | real I1 | boolean I1
I1 ® I | I1, I
S1 ® S |S1; S
Z1 ® : |ENTER
S ® S Z1 S | if E then S| if E then S else S | while E do S | for I ass E to E do S | read(I1) | write(E2) | I ass E
E2 ® E | E2 , E
E ® E1 | E1<>E1| E1=E1 | E1<E1 | E1<=E1|E1>E1 | E1>=E1
El ® T | T+E1 | T-E1 | T or El
T ® F | F*T | F/T | F and T
F ® I | N | L | not F | (E)
L ® true | false
I ® C | IC | IR
Z41 ® B | b
Z42 ® O | o
Z43 ® D | d
Z44 ® H | h
N ® R21Z41 | R81Z42 | R101 Z43 | R101 | R161Z44| V
R21® R2 | R21 R2
R81® R8 | R81 R8
R101® R10 | R101R10
R161® R10 | R161R16
Z2 ® + | -
Z3 ® E | e
V ® R101 P | .R101 P |R101 .R101 P | .R101 |R101 .R101
P ® Z3 Z2 R101 | Z3 R101
C ® A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z
R2 ® 0 | 1
R8 ® 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7
R10 ® 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
R16 ®
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F
Ниже
представлены диаграммы Вирта:
цифра
буква
идентификатор
число
целое
двоичное
десятичное
восьмиричное
Шестнадцатиричное
действительное
порядок
ключевое_слово
Разделитель
программа
описание
оператор
присваивания
условный
усл.
цикла
фикс. цикла
составной
ввода
вывода
выражение
слагаемое
множитель
операнд
логическая_константа
Примеры
программ для описываемого
языка
program
var integer k,n,sum,i;
boolean r;
begin
read(n);
sum ass 0
i ass 1;
while i<=n do
read(k)
sum ass sum+k {комментарий}
i ass i+1;
write(sum)
end.
program
var real a,b,c,d,e,x;
begin
a ass .35;
b ass 1.26;
c ass 5e-1;
d ass 1.2E-1;
e ass .3e+1;
x ass 154.36;
write(x)
end.
program
var integer i,a;
begin
read(a);
for i ass 0 to a do write (i)
end.
3 Структура программы
3.1 Лексический анализатор
Лексический анализатор (ЛА) – это первый этап процесса компиляции, на котором символы, составляющие исходную программу, группируются в отдельные минимальные единицы текста, несущие смысловую нагрузку – лексемы.
Задача лексического анализа - выделить лексемы и преобразовать их к виду, удобному для последующей обработки. ЛА использует регулярные грамматики.
ЛА необязательный этап компиляции, но желательный по следующим причинам:
1)
замена идентификаторов,
2)
ЛА уменьшает длину программы,
устраняя из ее исходного
3)
если будет изменена кодировка
в исходном представлении
В процедурных языках лексемы обычно делятся на классы:
- служебные слова;
- ограничители;
- числа;
- идентификаторы.
Каждая лексема представляет собой пару чисел вида (n, k), где n – номер таблицы лексем, k - номер лексемы в таблице.
Входные данные ЛА - текст транслируемой программы на входном языке.
Выходные данные ЛА - файл лексем в числовом представлении.
Для модельного языка М таблица служебных слов (1) будет иметь вид:
1)Program 2)var 3)begin 4)end 5)ass 6)or 7)and 8)not 9)for 10)to 11)do 12)read 13)write 14)if 15)then 16)else 17)while 18)true 19)false 20)integer 21)Boolean 22)real
Таблица ограничителей (2) содержит:
1)13 2)<> 3)<= 4)>= 5)= 6)< 7)> 8)+ 9)- 10)* 11)/ 12); 13): 14)( 15)) 16){ 17)} 18), 19). 20)W 21)R 22)! 23)!F 24)$ 25)%
Таблицы идентификаторов (4) и чисел (3) формируются в ходе лексического анализа.
Входные данные ЛА:
