formal_languages_translation_theory (Формальные грамматики), страница 5

Но тогда,по крайней мере, некоторые из цепочек с i  j  k будут порождаться обеими группами правил и, следовательно, будут иметь по два разных дерева вывода. Доказательство того, чтоКС-язык L неоднозначный, приведено в [3, т.1, стр. 235–236].Одна из грамматик, порождающих L, такова:S → AB | DCA → aA | B → bBc | C → cC | D → aDb | Она неоднозначна; однозначных грамматик для L не существует.Дерево вывода можно строить нисходящим либо восходящим способом.При нисходящем разборе дерево вывода формируется от корня к листьям; на каждомшаге для вершины, помеченной нетерминальным символом, пытаются найти такое правило10)18Как избавиться от правил, не участвующих в построении выводов, показано в разделе «Преобразованияграмматик».Элементы теории формальных языков и грамматик / Преобразования грамматиквывода, чтобы имеющиеся в нем терминальные символы проецировались на символы исходной (анализируемой) цепочки.Метод восходящего разбора основан на обратном построении вывода с помощьюсверток от исходной цепочки к цели грамматики S.

При этом дерево растет снизу вверх —от листьев (символов анализируемой цепочки) к корню S. Если грамматика однозначная, топри любом способе построения будет получено одно и то же дерево разбора.Преобразования грамматикВ некоторых случаях КС-грамматика может содержать бесполезные символы, которые не участвуют в порождении цепочек языка и поэтому могут быть удалены из грамматики.Определение: символ x  T  N называется недостижимым в грамматикеG  T, N, P, S , если он не появляется ни в одной сентенциальной форме этой грамматики.Алгоритм удаления недостижимых символовВход: КС-грамматика G  T, N, P, S ,Выход: КС-грамматика G'  T', N', P', S , не содержащая недостижимых символов,для которой L(G)  L(G').Метод:1. 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)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.