Главная: Рефераты

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

В качестве примера приводится пример разбора задания, описанного в приложении А.

2.3.7 Примерное задание для студента

Дана некоторая грамматика языка:

<prog> ::= PROGRAM <prog-name> VAR <dec-list> BEGIN <stmt-list> END.

<prog-name> ::= id

<dec-list> ::= <dec> | <dec-list> ; <dec>

<dec> ::= <id-list> : <type>

<type> ::= INTEGER

<id-list> ::= id | <id-list> , id

<stmt-list> ::= <stmt> | <stmt-list> ; <stmt>

<stmt> ::= <assign> | <for>

<assign> ::= id := <exp>

<exp> ::= <term> | <exp> + <term> | <exp> - <term>

<term> ::= id | int | ( <exp> )

<for> ::= FOR <index-exp> DO <body>

<index-exp> ::= id := <exp> TO <exp>

<body> ::= <stmt> | BEGIN <begin-list> END

Используя программу LEXAN произвести следующие действия:

Заполнить таблицу терминальных символов (таблица 1);

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

Заполнить таблицы: - символьных имен (таблица 2);

литералов (таблица 3);

лексического анализа (выходных символов);

Проверить правильность заполнения таблиц встроенным анализатором;

При наличии ошибок исправить имеющиеся, и повторно обработать программой LEXAN;

Получить листинг полученных результатов;

Сохранить результат в файл.

Пример выполнения приведен в приложении А.

2.3.8 Описание работы лексического анализатора

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

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

Если считанный символ является буквой или знаком подчеркивания «_», если да, то это либо ключевое слово, либо идентификатор. Далее считывается следующий символ (литера) и производится его проверка, входит ли этот символ во множество букв русского и латинского алфавитов, цифр, является ли он символом подчеркивания, если да, то полученный символ добавляется к строковой переменной, формирующей лексему. Дальнейшее считывание и обработка происходит до тех пор, пока не встретится какой либо другой символ.

Если считанный символ является цифрой, то далее происходит проверка, является ли следующий символ цифрой или точкой. Если полученная литера состоит из одних цифр, то полученное число целого (INTEGER) типа, если в литере есть точка, то число вещественного (REAL) типа.

Если считанный символ - одинарная кавычка, то текст, следующий за ней до следующей одинарной кавычки, будет являться строковой константой, а знаки кавычек будут определены как специальные символы.

Если считанный символ является знаком «{», то сам знак и следующие за ним символы до знака «}» включительно игнорируются, так как являются комментарием.

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

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

При обнаружении литерала, найденная лексема заносится в таблицу, в соответствующем поле заносится ее тип, далее указывается его размер в байтах. Затем заполняется таблица выходных кодов лексем.

В порядке распознавания лексем происходит заполнение таблицы выходных кодов лексем. Если распознанная лексема является терминальным символом, то в ячейку, соответствующую номеру таблицы, заносится номер 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

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
2012 © Все права защищены
При использовании материалов активная ссылка на источник обязательна.