Главная База знаний "Allbest" Программирование, компьютеры и кибернетика Программно-методический комплекс для обучения процессу создания компиляторов

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

Логическая структура компилятора. Лексический анализ. Сканер. Синтаксический и семантический анализ. Формирование промежуточного кода. Метод четверок. Обоснование создания учебного комплекса. Описание учебного языка. Таблица терминальных символов.

Рубрика Программирование, компьютеры и кибернетика
Вид дипломная работа
Язык русский
Дата добавления 16.11.2004
Размер файла 424,1 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Страница:

Таблица служит для хранения литералов, найденных в тексте программы. После внесения литерала в таблицу, в таблицу выходных кодов лексем заносится номер таблицы (№3) и спецификатор найденного элемента.

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

Работа сканера LEXAN происходит следующим образом. Студент в соответствующее поле пишет (или загружает из файла через меню) текст программы. Далее выбираются терминальные символы, необходимые для разбора текста программы и на основе правил разбора заполняются таблицы символических имен, литералов и выходных кодов лексем. После этого производится проверка правильности заполнения. При этом программа производит анализ текста и заполняет свои внутренние соответствующие таблицы и сравнивает с данными, полученными от студента и, при наличии ошибки, генерирует сообщения в поле сообщений. При необходимости можно получить листинг. Также можно сохранить результаты в файл для передачи данных на следующий этап - синтаксический анализ.

2.3.5 Структура листинга

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

2.3.6 Структура выходного файла

Выходной файл хранит в себе все 4 таблицы, построчно храня каждую ячейку. Это позволяет не ограничивать длину идентификаторов и ключевых слов. Вначале файла также построчно указываются размеры таблиц, сначала выбранных терминальных символов (число столбцов, число строк), затем символических имен, литералов и, наконец, выходных кодов лексем (только число столбцов). Структура промежуточного файла показана в таблице 9.

Таблица 9 - Пример промежуточного файла

№ строки

Содержи-мое

Описание содержимого

1

5

4 столбца + 1 (четвертый) зарезервирован

2

7

1 строка - заголовок таблицы, последующие 6 - строки с данными

3

5

5 столбцов

4

4

1 строка - заголовок таблицы, последующие 3 - строки с данными

5

5

5 столбцов

6

3

1 строка - заголовок таблицы, последующие 2 - строки с данными

7

16

1 столбец - описания, остальные 15 - с данными

(в таблице три строки)

8

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

…

7+5*7=42

43

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

…

42+5*4=62

63

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

…

62+5*3=77

78

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

…

77+16*3=125

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

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

Продолжение таблицы 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), обработка происходит в следующей последовательности:

если в ячейке возврата текущей строки нет знака %, то err:=0;

если параметр единственный (нет ИЛИ элемента) или это последний элемент последовательности ИЛИ, и в ячейке возврата текущей строки нет знака %, то генерировать ошибку «Должен быть элемент % в позиции %%», где % либо терминальный символ (или его код), либо “идентификатор”, либо “литера”; %% - позиция в таблице выходных символов;

при наличии нескольких параметров (разделенных элементом ИЛИ) и если текущий не последний из них, то перейти на следующий параметр, более правый, значение переменной err присвоить значение 0;

если номер столбца текущей ячейки - 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

<>

не равно

2.4.4 Формируемая таблица переходов. Правила заполнения

Таблица представляет собой набор ячеек. Столбцы и строки нумеруются. Столбцы определяют номер распознанной лексемы (элемента конструкции), строки определяют номер полученной конструкции.

В таблице могут существовать только два вида данных: указатели на таблицы и переходы.

Указатели на таблицы состоят из символа признака ссылки на таблицу «$», номера таблицы и, через запятую, кода (для терминального символа) или спецификатора. Номера таблиц: 1- таблица терминальных символов, 2 - таблица символических имен, 3 - таблица литералов.

Указатели на ячейки состоят из символа «@» и следующих за ним через запятую адресов столбца и строки, куда следует перейти, оказавшись в данной ячейке.

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

Чтобы заполнить формируемую таблицу переходов необходимо знать следующие правила.

Таблица заполняется в точности по БНФ, показанной на рисунке 4, при этом строки таблицы являются элементами конструкций данной грамматики. Разбор делается по данным, полученным из таблиц терминальных символов, символических имен, литералов, выходных кодов лексем.

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

При наличии вложенности конструкции (найден нетерминальный символ) создается (заполняется) новая строка, где в первой ячейке указывается адрес возврата: указатель перехода «@», номер строки, номер столбца, откуда осуществлен переход плюс один (т.е. переход на следующую ячейку за той, из которой был произведен вызов).

При наличии нескольких элементов, разделенных знаком «|», осуществляется перебор вариантов, которые подходят значениям, указанным в таблице выходных кодов.

При соответствии значения ячейки или одного из элементов ИЛИ терминальному символу указывается признак ссылки на таблицу «$», затем номер таблицы - 1 и код элемента в таблице терминальных символов (номер таблицы и код берется из таблицы кодов лексем).

При соответствии значения ячейки или одного из элементов ИЛИ идентификатору указывается признак ссылки на таблицу «$», затем номер таблицы - 2 и спецификатор (номер таблицы и спецификатор берется из таблицы кодов лексем).

При соответствии значения ячейки или одного из элементов ИЛИ литералу указывается признак ссылки на таблицу «$», затем номер таблицы - 3 и спецификатор (номер таблицы и спецификатор также берется из таблицы кодов лексем).

Подчеркнутые элементы в БНФ грамматике не обязательны (они могут отсутствовать).

2.4.5 Правила заполнения формируемой таблицы переходов

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

Заполнение формируемой таблицы переходов начинается со второй ячейки первой строки.

Для терминальных символов алгоритм может выглядеть таким образом.

Допустим, производится анализ первого элемента таблицы кодов лексем.

Номер позиции в таблице кодов лексем равен 1. Производится чтение данных из первого столбца таблицы кодов лексем. Полученное значение номера таблицы - 1 (таблица терминальных символов), код равен 1 (по таблице кодов - «объявление программы»).

Рассматривается первый элемент БНФ грамматики, им является ключевое слово PROGRAM, оно принадлежит таблице терминальных символов - 1, по таблице кодов определяется код, он равен 1.

Производится сравнение номеров таблиц, полученных на этапе 1 и этапе 2. Значения совпали.

Производится сравнение кодов таблиц. Значения совпали.

Во вторую ячейку первой строки формируемой таблицы переходов заносится указатель на таблицу 1, код 1 - «$1,1».

Номер позиции в таблице кодов лексем увеличивается на 1 (стает равным 2).

В грамматике БНФ начинает рассматриваться следующий элемент конструкции - нетерминальный символ <prog-name>.

Новое значение в формируемую таблицу переходов будет заноситься в правую ячейку от текущей (номер столбца увеличился на 1).

При несовпадении значений на этапах 3 и 4 происходит прекращение разбора, если только терминальный символ не является элементов массива ИЛИ - «|» (например <type> ::= INTEGER | REAL | STRING) или не является необязательным элементом конструкции (например, PROGRAM <prog-name>), тогда осуществляется переход на следующий элемент массива ИЛИ или переход к следующему элементу конструкции не входящему в данную группу необязательных элементов (подчеркиваются одной общей линией).

Для нетерминальных символов алгоритм примерно такой.

Допустим, производится анализ второго элемента таблицы кодов лексем. Текущая разбираемая лексема в грамматике БНФ является нетерминальным символом. В формируемой таблице переходов данные заносятся в третью ячейку первой строки.

Номер позиции в таблице кодов лексем равен 2. Производится чтение данных из второго столбца таблицы кодов лексем. Полученное значение номера таблицы - 2 (таблица символических имен), спецификатор равен 1.

Конструкция, определяющая структуру нетерминального символа <prog-name>, в грамматике БНФ имеет номер 2.

В формируемой таблице переходов добавляется новая строка, где в первую ячейку заносится адрес возврата на ячейку, вызвавшую переход, смещенную на 1 вправо (в данном случае указывается переход на четвертую ячейку первой строки - «@1,4»).

Номер позиции в таблице кодов лексем не изменяется (остается равным 2).

В грамматике БНФ начинает рассматриваться следующий элемент конструкции - id (идентификатор).

Новое значение в формируемую таблицу переходов будет заноситься в правую ячейку от текущей (в данном примере строка 2, столбец 2).

Для идентификаторов алгоритм примерно такой.

Допустим, производится анализ второго элемента таблицы кодов лексем. Текущая разбираемая лексема в грамматике БНФ находится в конструкции <prog-name> является первым ее элементом. В формируемой таблице переходов данные заносятся во вторую ячейку второй строки.

Номер позиции в таблице кодов лексем равен 2. Производится чтение данных из второго столбца таблицы кодов лексем. Полученное значение номера таблицы - 2 (таблица символических имен), спецификатор равен 1.

Рассматривается первый элемент БНФ грамматики конструкции <prog-name>, этот элемент является идентификатором, следовательно является элементом таблицы символических имен - таблицы 2.

Производится сравнение номеров таблиц. Значения совпали.

Во вторую ячейку второй строки заносится указатель на таблицу 2, спецификатор 1 (его значение берется из таблицы кодов лексем) - «$2,1»

Номер позиции в таблице кодов лексем увеличивается на 1 (стает равным 3).

В грамматике БНФ начинает рассматриваться следующий элемент конструкции <prog-name> - терминальный символ «;».

Новое значение в формируемую таблицу переходов будет заноситься в правую ячейку от текущей (номер столбца увеличился на 1) - вторая строка, третья ячейка.

При несовпадении значений на этапе 3, происходит прекращение разбора, если только текущий элемент не является элементов массива ИЛИ - «|» (например <factor> ::= id | int | real | <text-val> | (<exp>) ) или не является необязательным элементом конструкции (например, PROGRAM <prog-name>), тогда осуществляется переход на следующий элемент массива ИЛИ или переход к следующему элементу конструкции не входящему в данную группу необязательных элементов (подчеркиваются одной общей линией).

Если конструкция закончилась, то осуществляется переход на первую ячейку (ячейку возврата) текущей строки в формируемой таблице перехода. По значению адреса, содержащегося в ячейке возврата активной (готовой для внесения данных) стает ячейка с указанным номером строки и номером столбца. В грамматике БНФ осуществляется переход к элементу, следующему за элементом конструкции, который был определен в текущей конструкции. Например, после определения последнего элемента конструкции <prog-name> «;» осуществляется возврат к элементу, следующему за элементом, вызвавшим эту конструкцию. Возврат осуществлен на строку 1 грамматики БНФ, к элементу VAR, следующему за нетерминальным символом <prog-name>.

Для литералов алгоритм примерно такой.

Допустим, производится анализ шестнадцатого элемента таблицы кодов лексем. Текущая разбираемая лексема в грамматике БНФ находится в конструкции <factor> является вторым элементом конструкции ИЛИ. В формируемой таблице переходов данные заносятся во вторую ячейку десятой строки.

Номер позиции в таблице кодов лексем равен 16. Производится чтение данных из шестнадцатого столбца таблицы кодов лексем. Полученное значение номера таблицы - 3 (таблица литералов), спецификатор равен 1.

Рассматривается второй элемент множества ИЛИ БНФ грамматики конструкции <factor>, этот элемент является литералом целого типа, следовательно является элементом таблицы литералов - таблицы 3.

Производится сравнение номеров таблиц. Значения совпали.

Во вторую ячейку десятой строки заносится указатель на таблицу 3, спецификатор 1 (его значение берется из таблицы кодов лексем) - «$3,1»

Номер позиции в таблице кодов лексем увеличивается на 1 (стает равным 17).

В грамматике БНФ начинает рассматриваться следующий элемент конструкции <factor>, т.к. он отсутствует это говорит о том, что конец конструкции.

Вызывается обработка конца конструкции.

При несовпадении значений на этапе 3, происходит прекращение разбора, если только текущий элемент не является элементов массива ИЛИ - «|» (например <factor> ::= id | int | real | <text-val> | (<exp>) ) или не является необязательным элементом конструкции (например, PROGRAM <prog-name>), тогда осуществляется переход на следующий элемент массива ИЛИ или переход к следующему элементу конструкции не входящему в данную группу необязательных элементов (подчеркиваются одной общей линией).

Описание работы с элементами массива ИЛИ БНФ грамматики.

Если в БНФ грамматике встречается массив ИЛИ, перебор значений осуществляется с левого.

При возникновении ошибки при работе с одним из элементов массива ИЛИ осуществляется переход к следующему, находящемуся правее.

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

В случае положительного результата (сравнение одного из элементов удачно или сравнение с конечным результатом переходов удачно) происходит переход на следующую лексему грамматики БНФ, на следующий элемент таблицы кодов лексем, на следующую ячейку (на 1 правее) формируемой таблицы переходов.

Ниже рассматривается пример программы.

Program prog1;

var a,b,c:integer;

begin

a:=1+b*(a-c);

end.

Полученная последовательность символов от программы LEXAN представлена в таблице 12.

Таблица 12 - Таблица выходных символов

№ п.п.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

Таблица

1

2

1

1

2

1

2

1

2

1

1

1

1

2

1

Строка

1

1

27

2

2

29

3

29

4

31

5

27

3

2

28

№ п.п.

16

17

18

19

20

21

22

23

24

25

26

27

Таблица

3

1

2

1

1

2

1

2

1

1

1

1

Строка

1

32

3

34

35

2

33

4

36

27

4

30

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

Для лучшего понимания заполнения формируемой таблицы переходов заполняется таблица построений. Обработка данных и заполнение таблицы процесс довольно трудоемкий, однако, надо понимать, что и для машины данный разбор является самой трудоемкой задачей. Здесь же процесс разбора программы максимально унифицирован. Дается возможность отследить все возможные (исходные) параметры (значения). Прервать заполнение таблицы построений можно в любой момент времени, а потом продолжить, не теряя логику переходов (построения).

Таблица построений состоит из нескольких разделов, они называются: шаги, таблица кодов лексем, имя в программе, элемент грамматики БНФ, результат сравнения, формируемая таблица переходов, выполненное действие.

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

Таблица построения предлагается как вспомогательное средство для заполнения формируемой таблицы переходов. Заполнять все шаги и ячейки в ней не обязательно, главное понять логику заполнения формируемой таблицы переходов. Приобретя опыт, в дальнейшем, можно обходиться без таблицы построений, заполняя формируемую таблицу переходов по БНФ грамматике, тексту программы, таблице кодов терминальных символов, таблице кодов лексем.

Из данных, полученных в разделе «Формируемая таблица переходов, текущая позиция» таблицы построения, заполняется формируемая таблица переходов. В результате должна получиться таблица 14.

Принятые сокращения в таблице построений.

НС - нетерминальный символ

ТС - терминальный символ

ИД - идентификатор

Лх - литерал, где х: Ц - целый тип, В - вещественный тип, С - строковый тип.

Л - литерал любого типа.

Наличие знака «-» впереди типа у элемента грамматики БНФ показывает, что данный элемент в разборе может не участвовать.

При заполнении таблицы построений особую сложность представляет работа с переходами. Ниже описывается работа с ними.

При обнаружении терминального символа в грамматике БНФ, необходимо осуществить переход на первый элемент конструкции с тем же именем. В таблице построений определяется номер последней не занятой строки в формируемой таблице переходов. Номером следующей позиции указывается номер этой строки, номер столбца - 1. Значение вносимого значения должно указывать на вторую ячейку последней пустой строки. Следующим шагом заполняется значение текущий позиции, адрес возврата и адрес следующей позиции. Например. После нахождения терминального символа <prog-name> начинает рассматриваться первый элемент конструкции <prog-name> - id. В формируемой таблице переходов последней свободной строкой является строка 2, на нее и осуществляется переход, следующая позиция указывает на строку 2, столбец 1 (шаг 2). На третьем шаге в ячейку возврата 2,1 (где 2 - номер строки, 1 - номер столбца) будет внесено значение, указывающее на ячейку 1,4, т.к. переход осуществлен из ячейки 1,3. Текущая позиция - 2,1, следующая позиция - 2,2.

При возврате возникают другие трудности. К примеру, при окончании конструкции происходит переход на пустую ячейку, затем осуществляется переход на ячейку возврата. Значение, заполненное в ячейке возврата ищется по таблице. По полученному значению осуществляется переход. Например, при окончании конструкции <id-list> (шаг 20), текущей ячейкой оказывается ячейка 5,7. Затем производится переход в ячейку 5,1 (шаг 21). По таблице определяем, что адрес возврата @4,3 (значение из шага 14), т.е. перейти на четвертую строку, третий столбец.

Далее отыскивается положение в грамматике БНФ по имени предыдущей позиции. Например, после перехода в ячейку 4,3 (шаг 22) отыскиваем в таблице имя элемента грамматики ячейки 4,2 (значение из шага 13), им оказывается нетерминальный символ <id-list> конструкции <dec>. По грамматике БНФ определяется, что следующий элемент конструкции <dec> является «:».

Таблица 13 - Таблица построений

Шаги

Таблица кодов лексем

Имя в программе

Элемент грамматики БНФ

Результат сравнения

Формируемая таблица переходов

Выполненное действие

текущая позиция

следующая позиция

позиция

табл

код, специф

тип

имя

текущая конструкция

тип

табл

код

(для ТС)

строка

столбец

вносимое значение

строка

столбец

1

1

1

1

ТС

PROGRAM

PROGRAM

<prog>

-ТС

1

1

+

1

2

$1,1

1

3

2

2

2

1

ИД

Prog1

<prog-name>

<prog>

НС

1

3

@2,2

2

1

3

2

2

1

ИД

Prog1

2

1

@1,4

2

2

4

2

2

1

ИД

Prog1

id

<prog-name>

ИД

2

+

2

2

$2,1

2

3

5

3

1

27

ТС

;

;

<prog-name>

-ТС

1

27

+

2

3

$1,27

2

4

6

4

1

2

ТС

VAR

<prog-name>

2

4

2

1

конец конструкции

7

4

1

2

ТС

VAR

2

1

1

4

переход

8

4

1

2

ТС

VAR

VAR

<prog>

-ТС

1

2

+

1

4

$1,2

1

5

9

5

2

2

ИД

a

<dec-list>

<prog>

НС

1

5

@3,2

3

1

10

5

2

2

ИД

a

3

1

@1,6

3

2

11

5

2

2

ИД

а

<dec>

<dec-list>

НС

3

2

@4,2

4

1

12

5

2

2

ИД

а

4

1

@3,3

4

2

13

5

2

2

ИД

а

<id-list>

<dec>

НС

4

2

@5,2

5

1

14

5

2

2

ИД

а

5

1

@4,3

5

2

15

5

2

2

ИД

а

id

<id-list>

ИД

2

+

5

2

$2,2

5

3

16

6

1

29

ТС

,

,

<id-list>

ТС

1

29

+

5

3

$1,29

5

4

17

7

2

3

ИД

b

id

<id-list>

ИД

2

+

5

4

$2,3

5

5

18

8

1

29

ТС

,

,

<id-list>

ТС

1

29

+

5

5

$1,29

5

6

19

9

2

4

ИД

c

id

<id-list>

ИД

2

+

5

6

$2,4

5

7

20

10

1

31

ТС

:

<id-list>

5

7

5

1

конец конструкции

21

10

1

31

ТС

:

5

1

4

3

переход

22

10

1

31

ТС

:

:

<dec>

ТС

1

31

+

4

3

:

4

4

23

11

1

5

ТС

INTEGER

<type>

<dec>

НС

4

4

@6,1

6

1

24

11

1

5

ТС

INTEGER

6

1

@4,5

6

2

25

11

1

5

ТС

INTEGER

INTEGER

<type>

ТС

1

5

+

6

2

$1,5

6

3

26

12

1

27

ТС

;

<type>

6

3

6

1

конец конструкции

27

12

1

27

ТС

;

6

1

4

5

переход

28

12

1

27

ТС

;

<dec>

4

5

4

1

конец конструкции

29

12

1

27

ТС

;

4

1

3

3

переход

30

12

1

27

ТС

;

;

<dec-list>

-ТС

1

27

+

3

3

$1,27

3

4

31

13

1

3

ТС

BEGIN

<dec-list>

3

4

3

1

конец конструкции

32

13

1

3

ТС

BEGIN

3

1

1

6

переход

33

13

1

3

ТС

BEGIN

BEGIN

<prog>

ТС

1

3

+

1

6

$1,3

1

7

34

14

2

2

ИД

а

<stmt-list>

<prog>

-НС

1

7

@7,2

7

1

35

14

2

2

ИД

а

7

1

@1,8

7

2

36

14

2

2

ИД

а

<stmt>

<stmt-list>

НС

7

2

@8,2

8

1

37

14

2

2

ИД

a

8

1

@7,3

8

2

38

14

2

2

ИД

a

<assign>

<stmt>

НС

8

2

@9,2

9

1

39

14

2

2

ИД

a

9

1

@8,3

9

2

Продолжение таблицы 13

Шаги

Таблица кодов лексем

Имя в программе

Элемент грамматики БНФ

Результат сравнения

Формируемая таблица переходов

Выполненное действие

текущая позиция

следующая позиция

позиция

табл

код, специф

тип

имя

текущая конструкция

тип

табл

код

(для ТС)

строка

столбец

вносимое значение

строка

столбец

40

14

2

2

ИД

a

id

<assign>

ИД

2

+

9

2

$2,2

9

3

41

15

1

28

ТС

:=

:=

<assign>

ТС

1

28

+

9

3

$1,28

9

4

42

16

3

1

ЛЦ

1

<exp>

<assign>

НС

9

4

@10,2

10

1

43

16

3

1

ЛЦ

1

10

1

@9,5

10

2

44

16

3

1

ЛЦ

1

-

<exp>

--ТС

1

33

-

10

2

45

16

3

1

ЛЦ

1

<term>

<exp>

НС

10

2

@11,2

11

1

46

16

3

1

ЛЦ

1

11

1

@10,3

11

2

47

16

3

1

ЛЦ

1

<factor>

<term>

НС

11

2

@12,2

12

1

48

16

3

1

ЛЦ

1

12

1

@11,3

12

2

49

16

3

1

ЛЦ

1

id

<factor>

ИД

2

-

12

2

50

16

3

1

ЛЦ

1

int

<factor>

ЛЦ

3

+

12

2

$3,1

12

3

51

17

1

32

ТС

+

<factor>

12

3

12

1

конец конструкции

52

17

1

32

ТС

+

12

1

11

3

переход

53

17

1

32

ТС

+

*

<term>

ТС

1

34

-

11

3

54

17

1

32

ТС

+

DIV

<term>

ТС

1

17

-

11

3

55

17

1

32

ТС

+

/

<term>

ТС

1

37

-

11

3

56

17

1

32

ТС

+

<term>

11

3

11

1

конец конструкции

57

17

1

32

ТС

+

11

1

10

3

переход

58

17

1

32

ТС

+

+

<exp>

ТС

1

32

+

10

3

$1,32

10

4

59

18

2

3

ИД

b

<term>

<exp>

НС

10

4

@13,2

13

1

60

18

2

3

ИД

b

13

1

@10,5

13

2

61

18

2

3

ИД

b

<factor>

<term>

НС

13

2

@14,2

14

1

62

18

2

3

ИД

b

14

1

@13,3

14

2

63

18

2

3

ИД

b

id

<factor>

ИД

2

+

14

2

$2,3

14

3

64

19

1

34

ТС

*

<factor>

14

3

14

1

конец конструкции

65

19

1

34

ТС

*

14

1

13

3

переход

66

19

1

34

ТС

*

*

<term>

ТС

1

34

+

13

3

$1,34

13

4

67

20

1

35

ТС

(

<factor>

<term>

13

4

@15,2

15

1

68

20

1

35

ТС

(

<term>

15

1

@13,5

15

2

69

20

1

35

ТС

(

id

<factor>

ИД

2

-

15

2

70

20

1

35

ТС

(

int

<factor>

ЛЦ

3

-

15

2

71

20

1

35

ТС

(

real

<factor>

ЛВ

3

-

15

2

72

20

1

35

ТС

(

(

<factor>

ТС

1

35

+

15

2

$1,35

15

3

73

21

2

2

ИД

а

<exp>

<factor>

НС

15

3

@16,2

16

1

74

21

2

2

ИД

а

16

1

@15,4

16

2

75

21

2

2

ИД

а

-

<exp>

--ТС

1

33

-

16

2

76

21

2

2

ИД

а

<term>

<exp>

НС

16

2

@17,2

17

1

77

21

2

2

ИД

а

17

1

@16,3

17

2

78

21

2

2

ИД

а

<factor>

<term>

НС

17

2

@18,2

18

1

Продолжение таблицы 13

Шаги

Таблица кодов лексем

Имя в программе

Элемент грамматики БНФ

Результат сравнения

Формируемая таблица переходов

Выполненное действие

текущая позиция

следующая позиция

позиция

табл

код, специф

тип

имя

текущая конструкция

тип

табл

код

(для ТС)

строка

столбец

вносимое значение

строка

столбец

79

18

1

@17,3

18

2

80

21

2

2

ИД

а

id

<factor>

ИД

2

+

18

2

$2,2

18

3

81

22

1

33

ТС

-

18

3

18

1

конец конструкции

82

22

1

33

ТС

-

18

1

17

3

переход

83

22

1

33

ТС

-

*

<term>

ТС

1

34

-

17

3

84

22

1

33

ТС

-

DIV

<term>

ТС

1

17

-

17

3

85

22

1

33

ТС

-

/

<term>

ТС

1

37

-

17

3

86

22

1

33

ТС

-

17

3

17

1

конец конструкции

87

22

1

33

ТС

-

17

1

16

3

переход

88

22

1

33

ТС

-

+

<exp>

ТС

1

32

-

16

3

89

22

1

33

ТС

-

-

<exp>

ТС

1

33

+

16

3

$1,33

16

4

90

23

2

4

ИД

с

<term>

<exp>

НС

16

4

@19,2

19

1

91

23

2

4

ИД

с

19

1

@16,5

19

2

92

23

2

4

ИД

с

<factor>

<term>

НС

19

2

@20,2

20

1

93

23

2

4

ИД

с

20

1

@19,3

20

2

94

23

2

4

ИД

c

id

<factor>

ИД

2

+

20

2

$2,4

20

3

95

24

1

36

ТС

)

<factor>

20

3

20

1

конец конструкции

96

24

1

36

ТС

)

20

1

19

3

переход

97

24

1

36

ТС

)

*

<term>

-

19

3

98

24

1

36

ТС

)

DIV

<term>

-

19

3

99

24

1

36

ТС

)

/

<term>

-

19

3

100

24

1

36

ТС

)

<term>

19

3

19

1

конец конструкции

101

24

1

36

ТС

)

19

1

16

5

переход

102

24

1

36

ТС

)

+

<exp>

ТС

1

32

-

16

5

103

24

1

36

ТС

)

-

<exp>

ТС

1

33

-

16

5

104

24

1

36

ТС

)

<exp>

16

5

16

1

конец конструкции

105

24

1

36

ТС

)

16

1

15

4

переход

106

24

1

36

ТС

)

)

<factor>

ТС

1

36

+

15

4

$1,36

15

5

107

25

1

27

ТС

;

<factor>

15

5

15

1

конец конструкции

108

25

1

27

ТС

;

15

1

13

5

переход

109

25

1

27

ТС

;

*

<term>

ТС

1

34

-

13

5

110

25

1

27

ТС

;

DIV

<term>

ТС

1

17

-

13

5

111

25

1

27

ТС

;

/

<term>

ТС

1

37

-

13

5

112

25

1

27

ТС

;

13

5

13

1

конец конструкции

113

25

1

27

ТС

;

13

1

10

5

переход

114

25

1

27

ТС

;

+

<exp>

ТС

1

32

10

5

115

25

1

27

ТС

;

-

<exp>

ТС

1

33

10

5

116

25

1

27

ТС

;

10

5

10

1

конец конструкции

117

25

1

27

ТС

;

10

1

9

5

переход

Продолжение таблицы 13

Шаги

Таблица кодов лексем

Имя в программе

Элемент грамматики БНФ

Результат сравнения

Формируемая таблица переходов

Выполненное действие

текущая позиция

следующая позиция

позиция

табл

код, специф

тип

имя

текущая конструкция

тип

табл

код

(для ТС)

строка

столбец

вносимое значение

строка

столбец

118

25

1

27

ТС

;

<assign>

9

5

9

1

конец конструкции

119

25

1

27

ТС

;

9

1

8

3

переход

120

25

1

27

ТС

;

<stmt>

8

3

8

1

конец конструкции

121

25

1

27

ТС

;

8

1

7

3

переход

122

25

1

27

ТС

;

;

<stmt-list>

-ТС

1

27

+

7

3

$1,27

7

4

123

26

1

4

ТС

END

<stmt-list>

7

4

7

1

конец конструкции

124

26

1

4

ТС

END

7

1

1

8

переход

125

26

1

4

ТС

END

END

<prog>

ТС

1

4

+

1

8

$1,4

1

9

126

27

1

30

ТС

.

.

<prog>

ТС

1

30

+

1

9

$1,30

1

10

127

1

10

1

1

конец конструкции

128

1

1

Таблица 14 - Формируемая таблица переходов

1

2

3

4

5

6

7

8

9

10

1

PROGRAM

$1,1

<prog-name>

@2,2

VAR

$1,2

<dec-list>

@3,2

BEGIN

$1,3

<stmt-list>

@7,2

END

$1,4

.

$1,30

2

<prog-name>

@1,4

prog1

$2,1

;

$1,27

3

<dec-list>

@1,6

<dec>

@4,2

;

$1,27

4

<dec>

@3,3

<id-list>

@5,2

:

$1,31

<type>

@6,2

5

<id-list>

@4,3

a

$2,2

,

$1,29

b

$2,3

,

$1,29

c

$2,4

6

<type>

@4,5

INTEGER

$1,5

7

<stmt-list>

@1,8

<stmt>

@8,2

;

$1,27

8

<stmt>

@7,3

<assign>

@9,2

9

<assign>

@8,3

a

$2,2

:=

$1,28

<exp>

@10,2

10

<exp>

@9,5

<term>

@11,2

+

$1,32

<term>

@13,2

11

<term>

@10,3

<factor>

@12,2

12

<factor>

@11,3

1

$3,1

13

<term>

@10,5

<factor>

@14,2

*

$1,34

<factor>

@15,2

14

<factor>

@13,3

b

$2,3

15

<factor>

@13,5

(

$1,35

<exp>

@16,2

)

$1,36

16

<exp>

@15,4

<term>

@17,2

-

$1,33

<term>

@19,2

17

<term>

@16,3

<factor>

@18,2

18

<factor>

@17,3

a

$2,2

19

<term>

@16,5

<factor>

@20,2

20

<factor>

@19,3

c

$2,4

105

2.4.6 Построение деревьев

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

На основе введенных значений формируемой таблицы переходов в программу SINAN строится (формируется) синтаксическое дерево (дерево грамматического разбора).

Деревья могут быть представлены в вертикально как показано на рисунке 5, а и горизонтально - рисунок 5, б.

Рассмотрим выражение: a := c - (1 + b)

а)

б)

Рисунок 5 - а) вертикальное дерево, б) горизонтальное дерево

Рисунок 6 - Горизонтальное синтаксическое дерево

На рисунке 6 показано горизонтальное синтаксическое дерево, построенное по следующей программе:

PROGRAM prog1;

VAR a,b:INTEGER;

s:STRING;

BEGIN

b:=78;

s:='Дерево';

WRITE(s);

a:=b*(2+a);

END.

2.4.7 Семантический анализ

Функции семантического анализатора:

ведение табличных символов;

включение неявной информации (по умолчанию);

обнаружение ошибок;

макрообработка и операции, выполняемые во время компиляции.

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

Одно из предназначений семантического анализатора - поиск ошибок. Существуют следующие критерии поиска ошибок:

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

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

запрещается присвоение значению переменной одного типа значение другого типа (возможно только присвоение вещественному типу целого значения);

результат деления “ / “ всегда вещественное число;

перед использованием переменной (идентификатора) ей должно быть присвоено значение (данная ошибка не относится к критическим).

в цикле FOR, структуре <index-exp>, идентификатор должен быть целого типа, как и оба значения возвращаемые структурой <exp>.

Пример неправильно написанных элементов программы.

VAR

A,B,C:INTEGER;

C,D:REAL - повторное описание переменной C

BEGIN

A:=3.5; - присвоение переменной целого типа вещественного значения

B:=A/2; - присвоение переменной целого типа вещественного значения, образующегося при делении

D:=F*5; - не описана переменная F

FOR A:=1 TO D DO C:=C+A - переменная D вещественного типа

END.

2.5 Формирование промежуточного кода

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

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

Циклы

При адресации используются следующие команды.

C $BR - безусловный переход на позицию (индекс) в массиве, содержащем тетрады.

L $BRL - безусловный переход на метку

L - имя в таблице символов. Значение его - адрес перехода. Основная проблема при реализации этого оператора - определение адреса перехода.

<операнд1> <операнд2> BRZ|$BRM|$BRP|$BRMZ|$BRPZ

<операнд1> - значение арифметического выражения,

<операнд2> - номер или место позиции (адрес).

$BRZ - переход по значению 0,

$BRM - переход по значению <0,

$BRP - переход по значению >0,

$BRMZ - переход по значению <=0,

$BRPZ - переход по значению >=0.

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

FOR I=N1 TO N2 DO operator

может быть сконструирован на исходном языке:

I := N1;

L1: IF I>N2 THEN GOTO L2;

operator;

I:=I+1;

GOTO L1;

L2:

Представление конструкции FOR I=N1 TO N2 DO operator в виде тетрад показано в таблице 15.

Таблица 15 - конструкция for в виде тетрад

Выражения

Тетрады (четверки)

I:=N1

:=

N1

I

L1

IF I>N2 THEN GOTO L2

(IF N2-I<0 THEN GOTO L2)

-

$BRM

N2

L2

I

T1

T1

operator

operator

I:=I+1

+

I

1

I

GOTO L1

$BR

L1

L2

Далее рассмотрены циклы WHILE, REPEAT, а также конструкция IF…THEN…ELSE.

В таблице 16 разобрана конструкция WHILE a<b DO operator.

Таблица 16 - Конструкция while

Выражения

Тетрады (четверки)

L1

IF a-b>0 THEN

GOTO L2

-

$BRP

a

L2

b

T1

T1

operator

operator

GOTO L1

$BR

L1

L2

В таблице 17 разобрана конструкция REPEAT operator UNTIL a<b

Таблица 17 - Конструкция repeat

Выражения

Тетрады (четверки)

L1

operator

operator

IF a-b<0 THEN

GOTO L1

-

$BRM

a

L1

b

T1

T1

В таблице 18 разобрана конструкция IF a>b THEN operator1 ELSE operator2.

Таблица 18 - Конструкция if

Выражения

Тетрады (четверки)

L1

IF a-b<0 THEN

GOTO L2

-

$BRM

a

L2

b

T1

T1

operator1

operator1

GOTO L3

$BR

L1

L2

operator2

operator2

L3
ЭКОНОМИЧЕСКАЯ ЧАСТЬ
В данном разделе дипломного проекта рассмотрены следующие вопросы:
Определена трудоемкость анализа предметной области создания компилятора.
Определены затраты на анализ предметной области создания компилятора.
Определена трудоемкость создания учебного комплекса.
Определены затраты на создание учебного комплекса.
Определена трудоемкость разработки программного обеспечения для учебного комплекса.
Определены затраты на разработку программного обеспечения для учебного комплекса.
Определены суммарные затраты.

3 Определение трудоемкости по стадиям разработки

3.1 Методика расчета

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

Затраты времени, связанные с разработкой учебного комплекса составили 152 человеко-часа.

Для расчета затрат времени на разработку программной части использованы типовые нормы времени [10]. Нормы времени охватывают следующие стадии разработки:

техническое задание;

эскизный проект;

технический проект;

внедрение.

Нормы времени рассчитываются в человеко-часах при продолжительности рабочего дня - 8 ч.

Время, отведенное на выполнение дипломного проекта, составляет 4 месяца.

Для расчетов приняты:

степень новизны разрабатываемого комплекса - Б. Так как нет аналогичных решений;

сложность алгоритма - 2, так как включает создание отчетности, анализа и учета данных;

трудоемкость разработки - ПИ, так как информация постоянно видоизменяется;

принимая во внимание то, что существует перекрестная связь между входными данными, сложность организации контроля входной информации представлена группой 11;

сложность организации контроля выходной информации представлена группой 22, так как выводятся данные простой формы;

количество разновидностей форм входной информации - 1;

количество разновидностей форм выходной информации - 4.

Объем входной информации не превышает 50 тысяч документострок.

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

По табл. 1.1 [10] получен поправочный коэффициент для определения трудоемкости работ на стадии «Технический проект». Принимаем К=1,2.

По табл. 1.2 [10] получен поправочный коэффициент для определения трудоемкости работ на стадии «Рабочий проект». Принимаем К=1,44.

В табл. 1.4 [10] выбран коэффициент, учитывающий сложность контроля входной и выходной информации. Получаемый коэффициент К=1,07.

По таблице 1.7 определен поправочный коэффициент для определения времени работы ЭВМ при отладке и внедрении программ комплексов задач, принят равным 1,19, с учетом того, что программа пишется на языке высокого уровня в программной среде Delphi5.

Общий поправочный коэффициент Коб выражен через произведение всех коэффициентов.

Коб=1,2·1,44·1,07·1,19= 2,20

Норма времени (Нвр) с учетом общего поправочного коэффициента определяется по следующей формуле

, (1.1)

где Нврi - базисная норма времени, определенная по нормативной таблице, Коб - общий поправочный коэффициент.

Основной расчет трудоемкости программной части:

Разработка технического задания. По табл. 4.1 [10] значение человеко-дней - 36 (норма б8), при значении поправочного коэффициента 0,35 затраты времени равны 36·0,35 = 12,6 человеко-дней.

Разработка эскизного проекта. По табл. 4.2 [10] значение человеко-дней - 101 (норма б8), при значении поправочного коэффициента 0,3 затраты времени равны 101·0,3 = 30,3 человеко-дней.

Разработка технического проекта. По табл. 4.18 [10] значение человеко-дней - 8 (норма в1), при значении поправочного коэффициента Коб=2,20 затраты времени равны 8·2,20 = 17,6 человеко-дней.

Разработка рабочего проекта. По табл. 4.44 [10] значение человеко-дней - 59 (норма в1), при значении поправочного коэффициента 2,20 затраты времени равны 59·2,20 = 129,8 человеко-дней.

Разработка на внедрение. По табл. 4.70 [10] значение человеко-дней - 13 (норма в1), при значении поправочного коэффициента 2,20 затраты времени будут равны 13·2,20 = 28,6 человеко-дней.

Общая норма времени на создание программной части составляет

12,6+30,3+17,6+129,8+28,6 = 218,9 человеко-дней.

При продолжительности рабочего дня 8 ч, затраты на выполнение программной части составили

218,9·8 =1751 ч.

В связи с тем, что разрабатываемый комплекс программ для учебных целей, программа, реализованная на данном этапе незначительна по объему и сложности, является некоммерческой, для определения трудоемкости принимаем коэффициент пересчета Кпер = 0,1.

Тогда: трудоемкость разработки программной части составит

1751·0,1 = 175 ч.

Расчет общей трудоемкости разработки проекта (Тоб) производится по формуле

, (1.2)

где t - трудоемкость работ по стадиям проектирования (от 1 до n).

Суммируем затраты, связанные с разработкой проекта.

105 + 152 + 175 = 432 ч.

3.2 Определение затрат на выполнение проекта по стадиям разработки

Страница:


Подобные документы

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.

© 2000 — 2023, ООО «Олбест» Все права защищены