close

Вход

Забыли?

вход по аккаунту

?

Teoriya yazykov programm i metod trans

код для вставкиСкачать
Федеральное агентство по образованию
Государственное образовательное учреждение
высшего профессионального образования
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ
ТЕОРИЯ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ
И МЕТОДЫ ТРАНСЛЯЦИИ
Методические указания
к выполнению практических заданий
Санкт-Петербург
2007
Составитель Т. М. Максимова
Рецензент кандидат технических наук, доцент В. П. Попов
В методические указания включены краткие теоретические сведения
об автоматных моделях распознавателей формальных языков и их использовании в реализации лексического и синтаксического анализаторов, варианты индивидуальных заданий.
Предназначены для студентов всех форм обучения, проходящих подготовку по специальностям 230105 и 010503.
Подготовлены кафедрой компьютерной математики и программирования и рекомендованы к изданию редакционно-издательским советом СанктПетербургского государственного университета аэрокосмического приборостроения.
Редактор А. В. Семенчук
Верстальщик С. В. Барашкова
Сдано в набор 15.06.07. Подписано в печать 21.06.07. Формат 60 × 84 1/16.
Бумага офсетная. Печать офсетная. Усл. печ. л. 1,6. Уч.-изд. л. 1,8.
Тираж 100 экз. Заказ №
Редакционно-издательский центр ГУАП
190000, Санкт-Петербург, Б. Морская ул., 67
© ГУАП, 2007
1. Теоретическое введение
1.1. Задача лексического анализа.
Использование автоматной модели
для лексического анализа
Лексический анализ (сканер) представляет собой первую фазу
процесса компиляции, при которой отдельные литеры входной цепочки группируются в слова (лексемы). Каждому распознанному
слову входного языка ставится в соответствие некоторое внутреннее представление. Часто термин «лексема» относят и к этому внутреннему представлению. Во избежание двусмысленности будем называть внутреннее представление лексемы кодом лексемы.
Например, если предложения входного языка представляют собой списки идентификаторов, разделенных запятыми, то результатом лексического анализа предложения abc,d1,ef2 при условии, что
коды лексем зафиксированы в таблице лексем (табл. 1), будет следующий список кодов: 2 1 3 1 4.
Множество различных лексем языка программирования обычно
бесконечно. Поэтому формирование таблицы лексем выполняется
в процессе анализа конкретной входной цепочки. При этом каждый экземпляр определенной лексемы, присутствующий во входной цепочке,
должен получить в выходном списке один и тот же код, что обеспечивается наличием таблицы. Код лексемы обычно представляет собой пару
вида (тип лексемы, некоторые данные). Первая компонента пары является синтаксической категорией, указывая принадлежность лексемы
какой-либо непосредственной составляющей грамматики. В грамматиках языков программирования, как правило, к таким непосредственным составляющим относятся: иденТаблица 1. Таблица лексем
тификатор, константа, разделитель и др.
Лексема
Код лексемы
Вторая компонента кода может быть ука,
1
зателем на месторасположение информаabc
2
ции об этой конкретной лексеме, в частd1
3
ности, – просто номером соответствующей
ef2
4
записи в таблице лексем.
Обозначим в вышерассмотренном примере тип лексемы символом «r», если она является запятой, и символом «i», если она относится к категории <идентификатор>. Тогда код лексемы «,» приобретет вид: r1, а коды лексем «abc», «d1» и «ef2» соответственно: i2,
i3 и i4. При этом вторая компонента кода является указателем на
соответствующую запись таблицы лексем. Синтаксис лексем, как
правило, описывается в рамках автоматной грамматики, или грамматики типа 3 в соответствии с классификацией Хомского. Это означает, что лексический анализатор (сканер) может быть организован в виде модели конечного автомата. Так, если порождающие
правила грамматики имеют вид: <U>::=<W>N и <U>::=N, где <U>,
<W> – нетерминальные, а N – терминальный символы грамматики, то соответствующий автомат определяется пятеркой:
1) конечное множество V внутренних состояний, каждое из которых, за исключением одного (обозначим его – F), соответствует нетерминальному символу грамматики;
2) конечный входной алфавит T, каждый символ которого соответствует терминальному символу грамматики;
3) множество P переходов; при этом правилу грамматики <U>::=
=<W>N в автоматной модели соответствует переход P(W,N) = U (из
состояния W под воздействием входного символа N автомат переходит в состояние U), а правилу <U>::=N – переход P(F,N) = U (из начального состояния под воздействием входного символа N автомат
переходит в состояние U);
4) начальное состояние F;
5) множество S последних состояний, соответствующее множеству нетерминалов грамматики, являющихся альтернативными определениями ее аксиомы (начального символа). Попадание автомата в одно из состояний множества S означает, что процесс распознавания входного слова закончен. Можно сказать, что каждому из
последних состояний соответствует свой выходной символ (свойство модели автомата Мура), при появлении которого на выходе автомата запускается соответствующая семантическая подпрограмма
сканера, формирующая код распознанной лексемы.
Например, грамматике G[<S>] с порождающими правилами:
<S>::=<X>$
<X>::=<U>0|<V>1
<U>::=<X>1|1
<V>::=<X>0|0
соответствует автоматная модель, приведенная на рис. 1 в виде графа переходов и выходов и на рис. 2 – в виде таблицы переходов
6Z
'Z
4Z
9Z
7Z
Рис. 1. Граф переходов и выходов конечного автомата Мура
F
V
U
–
y0
0
1
$
U
X
–
–
Y0
V
–
X
–
y0
X
V
U
S
y0
S
–
–
–
y1
Рис. 2. Таблица переходов и выходов конечного автомата Мура
и выходов, где y1 – символ, cигнализирующий об успешном окончании распознавания слова, поступившего на вход автомата.
Символами «–» в матрице переходов отмечены запрещенные переходы в автомате. Попадание в клетку матрицы переходов с симво-
6
Z
Z
Z
]Z&
Z&
ž
'4
Z
9
Z
]Z&
Z
Z
7
Рис. 3. Граф переходов и выходов конечного автомата Мили
лом «–» означает наличие ошибки во входной цепочке терминальных символов. Можно ввести дополнительное внутреннее состояние
автомата E («ошибка») и заменить в матрице переходов символы «–»
символами состояния E, снабдив его выходом yE, по которому запускается семантическая подпрограмма обработки ошибочной ситуации. Построенный автомат является автоматом однократного
действия, т. е. предназначен для распознавания одного слова входной цепочки. Для преобразования его в автомат многократного
действия можно, полагая состояние S неустойчивым, описать переход из него при неизменном входном символе в начальное состояние
F. Другой вариант преобразования – построение автомата Мили,
в котором состояния F и S исходного автомата будут объединены,
и переход в это объединенное состояние будет сопровождаться появлением выходного символа y1. Граф переходов для такой автоматной модели изображен на рис. 3.
1.2. Алгоритмы синтаксического анализа
с использованием КС-грамматик
1.2.1. Постановка задачи синтаксического анализа.
Организация данных.
Общая схема алгоритмов
детерминированного разбора
Синтаксический анализ (разбор) – это процесс, в котором исследуется цепочка лексем и устанавливается, удовлетворяет ли она условиям, сформулированным в определении синтаксиса языка. Выходом синтаксического анализатора является синтаксическое дерево разбора, которое представляет синтаксическую структуру исходной программы.
Пример 1
Зададим грамматику G(V,T,P,S) следующим наборомправил (полагая, что терминальные символы в правых частях правил представлены соответствующими кодами лексем):
1) <S> ::= <E>
2) <E> ::= <T> + <E>
3) <E> ::= <T>
4) <T> ::= <F> * <T>
5) <T> ::= <F>
6) <F> ::= i
В результате синтаксического анализа цепочки i*i+i может быть
построено синтаксическое дерево разбора вида:
<S>

—<E>—
  
<E> + <T>


—<T>— <F>
   
<F> * <T> i


i
<F>

i
Синтаксическое дерево разбора может быть представлено с помощью стека, каждая запись которого содержит символ вершины дерева и указатель на запись, являющуюся ее предком. Дерево, полученное в примере 1, будет представлено стеком:
14
i
13
13 <F>
12
12 <T>
5
11
i
10
10 <F>
8
9
i
6
8
<T>
3
7
*
3
6
<F>
3
5
<E>
2
4
+
2
3
<T>
2
2
<E>
1
1
<S>
0
Алгоритмы, предлагаемые для изучения, положены в основу
функционирования однопроходных (детерминированных) синтаксических анализаторов. Возможность построения детерминированного анализатора обеспечивается ограничениями на класс контекстно-свободных (КС) грамматик, для которого проектируется этот
анализатор. К наиболее распространенным таким классам грамматик, которые практически отражают все синтаксические черты язы­
ков программирования, определяемых с помощью КС-грамматик,
относятся:
1) LL(k)-грамматики, для которых левый анализатор работает
детерминированно, если позволить ему принимать во внимание k
входных символов, расположенных справа от текущей входной позиции;
2) LR(k)-грамматики, для которых правый анализатор работает
детерминированно, если позволить ему принимать во внимание k
входных символов, расположенных справа от текущей входной позиции;
3) грамматики предшествования, для которых правый анализатор может находить основу правовыводимой цепочки, учитывая толь­
ко некоторые отношения между парами ее смежных символов.
Рассмотрим алгоритмы функционирования синтаксического анализатора в применении к LL(1)-, LR(1)-грамматикам и грамматикам
простого предшествования. Помимо вышеперечисленных структур
данных (входные: цепочка лексем, описание грамматики языка;
выходной стек, содержащий синтаксическое дерево разбора, или
выходная лента с последовательностью номеров правил грамматики, которые использовались при разборе), этими анализаторами используются еще две структуры: управляющая таблица и рабочий
стек, предназначенные для хранения текущей сентенциальной формы в процессе выполнения разбора. Все три алгоритма работают по
одной общей схеме, которая коротко может быть описана следующим образом. Входная цепочка просматривается слева направо,
символ за символом. С помощью управляющей таблицы, в зависимости от содержимого вершины рабочего стека (определяющего стро­
ку таблицы) и текущего входного символа (определяющего столбец
таблицы), решается вопрос о выполнении одной из процедур: занесение входного символа в рабочий стек или преобразование содержимого вершины рабочего стека в соответствии с каким-либо правилом грамматики и с переносом прежнего содержимого вершины
этого стека в выходной стек. Успешное завершение разбора входной
цепочки происходит по окончании ее просмотра при условии, что
рабочий стек оказывается пустым. Другой вариант окончания разбора – получение сообщения о том, что входная цепочка не принадлежит языку, описанному заданной грамматикой. Появление такого сообщения предусматривается управляющей таблицей, которая содержит его в своих элементах, соответствующих несочетаемым парам «содержимое вершины стека – входной символ».
Построение управляющей таблицы (автоматическое или вручную) выполняется во время проектирования синтаксического анализатора, и для алгоритма разбора она является постоянной табли
цей. Ее построение выполняется в результате анализа порождающих правил грамматики языка, определения свойства этой грамматики (LL(k), LR(k) или предшествования) и, возможно, преобразования ее правил, если они не удовлетворяют желаемому свойству.
Строки управляющей таблицы ставятся в соответствие возможным
символам в вершине рабочего стека, столбцы – символам входного
алфавита языка. Элемент таблицы, находящийся на пересечении
заданной строки и заданного столбца, содержит инструкцию о следующем действии алгоритма.
Остановимся теперь на особенностях каждого из трех вышеперечисленных алгоритмов синтаксического разбора.
1.2.2. Cинтаксический анализ для LL(1)-грамматики
Алгоритм синтаксического анализа на основе LL(k)-грамматики
относится к классу алгоритмов нисходящего разбора. Строкам управляющей таблицы М для грамматики G(V,T,P,S) ставятся в соответствие элементы множества {V∪T∪$} ($-маркер дна стека), столбцам – элементы множества {T∪$} ($ – маркер правого конца строки). Перед началом работы алгоритма в рабочий стек заносятся
символы $ и S. Возможные значения элементов таблицы и их интерпретация алгоритмом разбора приведены в табл. 2.
Для построения управляющей таблицы М по заданной LL(1)грамматике G(V,T,P,S) можно воспользоваться следующим алго­
ритмом.
Таблица 2. Интерпретация команд LL(1) управляющей таблицы
Значение элемента
управляющей
таблицы
Интерпретация алгоритмом разбора
Номер n порождающего правила грамматики
Удаление символа из рабочего стека; запись этого
символа в выходной стек; запись правой части
правила номер n в рабочий стек справа налево,
начиная с последнего символа; запись n в выходную ленту
«Выброс»
Удаление символа из рабочего стека, запись его
в выходной стек; считывание следующего символа входной строки
«Допуск»
Входная строка разобрана. Конец работы
«Ошибка»
Входная строка ошибочна. Конец работы
1. Если <A>::=r – правило номер n заданной грамматики, то
M(<A>,a)=n для всех a, являющихся терминальными префиксами
цепочек, выводимых из r. Если r – пустая строка (для ее обозначения будем использовать символ Λ), то М(<A>,b)=n для всех b, являющихся терминальными символами, которые могут встречаться
непосредственно справа от <A>, т. е. символов-следователей для нетерминала <A>.
2. M(a,a)=«сдвиг» для всех a, принадлежащих Т.
3. M($,$)=«допуск».
4. Оставшиеся незаполненными элементы таблицы М получают
значение «ошибка».
Для грамматики, обладающей свойством LL(1), терминальные
префиксы цепочек, выводимых из альтернативных правых частей
правил для одного нетерминала, и символы-следователи этого же
нетерминала должны быть различны. При построении управляющей таблицы это является гарантией того, что в одну клетку таблицы помещается не более одного правила грамматики в соответствии
с п. 1 алгоритма. В некоторых случаях не LL(1)-грамматика может
быть преобразована к виду LL(1). Так например, два или более правил для одного нетерминала, имеющие одинаковые начальные символы, могут быть объединены в одно правило по следующей схеме.
До преобразования:
<A>::=aα|aβ| Λ
После преобразования:
<A>::=a<Z>| Λ
<Z>::=α|β
Еще одним приемом, позволяющим привести грамматику к виду
LL(1), является устранение левой рекурсии по следующей схеме.
До преобразования:
<A>::=<A>α|a
После преобразования:
<A>::=a<Z>
<Z>::=α<Z>| Λ
Пример 2
Грамматика G(V,T,P,S) рассмотренного в п. 1.2.1 примера 1 не обладает свойством LL(1), поскольку обе правые части для нетерминала
<E> (правила 2 и 3) порождают цепочки, начинающиеся одним и тем
же терминалом i. То же можно сказать и о правилах для нетерминала <T>. Преобразуем грамматику G(V,T,P,S) к грамматике G1(V1,T,P1,
S), обладающей свойством LL(1). Правила последней примут вид:
1) <S>::=<E>
10
2) <E>::=<T><X>
3) <X>::=+<E>
4) <T>::=<F><Y>
5) <Y>::=*<T>
6) <F>::=i
7) <X>::=Λ
8) <Y>::=Λ
В соответствии с приведенным алгоритмом теперь можно построить управляющую таблицу для LL(1)-анализатора:
i
+
*
$
<S>
1
<E>
2
<T>
4
<F>
6
<X>
3
7
<Y>
8
5
8
i
Сдвиг
+
Сдвиг
*
Сдвиг
$
Допуск
Незаполненные элементы таблицы имеют значение «ошибка».
Проанализируем входную цепочку i*i с помощью алгоритма LL(1)анализатора. При этом для облегчения формирования выходного
стека, при записи символа в рабочий стек будем снабжать его указателем на символ, являющийся его предком в синтаксическом дереве разбора. Процесс анализа проиллюстрируем таблицей:
Рабочий стек
<S>.0
$
<E>,1
$
<T>,2
<X>,2
$
<F>,3
<Y>,3
<X>,2
$
i,4
<Y>,3
<X>,2
$
Входной символ
М(А,а)
i
M(<S>,i)=1
i
M(<E>,i)=2
i
M(<T>,i)=4
i
M(<F>,i)=6
i
M(i,i)=«сдвиг»
11
Окончание табл.
Рабочий стек
Входной символ
М(А,а)
<Y>,3
<X>,2
$
*
M(<Y>,*)=5
*,6
<T>,6
<X>,2
$
*
M(*,*)=«сдвиг»
<T>,6
<X>,2
$
i
M(<T>,i)=4
<F>,8
<Y>,8
<X>,2
$
i
M(<F>,i)=6
i,9
<Y>,8
<X>,2
$
i
M(i,i)=«сдвиг»
<Y>,8
<X>,2
$
$
M(<Y>,$)=8
<X>,2
$
$
M(<X>,$)=7
$
$
M($,$)=«допуск»
В результате анализа получено синтаксическое дерево разбора:
<S>

<E>

—<T>—
12

<X>



<F> —<Y>— Λ


i

*


—<T>—


<F>
<Y>
 
i
Λ
В выходном стеке это дерево представляется в виде:
12 <X> 2
11 <Y> 8
10
i
9
9 <F> 8
8 <T> 6
7
*
6
6 <Y> 3
5
i
4
4
<F> 3
3 <T> 2
2 <E> 1
1
<S> 0
Последовательность номеров примененных правил (левый разбор): 124654687.
1.2.3. Синтаксический анализ для LR(1)-грамматики
Алгоритм синтаксического анализа на основе LR(k)-грамматики
относится к классу алгоритмов восходящего разбора. Строкам управляющей таблицы М (LR-таблица разбора) ставятся в соответствие
состояния, в которых может находиться анализатор, столбцам – элементы множества {V∪T∪$}. Каждая запись рабочего стека представляет собой пару: (символ, номер состояния). Перед началом работы алгоритма в рабочий стек заносится пара (Λ,1), где 1 – символ
начального состояния анализатора. Возможные значения элементов таблицы и их интерпретация алгоритмом разбора приведены
в табл. 3.
Таблица 3. Интерпретация команд LR(1) управляющей таблицы
Значение элемента
управляющей таблицы
Номер n порождающего правила
грамматики
(«Сдвиг»,
номер j состояния)
Интерпретация алгоритмом разбора
Удаление из рабочего стека k записей (k – количество символов в правой части правила номер n); имитация считывания в качестве следующего входного
символа нетерминала левой части правила номер n;
запись n в выходную ленту
Запись текущего входного символа в выходной
стек и в паре с номером j – в рабочий стек; если
этот символ нетерминал, установка указателей на
него в ближайших к нему n записях выходного
стека с пустыми указателями
13
Окончание табл. 3
Значение элемента
управляющей таблицы
«Допуск»
«Ошибка»
Интерпретация алгоритмом разбора
Входная строка разобрана. Конец работы
Входная строка ошибочна. Конец работы
Для построения управляющей таблицы М может быть выполнена разметка порождающих правил грамматики номерами состояний анализатора. Номера состояний устанавливаются в правой части каждого правила: перед первым символом, между любыми двумя символами и после последнего символа. При этом номер состояния, непосредственно справа от которого находится нетерминал,
следует распространять на позиции перед первыми символами всех
правых частей правил для данного нетерминала (и т. д. рекурсивно). А если непосредственно слева от одного и того же символа в каких-либо правилах установлены одинаковые метки, то и непосредственно справа от этого символа в этих правилах следует поставить
одну и ту же метку. Начальные позиции правых частей правил для
аксиомы отмечаются номером начального состояния анализатора.
После разметки грамматики выполняется построение таблицы М
по следующему алгоритму.
1. Если символ А в правой части правила имеет непосредственно
слева от себя метку m, а непосредственно справа от себя – метку j, то
M(m,A)=(«сдвиг»,j).
2. Если метка j размещается за последним символом правой части правила номер n, то определяется множество Q символов, ко­
торые в какой-либо сентенциальной форме могут следовать за нетерминалом левой части правила номер n, и M(j,q)=n для всех
q∈ Q.
3. M(1,<S>)=«допуск», где 1 – символ начального состояния.
4. Оставшиеся незаполненными элементы таблицы M получают
значение «ошибка».
Пример 3
Разметим грамматику G(V,T,P,S):
1) <S>::= 1 <E>2
2) <E>::= 1,4 <T>3 + 4<E>5
3) <E>::= 1,4 <T>3
4) <T>::= 1,4,7 <F>6 * 7<T>8
5) <T>::= 1,4,7 <F>6
6) <F>::= 1,4,7 i 9
Тогда таблица М примет вид:
14
<S>
<E>
<T>
F
i
+
*
1 Допуск Сдвиг, 2 Сдвиг, 3 Сдвиг, 6 Сдвиг, 9
2
3
Сдвиг, 4
4
Сдвиг, 5 Сдвиг, 3 Сдвиг, 6 Сдвиг, 9
5
6
5
Сдвиг, 7
7
Сдвиг, 8 Сдвиг, 6 Сдвиг, 9
8
4
9
6
6
$
1
3
2
5
4
6
Незаполненные элементы таблицы имеют значение «ошибка».
Проанализируем входную цепочку i*i c помощью алгоритма LR(1)анализатора.
Рабочий стек
Входной символ
М(А,а)
Λ,1
i,9
Λ,1
Λ,1
<F>,6
Λ,1
*,7
<F>,6
Λ,1
i,9
*,7
<F>,6
Λ,1
*,7
<F>,6
Λ,1
<F>,6
*,7
<F>,6
Λ,1
*,7
<F>,6
Λ,1
<T>,8
*,7
<F>,6
Λ,1
Λ,1
i
M(1,i)=«сдвиг»,9
*
M(9,*)=6
<F>
M(1,<F>)=«сдвиг»,6
*
M(6,*)=«сдвиг»,7
i
M(7,i)=«сдвиг»,9
$
M(9,$)=6
<F>
M(7,<F>)=«сдвиг»,6
$
M(6,$)=5
<T>
M(7,<T>)=«сдвиг»,8
$
M(8,$)=4
<T>
M(1,<T>)=«сдвиг»,3
15
Окончание табл.
Рабочий стек
<T>,3
Λ,1
Λ,1
<E>,2
Λ,1
Λ,1
Входной символ
М(А,а)
$
M(3,$)=3
<E>
M(1,<E>)=«сдвиг»,2
$
M(2,$)=1
<S>
M(1,<S>)=«допуск»
В результате анализа получено синтаксическое дерeво разбора:
<S>

<E>

—<T>—
  
<F> * <T>
 
i
<F>

i
В выходном стеке это дерево представляется в виде:
9 <S> 0
8 <E> 9
7 <T> 8
6 <T> 7
5 <F> 8
4
i
5
3
*
7
2 <F> 7
1
i
2
Последовательность номеров примененных правил (правый разбор): 665431
1.2.4. Синтаксический анализ
для грамматики простого предшествования
Алгоритм синтаксического анализа на основе грамматики предшествования относится к классу алгоритмов восходящего разбора. Строкам и столбцам управляющей таблицы М (матрицы отно16
шений предшествования) ставятся в соответствие элементы множества T∪V∪$ (в строке – символ в вершине рабочего стека, в столбце – входной символ). Каждую запись рабочего стека представим
парой: (символ, знак отношения предшествования символа предыдущей записи стека с данным символом). Перед началом работы алгоритма в стек записывается пара ($,0).
Возможные значения элементов таблицы и их интерпретация
алгоритмом разбора приведены в табл. 4.
Отношения предшествования Вирта–Вебера < , =, > для КСграмматики G(V,T,P,S) определяются на множестве V ∪ T следующим образом:
1) X<Y, если в Р есть такое правило <A>::=rX<B>q, что Y является
головным символом хотя бы одной из цепочек, выводимых из <B>;
2) X=Y, если в Р есть правило <A>::=rXYq;
3) X>a, если a – терминал, и в Р есть правило <A>::=r<B>Yq такое, что X является хвостовым символом хотя бы одной из цепочек,
выводимых из <B>, а Y=at, или a является головным символом хотя
бы одной из цепочек, выводимых из Y.
Для анализа входной цепочки методом предшествования удобно
добавлять к ней левый и правый концевые маркеры ($). Будем счиТаблица 4. Интерпритация команд управляющей таблицы для грамматики простого предшествования
Значение
элемента
таблицы
Интерпретация значения алгоритмом разбора
<
Запись текущего входного символа в выходной стек и в паре со
знаком «<» – в рабочий стек; если этот символ – нетерминал,
установка указателей на него в ближайших к нему n – записях
выходного стека с пустыми указателями, где n – количество
символов в правой части правила для этого нетерминала
=
Запись текущего входного символа в выходной стек и в паре со
знаком «<» – в рабочий стек; если этот символ – нетерминал,
установка указателей на него в ближайших к нему n – записях
выходного стека с пустыми указателями, где n – количество
символов в правой части правила для этого нетерминала
>
Удаление из рабочего стека записей (символы которых образуют цепочку w) со знаками отношения « =» до первого знака
«<» включительно; если <A>::=w – правило с номером n заданной грамматики, имитация считывания <A> в качестве
следующего входного символа и запись n в выходную ленту
«Ошибка» Входная строка ошибочна. Конец работы
«Допуск» Входная строка разобрана. Конец работы
17
тать, что $<X для всех X, являющихся головными символами цепочек, выводимых из <S>, и Y>$ для всех Y, являющихся хвостовыми символами таких цепочек. КС-грамматика G(V,T,P,S) называется грамматикой предшествования, если она является приведенной,
не содержит Λ-правил, и для любой пары символов из T∪V выполняется не более одного отношения предшествования Вирта–Вебера.
Обратимая грамматика предшествования называется грамматикой
простого предшествования.
Пример 4
Анализируя грамматику G(V,T,P,S) из п. 1.2.1, заметим, что она
не удовлетворяет определению грамматики предшествования, поскольку <T> = + в соответствии с правилом 2) и <T> > + в соответствии с правилами 2) и 4). Чтобы избавиться от этого конфликта,
преобразуем эту грамматику к грамматике G2(V2,T,P2,S) с правилами:
1) <S>::=<E>
2) <E>::=<X>+<E>
3) <E>::=<X>
4) <T>::=<F>*<T>
5) <T>::=<F>
6) <F>::=i
7) <X>::=<T>
Матрица отношений предшествования для грамматики G2 имеет вид:
<S>
<S>
<E>
<T>
<F>
<X>
+
*
i
$
<E>
=
<T>
<
=
<F>
<X>
<
<
<
<
<
+
*
>
>
=
=
<
$
>
>
>
>
>
<
<
>
<
i
>
>
<
Незаполненные элементы матрицы соответствует парам символов грамматики, для которых не определены отношения предшествования. При использовании этой матрицы в качестве управляющей таблицы в алгоритме синтаксического анализа можно считать,
что эти элементы cодержат значение «ошибка», а M(<S>,$)= «допуск».
18
Проанализируем входную цепочку i*i с использованием метода
предшествования.
Рабочий стек
Входной символ
М(А,а)
$,0
i,<
$,0
$,0
<F>,<
$,0
*,=
<F>,<
$,0
i,<
*,=
<F>,<
$,0
*,=
<F>,<
$,0
<F>,<.
*,=
<F>,<
$,0
*,=
<F>,<
$,0
<T>,=
*,=
<F>,<
$,0
$,0
<T>,<
$,0
$,0
<X>,<
$,0
$,0
<E>,<
$,0
$,0
i
M($,i)= «<»
*
M(i,*)= «>»
<F>
M(<F>,$)= «<»
*
M(<F>,*)= «=»
i
M(*,i)= «<»
$
M(i,$)= «>»
<F>
M(*,<F>)= «<»
$
M(<F>,$)= «>»
<T>
M(*,<T>)= «=»
$
M(<T>,$)= «>»
<T>
M($,<T>)= «<»
$
M(<T>,$)= «>»
<X>
M($,<X>)= «<»
$
M(<X>,$)= «>»
<E>
M($,<E>)= «<»
$
M(<E>,$)= «>»
<S>
M($,<S>)= «<»
$
M(<S>,$)= «допуск»
<S>,<
$,0
19
В результате анализа получено синтаксическое дерево разбора:
<S>

<E>

<Х>

—<T>—
  
<F> * <T>
 
i
<F>

i
В выходном стеке это дерево представляется в виде:
10
9
8
7
6
5
4
3
2
1
<S>
<E>
<X>
<T>
<T>
<F>
i
*
<F>
i
0
10
9
8
7
6
5
7
7
2
Последовательность номеров примененных правил (правый разбор): 6654731.
1.2.5. Нейтрализация ошибок при LL(1)-разборе
Для нейтрализации ошибки (коррекции входной строки) при
LL(1)-разборе можно воспользоваться содержанием рабочего стека
как предсказанием того, что может появиться в разбираемой строке. С этой целью после окончания работы алгоритма LL(1)-разбора
по команде «ошибка» следует проверить все символы рабочего стека на возможность вывода из них цепочки, начинающейся с текущего символа входной строки. Если в рабочем стеке не найдется такого символа, то текущий символ входной строки следует удалить.
Если же в рабочем стеке обнаружится нужный символ, то для всех
20
символов, находящихся в рабочем стеке выше него, следует сгенерировать цепочки терминалов и вставить их во входную строку.
Пример 5
Пусть анализатору, построенному в п. 1.2.2, предложена строка
i*+i. В соответствии с командой «ошибка» анализатор прекратит разбор в то время, как текущим входным символом окажется +, а в рабочем стеке останутся записи:
<T>,6
<X>,2
$
Из нетерминала <X> можно вывести строку с терминальным пре­
фиксом + (правило 3). Тогда для формирования корректной строки
следует из нетерминала <T>, размещенного в стеке выше <X>, вывести строку терминалов и вставить ее во входную строку. Такой
строкой может быть, например, просто символ I, и следовательно,
входная строка i*+i будет исправлена на i*i+i.
1.2.6. Синтаксически-управляемый перевод
Переводом называется некоторое отношение между цепочками
или некоторое множество пар цепочек.
Перевoдoм с языка L1 (подмножество T1*) на язык L2 (подмножество Т2*) назовем отношение Π из T1* в Т2*, для которого L1 – oбласть определения, а L2 – множество значений.
Одним из формализмов, используемых для определения переводов, является схема синтаксически-управляемого перевода (СУ-схема). Фактически такая схема представляет собой грамматику, в которой к каждому правилу присоединяется элемент перевода. Всякий раз, когда правило участвует в выводе входной цепочки, с помощью элемента перевода вычисляется соответствующая часть выходной цепочки.
Формально СУ-схема определяется пятеркой Π=(V,Tin,Tout,R,S),
где V – конечное множество нетерминальных символов; Тin – конечный входной алфавит; Тout – конечный выходной алфавит; R – конечное множество правил вида A::=α,β, где α ∈ (V∪Tin)*, β ∈ (V∪Tout)*,
и вхождения нетерминалов в цепочку β образуют перестановку вхо­
ждений нетерминалов в цепочку α; S – начальный символ. Грамматика Gin = (V,Tin,Pin,S), где Pin = {A::= α  A::= α, β ∈ R), называется
входной грамматикой, а грамматика Gout = (V,Tout,Pout,S), где Pout =
21
= {A::= β  A::= α, β ∈ R) , называется выходной грамматикой СУсхемы Π.
При использовании для разбора входной строки какого-либо алгоритма восходящего разбора перевод, заданный СУ-схемой, может
быть выполнен в три этапа: построение правого разбора (соответствующей последовательности номеров правил) алгоритмом восходящего разбора, обращение полученной последовательности номеров
правил, генерация выходной строки в соответствии с выходной грамматикой и обращенной последовательностью правого разбора.
Пример 6
Задана СУ- схема Π = ({S,A},{0,1},{2,3},R,S),где R:
1) S::=0AS,SA2
2) S::=1,3
3) A::=0SA,AS2
4) A::=1,3
Правый разбор цепочки 00111 имеет вид: 24321. В соответствии
с обращенным правым разбором (12342) выполним вывод выходной
строки: S=>SA2=>3A2=>3AS22=>31S22=>31322.
2. Задания к практическим занятиям
2.1. Программирование алгоритмов лексического анализа
с использованием автоматных грамматик
1. Построить регулярную грамматику для заданного языка.
2. Построить конечный автомат для полученной грамматики.
3. Разработать и отладить лексический анализатор-препроцессор
на основе построенной автоматной модели.
Варианты задания
Код варианта содержит два числа. Первое из них определяет номер варианта описания языка, второе – способ представления автоматной модели (1 – граф переходов и выходов, 2 – таблица переходов
и выходов).
Таблица вариантов задания
№
варианта
1
2
3
4
5
6
7
8
9
10
Код
1.1
2.1
3.1
4.1
5.1
6.1
7.1
8.1
9.1
10.1
22
№
варианта
11
12
13
14
15
16
17
18
19
20
Код
1.2
2.2
3.2
4.2
5.2
6.2
7.2
8.2
9.2
10.2
Описания языков
1. Цепочка символов «а» произвольной длины, после которой
следует символ «b»;
цепочка символов «а» произвольной длины, после которой следует символ «с»;
цепочка символов «b» произвольной длины, после которой следуют «а» или «с».
2. Цепочка пар символов «а» «b» произвольной длины, после которой следует «b»;
цепочка пар символов «b» «а» произвольной длины, после которой следует «с»;
символ «с».
3. Произвольная цепочка символов из «а»,«b»,«с», заканчивающаяся на «аbс»;
произвольная цепочка символов из «а»,«b»,«с», заканчивающаяся на «сbа».
4. Три подряд пришедших символа «а» в произвольной цепочке
из «а» и «b», после которых следует «b»;
три подряд пришедших символа «b» в произвольной цепочке из
«а» и «b», после которых следует «а»;
три подряд пришедших символа «b» в произвольной цепочке из
«а» и «b», после которых следует «с».
5. Произвольное число символов «а» между двумя символами «b»;
произвольное число символов «b» между двумя символами «с»;
три подряд пришедших символа «с».
6. Произвольная цепочка из «0» и «1» между «/*» и «*/»;
произвольная цепочка символов «0» и «1», заканчивающаяся
тремя символами «0»;
символ «*».
7. Произвольная цепочка из «0» и «1», после которой следует «.»;
цепочка четной длины из «0» и «1» между двумя символами «.»;
два символа «.».
8. Цепочка четной длины из «0» между двумя «1»;
цепочка нечетной длины из «1» между двумя «0»;
две «1» подряд.
9. «1» между двумя цепочками из «0»,четной длины каждая;
23
«0» между двумя цепочками из «1»,четной длины каждая.
10. Произвольная цепочка из «0» и «1», заканчивающаяся на
«101»;
цепочка чередующихся «0» и «1» нечетной длины, за которой
следует «.».
2.2. Программирование алгоритмов разбора
на основе LL(1)-грамматик
1. Проверить, обладает ли заданная грамматика свойством LL(1),
и при необходимости, выполнить ее преобразование к этому виду.
2. Построить для полученной в п. 1 грамматики LL(1)-таблицу
разбора.
3. Разработать программную реализацию синтаксического анализатора на основе полученной LL(1)-грамматики и соответствующей таблицы разбора. Результат анализа представить в виде последовательности номеров правил грамматики, примененных в процессе разбора.
Варианты задания
1. G::=E
E::=AT
A::=E+|B
T::=MP
M::=T*|B
P::=x|y|(E)
B::=Λ
2.
O::=p|E
E::=YB
Y::=YStBe|Λ
S::=iv
B::=p
3.
P::=bDfLe
D::=dcD|d
L::=scL|s
P – аксиома
O – аксиома
G – аксиома
4.
D::=(L)M
L::=a,L|D,L|a|D
M::=i|j
D – аксиома
24
5.
S::=caA
A::=(L)|Λ
L::=e,L|e
S – аксиома
6.
S::=aA|bB
A::=0A1|01
B::=0B11|011
S – аксиома
7.
S::=t(L)
L::=E|E;L
F::=a|a,F
E::=iF
S – аксиома
8.
S::=aAd|aBc
A::=bA|b
B::=Bf|f
9.
S::=A|D
A::=ab|ac|Ab
D::=cD|a
S – аксиома
S – аксиома
10.
A::=B|D
B::=BCC|a
C::=ba
D::=CaD|b
A – аксиома
2.3. Нейтрализация ошибок при синтаксическом разборе
Дополнить синтаксический анализатор для LL(1)-грамматики,
разработанный в рамках предыдущего задания, функцией нейтрализации синтаксических ошибок с использованием алгоритма решения этой задачи для нисходящего синтаксического разбора.
2.4. Схемы синтаксически-управляемого перевода
Разработать программную реализацию заданной схемы синтаксически-управляемого перевода, воспользовавшись для анализа входного предложения одним из алгоритмов восходящего разбора в соответствии с вариантом задания.
Варианты задания
Код варианта задания состоит из двух цифр, первая из которых
определяет номер схемы синтаксически-управляемого перевода, вто­
рая – алгоритм восходящего разбора входного предложения (1 – алгоритм LR(1)-разбора, 2 – алгоритм разбора с использованием отношений простого предшествования).
25
Таблица вариантов задания
№
варианта
1
2
3
4
5
6
7
8
9
10
Код
11
12
21
22
31
32
41
42
51
52
Схемы синтаксически-управляемого перевода
1.
S::=Sa,aSa
S::=Sb,bSb
S::=c,c
2.
E::=+Ea,Ea+
E::=*Ea,Ea*
E::=a,a
3.
E::=T&E,TE&
E::=T,T
T::=a,a
T::=-a,aT::=(E),E
T::=-(E),EЕ = аксиома
4.
S::=aSbSc,1S2S3
S::=d,4
S::=e,5
5.
S::=S1,11S
S::=S0,00S
S::=+,*
2.5. Содержание отчета
1. Постановка задачи.
2. Грамматика, по которой строится автоматная модель.
3. Автоматная модель в виде графа переходов и выходов или управляющей таблицы.
4. Текст программы.
5. Описание тестовых примеров.
26
Библиографический список
1. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. М.: Мир, 1978. Т. 1. 612 c.
2. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. М.: Мир, 1978. Т. 2. 612 c.
3. Ахо А., Сети Р., Ульман Дж. Компиляторы: принципы, технологии
и инструменты. М.: Вильямс, 2003. 768 с.
4. Гордеев А. В., Молчанов А. Ю. Системное программное обеспечение.
СПб.: Питер, 2001. 736 с.
5. Грис Д. Конструирование компиляторов для ЦВМ. М.: Мир, 1975. 544 с.
7. Миллер Р. Теория переключательных схем. М.: Наука, 1970. Т. 1. 416 c.
8. Хантер Р. Основные концепции компиляторов. М.: Вильямс, 2002.
256 с.
9. Хантер Р. Проектирование и конструирование компиляторов. М.:
Финансы и статистика, 1984. 232 с.
Содержание
1. Теоретическое введение................................................... 1.1. Задача лексического анализа. Использование автоматной модели для лексического анализа............................... 1.2. Алгоритмы синтаксического анализа с использованием
КС-грамматик............................................................... 1.2.1.Постановка задачи синтаксического анализа. Организация данных. Общая схема алгоритмов детерминированного разбора......................................................... 1.2.2. Cинтаксический анализ для LL(1)-грамматики..... 1.2.3. Синтаксический анализ для LR(1)-грамматики..... 1.2.4. Синтаксический анализ для грамматики простого
предшествования....................................................... 1.2.5. Нейтрализация ошибок при LL(1)-разборе............ 1.2.6. Синтаксически-управляемый перевод.................. 2. Задания к практическим занятиям................................... 2.1. Программирование алгоритмов лексического анализа
с использованием автоматных грамматик.......................... 2.2. Программирование алгоритмов разбора на основе LL(1)грамматик.................................................................... 2.3. Нейтрализация ошибок при синтаксическом разборе.... 2.4. Схемы синтаксически-управляемого перевода............. 2.5. Содержание отчета................................................... Библиографический список................................................. 3
3
6
6
9
13
16
20
21
22
22
24
25
25
26
27
27
Документ
Категория
Без категории
Просмотров
2
Размер файла
289 Кб
Теги
teoriya, program, metod, yazykov, transp
1/--страниц
Пожаловаться на содержимое документа