Учебное пособие для студентов II курса (издание третье, переработанное и дополненное) Москва 2009 удк 519. 682. 1
 Скачать 2.2 Mb.
|
|
Задача. Доказать, что грамматика G с правилами вывода: (1, 2) S → aSBC | abC (3) CB → BC (4) bB → bb (5) bC → bc (6) cC → cc порождает язык L(G) { a n b n c n | n 1}. (В скобках слева приведена нумерация для удобства ссылок на правила). Решение I ) Приведем схемы порождения цепочек вида a n b n c n , n 1 c указанием номера пра- вила на каждом шаге вывода. Для n 1: S → (2) abC → (5) abc. Для n 1: S → (1) aSBC → (1) aaSBCBC → … → (1) a n − 1 S(BC) n − 1 → (2) a n bC(BC ) n − 1 → (3) … → (3) a n bB n − 1 C n → (4) a n bbB n − 2 C n → … → (4) a n b n C n → (5) a n b n cC n − 1 → (6) a n b n ccC n − 2 → … → (6) a n b n c n Элементы теории формальных языков и грамматик / Разбор цепочек 15 II) Из правил следует: 1. Новые символы а, [b | B] и C появляются только при применении правил (1), (2) в равных количествах, т. е. в любой сентенциальной форме всегда равное количество а, [b | B] и [с | С]. 2. Символ В заменяется только на b, а С — только на с. 3. Появившись, терминальные символы уже не меняют своей позиции, т. е. в любой сентенциальной форме символ а всегда левее любых [b | B] и [c | C]. 4. Первый символ b появляется только после применения правила (2). 5. Символ В заменяется на b, только если слева от В стоит b, т. е. второй символ b появляется только непосредственно справа от первого b, третий b — непосредственно справа от второго b и т. д. Правило (5) применяется только после того, как исчерпана возможность применять (3), иначе вывод не будет завершен из-за наличия подцепочки cB в сентенциальной форме. Из пунктов 3, 4 и 5 следует, что любой символ b расположен всегда левее любого [c | C]. Следовательно, в любой выводимой цепочке равное количество а, b и с; а всегда стоит левее, чем b и с, b всегда стоит левее, чем с, т. е. любая цепочка имеет вид a n b n c n , что и тре- бовалось доказать. Разбор цепочек Цепочка в алфавите T принадлежит языку, порождаемому грамматикой T, N, P, S , только в том случае, если существует ее вывод из начального символа S этой грамматики. Процесс построения такого вывода (а, следовательно, и определения принадлежности цепоч- ки языку) называется разбором 8) .Построение вывода можно осуществлять и в обратном по- рядке: в исходной цепочке ищем вхождение правой части некоторого правила и заменяем его на левую часть (это называется сверткой), в результате исходная цепочка «сворачивается» к некоторой сентенциальной форме, затем идет следующая свертка и т. д., пока не придем к цели грамматики — S . Процесс разбора называют также анализом. С практической точки зрения наибольший интерес представляет разбор по контекст- но-свободным грамматикам. Их порождающей мощности достаточно для описания боль- шей части синтаксической структуры языков программирования, для различных подклассов КС-грамматик имеются хорошо разработанные практически приемлемые способы решения задачи разбора. Рассмотрим основные понятия и определения, связанные с разбором по КС- грамматике. Определение: вывод цепочки T * из S N в КС-грамматике G T, N, P, S , называется левым (левосторонним), если в этом выводе каждая очередная сентенциальная форма получается из предыдущей заменой самого левого нетерминала. 8) Разбором также называют и результат этого процесса, т. е. вывод цепочки, представленный (зафиксирован- ный) каким-нибудь способом. Элементы теории формальных языков и грамматик / Разбор цепочек 16 Определение: вывод цепочки T * из S N в КС-грамматике G T, N, P, S , называется правым (правосторонним), если в этом выводе каждая очеред- ная сентенциальная форма получается из предыдущей заменой самого правого нетерминала. В грамматике для одной и той же цепочки может быть несколько выводов, эквива- лентных в том смысле, что в них в одних и тех же местах применяются одни и те же правила вывода, но в различном порядке. Например, для цепочки a b a в грамматике: G expr {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, а ее непосредственные потомки — символами a 1 , a 2 , ..., a n , где каждое a i T N, то A → a 1 a 2 ...a n — правило вывода в этой грамматике; (3) если вершина дерева помечена символом A, а ее непосредственный потомок по- мечен символом , то этот потомок единственный и A → — правило вывода в этой грамматике. На рисунке 2 изображен пример дерева для цепочки a b a в грамматике G expr Определение: КС-грамматика G называется неоднозначной, если существует хотя бы одна цепочка L(G), для которой может быть построено два или более различных деревь- ев вывода. В противном случае грамматика называется однозначной. 9) Упорядоченность означает, что порядок расположения потомков вершины существен. Например, деревья A a b и A b a считаются различными. Элементы теории формальных языков и грамматик / Разбор цепочек 17 Наличие двух или более деревьев вывода эквивалентно тому, что цепочка имеет два или более разных левосторонних (или правосторонних) выводов. S T S + a T S + b a T Рис. 2. Пример дерева вывода в грамматике G expr Определение: язык, порождаемый грамматикой, называется неоднозначным, если он не может быть порожден никакой однозначной грамматикой. Пример неоднозначной грамматики: G if-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(G if-then ) обязательно неоднозначный. Обнаружен- ная в G if-then неоднозначность — это свойство грамматики, а не языка. Для некоторых неод- нозначных грамматик существуют эквивалентные им однозначные грамматики. Если грамматика используется для определения языка программирования, то она должна быть однозначной. В приведенном выше примере разные деревья вывода предполагают соответствие else разным then. Если договориться, что else должно соответствовать ближайшему к нему then, и подправить грамматику G if-then , то неоднозначность будет устранена: S → if b then S | if b then S' else S | a S' → if b then S' else S' | a S if b then if b then a else a S S S S if b then if b then a else a S S S а) б) Рис. 3. Деревья вывода для «if b then if b then a else a» в грамматике G if-then Элементы теории формальных языков и грамматик / Разбор цепочек 18 Утверждение 8. Проблема, порождает ли данная КС-грамматика однозначный язык (т.е. существует ли эквивалентная ей однозначная грамматика), является алгоритмически не- разрешимой. Более того, справедливо следующее. Утверждение 9. Проблема, является ли данная КС-грамматика однозначной, алго- ритмически неразрешима. Поиск ответа на вопрос, неоднозначна или однозначна заданная грамматика — это искусство поиска цепочки с двумя различными деревьями вывода, или доказательство того, что таких цепочек не существует. Универсального способа решения этой задачи, к сожале- нию, нет. Однако можно указать некоторые виды правил вывода, которые приводят к неодно- значности (при условии, что эти правила не являются тупиковыми 10) , т. е. действительно ис- пользуются на каком-нибудь шаге вывода терминальной цепочки из начального символа): в приводимых схемах , , (T N ) * (1) A → AA | (2) A → A A | (3) A → A | A | (здесь хотя бы одна из цепочек или не пуста) (4) A → A | A A | Отметим, что это всего лишь некоторые шаблоны. Все ситуации, приводящие к неод- нозначности, перечислить невозможно в силу утверждения 9. Пример неоднозначного КС-языка: L {a i b j c k | i, j, k 0, i j или j k}. Интуитивно неоднозначность L объясняется тем, что цепочки с i j должны порож- даться группой правил вывода, отличных от правил, порождающих цепочки с j k. Но тогда, по крайней мере, некоторые из цепочек с i j k будут порождаться обеими группами пра- вил и, следовательно, будут иметь по два разных дерева вывода. Доказательство того, что КС-язык L неоднозначный, приведено в [3, т.1, стр. 235–236]. Одна из грамматик, порождающих L, такова: S → AB | DC A → aA | B → bBc | C → cC | D → aDb | Она неоднозначна; однозначных грамматик для L не существует. Дерево вывода можно строить нисходящим либо восходящим способом. При нисходящем разборе дерево вывода формируется от корня к листьям; на каждом шаге для вершины, помеченной нетерминальным символом, пытаются найти такое правило 10) Как избавиться от правил, не участвующих в построении выводов, показано в разделе «Преобразования грамматик». Элементы теории формальных языков и грамматик / Преобразования грамматик 19 вывода, чтобы имеющиеся в нем терминальные символы проецировались на символы исход- ной (анализируемой) цепочки. Метод восходящего разбора основан на обратном построении вывода с помощью сверток от исходной цепочки к цели грамматики 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. V 0 : {S }; i : 1. 2. V i : V i − 1 {x | x T N, A → x P, A V i − 1 , , ( T N ) } . Если V i V i − 1 , то i : i 1 и переходим к шагу 2, иначе N' : V i N ; T' : V i T ; P' состоит из правил множества P, содержащих только символы из V i ; 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' ). Метод: Строим множества N 0 , N 1 , ... 1. N 0 , i 1. 2. N i N i − 1 {A | A → P и (N i − 1 T) * }. Если N i N i − 1 , то i : i 1 и переходим к шагу 2, иначе N' : N i ; P' состоит из правил множества P, содержащих только символы из N' T ; G' T, N', P', S Определение: КС-грамматика G называется приведенной, если в ней нет недости- жимых и бесплодных символов. Элементы теории формальных языков и грамматик / Преобразования грамматик 20 Алгоритм приведения грамматики 1. Обнаруживаются и удаляются все бесплодные нетерминалы. 2. Обнаруживаются и удаляются все недостижимые символы. Удаление символов сопровождается удалением правил вывода, содержащих эти сим- волы. 11) |