Формальные языки, грамматики и основы построения трансляторов. Кревский И.Г - 75 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

75
грамматики, то w = γ
n
, где γ
n
– п-я правосентенциальная форма некоторого,
еще неизвестного правого порождения
wγγ...γγγS
n
rm
1n
rmrm
2
rm
1
rm
0
rm
=
⇒⇒⇒⇒⇒⇒
−
Для воссоздания этого порождения в обратном порядке мы находим
основу β
n
в γ
n
и заменяем ее левой частью продукции А
n
→ β
n
, для получения
(n-1)-й сентенциальной формы γ
n-1
. Заметим, что пока мы не знаем, каким
образом искать основы, но вскоре познакомимся с соответствующими
методами.
Затем мы повторяем описанный процесс, т.е. находим в γ
n-1
основу β
n-1
и свертываем ее для получения правосентенциальной формы γ
n-2
. Если после
очередного шага правосентенциальная форма содержит только стартовый
символ S, мы прекращаем процесс и сообщаем об успешном завершении
анализа. Обращенная последовательность продукций, использованных в
свертках, представляет собой правое порождение входной строки.
Пример 13.b
Рассмотрим грамматику (13.1) из примера 13.a и входную строку
id
1
+id
2
*id
3
. Последовательность сверток, приводящая входную строку к
стартовому символу E, показана в таблице 13.1. Следует отметить, что
последовательность правосентенциальных форм в этом примере
представляет собой обращение первой последовательности правых
порождений из примера 13.a.
Таблица 13.1. Свертки, выполняемые ПС-анализатором
правосентенциальная
форма
основа сворачивающая
продукция
id
1
+id
2
*id
3
id
1
Е→ id
E+id
2
*id
3
id
2
Е→ id
E+E*id
3
id
3
Е→ id
E+E*E E*E
Е→ E*E
E+E E+E
Е→ E+E
Е 
                                                                                  75
грамматики, то w = γn, где γn – п-я правосентенциальная форма некоторого,
еще неизвестного правого порождения
     S ⇒ γ0 ⇒γ1 ⇒γ2 ⇒ ...⇒γn−1 ⇒γn = w
       rm   rm    rm   rm   rm     rm


     Для воссоздания этого порождения в обратном порядке мы находим
основу βn в γn и заменяем ее левой частью продукции Аn → βn, для получения
(n-1)-й сентенциальной формы γn-1 . Заметим, что пока мы не знаем, каким
образом искать основы, но вскоре познакомимся с соответствующими
методами.
     Затем мы повторяем описанный процесс, т.е. находим в γn-1 основу βn-1
и свертываем ее для получения правосентенциальной формы γn-2. Если после
очередного шага правосентенциальная форма содержит только стартовый
символ S, мы прекращаем процесс и сообщаем об успешном завершении
анализа. Обращенная последовательность продукций, использованных в
свертках, представляет собой правое порождение входной строки.
Пример 13.b
     Рассмотрим грамматику (13.1) из примера 13.a и входную строку
id1+id2*id3. Последовательность сверток, приводящая входную строку к
стартовому символу E, показана в таблице 13.1. Следует отметить, что
последовательность          правосентенциальных          форм   в   этом     примере
представляет       собой         обращение     первой   последовательности   правых
порождений из примера 13.a.

                            Таблица 13.1. Свертки, выполняемые ПС-анализатором
                 правосентенциальная         основа     сворачивающая
                         форма                            продукция
                    id1+id2*id3              id1           Е→ id
                    E+id2*id3                id2           Е→ id
                    E+E*id3                  id3           Е→ id
                    E+E*E                    E*E           Е→ E*E
                    E+E                      E+E           Е→ E+E
                    Е

Страницы