Основы трансляции - 10 стр.

UptoLike

ВУЗ: 

ВПИ ВолгГТУ | Волжский

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

Рубрика: 

10
Эта грамматика является леворекурсивной. Построим эквивалентную ей
нелеворекурсивную грамматику .
Шаг 1. Обозначим , .
Тогда правила грамматики будут иметь вид:
Шаг 2. Для имеем правила . Их можно
записать в виде , где , , .
Запишем новые правила для множества :
Добавим эти правила в , а символы и во множество нетерминальных
символов, получим: .
Шаг 3. . Построение не закончено: , .
Шаг 4. Для символа в множестве правил нет правила вида ,
поэтому на этом шаге никаких действий не выполняем.
Шаг 5. , переходим опять к шагу 2.
Шаг 2. Для имеем правила . Их можно записать
в виде , где , , .
Запишем новые правила для множества :
Добавим эти правила в , а символы и во множество нетерминальных
символов, получим: .
Шаг 3. . Построение не закончено: , .
Шаг 4. Для символа в множестве правил нет правила вида ,
поэтому на этом шаге никаких действий не выполняем.
Шаг 5. , переходим к шагу 4.
Шаг 4. Для символа в множестве правил нет правила вида ,
поэтому на этом шаге никаких действий не выполняем.
Шаг 5. , переходим опять к шагу 2.
Шаг 2. Для имеем правила . Эти правила не содержат
левой рекурсии. Переносим их в , а символ добавляем в . Получим
.
Шаг 3. . Построение грамматики закончено.
В результате выполнения алгоритма преобразования получили
нелеворекурсивную грамматику
G
0
= (f+; ¡; =; ¤; a; bg; fA
1
; A
0
1
; A
2
; A
0
2
; A
3
g ; A
1
; R
0
)
, 
  Эта грамматика является леворекурсивной. Построим эквивалентную ей
нелеворекурсивную грамматику .
  Шаг 1. Обозначим               ,     .
  Тогда правила грамматики будут иметь вид:



   Шаг 2. Для      имеем правила                                         . Их можно
записать в виде                   , где                  ,           ,       .
   Запишем новые правила для множества           :


   Добавим эти правила в , а символы       и   во множество нетерминальных
символов, получим:                .
   Шаг 3.         . Построение не закончено:               ,     .
   Шаг 4. Для символа     в множестве правил      нет правила вида          ,
поэтому на этом шаге никаких действий не выполняем.
   Шаг 5.             , переходим опять к шагу 2.
   Шаг 2. Для    имеем правила                            . Их можно записать
в виде                      , где        ,         ,         .
   Запишем новые правила для множества :


   Добавим эти правила в , а символы           и     во множество нетерминальных
символов, получим:                          .
   Шаг 3.         . Построение не закончено:                       ,        .
   Шаг 4. Для символа       в множестве правил          нет правила вида               ,
поэтому на этом шаге никаких действий не выполняем.
   Шаг 5.              ,                  переходим к шагу 4.
   Шаг 4. Для символа       в множестве правил          нет правила вида               ,
поэтому на этом шаге никаких действий не выполняем.
   Шаг 5.                , переходим опять к шагу 2.
   Шаг 2. Для     имеем правила                          . Эти правила не содержат
левой рекурсии. Переносим их в , а символ                  добавляем в        . Получим
                         .
   Шаг 3.           . Построение грамматики закончено.
   В результате выполнения алгоритма преобразования получили
нелеворекурсивную грамматику
               G0 = (f+; ¡; =; ¤; a; bg ; fA1; A01; A2; A02; A3g ; A1; R0),
                                          10

Страницы