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

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

Текст из файла (страница 5)

е. чтобы КС-грамматикабыла неукорочивающей. Для любой КС-грамматики существует эквивалентная неукорачивающая (см. утверждение 2).Ниже приводится алгоритм, позволяющий преобразовать любую КС-грамматику внеукорачивающую. На первом шаге алгоритма строится множество X, состоящее из нетерминалов грамматики, из которых выводима пустая цепочка. Построение этого множестваможно провести по аналогии с шагами алгоритма удаления бесплодных символов:*(1) X1 : { A | (A → )  P }; i :2; (2) Xi : {A | (A → )  P и   Xi − 1 }  Xi − 1.

Далее, покаXi  Xi − 1 увеличиваем i на единицу и повторяем (2). Последнее Xi — искомое множество X.Алгоритм устранения правил с пустой правой частьюВход: КС-грамматика G   T, N, P, S .Выход: КС-грамматика G'   T, N', P', S' , G' — неукорачивающая, L(G')  L(G).Метод:1. Построить множество Х  {A  N | A  } ; N′:N .2. Построить P′, удалив из множества правил P все правила с пустой правой частью.3. Если S  X, то ввести новый начальный символ S′, добавив его в N′, и в множествоправил P′ добавить правило S′ S | . Иначе просто переименовать S в S′.4.ИзменитьP′следующимобразом.Каждоеправиловида*B → 1A12A2...n Ann  1, где Ai  X для i  1,..., n, i  ( (N′  X)  T ) для i  1,..., n  1 (т. е.ni — цепочка, не содержащая символов из X ), заменить 2 правилами, соответствующимивсем возможным комбинациям вхождений Аi между  i:B → 12...nn  1B → 12...nAnn  1...B → 12A2...nAnn  1B → 1A12A2...nAnn  111)20Если начальный символ S — бесполезный в грамматике, то грамматика порождает пустой язык.

МножествоP после приведения такой грамматики будет пустым, однако S не следует удалять из N, так как алфавит N неможет быть пустым и на последнем месте в четверке, задающей грамматику, должен стоять нетерминал —начальный символ./ ВведениеЗамечаниеЕсли i   для всех i  1, ..., n  1, то получившееся на данном шаге правило B →  не включать в множество P′.5. Удалить бесплодные и недостижимые символы и правила, их содержащие.

(Кромеизначально имеющихся (в неприведенной грамматике), бесполезные символы могут возникнуть в результате шагов 2–4).ЗамечаниеЕсли применить данный алгоритм к регулярной (автоматной) грамматике, то результатом будетнеукорачивающая регулярная (автоматная) грамматика.Далее везде, если не оговорено иное, будем рассматривать только приведенные грамматики.Элементы теории трансляцииВведениеВ этом разделе будут рассмотрены некоторые алгоритмы и технические приемы, применяемые при построении трансляторов. Практически во всех трансляторах (и в компиляторах, и в интерпретаторах) в том или ином виде присутствует большая часть перечисленныхниже процессов: лексический анализ, синтаксический анализ, семантический анализ, генерация внутреннего представления программы, оптимизация, генерация объектной программы.В конкретных компиляторах порядок этих процессов может быть несколько иным,какие-то из них могут объединяться в одну фазу, другие могут выполняться в течение всегопроцесса компиляции.

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

Приводится реализация в виде программы на Си  .Информацию о других методах, алгоритмах и приемах, используемых при созданиитрансляторов, можно найти в [1, 2, 3, 4, 5, 8].21Элементы теории трансляции / Разбор по регулярным грамматикамРазбор по регулярным грамматикамРассмотрим методы и средства, которые обычно используются при построении лексических анализаторов.

В основе таких анализаторов лежат регулярные грамматики, поэтомурассмотрим грамматики этого класса более подробно.Соглашение: в дальнейшем, если особо не оговорено, под регулярной грамматикойбудем понимать леволинейную автоматную грамматику G   T, N, P, S  без пустых правыхчастей12). Напомним, что в такой грамматике каждое правило из Р имеет вид A → Bt либоA → t, где A, B  N, t  T.Соглашение: предположим, что анализируемая цепочка заканчивается специальнымсимволом  — признаком конца цепочки.Для грамматик этого типа существует алгоритм определения того, принадлежит лианализируемая цепочка языку, порождаемому этой грамматикой (алгоритм разбора):(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) на некотором шаге работы алгоритма оказалось, что есть более одной подходящейсвертки, т. е. в грамматике разные нетерминалы имеют правила вывода с одинаковыми правыми частями, и поэтому непонятно, к какому из них производитьсвертку. Это говорит о недетерминированности разбора. Анализ этой ситуациибудет дан ниже.Допустим, что разбор на каждом шаге детерминированный.12)22Полное отсутствие -правил в грамматике не позволяет описывать языки, содержащие пустую цепочку. Длянаших целей в данном разделе это ограничение оправдано — мы будем применять автоматные грамматикидля описания и разбора лексических единиц (лексем) языков программирования.

Лексемы не могут быть пустыми.Элементы теории трансляции / Разбор по регулярным грамматикамДля того, чтобы быстрее находить правило с подходящей правой частью, зафиксируем все возможные свертки (это определяется только грамматикой и не зависит от вида анализируемой цепочки). Сделаем это в виде таблицы, столбцы которой помечены терминальными символами. Первая строка помечена символом Н (НN), а значение каждого элементаэтой строки — это нетерминал, к которому можно свернуть помечающий столбец терминальный символ. Остальные строки помечены нетерминальными символами грамматики.Значение каждого элемента таблицы, начиная со второй строки — это нетерминальный символ, к которому можно свернуть пару «нетерминал-терминал», которыми помечены соответствующие строка и столбец.Например, для леволинейной грамматики Gleft  {a, b, }, {S, A, B, C}, P, S , гдеP:S → CC → Ab | BaA → a | CaB → b | Cb ,такая таблица будет выглядеть следующим образом:abHAB—CABSA—C—BC——S———Знак «—» ставится в том случае, если соответствующей свертки нет.Но чаще информацию о возможных свертках представляют в виде диаграммы состояний (ДС) — неупорядоченного ориентированного помеченного графа, который строитсяследующим образом:(1) строим вершины графа, помеченные нетерминалами грамматики (для каждого нетерминала — одну вершину), и еще одну вершину, помеченную символом, отличным от нетерминальных, например, H.

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

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

Это означает,что исходная цепочка не принадлежит L(G).3) На некотором шаге не нашлось дуги, выходящей из текущего состояния и помеченной очередным анализируемым символом. Это означает, что исходная цепочкане принадлежит L(G).4) На некотором шаге работы алгоритма оказалось, что есть несколько дуг, выходящих из текущего состояния, помеченных очередным анализируемым символом,но ведущих в разные состояния. Это говорит о недетерминированности разбора.Анализ этой ситуации будет приведен ниже.Диаграмма состояний определяет конечный автомат, построенный по регулярнойграмматике, который допускает множество цепочек, составляющих язык, определяемый этойграмматикой.

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

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