РГЗ построение компилятора (стр. 4 )

Ri (A) = Ri-1(A)Ri-1(B), В (Ri-1(A)VN),

L (A) = Li-1(А) Li-1(B), В (Li-1(A) VN).

Для каждого нетерминального символа А: если множество L(A) содержит нетер­минальные символы грамматики А', А", ..., то его надо дополнить символами, входящими в соответствующие множества L(A'), L(A"), ... и не входящими в L(A). Ту же операцию надо выполнить для R(A).

Шаг 3. Если AVN: Ri(A) Ri-1(A) или Li (A) Li(А), то i:=i+l и вернуться к шагу 2, иначе построение закончено: R(A) = Ri (A) и L(A) = Li (A).

Если на предыдущем шаге хотя бы одно множество L(A) или R(A) для неко­торого символа грамматики изменилось, то надо вернуться к шагу 2, иначе по­строение закончено.

По данному алгоритму были построены следующие множества крайних левых и крайних правых символов:

L0(S)={class}

L0(D)={T}

L0(T)={private, protected, public, published}

L0(P)={M, O}

L0(O)={char, int, real}

L0(Q)={:}

L0(W)={;}

L0(M)={id}

L1(S)={class}

L1(D)={T, private, protected, public, published}

L1(T)={private, protected, public, published}

L1(P)={M, O,id, char, int, real}

L1(O)={char, int, real}

L1(Q)={:}

L1(W)={;}

L1(M)={id}

L2(S)={class}

L2(D)={T, private, protected, public, published}

L2(T)={private, protected, public, published}

L2(P)={M, O,id, char, int, real}

L2(O)={char, int, real}

L2(Q)={:}

L2(W)={;}

L2(M)={id}

L3(S)={class}

L3(D)={T, private, protected, public, published}

L3(T)={private, protected, public, published}

L3(P)={M, O,id, char, int, real}

L3(O)={char, int, real}

L3(Q)={:}

L3(W)={;}

L3(M)={id}

R0(S)={W}

R0(D)={T}

R0(T)={P}

R0(P)={W, O}

R0(O)={W}

R0(Q)={:}

R0(W)={;}

R0(M)={id}

R1(S)={W,;}

R1(D)={T, P}

R1(T)={P, W,O}

R1(P)={W, O,;}

R1(O)={W,;}

R1(Q)={:}

R1(W)={;}

R1(M)={id}

R2(S)={W,;}

R2(D)={T, P,W, O,;}

R2(T)={P, W,O,;}

R2(P)={W, O,;}

R2(O)={W,;}

R2(Q)={:}

R2(W)={;}

R2(M)={id}

R3(S)={W,;}

R3(D)={T, P,W, O,;}

R3(T)={P, W,O,;}

R3(P)={W, O,;}

R3(O)={W,;}

R3(Q)={:}

R3(W)={;}

R3(M)={id}

9.4. Построение матрицы предшествования

После построения множеств L(A) и R(A) по правилам грамматики создается матрица предшествования. Матрицу предшествования дополняют символами $н и $к (начало и конец цепочки). Для них определены следующие отношения предшествования:

$н <• X, aV, если S=>*Xy, где SVN, yV* или (с другой стороны) если XL(S); $к •> X, aV, если S=>*yX, где SVN, yV* или (с другой стороны) если XR(S).

Здесь S — целевой символ грамматики.

Матрица предшествования служит основой для работы распознавателя языка, заданного грамматикой простого предшествования.

В результате была построена следующая матрица предшествования:

Рис. 10. Матрица предшествования.

9.5. Построение дерева разбора

После успешного разбора входной строки строится дерево вывода, которое наглядно показывает, как стартовый символ грамматики порождает цепочку языка. Если нетерминал А имеет продукцию A→XYZ, то дерево разбора может иметь внутренний узел А стремя потомками, помеченными слева направо как X, Y, Z. Формально для данной контекстно-свободной грамматики G=(VT, VN, P, S) дерево разбора представ­ляет собой дерево со следующими свойствами.

Корень дерева помечен стартовым символом S; Каждый лист помечен терминалом из множества VT или символом е; Каждый внутренний узел представляет нетерминальный символ; Если А является нетерминалом и помечает некоторый внутренний узел, a XlX2...Хn — отметки его дочерних узлов, перечисленные слева направо, то А→Х1Х2...Хn — продукция. Здесь XlX2...Хn могут представлять собой как терминальные, так и нетерминальные символы. В качестве специального случая продукции А→е соот­ветствует узел А с единственным дочерним узлом е.

Листья дерева разбора, читаемые слева направо, образуют крону дерева, кото­рая представляет собой строку, выведенную, или порожденную из нетерминального сим­вола в корне дерева. Все листья должны рассматриваться в определенном порядке слева направо: если а и b — два дочерних узла одного родителя и узел а находится слева от b, то все потомки а будут находиться слева от любого потомка b.

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

1) Обозначить корень дерева стартовым символом грамматики S.

2) Просмотр всех правил, примененных в ходе синтаксического анализа, проводится в обратном порядке. Перебрать все листья дерева справа налево:

— если лист обозначен, как терминал, то переходим к следующему листу;

— если лист обозначен как нетерминал, то применяем соответствующее правило, добавляя узлы, соответствующие правой части продукции.

Перейти к следующему узлу и следующему правилу.

3) Построение дерева завершается, когда все листья будут обозначены терминалами.

       В результате было построено следующее дерево разбора (Рис. 11):

Рис. 11.  Дерево разбора.

Заключение

В ходе проделанной работы были получены и закреплены знания по курсу «Теория языков программирования и методы трансляции». Были рассмотрены основные этапы работы компилятора, детально рассмотрен алгоритм построения лексического анализатора на базе конечного автомата, алгоритм построения распознавателя на основе грамматики простого предшествования, построение дерева разбора. Была написана программа, представляющая собой модель компилятора для обработки конструкции классов языка Си.

Список литературы

Ганичева языков программирования и методы трансляции:

  Учеб. пособие. – Череповец: ГОУ ВПО ЧГУ, 2011. – 186 с.

А. Ахо, Р. Сети, Дж. Ульман «Компиляторы. Принципы, технологии, инструменты», изд. «Вильямс», 2003. , «Системное программное обеспечение», изд. «ПИТЕР», 2001.

       

ПРИЛОЖЕНИЕ 1

минобрнауки России

федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«ЧЕРЕПОВЕЦКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

Институт информационных технологий

Кафедра математического и программного обеспечения ЭВМ

Дисциплина: Теория языков программирования и методы трансляции

Техническое задание

Листов 6

Руководитель
Исполнитель
студент группы	1ИВТб-41
Оценка
Подпись

2014 год

Введение

Настоящее техническое задание распространяется на разработку программы –компилятора, которая будет предназначена для описания классов языка Си.

Программа должна реализовывать:

Лексический анализатор; Синтаксический анализатор; Обнаружение ошибок в работе синтаксического анализатора и восстановление после ошибок.

Основание для разработки

Основанием для разработки данного программного продукта является расчётное графическое задание по дисциплине «Теория языков программирования и методов трансляции», выданное преподавателем кафедры МПО ЭВМ ЧГУ в рамках учебного плана.