fl_task11 (1) (1178916)
Текст из файла
Задание 11LL-анализКлючевые слова 1 :язык, контекстно-свободный язык, магазинныйавтомат, грамматика, LL(k)-грамматика, LL(1)-анализатор, функцииFIRST, FOLLOW.1Нисходящий и восходящий разборНапомним определение вывода КС-грамматики.Выводом цепочки α называется такая последовательность применений правил с указанием раскрываемого нетерминала, что применяя правила из неё начиная с аксиомы получается цепочка α. Если цепочка α несодержит нетерминалов, то α принадлежит языку, порождаемому КСграмматикой. Нам будет удобно пользоваться такими понятиями как левый вывод (правый вывод). Левым выводом называют такой вывод, чтона каждом его шаге раскрывается самый левый нетерминал в промежуточной цепочке.
Правый вывод определяется аналогично.Также напомним что мы называем деревом вывода или деревом разбора. С формальным определением дерева разбора вы можете познакомиться, например, в книге Хопкрофта, Мотвани и Ульмана, а мы воспользуемся неформальным описанием этого понятия. Деревом разборадля грамматики G называется упорядоченное дерево, в корне которогонаходится аксиома S, каждая вершина помечена нетерминалом, терминалом или пустым словом, если вершина помечена терминалом или ε, тоэта вершина является листом, если же вершина помечена нетерминаломA, то существует такое правило A → X1 X2 .
. . Xn ∈ P (Xi ∈ N ∪ T ), чтовершины-потомки A помечены символами X1 , X2 . . . Xn слева направо.Будем говорить, что для КС-грамматики G слово w разобрано, еслиизвестно хотя бы одно из её деревьев вывод.Левым разбором цепочки α ∈ (N ∪ T )∗ будем называть последовательность правил, применённых при левом выводе цепочки α. Правымразбором цепочки α назовём обратную последовательность правил, применённых при правом выводе цепочки α.1минимальный необходимый объем понятий и навыков по этому разделу)1Пример 1.
Грамматики G = (N, T, P, E), и Gπ = (N, T 0 , P 0 , E), T ={a, +, ∗} заданы правилами:EETTFF→E+T→T→T ∗F→F→ (E)→a(1)(2)(3)(4)(5)(6)EETTFF→ 1ET→ 2T→ 3T F→ 4F→ 5E→6Построим дерево разбора для слова w = a + (a ∗ a) и дерево выводав грамматики G0 , соответствующее выводу w :2EETT∗FF(E)aE+TTFFa2T3T4FF5E61E2aTT4F4F66Если грамматика G выводит слово w, то применяя соответствующиеправила в G0 выводим из неё слово πl (w), соответствующее левому выводу слова w.Назовём переводом бинарное отношение T , действующее из языка L1в язык L2 . Если пара слов (u, v) удовлетворяет отношению T , то будемговорить, что слово u транслируется переводом T в слово v, а слово vбудем называть выходом для u. Мы будем рассматривать синтаксическиуправляемые переводы.
Неформально, перевод является синтаксическиуправляемым, если существует пара грамматик, правила которых занумерованы и если на шаге вывода из одной грамматики получена цеапочкаα, а для соответствующего шага вывода из другой грамматики полученацепочка β, то любой нетерминал входящий в цепочку α, входит и в цепочку β с одинаковой кратностью. Например, в лингвистике нетерминалымогут соответствовать частям речи.
Тогда при переводе с одного языка3на другой подлежащее перейдёт в подлежащее, а сказуемое в сказуемое,таким образом, синтаксис определяет некоторые особенности семантикиязыка. Эта особенность также весьма полезна и при построении компиляторов. Формально, перевод называется синтаксически управляемым,если есть синтаксически управляемая схема (СУ-схема), его реализующая. Определим формально СУ-схему.Определение 1. Синтаксически управляемой схемой назовём пятёркуT = (N, Σ, ∆, R, S), где N множество нетерминалов, Σ и ∆ алфавитывхода и выхода схемы, R – множество правил вида A → α, β, причёмнетерминалы входящие в цепочку α входят также и в цепочку β, причёмс той же кратностью.Как легко видеть, из языка L(G) существует СУ-перевод в языкL(G0 ), схема которого строится по грамматикам. А именно множествоR строится по соответствующим парам правил, описанных выше.Упражнение 1.
Предъявить алгоритм построения по грамматики Gсинтаксический перевод Tl , переводящий слово w из L(G) в левый выводданного слова πl (w).Восходящий разбор строится аналогично по правому выводу.Упражнение 2. Построить правый вывод w = a + (a ∗ a) по деревуразбора. По правому выводу построить разбор πr (w).Упражнение 3. Построить по описанной выше грамматике G схемуСУ-перевода, реализующую перевод w → πr (w). Предъявить алгоритмпостроения схемы данного СУ-перевода по грамматике.2Функция FIRSTПри построении (детерминированных) анализатаров по грамматике, нампотребуется определять множество первых k символов слов, выводимыхиз цепочки α ∈ (N ∪ T )∗ . Для этого мы будем использовать функциюFIRSTk , которая определена через функцию FIRST1 или просто FIRST.Таким образом умение вычислять функцию FIRST является ключевымпри построении анализаторов.Формально,FIRSTk (α) = {w[1, k] | α ⇒ w, |w| > k} ∪ {w | α ⇒ w, |w| < k}4Если α ⇒ ε, то пустое слово лежит в FIRSTk (α).Приведём процедуру вычисления функции FIRST(α).Идея алгоритма: Если α = X1 X2 .
. . Xn начинается с терминала σ,то первым символом может быть только этот терминал, таким образом,мы сразу получаем ответ σ. Если же α начинается с нетерминала, тоFIRST(α) = FIRST(X1 ), если из нетерминала X1 не выводится пустоеслово, и FIRST(α) = FIRST(X1 ) ∪ FIRST(X2 X3 . . . Xn ), если X1 ⇒ ε.Таким образом, мы описали вычисление функции FIRST на множестве терминалов и цепочек, начинающихся с терминалов, осталось описать вычисление функции на множестве нетерминалов, как видно вычисление функции FIRST на множестве сентенциальных форм сводитсяк вычислению функции на отдельных нетерминалах.Пусть мы вычисляем функцию FIRST(X) для нетерминала X.
Рассмотрим все правила вида X → β. Очевидно, что FIRST(β) являетсяподмножеством FIRST(X), но просто добавляя множество FIRST(β) кFIRST(X) мы получим порочный круг, в случае правил вида X → Xa.Как нам избежать порочного круга при вычислении множества FIRST(X)?Определим множества Fi (Y ), Y ∈ N . При i = 0 для любого нетерминала Y , множество Fi (Y ) = ∅, или {ε}, если есть правило Y → ε.
Наi−ом шаге алгоритма будем вычислять множества Fi (X) следующим образом. В начале шага Fi (X) включает себя множество Fi−1 (X) Если естьправило X → β = Y1 Y2 . . . Yn и Y1 – терминал или β – пустое слово, тодобавим к множеству Fi (X) элемент Y1 (быть может пустое слово). Еслиже Y1 – нетерминал, и при этом пустое слово не лежит в Fi−1 (Y1 ), тодобавим к множеству Fi (X) множество Fi−1 (Y1 ) и вычислим множествоFi (Y1 ). Если же ε ∈ Fi−1 (Y1 ), то добавим к Fi (X) множество Fi (Y1 ) \ {ε}и повторим описанную операцию для β = Y2 . . . Yn .Алгоритм останавливается, как только для каждого нетерминала Y ,множества Fi и Fi−1 совпадают.Алгоритм:Шаг 0.
Для каждого терминала σ положим Fi (σ) = σ для любогоi. Для каждого нетерминала Y , если есть правило Y → ε, положимF0 (Y ) = {ε}, иначе положим F0 (Y ) = ∅.Шаг i. Добавить к множеству Fi (X) множество Fi−1 (X). Для каждого правила X → β = Y1 . . . Yn выполнить:j=15Пока ε ∈ Fi−1 (Yj )добавить Fi−1 (Yj ) \ {ε} к Fi (X),увеличить j.Если ε ∈ Fi−1 (Yn ), добавить ε к Fi (X),Остановка. Fi (Y ) = Fi−1 (Y ) для любого Y из N . Положить FIRST(X) =Fi (X).Упражнение 4. Доказать корректность данного алгоритма.3Функция FOLLOWПомимо префикса порождаемого цепочкой β нас будет интересовать также и множество слов, которые могут следовать после слова, выведенного из цепочки β.
Запишем сначала формальное определение функцииFOLLOWk .FOLLOWk (β) = {w | S ⇒ αβγ, w ∈ FIRSTk (γ)}.Неформально, в множестве FOLLOWk (β) содержатся те слова, которые могут следовать за словом, выведенным из β, в цепочке αβγ, выводимой из аксиомы. Длина этих слов ограничена k, что означает, что еслиγ ⇒ w и длина слова w меньше k, то w лежит в множестве FOLLOWk (β),а если же длина слова w больше k, то в множестве FOLLOWk (β) лежитпрефикс w длины k.Аналогично функции FIRST, мы будем обозначать FOLLOW1 какFOLLOW.Мы будем часто пользоваться функцией FOLLOWk в теоретическихцелях и для обозначения объектов, однако на практике мы будем вычислять функцию FOLLOW только на множестве нетерминалов.Приведём алгоритм для вычисления функции FOLLOW.Идея алгоритма: Если в грамматике есть правило A → αXβ, тоза словом, выведенным из нетерминала X следует слово выведенноеиз β, таким образом множество FOLLOW(X) включает в себя множество FIRST(β).
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
