Методические указания (1114907), страница 11
Текст из файла (страница 11)
Данный подграф отражает первую строку таблицы. Остальные строки строятся аналогично. В случае равенства приоритетов две функции соединяются в одну вершину. Как будет показано далее.
Далее в полученном графе находим самые длинные пути от каждой группы f и g. Они и будут являться соответствующими значениями функций приоритетов.
В итоге получаем таблицу значений функций приоритетов.
| + | - | * | / | ^ | u | ( | ) | id | $ | |
| f | 2 | 2 | 4 | 4 | 6 | 7 | 0 | 10 | 12 | 0 |
| g | 1 | 1 | 3 | 3 | 5 | 8 | 9 | 0 | 11 | 0 |
-
Приведем пример разбора трех операторных выражений.
Подчеркиванием обозначается символ, на котором установлен указатель.
А) (id+id*id)^id^id-id
| Входной поток | Стек | Результат | Комментарий |
| (id+id*id)^id^id-id$ | $ | Помещаем в стек ‘(‘, т.к. $ <∙ ‘(‘ | |
| id+id*id)^id^id-id$ | ($ | Помещаем в стек id, т.к. ‘(‘<∙ id | |
| +id*id)^id^id-id$ | id($ | id | Снимаем id со стека, т.к. id ∙> +, затем устанавливаем, что ‘(‘ <∙ id, поэтому больше символов со стека не снимаем |
| +id*id)^id^id-id$ | ($ | id | Помещаем в стек +, т.к. ‘(‘ <∙ + |
| id*id)^id^id-id$ | +($ | id | Помещаем в стек id, т.к. + <∙ id |
| *id)^id^id-id$ | id+($ | id id | Снимаем id со стека, т.к. id ∙> *, затем устанавливаем, что + <∙ id, поэтому больше символов со стека не снимаем |
| *id)^id^id-id$ | +($ | id id | Помещаем в стек *, т.к. + <∙ * |
| id)^id^id-id$ | *+($ | id id | Помещаем в стек id, т.к. * <∙ id |
| )^id^id-id$ | id*+($ | id id id | Снимаем id со стека, т.к. id ∙> ‘)‘, затем устанавливаем, что * <∙ id, поэтому больше символов со стека не снимаем |
| )^id^id-id$ | *+($ | id id id * | Снимаем * со стека, т.к. * ∙> ‘)‘, затем устанавливаем, что + <∙ *, поэтому больше символов со стека не снимаем |
| )^id^id-id$ | +($ | id id id * + ( | Снимаем + со стека, т.к. + ∙> ‘)‘, затем устанавливаем, что ‘(‘ |
| )^id^id-id$ | $ | id id id * + ( | Помещаем в стек ‘)’, т.к. $ <∙ ‘)’ |
| ^id^id-id$ | )$ | id id id * + ( ) | Снимаем ‘)’ со стека, т.к. ‘)’ ∙> ^, затем устанавливаем, что $ <∙ ‘)’, поэтому больше символов со стека не снимаем |
| ^id^id-id$ | $ | id id id * + ( ) | Помещаем в стек ^, т.к. $ <∙ ^ |
| id^id-id$ | ^$ | id id id * + ( ) | Помещаем в стек id, т.к. ^ <∙ id |
| ^id-id$ | id^$ | id id id * + ( ) id | Снимаем id со стека, т.к. id ∙> ^, затем устанавливаем, что ^ <∙ id, поэтому больше символов со стека не снимаем |
| ^id-id$ | ^$ | id id id * + ( ) id | Помещаем в стек ^, т.к. ^ <∙ ^ |
| id-id$ | ^^$ | id id id * + ( ) id | Помещаем в стек id, т.к. ^ <∙ id |
| -id$ | id^^$ | id id id * + ( ) id id | Снимаем id со стека, т.к. id ∙> -, затем устанавливаем, что ^ <∙ id, поэтому больше символов со стека не снимаем |
| -id$ | ^^$ | id id id * + ( ) id id ^ | Снимаем ^ со стека, т.к. ^ ∙> -, затем устанавливаем, что ^ <∙ ^, поэтому больше символов со стека не снимаем |
| -id$ | ^$ | id id id * + ( ) id id ^ ^ | Снимаем ^ со стека, т.к. ^ ∙> -, затем устанавливаем, что $ <∙ ^, поэтому больше символов со стека не снимаем |
| -id$ | $ | id id id * + ( ) id id ^ ^ | Помещаем в стек -, т.к. $ <∙ - |
| id$ | -$ | id id id * + ( ) id id ^ ^ | Помещаем в стек id, т.к. - <∙ id |
| $ | id-$ | id id id * + ( ) id id ^ ^ id | Снимаем id со стека, т.к. id ∙> $, затем устанавливаем, что - <∙ id, поэтому больше символов со стека не снимаем |
| $ | -$ | id id id * + ( ) id id ^ ^ id - | Снимаем - со стека, т.к. - ∙> $, затем устанавливаем, что $ <∙ -, поэтому больше символов со стека не снимаем |
| $ | $ | id id id * + ( ) id id ^ ^ id - | Символ на вершине стека и текущий символ входного потока равны $, таким образом выражение успешно разобрано. |
‘)’, поэтому снимаем ‘(’ со стека. Далее устанавливаем, что $ <∙ ‘(‘, поэтому больше символов со стека не снимаемБ) (id+id*id)id^id-id
| Входной поток | Стек | Результат | Комментарий |
| (id+id*id)id^id-id$ | $ | Помещаем в стек ‘(‘, т.к. $ <∙ ‘(‘ | |
| id+id*id)id^id-id$ | ($ | Помещаем в стек id, т.к. ‘(‘<∙ id | |
| +id*id)id^id-id$ | id($ | id | Снимаем id со стека, т.к. id ∙> +, затем устанавливаем, что ‘(‘ <∙ id, поэтому больше символов со стека не снимаем |
| +id*id) id^id-id$ | ($ | id | Помещаем в стек +, т.к. ‘(‘ <∙ + |
| id*id)id^id-id$ | +($ | id | Помещаем в стек id, т.к. + <∙ id |
| *id)id^id-id$ | id+($ | id id | Снимаем id со стека, т.к. id ∙> *, затем устанавливаем, что + <∙ id, поэтому больше символов со стека не снимаем |
| *id)id^id-id$ | +($ | id id | Помещаем в стек *, т.к. + <∙ * |
| id)id^id-id$ | *+($ | id id | Помещаем в стек id, т.к. * <∙ id |
| )id^id-id$ | id*+($ | id id id | Снимаем id со стека, т.к. id ∙> ‘)‘, затем устанавливаем, что * <∙ id, поэтому больше символов со стека не снимаем |
| )id^id-id$ | *+($ | id id id * | Снимаем * со стека, т.к. * ∙> ‘)‘, затем устанавливаем, что + <∙ *, поэтому больше символов со стека не снимаем |
| )id^id-id$ | +($ | id id id * + ( | Снимаем + со стека, т.к. + ∙> ‘)‘, затем устанавливаем, что ‘(‘ |
| )id^id-id$ | $ | id id id * + ( | Помещаем в стек ‘)’, т.к. $ <∙ ‘)’ |
| id^id-id$ | )$ | id id id * + ( ) | Обнаруживаем пустую ячейку в таблице приоритетов. (Ячейка [‘)’,id]. Анализ завершился с ошибкой. |
B) (id+idid)^id^id-id
| Входной поток | Стек | Результат | Комментарий |
| (id+idid)^id^id-id$ | $ | Помещаем в стек ‘(‘, т.к. $ <∙ ‘(‘ | |
| id+idid)^id^id-id$ | ($ | Помещаем в стек id, т.к. ‘(‘<∙ id | |
| +idid)^id^id-id$ | id($ | id | Снимаем id со стека, т.к. id ∙> +, затем устанавливаем, что ‘(‘ <∙ id, поэтому больше символов со стека не снимаем |
| +idid)^id^id-id$ | ($ | id | Помещаем в стек +, т.к. ‘(‘ <∙ + |
| idid)^id^id-id$ | +($ | id | Помещаем в стек id, т.к. + <∙ id |
| id)^id^id-id$ | id+($ | id id | Обнаруживаем пустую ячейку в таблице приоритетов. (Ячейка [id, id]. Анализ завершился с ошибкой. |
Задача 5. «Синтаксически управляемая трансляция»
Теоретическая часть:
Промежуточный код может иметь три типа представления:
-
Синтаксические деревья
-
Постфиксная запись
-
Трехадресный код
Далее подробнее о каждом типе представления. Постфиксная запись в данной задаче рассматриваться не будет.
Синтаксические деревья
Синтаксические деревья бывают двух видов: собственно синтаксическое дерево и даг. Синтаксическое дерево изображает естественную иерархическую структуру исходной программы. В свою очередь, даг дает ту же информацию, но в более компактном виде (одинаковые подвыражения в нем объединены).
Приведем пример графического представления синтаксического дерева и дага для инструкции присваивания a := b * -c + b * -c. Данный пример не описывает всю специфику представления промежуточного кода в виде синтаксических деревьев. Более подробный пример будет приведен в разборе задачи.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
