Материалы представленные на сайте исключительно с целью ознакомления пользователям Интернета и не преследуют коммерческих целей или нарушение авторских прав.
© 2018 - 2024
Цель создания программы SINAN состоит в том, чтобы научить студента проверять правильность грамматики программы с помощью синтаксических деревьев (деревьев грамматического разбора).
Программа SINAN сама производит разбор программы, строит синтаксическое дерево и проверяет введенные пользователем данные на корректность, сообщая обо всех найденных ошибках и несоответствиях.
Таблица переходов
Существует два пути анализа: восходящий и нисходящий, данный проект реализован с помощью нисходящего, он называется рекурсивный спуск. В проекте грамматический разбор реализован с помощью правил БНФ грамматики, заданных в таблице переходов.
В таблице переходов с помощью специальных кодов реализованы ссылки, переходы, обозначения терминальных символов, идентификаторов и литералов, см. таблицу 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 |
Дата: 2019-05-29, просмотров: 167.