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

Вообще говоря, следует доказывать, что заданная грамматика порождает нужныйязык. Для этого требуется доказать, что в данной грамматике:I ) выводится любая цепочка, принадлежащая языку,II ) не выводятся никакие другие цепочки.Задача.Доказать, что грамматика G с правилами вывода:(1, 2)(3)(4)(5)(6)SCBbBbCcC→→→→→aSBC | abCBCbbbcccn n nпорождает язык L(G)  { a b c | n  1}.(В скобках слева приведена нумерация для удобства ссылок на правила).Решениеn n nI ) Приведем схемы порождения цепочек вида a b c , n  1 c указанием номера правила на каждом шаге вывода.Для n  1: S → (2) abC → (5) abc.n−1n−1nn−1Для n  1: S →(1) aSBC →(1) aaSBCBC → … →(1) aS(BC)→(2) a bC(BC )→(3)n n−1 nnn−2 nn n nn nn−1n nn−2… →(3) a bB C →(4) a bbB C → … →(4) a b C →(5) a b cC→(6) a b ccC→…→n n n(6) a b c .14Элементы теории формальных языков и грамматик / Разбор цепочекII) Из правил следует:1.

Новые символы а, [b | B] и C появляются только при применении правил (1), (2) вравных количествах, т. е. в любой сентенциальной форме всегдаравное количество а, [b | B] и [с | С].2. Символ В заменяется только на b, а С — только на с.3. Появившись, терминальные символы уже не меняют своей позиции, т.

е. влюбой сентенциальной форме символ а всегда левее любых [b | B] и [c | C].4.Первый символ b появляется только после применения правила (2).Символ В заменяется на b, только если слева от В стоит b, т. е. второйсимвол 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.