Практическое применение СУ-схем

СУ-схемы предполагают существование отображения f: P1 —> P2 множества правил грамматики исходного языка в множество пра­вил грамматики объектного языка.

Выделяют два метода построения объектной программы путем преобразования исходной программы:

1 СУ-компиляция – строит объектную программу по ходу синтаксического анализа. В этом случае строить полное дерево разбора исходной программы, а тем более сохранять его после синтаксического анализа не требуется.

2 СУ-перевод – строит объектную программу после синтаксического анализа по его результату, представленным в виде дерева разбора.

Рассмотрим метод построения объектной про­граммы на основе СУ-перевода. В основу метода положено преобразование дерева разбора строки со во входной грамматике GBX в дерево разбора выходной строки у в грамматике GBbIХ. Метод позволяет получить перевод (w, у) любой входной строки w пу­тем последовательного решения следующих трех задач:

- построить дерево разбора w в грамматике GBX;

- преобразовать полученное дерево в дерево разбора соответствующей строки у в грамматике GBbIX, используя правила СУ-схемы;

- получить выходную строку у, взяв крону дерева разбора строки у.

 

Алгоритм преобразования дерева разбора входной строки

 

Обозначим: А — произвольный нетерминал СУ-схемы, А —> — правило входной грамматики, где = n1…nk . Пусть нетерминалу А соответствует узел А дерева разбора (нетерминальный узел). Тогда узлы n1,n2 , . . ., nk - прямые потомки узла А. Преобразование дерева разбора начинается с его корня и состоит в следующем:

1) выбрать очередной нетерминальный узел А дерева разбора
входной строки; если все узлы обработаны, завершить работу;

2) устранить листья из множества узлов n1…nk (вершины,
помеченные терминалами или );

3) найти в СУ-схеме правило вида —> , ) и переставить
оставшихся прямых потомков узла А в соответствии с их размещением в строке (поддеревья перемещать вместе с их корнями);

4) добавить в качестве прямых потомков узла А листья так,
чтобы метки всех его прямых потомков образовали цепочку ;

5) повторять п. 1—4 для всех прямых нетерминальных потом­
ков узла А по порядку, слева направо.

ПримерДана СУ-схема Т2 = ({0, 1}, {S, A}, {a, b), R, S),где R содержит правила:

1) S->0AS,SAa 2) A->0SA,ASa 3) S->1,b 4) A->1,b.

На рис. 5.1.2а показано дерево разбора входной строки 00111. При­менение алгоритма преобразования к корню S этого дерева устраняет левый лист, помеченный 0 (шаг 2).

Рисунок 5.2 - Преобразование дерева разбора: а - дерево входной строки;

б - дерево после однократного применения алгоритма;

в - дерево выходной строки

Далее, так как корню соответ­ствует правило S -> 0AS и для этого правила = SAa, нужно поме­нять местами оставшихся прямых потомков корня (шаг 3). Затем сле­дует добавить а в качестве самого правого, третьего, прямого потом­ка (шаг 4). Результатом будет дерево, показанное на рис. 5.1.2б. Снова применяем алгоритм, теперь уже к первым двум потомкам корня. Обработка второго из них приводит еще к двукратному повторению алгоритма. Окончательный результат показан на рис. 5.1.2в, это дере­во разбора выходной строки bbbaa. Из анализа правил СУ-схемы Т2 следует, что она является не простой постфиксной схемой.








Дата добавления: 2016-03-27; просмотров: 781;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.004 сек.