И.А. Волкова, Т.В. Руденко - Формальные грамматики и языки. Элементы теории трансляции. (1114901)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Волкова И.А., Руденко Т.В.Системное программное обеспечениеФормальные грамматики и языки.Элементы теории трансляции.ЭЛЕМЕНТЫ ТЕОРИИ ТРАНСЛЯЦИИВведение.В этом разделе будут рассмотрены некоторые алгоритмы и техническиеприемы, применяемые при построении трансляторов. Практически вовсех трансляторах (и в компиляторах, и в интерпретаторах) в том илиином виде присутствует большая часть перечисленных ниже процессов:••••••лексический анализсинтаксический анализсемантический анализгенерация внутреннего представления программыоптимизациягенерация объектной программы.В конкретных компиляторах порядок этих процессов может бытьнесколько иным, некоторые из них могут объединяться в одну фазу,другие могут выполнятся в течение всего процесса компиляции.

Винтерпретаторах и при смешанной стратегии трансляции некоторыеэтапы могут вообще отсутствовать.В этом разделе мы рассмотрим некоторые методы, используемые дляпостроенияанализаторов(лексического,синтаксическогоисемантического), язык промежуточного представления программы,способ генерации промежуточной программы, ее интерпретации.Излагаемые алгоритмы и методы иллюстрируются на примеремодельного паскалеподобного языка (М-языка). Все алгоритмы записанына Си.Информацию о других методах, алгоритмах и приемах, используемыхпри создании трансляторов, можно найти в [1, 2, 3, 4, 5, 8].Описание модельного языкаPD1program D1; B→ var D {;D}D→ I {,I}: [ int | bool ]B→ begin S {;S} endS→ I := E | if E then S else S | while E do S | B | read (I) | write (E)E→ E1 [ = | < | > | != ] E1E1→ T {[ + | - | or ] T}T→ F {[ * | / | and ] F}F→ I | N | L | not F | (E)L→ true | falseI→ C | IC | IRN→ R | NRC→ a | b | ...

| z | A | B | ... |ZR → 0 | 1 | 2 | ... | 9Замечание:1. запись вида {α} означает итерацию цепочки α, т.е. в порождаемойцепочке в этом месте может находиться либо ε, либо α, либо αα,либо ααα, и т.д.2. запись вида [ α | β ] означает, что в порождаемой цепочке в этомместе может находиться либо α, либо β.3. P - цель грамматики; символ- маркер конца текста программы.Контекстные условия:1. Любое имя, используемое в программе, должно быть описано итолько один раз.2. В операторе присваивания типы переменной и выражения должнысовпадать.3.

В условном операторе и в операторе цикла в качестве условиявозможно только логическое выражение.4. Операнды операции отношения должны быть целочисленными.5. Тип выражения и совместимость типов операндов в выраженииопределяются по обычным правилам; старшинство операцийзадано синтаксисом.В любом месте программы, кроме идентификаторов, служебных слов ичисел, может находиться произвольное число пробелов и комментариеввида {< любые символы, кроме} и ⊥ >}.True, false, read и write - служебные слова (их нельзя переопределять,как стандартные идентификаторы Паскаля).Сохраняетсяпаскалевскоеправилооразделителяхмеждуидентификаторами, числами и служебными словами.Лексический анализРассмотрим методы и средства, которые обычно используются припостроении лексических анализаторов. В основе таких анализаторовлежат регулярные грамматики, поэтому рассмотрим грамматики этогокласса более подробно.Соглашение: в дальнейшем, если особо не оговорено, под регулярнойграмматикой будем понимать леволинейную грамматику.Напомним, что грамматика G = (VT, VN, P, S) называется леволинейной,если каждое правило из Р имеет вид A → Bt либо A → t, где A ⊂ VN, B ⊂ VN, t⊂ VT.Соглашение: предположим, что анализируемая цепочка заканчиваетсяспециальным символом ⊥ - признаком конца цепочки.Для грамматик этого типа существует алгоритм определения того,принадлежит ли анализируемая цепочка языку, порождаемому этойграмматикой (алгоритм разбора):(1) первый символ исходной цепочки a1a2...an⊥ заменяем нетерминаломA, для которого в грамматике есть правило вывода A → a1 (другими словами,производим "свертку" терминала a1 к нетерминалу A)(2) затем многократно (до тех пор, пока не считаем признак концацепочки) выполняем следующие шаги: полученный на предыдущем шагенетерминал A и расположенный непосредственно справа от негоочередной терминал ai исходной цепочки заменяем нетерминалом B, длякоторого в грамматике есть правило вывода B → Aai (i = 2, 3,.., n);Это эквивалентно построению дерева разбора методом "снизу-вверх": накаждом шаге алгоритма строим один из уровней в дереве разбора,"поднимаясь" от листьев к корню.При работе этого алгоритма возможны следующие ситуации:(1) прочитана вся цепочка; на каждом шаге находилась единственнаянужная "свертка"; на последнем шаге свертка произошла к символу S.Это означает, что исходная цепочка a1a2...an⊥ ⊂ L(G).(2) прочитана вся цепочка; на каждом шаге находилась единственнаянужная "свертка"; на последнем шаге свертка произошла к символу,отличному от S.

Это означает, что исходная цепочка a1a2...an⊥ ⊆ L(G).(3) на некотором шаге не нашлось нужной свертки, т.е. дляполученного на предыдущем шаге нетерминала A и расположенногонепосредственно справа от него очередного терминала ai исходнойцепочки не нашлось нетерминала B, для которого в грамматике было быправило вывода B → Aai.

Это означает, что исходная цепочка a1a2...an⊥ ⊆L(G).(4) на некотором шаге работы алгоритма оказалось, что есть болееодной подходящей свертки, т.е. в грамматике разные нетерминалыимеют правила вывода с одинаковыми правыми частями, и поэтомунепонятно, к какому из них производить свертку. Это говорит онедетерминированности разбора. Анализ этой ситуации будет дан ниже.Допустим, что разбор на каждом шаге детерминированный.Для того, чтобы быстрее находить правило с подходящей правой частью,зафиксируем все возможные свертки (это определяется толькограмматикой и не зависит от вида анализируемой цепочки).Это можно сделать в виде таблицы, строки которой помеченынетерминальными символами грамматики, столбцы - терминальными.Значение каждого элемента таблицы - это нетерминальный символ, ккоторому можно свернуть пару "нетерминал-терминал", которымипомечены соответствующие строка и столбец.Например, для грамматики G = ({a, b, ⊥}, {S, A, B, C}, P, S), такая таблицабудет выглядеть следующим образом:P: S → C⊥С → Ab | BaA → a | CaB → b | Cba bC ABSA- CBC- S - - Знак "-" ставится в том случае, если для пары "терминал-нетерминал"свертки нет.Но чаще информацию о возможных свертках представляют в видедиаграммы состояний (ДС) - неупорядоченного ориентированногопомеченного графа, который строится следующим образом:(1) строят вершины графа, помеченные нетерминалами грамматики(для каждого нетерминала - одну вершину), и еще одну вершину,помеченную символом, отличным от нетерминальных (например, H).

Этивершины будем называть состояниями. H - начальное состояние.(2) соединяем эти состояния дугами по следующим правилам:a) для каждого правила грамматики вида W → t соединяем дугой состояния Hи W (от H к W) и помечаем дугу символом t;б)для каждого правила W → Vt соединяем дугой состояния V и W (от V к W)и помечаем дугу символом t;Диаграмма состояний для грамматики G (см. пример выше):Алгоритм разбора по диаграмме состояний:(1) объявляем текущим состояние H;(2) затем многократно (до тех пор, пока не считаем признак концацепочки) выполняем следующие шаги: считываем очередной символисходной цепочки и переходим из текущего состояния в другоесостояние по дуге, помеченной этим символом.

Состояние, в которое мыпри этом попадаем, становится текущим.Приработеэтогоалгоритмавозможныследующиеситуации(аналогичныеситуациям,которыевозникаютприразборенепосредственно по регулярной грамматике):(1) прочитана вся цепочка; на каждом шаге находилась единственнаядуга, помеченная очередным символом анализируемой цепочки; врезультате последнего перехода оказались в состоянии S. Это означает,что исходная цепочка принадлежит L(G).(2) прочитана вся цепочка; на каждом шаге находилась единственная"нужная" дуга; в результате последнего шага оказались в состоянии,отличном от S.

Это означает, что исходная цепочка не принадлежитL(G).(3) на некотором шаге не нашлось дуги, выходящей из текущегосостояния и помеченной очередным анализируемым символом. Этоозначает, что исходная цепочка не принадлежит L(G).(4) на некотором шаге работы алгоритма оказалось, что есть несколькодуг, выходящих из текущего состояния, помеченных очередныманализируемым символом, но ведущих в разные состояния. Это говорито недетерминированности разбора. Анализ этой ситуации будетприведен ниже.Диаграмма состояний определяет конечный автомат, построенный порегулярной грамматике, который допускает множество цепочек,составляющих язык, определяемый этой грамматикой. Состояния и дугиДС - это графическое изображение функции переходов конечногоавтомата из состояния в состояние при условии, что очереднойанализируемый символ совпадает с символом-меткой дуги. Среди всехсостояний выделяется начальное (считается, что в начальный моментсвоей работы автомат находится в этом состоянии) и конечное (еслиавтомат завершает работу переходом в это состояние, то анализируемаяцепочка им допускается).Определение: конечный автомат (КА) - это пятерка (K, VT, F, H, S), гдеK - конечное множество состояний;VT - конечное множество допустимых входных символов;F - отображение множества K × VT → K, определяющее поведение автомата;отображение F часто называют функцией переходов;H ⊂ K - начальное состояние;S ⊂ K - заключительное состояние (либо конечное множество заключительныхсостояний).F(A, t) = B означает, что из состояния A по входному символу tпроисходит переход в состояние B.Определение: конечный автомат допускает цепочку a1a2...an, еслиF(H,a1) = A1; F(A1,a2) = A2; .

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов книги