Главная страница Случайная лекция
Мы поможем в написании ваших работ!
Порталы:
БиологияВойнаГеографияИнформатикаИскусствоИсторияКультураЛингвистикаМатематикаМедицинаОхрана трудаПолитикаПравоПсихологияРелигияТехникаФизикаФилософияЭкономика
Мы поможем в написании ваших работ!
Генерация ОПС для присваиваний и арифметических выражений с индексами
Вначале надо расширить грамматику арифметических выражений так, чтобы из начального нетерминала порождалось присваивание, и чтобы операндами могли быть индексируемые элементы массивов.
Пример 14. Грамматика присваиваний и арифметических выражений с индексами для одно- и двумерных массивов (A – начальный нетерминал) будет такой:
A → aH := S
S → S + T | T
T → T * F | F
F → (S) | aH
H → [S] | [S, S] | λ
Последняя группа порождающих правил (для нетерминала H) вносит неопределенность: две различные правые части начинаются с одного и того же терминального символа. Поэтому заменим эту группу правил на следующие правила, добавив в грамматику новый нетерминал:
H → [SK | λ
K → ] | , S]
После этого в грамматике устраним левую рекурсию и преобразуем ее к обобщенной нормальной форме Грейбах, в результате получим правила:
A → aH := S
S → (S)VU | aHVU
U → + TU | λ
T → (S)V | aHV
V → * FV | λ
F → (S) | aH
H → [SK | λ
K → ] | , S]
В табл. 17 представлен построенный по этим правилам LL(1)-анализатор, дополненный семантическими действиями для генерации ОПС. При этом правая часть правила A → aH := S в конце дополнена пустым символом □ для того, чтобы знак операции := генерировался после ОПС для выражения в правой части присваивания.
Табл. 17
| + | * | ( | ) | a | [ | ] | , | := | ┴ | |
| A | aH:=S□ a□□□:= | |||||||||
| S | (S)VU □□□□□ | aHVU a□□□ | ||||||||
| U | +TU □□+ | λ | λ | λ | λ | λ | λ | λ | λ | λ |
| T | (S)V □□□□ | aHV a□□ | ||||||||
| V | λ | *FV □□* | λ | λ | λ | λ | λ | λ | λ | λ |
| F | (S) □□□ | aH a□ | ||||||||
| H | λ | λ | λ | λ | λ | [SK □□□ | λ | λ | λ | λ |
| K | ] <i> | , S] □□<i2> |
Пусть на вход анализатора поступает цепочка M[i] := a*L[i, j + d]. Шаги ее анализа и генерации ОПС представлены в табл. 18. Для сокращения таблицы из нее удалены некоторые шаги, при выполнении которых подряд удаляются из магазина несколько нетерминалов.
Табл. 18
| № шага | Входные символы | Содержимое магазина | Дополнит. магазин | ОПС |
| M[i] := a*L[i, j + d]┴ | A ┴ | □□ | ||
| M[i] := a*L[i, j + d]┴ | aH:=S□┴ | a□□□:=□ | M | |
| [i] := a*L[i, j + d]┴ | H:=S□┴ | □□□:=□ | M | |
| [i] := a*L[i, j + d]┴ | [SK:=S□┴ | □□□□□:=□ | M | |
| i] := a*L[i, j + d]┴ | SK:=S□┴ | □□□□:=□ | M | |
| i] := a*L[i, j + d]┴ | aHVUK:=S□┴ | a□□□□□□:=□ | M i | |
| ] := a*L[i, j + d]┴ | HVUK:=S□┴ | □□□□□□:=□ | M i | |
| ] := a*L[i, j + d]┴ | K:=S□┴ | □□□:=□ | M i | |
| ] := a*L[i, j + d]┴ | ]:=S□┴ | <i>□□:=□ | M i <i> | |
| := a*L[i, j + d]┴ | :=S□┴ | □□:=□ | M i <i> | |
| a*L[i, j + d]┴ | S□┴ | □:=□ | M i <i> | |
| a*L[i, j + d]┴ | aHVU□┴ | a□□□:=□ | M i <i> a | |
| *L[i, j + d]┴ | HVU□┴ | □□□:=□ | M i <i> a | |
| *L[i, j + d]┴ | VU□┴ | □□:=□ | M i <i> a | |
| *L[i, j + d]┴ | *FVU□┴ | □□*□:=□ | M i <i> a | |
| L[i, j + d]┴ | FVU□┴ | □*□:=□ | M i <i> a | |
| L[i, j + d]┴ | aHVU□┴ | a□*□:=□ | M i <i> a L | |
| [i, j + d]┴ | HVU□┴ | □*□:=□ | M i <i> a L | |
| [i, j + d]┴ | [SKVU□┴ | □□□*□:=□ | M i <i> a L | |
| i, j + d]┴ | SKVU□┴ | □□*□:=□ | M i <i> a L | |
| i, j + d]┴ | aHVUKVU□┴ | a□□□□*□:=□ | M i <i> a L i | |
| , j + d]┴ | HVUKVU□┴ | □□□□*□:=□ | M i <i> a L i | |
| , j + d]┴ | KVU□┴ | □*□:=□ | M i <i> a L i | |
| , j + d]┴ | KVU□┴ | □*□:=□ | M i <i> a L i | |
| , j + d]┴ | , S]VU□┴ | □□<i2>*□:=□ | M i <i> a L i | |
| j + d]┴ | S]VU□┴ | □<i2>*□:=□ | M i <i> a L i | |
| j + d]┴ | aHVU]VU□┴ | a□□□<i2> … | M i <i> a L i j | |
| + d]┴ | HVU]VU□┴ | □□□<i2> … | M i <i> a L i j | |
| + d]┴ | U]VU□┴ | □<i2>*□:=□ | M i <i> a L i j | |
| + d]┴ | +TU]VU□┴ | □□+<i2>… | M i <i> a L i j | |
| d]┴ | TU]VU□┴ | □+<i2>*□:=□ | M i <i> a L i j | |
| d]┴ | aHVU]VU□┴ | a□□+<i2>… | M i <i> a L i j d | |
| ]┴ | HVU]VU□┴ | □□+<i2>… | M i <i> a L i j d | |
| ]┴ | U]VU□┴ | +<i2>*□:=□ | M i <i> a L i j d + | |
| ]┴ | ]VU□┴ | <i2>*□:=□ | M i<i>a L i j d+<i2> | |
| ┴ | VU□┴ | *□:=□ | M i<i>a L i j d+<i2>* | |
| ┴ | □┴ | :=□ | M i<i>a Li j d+<i2>*:= | |
| ┴ | ┴ | □ | M i<i>a Li j d+<i2>*:= |
Конец примера.
| <== предыдущая страница | | | следующая страница ==> |
| Вычисление ОПС для присваиваний и арифметических выражений с индексами | | | ОПС для условных, циклических и составных операторов |
Дата добавления: 2015-07-26; просмотров: 102; Нарушение авторских прав
Мы поможем в написании ваших работ!