Операции над языками

Размещено на http://www.allbest.ru/

1. Операции над языками. Регулярные выражения

L M = {s | s L s M}

LM = { append(s₁, s₂) | s₁ L s₂ M}

L⁰ L¹ L² … L^* = ^? _i=0 Lⁱ

L⁺ = ^? _i=1 Lⁱ

Формальные языки можно определить, пользуясь регулярными выражениями. С их помощью можно показать, как строятся элементы языка. Регулярные выражения над алфавитом определяются индуктивно.

Регулярное множество в алфавите T определяется рекурсивно следующим образом:

1. (пустое множество) ? регулярное множество в алфавите T;

2. {e} ? регулярное множество в алфавите T (e ? пустая цепочка);

3. {a} ? регулярное множество в алфавите T для каждого ;

4. если P и Q ? регулярные множества в алфавите T, то регулярными являются и множества

1. p|q

2. pq

3. p*

5. ничто другое не является регулярным множеством в алфавите T.

Итак, множество в алфавите T регулярно тогда и только тогда, когда оно либо , либо {e}, либо {a} для некоторого , либо его можно получить из этих множеств применением конечного числа операций объединения, конкатенации и итерации.

формальный контекстный грамматика язык

2. НКА: формальное описание, построение множества достижимых состояний

Цепочка принимается автоматом, если существует путь из начального состояния в конечное, метки дуг которого формируют эту цепочку.

Формально КА определяется пятеркой <S, , , s₀, F>,

S - конечное множество состояний;

- конечное множество входных символов (алфавит);

- отношение переходов, это подмножество S на У, к которому добавлена пустая строка; s Ч( {})Чs

s₀ - начальное состояние; s₀ S

F S - множество финальных состояний.

Функция переходов - определяет для заданного состояния s и входной последовательности w множество состояний, в которых может оказаться автомат, обработав входную строку w. Определяется:

1) s' (S,) если s' (s, )

2) s' (S,) если есть путь по переходам, т.е. если есть состояние s'' (S,) и одновременно s' (s'',)

3) когда строка не пустая: s' (S,aw), если есть состояние s'' (s, а) и s' (s'',w). Работа конечного автомата представляет собой некоторую последовательность шагов, или тактов. Такт определяется текущим состоянием управляющего устройства и входным символом, обозреваемым в данный момент входной головкой. Сам шаг состоит из изменения состояния и, возможно, сдвига входной головки на одну ячейку вправо.

Недетерминизм автомата заключается в том, что, во-первых, находясь в некотором состоянии и обозревая текущий символ, автомат может перейти в одно из, вообще говоря, нескольких возможных состояний, и во-вторых, автомат может делать переходы по e.

3. Преобразование регулярных выражений в НКА

Описывать лексику языка удобнее в форме регулярных выражений, а распознавать язык с помощью КА. Поэтому важно уметь преобразовывать определения языка в форме регулярных выражений в определение в форме КА. Такое преобразование предложил Kennet Thompson. Покажем его в форме диаграмм. Т - функция определения преобразования.

Регулярные выражения служат для описания регулярных множеств. Для распознавания регулярных множеств служат конечные автоматы.

1. Для выражения s|t автомат M(s|t):

2. Для выражения st автомат M(st):

3. Для выражения s* автомат M(s*) строится:

4. Преобразование НКА в ДКА

Входные данные: НКА - N. Нужно получить ДКА - D с множеством состояний Dstates и множеством переходов Dtrans. Этот ДКА должен быть таким, чтобы его язык был бы таким же, как и у НКА.

Рассмотрим теперь сам метод: s - состояние, T - множество состояний.

Для работы понадобятся функции:

1) - closure (s) - замыкание, которое вычисляет множество состояний НКА N, достижимых из состояния s через -переходы.

2) - closure (T), которая выдает множество состояний автомата N, достижимых из состояния, принадлежащего Т, через -переходы.

3) move (T, a) - переход. Она строит множество состояний автомата N, в которые есть переход по символу «а» из некоторого состояния, принадлежащего Т.

Рассмотрим, как строится множество Dstates. Состояния из Dstates можно помечать.

АЛГОРИТМ:

1) заносим в множество Dstates состояние Т = - closure (s₀) и оставляем это состояние не помеченным.

2) в цикле while существует Т, Т Dstates и Т - непомечено

do begin

1. помечаем состояние Т

2. в цикле для каждого входного символа «а», принадлежащего - алфавиту автомата, выполним следующее: вычислим множество U = - closure(move (T, a))

3. проверим, если U не принадлежит Dstates, тогда заносим U в Dstates непомеченным, т.е. (должны найти варианты переходов (оно должно быть обработано)). В множество Dstates заносим переход (Т, а, U).

На этом все циклы завешаются. Этот алгоритм позволяет построить ДКА.

При работе НКА нужно каждый раз вычислять множество состояний, в которые можно попасть по - переходам. Если примем такие переходы за состояние нового автомата, тогда получим ДКА.

5. Минимизация ДКА

Было доказано, что для каждого ДКА можно определить единственный минимальный (с точностью до наименований состояний) ДКА. В автомате некоторые состояния могут быть эквивалентными.

Состояние S_i и S_j эквивалентны при выполнении двух условий:

1) оба конечные

2) оба не конечные, но для каждого входного символа они имеют переходы в эквивалентное состояние.

Алгоритм минимизации:

1) разбиваем множество состояний КА на два подмножества - финальное и не финальное.

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

6. Контекстно-свободные языки. Вывод. Дерево вывода

КСЯ можно разбирать на части. Паскаль имеет вложенную структуру. If E then S1 (оператор) else S2 (оператор). Здесь можно выделить синтаксические категории (S1) - нетерминалы и ключевые слова - терминалы (имеют законченный вид). Для описания синтаксиса ЯП используется БНФ (Форма Бэкуса-Наура). В ней даются определения нетерминалов через терминалы и нетерминалы. Для оператора if:

<оператор>::= if <выражение> then <оператор> else <оператор>. Далее каждый оператор также можно раскрыть.

Для каждой грамматики можно определить правило непосредственного вывода: если определены последовательности символов и такие, что V* и V* (конечное множество грамматических символов), и если задана продукция А>Р, то из последовательности символов А можно получить .

Здесь > означает применение правила подстановки или непосредственного вывода.

Выводом называется последовательность постановок, она обозначается >*. Эта запись означает, что из выводится за 0 или более шагов. >+: из выводится за 1 или более шагов.

Каждая цепочка символов, встречающихся в выводе, называется промежуточной цепочкой. Если промежуточная цепочка выводима из начального символа, то она называется выводимой цепочкой (сентенциальной формой).

Вывод цепочки можно представить в виде дерева. Если на каждом шаге заменяется самый левый нетерминал, то вывод называется левосторонним, если самый правый, то правосторонний.

В общем случае грамматика может порождать несколько различных деревьев вывода для одной и тоже цепочки (неоднозначная). Однозначная - если каждой выводимой цепочке соответствует единственное дерево вывода.

7. Контекстно-свободные грамматики для регулярных языков

КСГ описывают язык как множество строк, полученных применением конечного числа продукций к стартовому символу. КСГ - четверка символов <V, , P, S>, где

V - конечное множество грамматических символов;

- терминальные символы; N = V - - нетерминальные символы. , N V.

P - множество продукций; P N * V* - последовательность грамматических символов (возможно пустая). Условие, что <A, > p, будет записываться в виде А>.

Каждая продукция имеет голову и хвост (правая и левая части). Голова всегда нетерминал, который частично определяется этой продукцией, хвост - конечная цепочка грамматических символов, которая служит определением этого нетерминала.

S- стартовый (начальный) нетерминал.

Отметим условные обозначения:

а, b, c - терминальные символы;

A, B, C - нетерминальные символы;

U, V, W - переменные, принадлежащие множество V;

, , - последовательности грамматических символов (, , V*);

u, v, w - элементы алфавита (u, v, w ).

Пример грамматики

S > aABc 1. S > aABc

S > 2.

A > cSB 3. A > cSB

A > Ab 4. Ab

B > bB 5. B > bB

B> a 6. a

Для каждой грамматики можно определить правило непосредственного вывода или правила постановки правила.

Любой регулярный язык м. б. описан КСГ. Алгоритм: для каждого КА строит КСГ.

1. берем алфавит КА и считаем его множеством терминальных символов;

2. множество состояний автомата берем в качестве множества нетерминальных символов, где начальное состояние соответствует стартовому нетерминалу;

3. если в КА есть переход из сост-я А в сост-е В по входному символу х, в грамматику включается продукция А>хВ

4. если состояние С - финальное, то включается продукция С>.

Класс грамматик, порождающих регулярные языки, называется праволинейными (правая часть каждого ее правила содержит не более 1 нетерминала, который стоит в конце)

8. Метод грамматического разбора сверху-вниз. LL(1)-грамматики

Суть: начинаем разбор со стартового нетерминала и, применяя продукции, заменяем нетерминал ее левой части на последовательность символов ее правой части. Цель: получить в обрамлении листьев этого дерева исходную последовательность.

Как сделать выбор среди двух продукций: A > б | в?

x ? FIRST(б) ? б ?* x г е ? FIRST(б) ? б ? е

Грамматика относится к классу LL(1) если FIRST(б) ? FIRST(в) = ? ,

а если б ?* е то должно выполняться FIRST(в) ? FOLLOW(A) = ? .

Для правой части продукции определить множество FIRST, как множество нетерминалов, с которого может начинаться выводимая этим правилом последовательность. А для каждого нетерминала определить множество FOLLOW, т.е. множество следующих нетерминалов, которые могут встретиться непосредственно за этим нетерминалом.

9. Исключение левой рекурсии

Для такого случая существует алгоритм, исключающий левую рекурсию:

1) определяем на множестве нетерминалов какой-либо порядок (А₁, А₂, …, А_n)

2) берем каждый нетерминал, если для него есть продукция, учитывающая нетерминал, стоящий левее, и преобразуем грамматику:

for i:=1 to n do

for j:=1 to i-1 do

if Ai > Ajг then Ai>д1г

¦ д2г

¦ дkг, где

Aj > д1¦ д2¦ …¦ дk

3) исключаем все случаи непосредственной левой рекурсии (правило1)

10. Левая факторизация

LL(1)-грамматики нужны для того, чтобы выбрать нужную продукцию для разбора сверху-вниз, чтобы не произошло зацикливание.

Иногда существует возможность преобразовать грамматику к LL(1) виду, используя метод левой факторизации.

Например: S> if B then S

¦if B then S else S

Эти продукции нарушают условие LL(1)-грамматик. Эту грамматику можно преобразовать к виду LL(1).

S > if B then S Tail

Tail > else S

| е

В общем виде это преобразование можно определить так:

A > б в₁ | б в₂ … | б в_N | г

вводим новый нетерминал В, для которого

A > б B

| г

B > в₁

| в₂

…

| в_N



11. Построение множества FIRST

Для последовательности определим множество first как множество терминалов, с которых может начинаться последовательность, выводимая из . Если из можно вывести пустую строку, то в множество first последовательности должно присутствовать . Определим множество first для некоторого грамматического символа х.

1. Если х - терминал, то first(x)={x}. Так как первым символом последовательности из одного терминала может являться только сам терминал.

2. Если в грамматике присутствует правило Х , то множество first(х) включает . Это означает, что Х может начинаться с пустой последовательности, то есть отсутствовать вообще.

3. Для всех продукций вида XY₁ Y₂ … Y_k выполняем следующее. Добавляем в множество first(Х) множество first(Y_i) до тех пор, пока first(Y_i-1) содержит , а first(Y_i) не содержит . При этом i изменяется от 0 до k. Это необходимо, так как если Y_i-1 может отсутствовать, то необходимо выяснить, с чего будет начинаться вся последовательность в этом случае.

12. Построение множества FOLLOW

Алгоритм построения множества follow заключается в следующем. Вначале символ конца входной последовательности помещается в множество follow стартового нетерминала (шаг 1). Затем выполняются шаги 2 - 4 до тех пор, пока можно еще что-либо добавить в множество follow какого-либо грамматического символа.

2. Если есть правило АB, то в множество follow(В) добавляем множество first() без . То есть, если есть правило, утверждающее, что за В следует , то за нетерминалом будут следовать терминалы, с которых начинается последовательность .

3. Если есть правило АB, то в множество follow(B) добавляется множество follow(A). Таким образом, если есть правило, утверждающее, что нетерминалом В заканчивается последовательность А, то за нетерминалом В будут следовать те же терминалы, что и за всей последовательностью А.

4. Если есть продукция АB и пустая последовательность принадлежит first(), то в множество follow(B) добавляется множество follow(A). Если последовательность не пуста, то за B могут следовать терминалы из , которые уже были добавлены в follow(B) на втором шаге алгоритма. Для , являющейся пустой последовательностью, можно привести рассуждения, аналогичные шагу 3.

13. Построение таблицы разбора для LL(1)-грамматики

После построения множеств first и follow можно сформировать саму таблицу разбора следующим образом.

Для всех продукций А грамматики выполняем:

1. Для всех терминалов а, принадлежащих first(), в клетку [А, а] таблицы разбора записываем продукцию А.

2. Если принадлежит first(), то для всех b, принадлежащих follow(А), в клетку [A, b] записываем продукцию А.

Во все остальные клетки таблицы записываем признак ошибки.



14. Алгоритм работы таблично-управляемого анализатора для LL(1)-грамматики

Алгоритм:

Вначале входной буфер содержит лексические знаки исходной программы. В стеке, на дне, лежит стартовый нетерминал. Алгоритм берет символ из вершины стека (Х), берет первый символ и входного буфера (а), и эта пара определяет дальнейшие действия. 3 варианта:

1) Х=а=$, тогда алгоритм успешно завершает работу.

2) Х=а<>$, тогда анализатор удаляет Х из стека и перемещает указатель входного буфера на следующий символ, иначе выдается ошибка.

3) если Х - нетерминал, тогда алгоритм обращается к ячейке М[Х,а]. Если в этой ячейке содержится продукция Х>UVW, то в стеке Х заменяется на UVW, причем U должно оказаться сверху. В этой ячейке содержится признак ошибки, тогда необходимо запустить процедуру выхода из ошибочной ситуации.

15. Грамматики простого предшествования. Использование отношения предшествования операторов

Грамматики простого предшествования отличаются следующим:

1) у них нет продукций, имеющих в правой части .

2) нет продукций, в которых два нетерминала стоят рядом.

Основы получаются: цепочка просматривается до знака *> метка идем обратно до знака <* метка. Между метками будет основа. Когда свернем эти основы, получим: Е+Е*Е. Нетерминалы нужны только для генерации результирующего кода.

16. Построение отношения предшествования операторов исходя из их ассоциативности и приоритета. Алгоритм разбора для ГПП

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

1) А1*>А2, а А2<*А1. Напр: **>+, +<**

2) для ассоциат-х А1<*А2, А2<*А1

3) А <* id, id*>А, id<*'(', `)' *>А, A*>')', A*>$, $<*$.

Алгоритм:

Повторять бесконечно:

если в вершине стека $, и тек. символ - $,

то успешный выход.

иначе пусть

a - самый верхний в стеке терминал,

b - первый символ входного буфера.

если a ? b или a ? b то, (* сдвиг *)

1) делаем push b;

2) следующий вх. символ становится тек.

иначе если a ? b то , (* свёртка *)

repeat pop X_i

until (верш. стека ? X_i)

иначе ошибочная ситуация.



17. Синтаксический анализ снизу - вверх. Основа. Подрезка основы

Из входной последовательности берем по символу и сдвигаем в стек. Если в стеке окажется правая часть правила, то замещаем ее на нетерминал левой части. Просматривая входную последовательность слева на право, находим в ней правую часть правила, и заменяем на нетерминал в левой части (Должен быть правый вывод).

Основой правой сентенциальной г называется продукция а) А>в , и позиция в г , где находится фрагмент в, который можно заменить на А, и при этом получится предыдущая правая сентенциальная форма с правым выводом г.

Основа - самое левое полное поддерево, состоящее из узла и потомков.

18. Восходящий разбор методом «сдвиг-свертка» на основе стека

Этот алгоритм должен выполнить 4 операции:

1)Сдвиг-символ из буфера заносим в стек.

2)Свертка-анализатор определяет, что в стеке находится основа, затем на левую часть правила.

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

4)Ошибка - обнаруживается ошибки и запускается приложение обработки ошибки.

19.Активный префикс. Обосновать, что основа всегда формируется в вершине стека

Стек в синтаксическом анализаторе используется потому что основа всегда появляется на поверхности стека и не может сформироваться внутри него. Может быть 2 варианта таких шагов:

1) когда есть в правой части нетерминал

S ->*бAz -> (A->вBy) бвByz -> (B->г) бвгyz

2) когда их нет

S ->*бBxAz -> (A->y) бBxyz -> (B->г) бгxyz

y - последовательность определенных терминалов

20. SLR(1)-разбор. Ситуация. Дополненная грамматика

Рассмотрим SLR методы.

Метод не анализирует, а использует множество Follow. Каждая продукция грамматики может ожидать в стеке свою основу, это ожидание разбивается на ряд этапов, в зависимости, какая часть основы уже распознана.

Фазу ожидания правила называют - ситуацией (Item).

`*' - указывает какой фрагмент основы уже распознан в данной ситуации

f > е [A> *] эту ситуацию можно представить парой чисел: Номер продукции; Позиция точки;

Эти ситуации можно расшифровать как состояния конечного недетерминированного автомата распознающего основы.

Если грамматика G имеет стартовый символ S, то грамматика G' будет для нее дополненной грамматикой, если в нее добавить стартовый символ S' и продукцию S> S'.



21. Алгоритм вычисления замыкания множества ситуаций (Closure)

Для заданного множества ситуаций I грамматики G, замыкание этого множества Closure(I):

Базовый случай: все ситуации I closure(I).

Общий случай (шаг индукции): если ситуация [ A > б * B в ] closure(I), правило может начать ожидать свою основу B > г (существует такая продукция), то добавим ситуацию [ B > * г ] closure(I).

Этот процесс выполняется до тех пор, пока что-то можно добавить в множество closure(I).

Вначале введем понятие замыкание множества ситуаций I (closure(I)). Замыкание I строится по двум правилам.

1 В замыкание I заносится множество ситуаций I.

2 Если ситуация [AB] уже принадлежит closure(I) и есть продукция B, то добавляем в closure(I) ситуацию [B].

Теперь рассмотрим переходы (goto (I,x)). Переход представляет собой множество ситуаций, в которые можно перейти из множества ситуаций I по грамматическому символу х, то есть по терминалу или нетерминалу. При выполнении функции (goto (I,x)) строят замыкание множества состояний вида [Ax], если в I есть ситуация [Ax], то есть точка переходит за символ х в ситуациях. После этого строиться замыкание этого множества.



22. Каноническая совокупность всех возможных ситуаций

Используя функцию Clouse(I) и функцию Goto(I,x), можно построить множество C -- канонической совокупности для любых множеств ситуаций и дополненной грамматики G'.

Берем множество ситуаций состоящей из 1-ой ситуации {[S' >* S]}, и строим для него замыкание, затем в цикле для каждого грамматического символа находим Ґ множества Ii, в которые есть переход из уже известного множества.

Построение канонического множества:

procedure Items (G')

begin

C := {closure({[S' > * S]})}

repeat

Для каждого множества ситуаций I C выполнить:

Для каждого грамматического символа X выполнить:

если goto(I,X) ? и goto(I,X) C то добавить goto(I,X) в C.

until C - не пополняется

end

Активная ситуация -- это ситуация вида [A>в1*в2], для активного префикса б в1, если есть правый вывод S'=>* бAW =>* б в1 в2W.

Активная ситуация та, которая возможна при разборе активного префикса, такую ситуацию должен выполнять синтаксический анализатор.

Если в2?е, то в стеке основа еще не сформировалась и нужно выполнить операцию «сдвиг». Если в2=е, то в1-это «основа» с правилом A>в1и нужно выполнить «свертку».

23. Переходы в SLR(1) анализаторе. Функция Goto

Определение переходов

Определим функцию переходов Goto(I,x), где I-множество ситуаций, X-грамм символ. Строит то же множество ситуаций в которые можно перейти из заданного множества по символу X. Функция Goto строит замыкания вида:

[ A > б X * в ] если ситуация [ A > б * X в ] closure(I). Если в I есть ситуация в которой следует заданный символ X, она превращается в (2).

24. Алгоритм заполнения таблиц Action и Goto

Таблица action в зависимости от пары <входной сигнал, состояние> определяет, достигнут ли конец основы. Если конец основы достигнут, то выполняется приведение, в противном случае выполняется сдвиг.

Таблица goto в зависимости от пары <нетерминал в вершине стека, состояние> определяет состояние конечного автомата после выполнения приведения.

Алгоритм заполнения таблиц анализа заключается в следующем.

1. Построить каноническую совокупность множества ситуаций.

2. Каждое множество I канонической совокупности определяет состояние конечного автомата с соответствующим номером, а следовательно, строку в таблицах анализа. Ячейки в таблице заполняются по следующим вариантам:

а) если ситуация [Aa] принадлежит множеству I_i и существует переход по терминалу a в некоторое множество I_j, то в ячейку action[i, a] заносим значение shift j. В приведенной ситуации основа не может быть найдена, так как для ее завершения как минимум необходимо распознать терминал a, то есть выполнить сдвиг;

б) если ситуация [A] принадлежит множеству I_i, то для всех терминалов а, принадлежащих follow(A), в ячейку action[i, a] заносим значение reduce A. Это происходит потому, что основа найдена полностью и распознавание любого символа, следующего за А, должно повлечь приведение основы;

в) если ситуация [SS] принадлежит множеству I_i, то есть можно осуществить редукцию для стартовой продукции, то в ячейку action[I, eof] записываем значение accept. Разбор успешно закончен, если достигнут конец входной последовательности.

3. Если существует переход из множества I_i во множество I_j по некоторому нетерминалу А, то в ячейку goto[i, А] заносим значение j.

4. Все незаполненные ячейки в таблицах action и goto заполняем значением «ошибка».

5. Начальным состоянием автомата является состояние, содержащее ситуацию [SS].

25. Алгоритм LR- разбора

LR-грамматический разбор используется для большого класса КСГ. Повторять бесконечно:

пусть s_m - состояние в вершине стека,

a_i - текущий символ входной посл-ти.

если action[s_m,a_i] = shift s,

то push a_i; push s; a_i+1 - тек. символ.

если action[s_m,a_i] = reduce A > в,

то пусть r - длина посл-ти в,

1) делаем pop 2*r раз;

2) находим в таблице переходов

новое состояние s = goto[s_m-r,A].

3) push A; push s;

если action[s_m,a_i] = accept, то успешный выход.

если action[s_m,a_i] = error, то обраб. ош. ситуации.

26. Контекстно-зависимый анализ. Синтаксически управляемая трансляция

В процессе синтаксического анализа формируется дерево разбора, вершинами являются грамматические символы. Ветви дерева придают определенный смысл. Для этого грамм. символам добавляют атрибуты, которые и отражают смысл конструкции языка. В процессе построения дерева разбора можно вычислить его значения. Вычисления выполняются в соответствии с семантическими правилами, связываются с продукцией грамматики.

E0>E1+E2 { E0:=E1+E2}

Есть 2 способа объединения продукций семантических правил.

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

2)Схемы трансляции в этом случае указывают порядок вычисления семантических правил.

Входная последовательность лексических знаков>дерево разбора>граф зависимостей> порядок выполнения семантических правил

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

27 Синтезируемые атрибуты. Их обработка в алгоритме сдвиг - свертка

Являются расширением контекстно-свободными грамматик. С грамматическими символами связывают множество атрибутов. Дерево будет в вершинах иметь набор переменных. Это дерево называется аннотированным деревом разбора. Значения атрибутов определяется семантическими правилами, связанными с продукциями грамматики в зависимости от вида семантических правил атрибуты м.б. синтезируемыми и наследуемыми.

Синтезируемые -- вычисляют свои значения не используя атрибуты своих «детей».

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

28. Построение абстрактного синтаксического дерева

Транслятор на основе текста программы формирует некоторый промежуточный код. Этот код м.б. абстрактным синтаксическим деревом (АСД).

АСД - это абстрактное представление конструкций языка, полученное из дерева разбора. Обычно в АСД ключевые слова и операторы не показываются, а объединяются в один родительский узел.

Продукция S > if B then S₁ else S₂ порождает сл. фрагмент дерева разбора:

Этому фрагменту соответствует конструкция языка - условный оператор, состоящий из условия и двух операторов:

Самый простой способ вычислить это выражение - это использование постфиксной записи. П.з. - это линеаризированное, т.е. представленное последовательно, представление синтаксического дерева. В ней узлы следуют сразу после своих детей: а в с uminus * в с uminus * + assign

Дуги дерева явно не представлены, но их можно восстановить. Чтобы вычислить такое выражение нужно использовать стек.

Алгоритм: если встречается идентификатор или константа, то заносим в стек, а если операция, то для нее извлекаются необходимые данные из стека, она выполняется, и результат опять заносится в стек.

Для того, чтобы вычислить это выражение на обычном компьютере, нужно взять дерево или граф.

Полученное дерево можно представить в виде массива:

Из этого представления в форме массива можно получить трехадресный код, где каждая команда представляется следующим образом: х:=y op z. x,y,z -имена, константы или генерируемые компилятором временные ячейки. ор - оператор.

С помощью трехадресных команд можно представить и АСД и НАГ.

АСД:

t1:=-c, t2:=b*t1, t3:=-c, t4:=b*t3, t5;=t2+t4, a:=t5.

Для НАГ программа будет проще:

t1:=-c, t2:=b*t1, t5:=t2+t2, a:=t5

Имена переменных можно рассматривать как указатели на записи в таблице символов.

29. Наследуемые атрибуты. Граф зависимостей

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

Синтезируемые -- вычисляют свои значения не используя атрибуты своих «детей».

Наследуемые -- вычисляют свои значения, обращаясь к «братьям» и «родителям».

Наследуемые атрибуты позволяют определить положение идентификатора относительно оператора присваивания.

Возьмем пример с наследуемым атрибутом. Для применения в общем случае нужно уметь строить граф зависимостей. Зависимости можно представить стрелками. Если есть фрагмент дерева разбора, то мы можем граничные символы, имеющие атрибуты поставить в соответствие вершине графа (на обороте):

Если есть продукция A > XY и связанное с ней семантическое правило A.a := f (X.x, Y.y), то для них получится сл. фрагмент графа зависимостей:

Полученный граф должен быть ацикличным (не должно быть циклов), тогда сможем вычислить значения. Для определения порядка вычисления атрибутов нужно применить топологическую сортировку. Эта сортировка определяет порядок узлов графа зависимостей такой, что дуги графа выходят от более ранних узлов к более поздним



30. L-атрибутные определения (L-АО). Схема трансляции

Выделим класс синтаксически управляемых определений L-АО, чьи атрибуты всегда м.б. вычислены, если дерево разбора будет строится в глубину. L-left, т.к. значения атрибутов перемещаются слева направо.

Синтаксическое управление определения называется L-атрибутным, если каждый наследуемый атрибут символа Xi (1<=i<=n) в правой части продукции А>x1, x2,…,xn зависят только:

1)от атрибутов грамматических символов X1, X2,…,Xi-1 (расположенных левее него)

2) от наследуемых атрибутов символа А: А> X1, X2,…,Xi,…,Xn

Схема трансляции

Схема трансляции - это КСГ, в которой с грамматическими символами связаны атрибуты, а в правых частях продукций между грамматических символов могут встречаться семантические действия, которые обычно заключаются в фигурные скобки.

В схеме трансляции используются как наследуемые, так и синтезируемые атрибуты.

При обходе в глубину выполняются семантические действия и получается постфиксная запись. Семантические действия будут выполняться правильно при использовании L-атрибутных определений.

Практически это используется:

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

- при использовании еще и наследуемых атрибутов необходимо руководствоваться следующими правилами:

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

2. действие не д. обращаться к синтезируемому атрибуту символа, стоящего от него правее.

3. синтезируемый атрибут нетерминала левой части правила м.б. вычислен только после всех используемых им атрибутов. Такое действие помещается в конце левой части продукции

31. L - атрибутные грамматики в детерминированном разборе сверху - вниз:

а) Устранение левой рекурсии

б) Проектирование детерминированного транслятора

а) Устранение левой рекурсии (из схемы трансляции)

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

Схема трансляции, представленная на рис.1, преобразуется в схему (рис. 2), ко-торая порождает для выражения 9-5+2 аннотированное дерево разбора, показанное на рис. 3. Стрелки на рисунке указывают путь определения значения выражения.

Рис. 3 - Вычисление выражения 9-5+2

E > E₁ - T { E.val := E₁.val - T.val }

E > T{ E.val := T.val }

T > num { T.val := num.lexval }

E > T { R.i := T.val }

R { E.val := R.s }

R > -

T { R₁.i := R.i - T.val }

R₁ { R.s := R₁.s }

R > е { R.s := R.i }

T > num { T.val := num.val }

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

A > A₁ Y { A.a := g(A₁.a, Y.y) } (01)

A > X { A.a := f(X.x) }

Каждый грамматический символ имеет синтезируемые атрибуты, записанные с использованием соответствующих строчных букв, а f и g -- произвольные функции. Устранив левую рекурсию получим грамматику:

A > X R (02)

R > Y R

| е

С учетом семантических действий запишем преобразованную схему в виде

A > X { R.i := f(X.x) }

R { A.a := R.s }

R > Y { R₁.i := g(R.i, Y.y) } (03)

R₁ { R.s := R.i }

R > е { R.s := R.i }

E > T { R.i := T.nptr }

R { E.nptr := R.s }

R > + T { R₁.i := mknode(`+', R.i, T.nptr)}

R₁ { R.s := R.i }

R > - T { R₁.i := mknode(`-', R.i, T.nptr)}

R₁ { R.s := R.i }

R > е { R.s := R.i }

T > ( E ) { F.nptr := E.nptr }

T > id { mkid (id.entry)}

T > num { T.nptr := mknum(num.value)}

Рис. 5 Преобразованная схема трансляции для построения синтаксических деревьев

На рис. 6 показано, каким образом действия на рис. 5 строят синтаксическое дерево для выражения а-4+с. Синтезируемые атрибуты представлены справа от узлов грамматических символов, а наследуемые -- слева. Листья синтаксического дерева создаются с помощью действий, связанных с продукциями Т > id и T > num. У крайнего слева T атрибут T.nptr указывает на лист для а. Указатель на узел для а наследуется как атрибут R.i в правой части Е > Т R.

При применении продукции R > -TR1 к правому потомку корня, R.i указывает на узел для a, a T.nptr-- на узел для 4. Узел для а-4 строится путем вызова функции mknode для оператора "-" и этих указателей.

И наконец, при использовании продукции R > е атрибут R. i указывает на корень синтаксического дерева в целом. Все дерево целиком возвращается как значение E.nptr, вычисляемое с помощью (не показанных на рис. 6) атрибутов s узлов для R.

32. Генератор компиляторов УАСС. Использование неоднозначных грамматик

Yacc - Yet Another Compiler - Compiler.

Описание компилятора имеет три части:

определения

%%

продукции

%%

вспомогательные процедуры

Задание стартового нетерминала

%start <symbol>

Определение терминалов

%token <symbol>

Задание ассоциативности операторов

%left <symbol>

%right <symbol>

%nonassoc <symbol>

Задание типов символов

%token <Real> <symbol>

%left <AddOp> <symbol>

%type <Real> expr

Работа синтаксического анализатора

%token NUM

%left '+'

%left '*'

%%

expr : expr '+' expr

| expr '*' expr

| '(' expr ')'

| NUM

;

Дополнительная продукция

state 0:

$accept : _ expr $end

'(' shift 2

NUM shift 3

. error

expr goto 1

33. Автомат с магазинной памятью. Графическое представление автомата с магазинной памятью. Вычислительный процесс в МП - автомате

Автомат с магазинной памятью - это конечный автомат, использующий магазин (стек).

Единственное ограничение АсМП: доступ к инфе по принципу последний пришел - первый ушел.

Формально АсМП - это семерка <Q, ? , Г, д ,q₀, Z₀, F>, где

Q- конечное множество состояний

?- алфавит - конечное множество символов

Г- конечное множество символов - алфавит магазина

д - ф-ция переходов

q₀ - начальное состояние

Z₀- начальный символ магазина

F- множество финальных или допускающих состояний

Графическое представление автомата с магазинной памятью

34.Автомат с магазинной памятью. Допустимость по заключительному состоянию и по пустому магазину

Допустимость по финальному состоянию.

Пусть задан автомат Р=<Q, ? , Г, д ,q₀, Z₀, F>, тогда L(P) - язык допустимый Р по заключительному состоянию определяется так: {w| (q₀,w, Z₀) |- p*(q, E, б), q€F}, где б - любая цепочка.

Допустимость по пустому магазину.

Пусть Р=<Q, ? , Г, д ,q₀, Z₀, F> - АсМП, тогда N(P)- язык допустимый РЗ по пустому признаку определяется так: {w| (q₀,w, Z₀) |- p*(q, E, Е)} }, где б - любое состояние. Множество F задавать необязательно

35. Типы и проверка типов

Соответствие типов переменных можно сформулировать в виде логических правил типирования.

В системе проверки типов содержаться аксиомы и правила вывода, на основе которых можно выводить типы выражений. Тип выражения определяется из контекста программы.

Информацию, получаемую из контекста, будем называть окружением типирования или просто окружением (Е).

Тот факт, что е имеет тип ф в окружении Е будем записывать: Е+ е : ф. Такое утверждение называется типированием. Система проверки типов является дедуктивной системой. А тип сложного выражения определяется исходя из типов составляющих его частей с применением соответствующего правила вывода:

36. LR(1) анализ. LR(1)-ситуация. Замыкание множества ситуаций. Определение переходов

LR(1)- ситуация. В описании добавляется инфа о том, какие символы м б текущими во время свертки. [A-> б^.в₁a]. Такая ситуация считается допустимой для активного префикса г, если существует вывод B=> ^. дAw=>дбвw

Замыкание множества ситуаций closure(I) определяется индуктивно.

Базовый случай: I € closure(I)

Шаг индукции: Если [A-> б^. Bв,a] € closure(I) и существует продукция В->г, тогда [B->^. г, b] € closure(I) для всех b € FIRST(вa)

Определение переходов. Если ситуация [A-> б^.xб,a] € closure(I), то goto(I,x)строит замыкание вида [A-> бх^. в,a]

37. LR(1) Анализ. заполнение таблиц LR разбора

* LR(1)?анализ ? наиболее мощный метод анализа без возвратов типа сдвиг?свертка;

* LR(1)?анализ может быть реализован довольно эффективно;

* LR(1)?анализаторы могут быть построены для практически всех конструкций языков программирования;

* класс грамматик, которые могут быть проанализированы LR(1)?методом, строго включает класс грамматик,

которые могут быть проанализированы предсказывающими анализаторами (сверху?вниз типа LL(1)).

Анализатор состоит из входной ленты, выходной ленты, магазина, управляющей программы и таблицы анализа (LR(1)-таблицы), которая имеет две части - функцию действий (Action) и функцию переходов (Goto). Управляющая программа одна и та же для всех LR(1)-анализаторов, разные анализаторы отличаются только таблицами анализа.

Анализатор читает символы на входной ленте по одному за шаг. В процессе анализа используется магазин, в котором хранятся строки вида S0X1S1X2S2 ... XmSm (Sm - верхушка магазина). Каждый Xi - символ грамматики (терминальный или нетерминальный), а Si - символ состояния.

Заметим, что символы грамматики (либо символы состояний) не обязательно должны размещаться в магазине. Однако, их использование облегчает понимание поведения LR-анализатора.

Элемент функции действий Action[Sm; ai] для символа состояния Sm и входа , может иметь

одно из четырех значений:

1. shift S (сдвиг), где S ? символ состояния,

2. reduce A г (свертка по правилу грамматики A г),

3. accept (допуск),

4. error (ошибка).

Алгоритм заполнения таблиц анализа заключается в следующем.

1 Построить каноническую совокупность множества ситуаций.

2 Каждое множество I канонической совокупности определяет состояние конечного автомата с соответствующим номером, а следовательно строку в таблицах анализа. Ячейки в таблице заполняются по следующим вариантам.

а) Если ситуация [Aa] принадлежит множеству I_i и существует переход по терминалу a в некоторое множество I_j, то в ячейку action(i, a) значение shift j. В приведенной ситуации основа не может быть найдена, так как для ее завершения как минимум необходимо распознать терминал a, то есть выполнить сдвиг.

б) Если ситуация [A] принадлежит множеству I_i, то для всех терминалов а, принадлежащих follow(A), в ячейку action[i, a] заносим значение reduce A. Это происходит потому что основа найдена полностью и распознавание любого символа, следующего за А, должно привести к приведению основы.

в) Если ситуация [SS], принадлежит множеству I_i, то есть можно осуществить редукцию для стартовой продукции, то в ячейку action[I, eof] записываем значение accept. То есть разбор успешно закончен, если достигнут конец входной последовательности.

3 Если существует переход из множества I_i в множество I_j по некоторому нетерминалу А, то в ячейку goto[i, А] заносим значение j.

4 Все незаполненные ячейки в таблицах action и goto заполняем значением “ошибка”.

5 Начальным состояние автомата является состояние, содержащее ситуацию [SS]

38. LALR(1) - грамматики. Построение LALR(1) - таблиц разбора

LALR(1) - грамматики. LR(1) - таблицы разбора имеют слишком много состояний. LALR(1) разбор (Look-Ahead - с предпросмотром) использует объединение LR(1)-множеств и таким образом сокращается объём таблиц. LALR(1) слабее чем LR(1). В нём не может возникнуть конфликт сдвига со свёрткой, поскольку команда сдвига включается не зависимо от предпросмотра. Может возникнуть конфликт свёрток, но это бывает очень редко.

Построение LALR(1) - таблиц разбора

• Строим множества LR(1) ситуаций.

• Объединяем множества, имеющие одинаковые ядра:

39. LR-разбор для неоднозначных грамматик

• Пример грамматики:

1) E' > E

2) E > E + Е

3) E > E * Е

4) Е > ( E )

5) Е > id

Размещено на Allbest.ru

...