И.А. Волкова, А.А. Вылиток, Т.В. Руденко - Формальные грамматики и языки. Элементы теории трансляции (1114891), страница 5
Текст из файла (страница 5)
V0 := {S }; i := 1.2. Vi := Vi − 1 ∪ {x | x ∈ T ∪ N,A → αxβ ∈ P, A ∈ Vi − 1, α, β ∈ ( T ∪ N )∗} .Если Vi ≠ Vi − 1, то i := i + 1 и переходим к шагу 2, иначе N' := Vi ∩ N ; T' := Vi ∩ T ;P' состоит из правил множества P, содержащих только символы из Vi ;G' := 〈T', N', P', S 〉.Определение:символA∈Nназывается*G = 〈 T, N, P, S 〉, если множество {α ∈ T | A ⇒ α} пусто.бесплоднымвграмматикеАлгоритм удаления бесплодных символовВход: КС-грамматика G = 〈T, N, P, S 〉.Выход: КС-грамматика G' = 〈T, N', P', S 〉, не содержащая бесплодных символов, длякоторой L(G) = L(G' ).Метод:Строим множества N0, N1, ...1.
N0 := ∅, i := 1.*2. Ni := Ni − 1 ∪ {A | A → α ∈ P и α ∈ (Ni − 1 ∪ T) }.Если Ni ≠ Ni − 1, то i := i + 1 и переходим к шагу 2, иначе N' := Ni ; P' состоит из правилмножества P, содержащих только символы из N' ∪ T ; G' := 〈T, N', P', S 〉.Определение: КС-грамматика G называется приведенной, если в ней нет недостижимых и бесплодных символов.19Элементы теории формальных языков и грамматик / Преобразования грамматикАлгоритм приведения грамматики1.
Обнаруживаются и удаляются все бесплодные нетерминалы.2. Обнаруживаются и удаляются все недостижимые символы.Удаление символов сопровождается удалением правил вывода, содержащих эти сим-волы.11)ЗамечаниеЕсли в этом алгоритме приведения поменять местами шаги (1) и (2), то не всегда результатомбудет приведенная грамматика.Для описания синтаксиса языков программирования стараются использовать однозначные приведенные КС-грамматики.Некоторые применяемые на практике алгоритмы разбора по КС-грамматикам требуют, чтобы в грамматиках не было правил с пустой правой частью, т.
е. чтобы КС-грамматикабыла неукорочивающей. Для любой КС-грамматики существует эквивалентная неукорачивающая (см. утверждение 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)Если начальный символ S — бесполезный в грамматике, то грамматика порождает пустой язык.
МножествоP после приведения такой грамматики будет пустым, однако S не следует удалять из N, так как алфавит N неможет быть пустым и на последнем месте в четверке, задающей грамматику, должен стоять нетерминал —начальный символ.20/ ВведениеЗамечаниеЕсли α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Элементы теории трансляции / Разбор по регулярным грамматикамДля того, чтобы быстрее находить правило с подходящей правой частью, зафиксируем все возможные свертки (это определяется только грамматикой и не зависит от вида анализируемой цепочки). Сделаем это в в виде таблицы, строки которой помечены нетерминальными символами грамматики, столбцы — терминальными. Значение каждого элементатаблицы — это нетерминальный символ, к которому можно свернуть пару «нетерминалтерминал», которыми помечены соответствующие строка и столбец.Например, для леволинейной грамматики Gleft = 〈{a, b, ⊥}, {S, A, B, C}, P, S 〉, гдеP:S → C⊥C → Ab | BaA → a | CaB → b | Cb ,такая таблица будет выглядеть следующим образом:ab⊥CABSA—C—BC——S———Знак «—» ставится в том случае, если для пары «нетерминал-терминал» свертки нет.Но чаще информацию о возможных свертках представляют в виде диаграммы состояний (ДС) — неупорядоченного ориентированного помеченного графа, который строитсяследующим образом:(1) строим вершины графа, помеченные нетерминалами грамматики (для каждого нетерминала — одну вершину), и еще одну вершину, помеченную символом, отличным от нетерминальных, например, H.
Эти вершины будем называть состояниями. H — начальное состояние.(2) соединяем эти состояния дугами по следующим правилам:а) для каждого правила грамматики вида W → t соединяем дугой состояния Hи W (от H к W ) и помечаем дугу символом t;б) для каждого правила W → Vt соединяем дугой состояния V и W (от V к W) ипомечаем дугу символом t;Диаграмма состояний для грамматики Gleft (см. пример выше) изображена на рис.4:Рис. 4. Диаграмма состояний для грамматики Gleft.23Элементы теории трансляции / Разбор по регулярным грамматикамАлгоритм разбора по диаграмме состояний(1) объявляем текущим начальное состояние H;(2) затем многократно (до тех пор, пока не считаем признак конца цепочки) выполняем следующие шаги: считываем очередной символ исходной цепочки и переходим из текущего состояния в другое состояние по дуге, помеченной этим символом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
