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

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

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

второйсимвол b появляется только непосредственно справа от первого b, третийb — непосредственно справа от второго b и т. д. Правило (5) применяетсятолько после того, как исчерпана возможность применять (3), иначевыводнебудетзавершениз-заналичияподцепочкиcBвсентенциальной форме.Из пунктов 3, 4 и 5 следует, что любой символ b расположен всегда левее любого [c |C]. Следовательно, в любой выводимой цепочке равное количество а, b и с; а всегда стоитn n nлевее, чем b и с, b всегда стоит левее, чем с, т. е.

любая цепочка имеет вид a b c , что и требовалось доказать.5.Разбор цепочекЦепочка в алфавите T принадлежит языку, порождаемому грамматикой  T, N, P, S ,только в том случае, если существует ее вывод из начального символа S этой грамматики.Процесс построения такого вывода (а, следовательно, и определения принадлежности цепочки языку) называется разбором 8). Построение вывода можно осуществлять и в обратном порядке: в исходной цепочке ищем вхождение правой части некоторого правила и заменяем егона левую часть (это называется сверткой), в результате исходная цепочка «сворачивается» кнекоторой сентенциальной форме, затем идет следующая свертка и т. д., пока не придем кцели грамматики — S . Процесс разбора называют также анализом.С практической точки зрения наибольший интерес представляет разбор по контекстно-свободным грамматикам.

Их порождающей мощности достаточно для описания большей части синтаксической структуры языков программирования, для различных подклассовКС-грамматик имеются хорошо разработанные практически приемлемые способы решениязадачи разбора.Рассмотрим основные понятия и определения, связанные с разбором по КСграмматике.*Определение:выводцепочкиTизSNвКС-грамматикеG   T, N, P, S , называется левым (левосторонним), если в этом выводе каждая очереднаясентенциальная форма получается из предыдущей заменой самого левого нетерминала.8)Разбором также называют и результат этого процесса, т. е. вывод цепочки, представленный (зафиксированный) каким-нибудь способом.15Элементы теории формальных языков и грамматик / Разбор цепочек*Определение:выводцепочкиTизSNвКС-грамматикеG   T, N, P, S , называется правым (правосторонним), если в этом выводе каждая очередная сентенциальная форма получается из предыдущей заменой самого правого нетерминала.В грамматике для одной и той же цепочки может быть несколько выводов, эквивалентных в том смысле, что в них в одних и тех же местах применяются одни и те же правилавывода, но в различном порядке.Например, для цепочки a  b  a в грамматике:Gexpr   {a, b, }, {S, T}, {S → T | T  S ; T → a | b}, S можно построить выводы:(1) S → T  S → T  T  S → T  T  T → a  T  T → a  b  T → a  b  a(2) S → T  S → a  S → a  T  S → a  b  S → a  b  T → a  b  a(3) S → T  S → T  T  S → T  T  T → T  T  a → T  b  a → a  b  aЗдесь (2) — левосторонний вывод, (3) — правосторонний, а (1) не является ни левосторонним, ни правосторонним, но все эти выводы являются эквивалентными в указанномвыше смысле.Для КС-грамматик можно ввести удобное графическое представление вывода, называемое деревом вывода, причем для всех эквивалентных выводов деревья вывода совпадают.Определение: ориентированное упорядоченное9) дерево называется деревом вывода(или деревом разбора) в КС-грамматике G   T, N, P, S , если выполнены следующие условия:(1) каждая вершина дерева помечена символом из множества N  T  {}, при этомкорень дерева помечен символом S; листья — символами из T  {};(2) если вершина дерева помечена символом A, а ее непосредственные потомки —символами a1, a2, ..., an, где каждое ai  T  N, то A → a1a2...an — правило выводав этой грамматике;(3) если вершина дерева помечена символом A, а ее непосредственный потомок помечен символом , то этот потомок единственный и A →  — правило вывода вэтой грамматике.На рисунке 2 изображен пример дерева для цепочки a  b  a в грамматике GexprОпределение: КС-грамматика G называется неоднозначной, если существует хотя быодна цепочка   L(G), для которой может быть построено два или более различных деревьев вывода.В противном случае грамматика называется однозначной.9)Упорядоченность означает, что порядок расположения потомков вершины существен.

Например, деревьяAa16Abиbaсчитаются различными.Элементы теории формальных языков и грамматик / Разбор цепочекНаличие двух или более деревьев вывода эквивалентно тому, что цепочка  имеет дваили более разных левосторонних (или правосторонних) выводов.STSTSTa+b+aРис. 2. Пример дерева вывода в грамматике Gexpr.Определение: язык, порождаемый грамматикой, называется неоднозначным, если онне может быть порожден никакой однозначной грамматикой.Пример неоднозначной грамматики:Gif-then  {if, then, else, a, b}, {S}, P, S ,где P  {S → if b then S else S | if b then S | a}.В этой грамматике для цепочки if b then if b then a else a можно построить два различных дерева вывода, изображенных на рисунке 3 (а, б).Однако это не означает, что язык L(Gif-then) обязательно неоднозначный.

Обнаруженная в Gif-then неоднозначность — это свойство грамматики, а не языка. Для некоторых неоднозначных грамматик существуют эквивалентные им однозначные грамматики.Если грамматика используется для определения языка программирования, то онадолжна быть однозначной.В приведенном выше примере разные деревья вывода предполагают соответствие elseразным then. Если договориться, что else должно соответствовать ближайшему к нему then, иподправить грамматику Gif-then, то неоднозначность будет устранена:SS'→ if b then S | if b then S' else S | a→ if b then S' else S' | aSSSSSifbthenifbthenа)SaelseaSifbthenifbthenSaelseaб)Рис. 3. Деревья вывода для «if b then if b then a else a» в грамматике Gif-then.17Элементы теории формальных языков и грамматик / Разбор цепочекУтверждение 8.

Проблема, порождает ли данная КС-грамматика однозначный язык(т.е. существует ли эквивалентная ей однозначная грамматика), является алгоритмически неразрешимой.Более того, справедливо следующее.Утверждение 9. Проблема, является ли данная КС-грамматика однозначной, алгоритмически неразрешима.Поиск ответа на вопрос, неоднозначна или однозначна заданная грамматика — этоискусство поиска цепочки с двумя различными деревьями вывода, или доказательство того,что таких цепочек не существует. Универсального способа решения этой задачи, к сожалению, нет.Однако можно указать некоторые виды правил вывода, которые приводят к неоднозначности (при условии, что эти правила не являются тупиковыми10), т.

е. действительно используются на каком-нибудь шаге вывода терминальной цепочки из начального символа):в приводимых схемах , ,   (T  N )*(1) A → AA | (2) A → AA | (3) A → A | A |  (здесь хотя бы одна из цепочек  или  не пуста)(4) A → A | AA | Отметим, что это всего лишь некоторые шаблоны. Все ситуации, приводящие к неоднозначности, перечислить невозможно в силу утверждения 9.Пример неоднозначного КС-языка:ij kL  {a b c | i, j, k  0, i  j или j  k}.Интуитивно неоднозначность L объясняется тем, что цепочки с i  j должны порождаться группой правил вывода, отличных от правил, порождающих цепочки с j  k.

Но тогда,по крайней мере, некоторые из цепочек с 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), то не всегда результатомбудет приведенная грамматика.Для описания синтаксиса языков программирования стараются использовать однозначные приведенные КС-грамматики.Некоторые применяемые на практике алгоритмы разбора по КС-грамматикам требуют, чтобы в грамматиках не было правил с пустой правой частью, т.

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

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