Реферат на тему "Программно методический комплекс для обучения процессу создания компиляторов"




Реферат на тему

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




Диплом на тему Программно методический комплекс для обучения процессу создания компиляторов

скачать

Найти другие подобные рефераты.

Диплом *
Размер: 209.36 кб.
Язык: русский
Разместил (а): Кузнецов Александр Иванович
Предыдущая страница 1 2 3 4 5 6 7 8 9 10 Следующая страница

добавить материал

При обнаружении литерала, найденная лексема заносится в таблицу, в соответствующем поле заносится ее тип, далее указывается его размер в байтах. Затем заполняется таблица выходных кодов лексем.
В порядке распознавания лексем происходит заполнение таблицы выходных кодов лексем. Если распознанная лексема является терминальным символом, то в ячейку, соответствующую номеру таблицы, заносится номер 1, если является идентификатором – номер 2, если литералом – 3. Спецификатор («код» для терминального символа) заносится в поле «Строка».
Далее происходит пошаговое сравнение значений, полученных программой, со значениями внесенными студентом. Сравнение происходит по таблице выходных кодов лексем. При каждом несоответствии генерируется сообщение в окне сообщений, что в такой-то позиции не верно заполнено значение номера таблицы, кода элемента, спецификатора.
Имеется возможность получения листинга в отдельный файл с расширением LOG.
Кроме того, необходимо сохранить файл для работы на следующем этапе синтаксического анализа.

2.4 Синтаксический анализатор SinAn

 
Цель создания программы SINAN состоит в том, чтобы научить студента проверять правильность грамматики программы с помощью синтаксических деревьев (деревьев грамматического разбора).
Программа SINAN сама производит разбор программы, строит синтаксическое дерево и проверяет введенные пользователем данные на корректность, сообщая обо всех найденных ошибках и несоответствиях.

2.4.1 Таблица переходов

 
Существует два пути анализа: восходящий и нисходящий, данный проект реализован с помощью нисходящего, он называется рекурсивный спуск. В проекте грамматический разбор реализован с помощью правил БНФ грамматики, заданных в таблице переходов.
В таблице переходов с помощью специальных кодов реализованы ссылки, переходы, обозначения терминальных символов, идентификаторов и литералов, см. таблицу 10. Нетерминальные символы представляют собой ссылки на конструкции, терминальные – указатели на код элемента соответствующей таблицы, идентификаторы и литералы представляют собой соответствующие обозначения. Для решения проблемы выбора одного из нескольких вариантов введен элемент ИЛИ, позволяющий реализовать все возможные варианты ветвления. Для реализации стека в каждой строке предусмотрена ячейка возврата, в которой указывается адрес, куда следует перейти после отработки соответствующей конструкции.
На основе данной таблицы производится анализ кодов лексем и создается новая формируемая таблица переходов, по которой в дальнейшем строится синтаксическое дерево.
Таблица переходов полностью основана на БНФ грамматике, показанной на рис. 4. Эта таблица предназначена для реализации синтаксического разбора с помощью метода рекурсивного спуска. С помощью нее можно определить законченность выражений, отследить грамматику учебного языка. Она служит основной базой при написании программы, хотя ее можно использовать и для построения формируемой таблицы переходов вручную.
На основе этой таблицы формируется другая (которую при необходимости легко можно преобразовать в дерево грамматического разбора), конечная таблица представляет собой программу, разобранную по грамматикам (на грамматики), представленную переходами (ссылками) и адресами таблиц и спецификаторов (№-в строк) на хранящиеся в них данные.
Работа с данной таблицей не оптимальна по скорости, т.к. при работе не используется стек, зато данное представление более наглядно.

Таблица 10 – Таблица переходов
 
 
1
2
3
4
5
6
7
8
9
1
<prog>
 
PROGRAM| 1,4
$1                |@1,4
<prog-name>
~2
VAR| 1,6
$2    | @1,6
<dec-list>
~3
BEGIN
$3
<stmt-list>
~7
END
$4
  .
$30
2
<prog-name>
 
 
+id
;
$27
 
 
 
 
 
 
3
<dec-list>
 
<dec>
~4
;
$27
<dec>|
  ~4    | @3,1
;
$27
 
@3,4
 
 
 
4
<dec>
 
<id-list>
~6
:
$31
<type>
~5
 
 
 
 
 
5
<type>
 
INTEGER| REAL | STRING
       $5      |     $6    |      $7
 
 
 
 
 
 
 
6
<+id-list>
 
 
+id
  ,   |
$29| @6,1
 
+id
 
@6,3
 
 
 
 
7
<stmt-list>
 
<stmt> |
   ~8     | @7,1
  ;   |
$27| @7,1
 
@7,2
 
 
 
 
 
 
8
<stmt>
 
<assign>|<for>|<read>|<write>|<for>|<while>|<repeat>| <if>  
     ~9     |  ~15 |   ~13   |   ~14   |  ~15 |   ~24     |   ~25     | ~21 
 
 
 
 
9
<assign>
 
 
+id
:=
$28
<exp>
~10
 
 
 
 
 
10
<exp>
 
   -   |   +  |
$33 | $32 | @10,3
<term>
~11
  +  |   -  |
$32| $33| @10,1
<term>
~11
 
@10,4
 
 
 
11
<term>
 
<factor>
~12
  *  | DIV |   /   |
$34|  $17 | $37|11,1
<factor>
~12
 
11,3
 
 
 
 
12
<factor>
 
                        
+id | ^int | ^real | ^string |@12,4
 
   (
$35| @12,1
<exp>
~10
  )
$36
 
 
 
13
<read>
 
READ
$19
  (
$35
<id-list>
    ~6
  )
$36
 
 
 
 
14
<write>
 
WRITE
$18
  (
$35
<VALUE>
     ~18
  ,    | 14,9
$29| @14,9
<VALUE>
~18
 
@14,5
 
  )
$36
15
<for>
 
FOR
$8
<index-exp>
~16
DO
$10
<body>
~17
 
 
 
 
16
<index-exp>
 
 
+id
:=
$28
<exp>
~10
TO|DOWNTO
 $9 |    $20
<exp>
~10
 
 
 
17
<body>
 
<stmt>| 17,4
   ~8     | @17,4
 
BEGIN
$3
<stmt-list>
END
$4
   ;  |
$27| @17,1
 
 
18
<value>
 
<id-list>| <text-val>
    ~6        | ~19
 
 
 
 
 
 
 
Продолжение таблицы 10
19
<text-val>
 

$38
<text>
~20

$38
 
 
 
 
 
20
<text>
 
 
^string
 
 
 
 
 
 
 
21
<if>
 
IF
$14
<сравнение>
~22
THEN
$15
<body>
~17
ELSE |
  $16  | @21,1
<body>
~17
 
 
22
<сравнение>
 
<factor>
~12
<условие>
~23
<factor>
~12
 
 
 
 
 
23
<условие>
 
  <  |  >  |  = | >= | <=| <>
$39|$40|$41|$42|$43|$44
 
 
 
 
 
 
 
24
<while>
 
WHILE
~13
<сравнение>
~22
DO
$10
<body>
~17
 
 
 
 
25
<repeat>
 
REPEAT
$11
<body>
~17
UNTIL
$12
<сравнение>
~22
 
 
 
 

2.4.2 Правила работы с таблицей переходов

 
Ячейкой возврата является первая ячейка каждой строки, ее описание: X,1, где Х – строка, 1 – столбец.
~x – переход на строку с номером х, столбец №2, формирование адреса возврата в первой ячейке, если переход был осуществлен от одного из параметров условий ИЛИ, то формирование адреса возврата и адреса перехода при ошибке (отрицательном результате).
| – элемент ИЛИ, предпочтение отдается более левому элементу. Перебором сравнивается каждый элемент, и если не один не подошел, то ошибка.
$x – в таблице переходов – номер строки в таблице терминальных символов
$x,y – в формируемой таблице переходов – одна из трех таблиц (x=1 – терминальных символов, x=2 –идентификаторов, x=3 – литер);
+id – таблица идентификаторов (№2) в таблице переходов.
Элементы, начинающиеся со знака ^ (int, real, string) в таблице переходов являются элементами таблицы литералов (№3).
@x,y,z – переход в строку x, столбец y, параметр z
@x,y,z%a,b,c – переход в строку x, столбец y, параметр z (при наличии элемента ИЛИ), при наличии ошибки в a,b,c (указывается только в ячейках возврата, формируется только при присутствии элемента ИЛИ)
Переход по ошибке (значение после знака % в ячейке возврата) действует только для ячеек столбца №2.
Алгоритмы:
Используются таблицы Table_Perehod[i,j], Table_Perehod1[i1,j1]
Table_Perehod –основная таблица перехода
Table_Perehod1 – формируемая таблица перехода
[i,j] – адреса ячеек внутри Table_Perehod, i – столбцы, j – строки
[i1,j1] – адреса ячеек внутри Table_Perehod1, i1 – столбцы, j1 – строки
count_vs – счетчик перемещения, показывающий текущее положение в таблице выходных символов (Tabl_vs);
pos – номер позиции в ячейке (при наличии элемента ИЛИ).
Таблица №1 – таблица терминальных символов.
Таблица №2 – таблица символических имен (идентификаторов).
Таблица №3 – таблица литералов.
Просмотр осуществляется слева направо, и по переходам. Каждый раз происходит сравнение с текущим элементом из таблицы выходных символов.
При положительном результате сравнения (терминальных символов, идентификаторов, литер), осуществляется переход на более правую ячейку.
При отрицательном результате (err=1), обработка происходит в следующей последовательности:
1)    если в ячейке возврата текущей строки нет знака %, то err:=0;
2)    если параметр единственный (нет ИЛИ элемента) или это последний элемент последовательности ИЛИ, и в ячейке возврата текущей строки нет знака %, то генерировать ошибку «Должен быть элемент % в позиции %%», где % либо терминальный символ (или его код), либо “идентификатор”, либо “литера”; %% – позиция в таблице выходных символов;
3)    при наличии нескольких параметров (разделенных элементом ИЛИ) и если текущий не последний из них, то перейти на следующий параметр, более правый, значение переменной err присвоить значение 0;
4)    если номер столбца текущей ячейки – 2, то если в ячейке возврата есть знак %, то перейти по адресу, указанному за знаком % и:
-         в таблице переходов очистить ячейку возврата, 
-         в формируемой таблице переходов удалить последнюю строку.

2.4.3 Правила таблицы переходов для написания программы

 
Если ячейка пуста, то осуществляется переход на первую ячейку текущей строки, i:=1.
Если значение в ячейке типа x,y или x,y,z, то необходимо перейти на строку х, ячейку y, позицию z. При этом: после перехода в указанную ячейку на указанную позицию ячейка с адресом перехода, если она является ячейкой возврата, очищается (Table_Perehod[i,j]:=’’; i:=y; j:=x; pos:=z), в формируемой таблице переходов происходит переход в ячейку, указанную в первой ячейке строки без очищения ее значения (i1:=y; j1:=x).
Если значение в ячейке типа x,y%a,b,c, при этом err=1 и номер столбца равен 2 (i=2), то следует перейти по ссылке a,b,c, очистить ячейку возврата таблицы переходов (Table_Perehod[i,j]:=’’; i:=b; j:=a; pos:=c), в формируемой таблице переходов перейти по адресу возврата и удалить последнюю строку (i1:=y; j1:=x).
Если значение в ячейке типа x,y%a,b,c, и err=0, то перейти по ссылке x,y, в формируемой таблице переходов перейти по адресу, указанному в текущей ячейке.
Если номер столбца текущей ячейки = 3 и err<>0, то в ячейке возврата удалить при наличии знак % и значения за ним.
Если первый символ ^ – значение в ячейке является литерой (таблица литералов – №3). Осуществляемая при этом проверка: если в таблице выходных символов № текущей таблицы равен 3 (if Tabl_vs[count_vs,2]=’3’), то занести в текущую ячейку формируемой таблицы № таблицы (3) и № строки в ней (Table_Perehod1[i1,j1]:=$3,№строки), перейти на следующую ячейку (i:=i+1; i1:=i1+1; count_vs:=count_vs+1). В случае отрицательного результата сравнения переменной err присваивается значение 1.
Если первый символ $ – значение в ячейке является терминальным символом (таблица терминальных символов – №1). Осуществляемая проверка: если в таблице выходных символов № текущей таблицы равен 1 (if Tabl_vs[count_vs,2]=’1’), то занести в текущую ячейку формируемой таблицы № таблицы (1) и № строки в ней (Table_Perehod1[i1,j1]:=$1,код), перейти на следующую ячейку (i:=i+1; i1:=i1+1; count_vs:=count_vs+1). В случае отрицательного результата сравнения переменной err присваивается значение 1.
Если первый символ ~ – это переход на вторую ячейку строки с номером, указанным за символом ~, в формируемой таблице переходов добавляется новая строка и переход осуществляется на нее. При этом осуществляется следующее: в первую ячейку (ячейку возврата) указанной строки заносится адрес возврата: если переход осуществляется с одной из позиций с элементом ИЛИ и не является последним в списке, то в ячейке возврата формируется код возврата типа x,y,z, где x – номер строки, y – номер столбца, z – номер позиции откуда был произведен переход (x:=j; y:=i; z:=pos; j:=a; i:=2, где а номер строки в адресе перехода – ~a), тоже происходит и в формируемой таблицей переходов (x:=j1; y:=i1; j1:=№последней строки; i1:=2).
Коды терминальных символов показаны в таблице 11.

Таблица 11 – Таблица кодов терминальных символов
Код
Терминальный символ
Комментарий
 
 
1
PROGRAM
объявление программу
 
 
2
VAR
объявление переменных
 
 
3
BEGIN
начало тела
 
 
4
END
конец тела
 
 
5
INTEGER
тип целое
 
 
6
REAL
вещественный тип
 
 
7
STRING
строковый тип
 
 
8
FOR
цикл с параметром – ДЛЯ
 
 
9
TO
цикл с параметром – ДО
 
 
10
DO
ВЫПОЛНИТЬ
 
 
11
REPEAT
цикл с постусловием – ПОВТОРЯТЬ
 
 
12
UNTIL
цикл с постусловием – ПОКА НЕ
 
 
13
WHILE
цикл с предусловием – ПОКА
 
 
14
IF
условный оператор – ЕСЛИ
 
 
15
THEN
условный оператор – ТО
 
 
16
ELSE
условный оператор – ИНАЧЕ
 
 
17
DIV
делить на цело
 
 
18
WRITE
вывести на консоль
 
 
19
READ
считать с консоли
 
 
20
DOWNTO
цикл с параметром – ДО
 
 
21
FUNCTION
функция
 
 
22
PROCEDURE
процедура
 
 
23
{
начало комментария
 
 
24
}
конец комментария
 
 
25
[
открытие квадратных скобок
 
 
26
]
закрытие квадратных скобок
 
 
27
;
конец операции
 
 
28
:=
присвоить значение
 
 
29
,
разделитель
 
 
30
.
конец программы/отделение дробной части
 
 
31
:
разделение идентификатора от его типа
 
 
32
+
оператор сложения
 
 
33
-
оператор вычитания
 
 
34
*
оператор умножения
 
 
35
(
открывающаяся скобка
 
 
36
)
закрывающаяся скобка
 
 
37
/
оператор деления
 
 
38
΄
кавычка
 
 
39

меньше
 
 
40

больше
 
 
41
=
равно
 
 
42
>=
больше или равно
 
 
43
<=
меньше или равно
 
 
44
<> 
не равно
 
 
Предыдущая страница 1 2 3 4 5 6 7 8 9 10 Следующая страница


Программно методический комплекс для обучения процессу создания компиляторов

Скачать дипломную работу бесплатно


Постоянный url этой страницы:
http://referatnatemu.com/?id=544&часть=6



вверх страницы

Рейтинг@Mail.ru
Copyright © 2010-2015 referatnatemu.com