И.А. Волкова, А.А. Вылиток, Т.В. Руденко - Формальные грамматики и языки. Элементы теории трансляции (1114891), страница 4
Текст из файла (страница 4)
Новые символы а, [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 и с; а всегда стоn n nит левее, чем b и с, b всегда стоит левее, чем с, т. е. любая цепочка имеет вид a b c , что итребовалось доказать.Разбор цепочекЦепочка в алфавите T принадлежит языку, порождаемому грамматикой 〈 T, N, P, S 〉,только в том случае, если существует ее вывод из начального символа S этой грамматики.Процесс построения такого вывода (а, следовательно, и определения принадлежности цепочки языку) называется разбором 8). Построение вывода можно осуществлять и в обратном порядке: в исходной цепочке ищем вхождение правой части некоторого правила и заменяем егона левую часть (это называется сверткой), в результате исходная цепочка «сворачивается» кнекоторой сентенциальной форме, затем идет следующая свертка и т.
д., пока не придем кцели грамматики — S . Процесс разбора называют также анализом.С практической точки зрения наибольший интерес представляет разбор по контекстно-свободным грамматикам. Их порождающей мощности достаточно для описания большей части синтаксической структуры языков программирования, для различных подклассовКС-грамматик имеются хорошо разработанные практически приемлемые способы решениязадачи разбора.Рассмотрим основные понятия и определения, связанные с разбором по КСграмматике.*Определение:выводцепочкиβ∈TизS∈NвКС-грамматикеG = 〈 T, N, P, S 〉, называется левым (левосторонним), если в этом выводе каждая очереднаясентенциальная форма получается из предыдущей заменой самого левого нетерминала.8)Разбором также называют и результат этого процесса, т. е.
вывод цепочки, представленный (зафиксированный) каким-нибудь способом.15Элементы теории формальных языков и грамматик / Разбор цепочек*изS∈NвКС-грамматикеОпределение:выводцепочкиβ∈TG = 〈 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считаются различными.Элементы теории формальных языков и грамматик / Разбор цепочекНаличие двух или более деревьев вывода эквивалентно тому, что цепочка α имеет дваили более разных левосторонних (или правосторонних) выводов.Рис. 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' | aа)б)Рис. 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
