Теория компиляторов-1. Л.31 Классическая теория компиляторов Лекция 3

Теория компиляторов-1. Л.32 КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ P: A, где A N, (N )+ N = {группа_существ, глагол, прилагательное, существительное, предлог, фраза} = {печатать, стереть, зеленый, первый, последний, символ, строка, страница, в} S = фраза P = { Фр Г, Гс Гс Прил, С Гс Прил, С, Предлог, Гс Г печатать Г стереть Прил зеленый Прил первый Прил последний С символ С строка С страница Предлог в} "Печатать зеленый строка", "Стереть первый символ в последний строка в первый страница" и т.п.

Теория компиляторов-1. Л.33 Анализатор на Прологе /* Фраза -> Глагол, Группа_сущ Группа_сущ -> Прилагат, Существ Группа_сущ -> Прилагат, Существ, Предлог, Группа_сущ Глагол ->... Прилагат ->... Существ ->... Предлог ->...*/ goal FRAZA = ["печатать","первый","символ","в","последний", "строка"], print_list(FRAZA), s(FRAZA). clauses s(A) :- sentence(A), write("\nФРАЗА РАСПОЗНАНА\n"). s(_) :- write("\nОШИБКА: ФРАЗА НЕ РАСПОЗНАНА\n"). % СЛУЖЕБНЫЕ И СЕРВИСНЫЕ ПРЕДИКАТЫ append([],L,L). append([H|A],B,[H|C]) :- append(A,B,C). print_list([]). print_list([Head|Tail]) :- write(Head,"."), print_list(Tail). % СИНТАКСИС sentence(S) :- append(S1,S2,S), glagol(S1), GS(S2), write("\nГлагол:"), writel(S1), write("\nГс: "), writel(S2). GS(S) :- append(S1,S2,S), prilagat(S1), noun(S2), write("\n*** Разбор ГС-1:"), write("\nПрилагательное: "),writel(S1), write("\nСуществительное:"),writel(S2). GS(S) :- append(S1,Stmp1,S), append(S2,Stmp2,Stmp1), append(S3,S4,Stmp2), prilagat(S1), noun(S2), predlog(S3), GS(S4), write("\n*** Разбор ГС-2:"), write("\nПрилагательное: "), print_list(S1), write("\nСуществительное:"), print_list(S2), write("\nПредлог: "), print_list(S2), write("\nГс: "), print_list(S2). % СЛОВАРЬ noun(["символ"]). noun(["строка"]). noun(["страница"]). glagol(["печатать"]). glagol(["стереть"]). prilagat(["первый"]). prilagat(["второй"]). prilagat(["последний"]). predlog(["в"]).

Теория компиляторов-1. Л.34 Грамматика арифметического выражения G 0 =({E,T,F},{a,+,*,(,)},P,E) P = { E E+T E T T T*F T F F (E) F a }

Теория компиляторов-1. Л.35 Анализатор на Прологе 1.E(L) :- T(L). 2.E(L) :- a3(L1,["+"],L3,L), 3. E(L1), 4. T(L3). 5.T(L) :- F(L). 6.T(L) :- a3(L1,["*"],L3,L), 7. T(L1), F(L3). 8.F(L) :- L=["a"]. 9.F(L) :- a3(["("],L2,[")"],L), 10. E(L2).

Теория компиляторов-1. Л.36 ОК-ГРАММАТИКИ Грамматики определенных клауз. Наличие контекстуальных аргументов. Гс Мест(k), Прил(k), Сущ(k), ГС k - контекстуальный аргумент, отвечающий за согласование родов. Мест(муж) этот Мест(жен) эта Прил(муж) второй Прил(жен) вторая Сущ(жен) строка Сущ(муж) пароль и т.д. На Прологе: mest(муж, этот). pril ("жен", "вторая"). и т.п.

Теория компиляторов-1. Л.37 СИНТАКСИЧЕСКИ УПРАВЛЯЕМЫЙ ПЕРЕВОД S E E T, E E+T, T F, T T*F, F a, F (E) Левый вывод цепочки: Пусть дана фраза: a+a*a. S E E+T E+T*F T+T*F F+F*F a+a*a фраза принадлежит нашему языку. Но: 1) долго, 2) неопределенно, 3) надо сделать что-то полезное (сформировать ПФ)

Теория компиляторов-1. Л.38 Идея СУ-перевода Применение каждого правила грамматики будет вызывать выполнение той или иной семантической процедуры. (E,E) (E+T, ET+) (T+T, TF+) (F+T, FT+) (a+T, aT+) (a+T*F, aTF*+) (a+F*F, aFF*+) (a+a*F, aaF*+) (a+a*a, aaa*+).

Теория компиляторов-1. Л.39 Перевод инфиксной формы записи в ПФ Z ::= E E ::= T | E+T | E-T | -T T ::= F | T*F | T/F F ::= a | (E)

Теория компиляторов-1. Л.310 Алгоритм СУ-перевода "a*(b+c)#" Признак нормального окончания работы алгоритма: когда в стеке остался единственный символ Z, а текущим символом является #, то процедура завершена успешно. В противном случае фраза построена неверно. Недостаток: плохая диагностика

Теория компиляторов-1. Л.311 Замечание об унарных операторах Считается, что унарные операторы имеют наивысший приоритет. Исходя из этого, соответствующий правила грамматики должны записываться в конце списка. Тогда получаем: … T -F T !F … Т.е. действие унарного оператора (- или !) будет направлено на F (F (E), F a). Если же поместить унарный оператор в правило E -T (или E !T), то оператор будет действовать уже на терм. Это означает, что в выражении "!a*b" сначала будет вычислено произведение a*b, а затем только будет взято его отрицание.

Теория компиляторов-1. Л.312 АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ Для КСГ создать конечный распознающий автомат уже невозможно. Более сложные по своей структуре автоматы – автоматы с магазинной памятью, которые применяются для распознавания фраз КСГ. МП = (, Q, Г, q 0, z 0, T, P), где – конечный входной алфавит (входной словарь); Q – конечное множество состояний; Г – конечный алфавит магазинных символов; q 0 – начальное состояние управляющего устройства (q 0 Q); z 0 – символ, находящийся в магазине в начальный момент времени (начальный символ), z 0 Г; T – множество терминальных (заключительных) состояний, T Q; P: Q ( {e}) Г Q Г*

Теория компиляторов-1. Л.313 Понятия, связанные с АМП Конфигурацией МП-автомата называется тройка (q,, ) Q * Г*, где –q – текущее состояние устройства; – – неиспользованная часть входной цепочки; первый символ цепочки находится под входной головкой; если = e, то считается, что вся входная лента прочитана; – – содержимое магазина; самый левый символ цепочки a считается верхним символом магазина; если a=e, то магазин считается пустым. Такт работы МП-автомата: (q,a,Z ) (q',, ) Если a=e, то этот такт называется e-тактом. В e-такте входной символ не принимается во внимание и входная головка не сдвигается. Если =e, то верхний символ удаляется из магазина (магазинный список сокращается). Начальная конфигурация МП-автомата – это тройка (q 0,, Z 0 ), * Говорят, что цепочка допускается МП-автоматом, если (q 0,, Z 0 ) *(q, e, ) для некоторых q T и Г* Расширенный МП-автомат МП r = (, Q, Г, q 0, Z 0, T, P r ), где P r – отображение множества Q ( {e}) Г* Q Г*. Расширенный МП-автомат обладает способностью продолжать работу и тогда, когда магазин пуст. Теорема. Пусть G = (N,,P,S) – КС-грамматика. По грамматике G можно построить такой МП-автомат R, что Le(R)=L(G).

Теория компиляторов-1. Л.314 Пример МП-автомата Дано: G 0 =({E,T,F},{a,+,*,(,),#},P,E) P = {E E+T|T T T*F|F F (E)|a} Здесь '#' – символ конца входной последовательности. R = (, Q, Г, q 0, Z 0, T, P), где Q = {q, r}, Г={E, T, F, $} q 0 = q, Z 0 = $, T = {r}, P: (1)(q,e,E+T) (q,E)(*) (2)(q,e,T) (q,E)(*) (3)(q,e,T*F) (q,T) (4)(q,e,F) (q,T) (5)(q,e,(E)) (q,F) (6)(q,e,a) (q,F) (7)(q,#,$E) (r,e) (8)(q,b,e) (q,b) для всех b {a,+,*,(,)}; Замечание 1. Правила (*), применимы, если следующим символом входной цепочки является '+', или '-', ')' или входная цепочка пуста. Замечание 2. Приоритет выполнения правил определяется содержимым стека.

Теория компиляторов-1. Л.315 Пример разбора Вход: "a+a*a". (q,a+a*a#,$) (q, +a*a#, $a) (q, +a*a#, $F) (q, +a*a#, $T) (q, +a*a#, $E) (q, a*a#, $E+) (q, *a#, $E+a) (q, *a#, $E+F) (q, *a#, $E+T) (q, a#, $E+T*) (q, e, $E+T*a) (q, e, $E+T*F) (q, e, $E+T) (q, #, $E) (r, #, e) Схема СУ-перевода и разбор КС-грамматики с помощью АМП эквивалентны. Можно дополнить АМП набором семантических процедур. Тогда можно формировать ПФ. АМП можно считать просто более формальным изложением алгоритма СУ- перевода. Например: 1) алгоритм СУ-перевода: если ни одно из правил не применимо к содержимому стека, то следует поместить в стек очередной символ входной последовательности. В МП- автомате вместо этого используется правило (8) ( (q,b,e) (q,b) для всех b {a,+,*,(,)};) 2) Условие завершения СУ-перевода формулируется правилом (7) ( (q,#,$E) (r,e) ).