programming.systems.L13-14.slides (1119459), страница 2
Текст из файла (страница 2)
е. рекурсивноперечислимым языком), но существуют языки типа 0,которые не являются КЗ-языками, например: язык,состоящий из записей самоприменимых алгоритмовМаркова в некотором алфавите.32Иерархия классов языковТип 3 (Регулярные) ⊂ Тип 2 (КС) ⊂ Тип 1 (КЗ) ⊂ Тип 033Проблема «Можно ли язык, описанный грамматикой типа k(k = 0, 1, 2), описать грамматикой типа k + 1 ?» являетсяалгоритмически неразрешимой.Язык La,b = {a, b}.
Какого он типа? Обычно требуется указатьмаксимально возможный тип.Ответ: типа 3S→a|b— грамматика типа 3, порождающая данный язык.(La,b является также языком типа 2, 1, 0 в силу иерархии Хомского)34(1)Примеры грамматик и языковS → ABCS| ABcBA → ABCA → ACCB → BCCc → ccBc → bcBb → bbAb → abAa → aaТип 1.
Неукорачивающая, но не КЗ{a nb nc n | n > 0}Язык:35Примеры грамматик и языков(2)S → aSb | abЯзык:{a n b n | n > 0}(3)S → aS | aЯзык:{a n | n > 0}36Иерархия классов Хомского{an bn | n>0}{an | n>0}{an bn cn| n>0}Язык записей самоприменимых алгоритмов37Задача распознаванияДаны грамматика G и цепочка xx∈L(G) ?Для грамматик типа 1 (а также типов 2 и 3) по классификацииХомского задача распознавания разрешима, т.е. существуетобщий алгоритм, отвечающий на вопрос: x ∈ L(G) ?38Контекстно-свободные грамматики и языки39КС-грамматики позволяют выразить такие свойства языковпрограммирования, как скобочные структуры, последовательностьописаний и операторов и др.
Но не могут задавать контекстнозависимые свойства, например, соответствие числа формальных ифактических параметров при вызове функции. Для КС-грамматиксуществуют эффективные алгоритмы анализа, поэтому ониприменяются в трансляции, контекстные условия проверяются наэтапе семантического анализа40Левый (левосторонний) вывод цепочки β ∈ (VT)* из S ∈ VN в КСграмматике G = (VT, VN, P, S) :в этом выводе каждая очередная сентенциальная форма получаетсяиз предыдущей заменой самого левого нетерминала.Правый (правосторонний) вывод цепочки β ∈ (VT)* из S ∈ VN в КСграмматике G = (VT, VN, P, S ):в этом выводе каждая очередная сентенциальная форма получаетсяиз предыдущей заменой самого правого нетерминала.41Рассмотрим пример грамматики:G = ({a,b,+}, {S,T}, {S → T | T+S; T → a | b}, S)можно построить выводы для цепочки a+b+a :(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) не являетсяни левосторонним, ни правосторонним42Определение: упорядоченное ориентированное деревоназывается деревом вывода (или деревом разбора) в КСграмматике G = (T, N, P, S), если выполнены следующиеусловия:(1) каждая вершина дерева помечена символом из множестваN∪T∪{ε}, при этом корень дерева помечен символом S; листья символами из T∪{ε};(2) если вершина дерева помечена символом A , а еенепосредственные потомки - символами a1, a2, ...
, an, гдекаждое ai ∈ T∪N, то A → a1a2...an - правило вывода в этойграмматике;(3) если вершина дерева помечена символом A , а ее единственныйнепосредственный потомок помечен символом ε, то A → ε —правило вывода в этой грамматике.43Пример дерева вывода для цепочки a+b+a в грамматике G =({a,b,+}, {S,T}, {S → T | T+S; T → a | b}, S) :STS+SaT+Tba(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+a44КС-грамматика G называется неоднозначной,если существует хотя бы одна цепочка α ∈ L(G), для которойможет быть построено два или более различных деревьеввывода.Это утверждение эквивалентно тому, что цепочка α имеет дваили более разных левосторонних (или правосторонних)выводов.В противном случае грамматика называется однозначной.45Утв.
Проблема определения, является ли заданная КСграмматика однозначной, является алгоритмическинеразрешимой.Язык, порождаемый грамматикой, называется неоднозначным,если он не может быть порожден никакой однозначнойграмматикой.Утв. Проблема определения, порождает ли данная КСграмматика однозначный язык (т.е. существует лиэквивалентная ей однозначная грамматика), являетсяалгоритмически неразрешимой.•Пример неоднозначного языка:L= {an bn cm| n>0, m>0} ∪ {an bm cm| n>0,m>0}46Приведенные КС-грамматикиСимвол x ∈ (T ∪ N) называется недостижимымв грамматике G=(T, N, P, S), если он не появляется нив одной сентенциальной форме этой грамматики.Символ А ∈ N называется бесплодным вграмматике G=(T, N, P, S), если множествовыводимых из этого символа терминальных цепочекпусто.КС-грамматика называется приведенной, если вней нет недостижимых и бесплодных символов.47Приведенные КС-грамматикиАлгоритм приведения грамматики:1.Найти и удалить все бесплодные символы иправила, их содержащие.2.Найти и удалить все недостижимые символы иправила, их содержащие.Примечание.
Если начальный символ грамматики окажется бесплодным, тоследует удалить содержащие его правила, а сам символ оставить в алфавитенетерминалов N, так как по определению грамматики N обязан содержатьначальный символ.48Для нахождения бесплодных и недостижимыхсимволов полезен граф КС-грамматики:• каждому символу из T ∪ N соответствуетединственная вершина, помеченная этим символом;если в P есть правило с пустой правой частью ε, тограф имеет вершину, помеченную ε ;• вершина X соединяется с вершиной Y стрелкой(дугой), если в грамматике есть правило X→αYβ,α,β∈(T∪N)* ;• X соединяется с вершиной ε, если в грамматикеесть правило X→ε .49Алгоритм удаления бесплодных символов:1.
Отметить терминальные вершины (вершины,помеченные терминальными символами), а такжевершину ε, если таковая имеется.2. Если в Р есть правило А→α, где α состоит из ужеотмеченных в графе символов, а вершина А неотмечена, то отметить эту вершину. Повторятьшаг 2 пока возможно.3. Из грамматики удалить неотмеченные символы иправила, их содержащие.50Алгоритм удаления бесплодных символов:1.
Отметить терминальные вершины (вершины, помеченныетерминальными символами), а также вершину ε, если такаяимеется.2. Если в Р есть правило А→α, где α состоит из ужеотмеченных в графе символов, а вершина А не отмечена, тоотметить эту вершину. Повторять шаг 2 пока возможно.3. Из грамматики удалить неотмеченные символы и правила, ихсодержащие.Алгоритм удаления недостижимых символов:1.
Отметить вершины, в которые есть путь из вершины S(достижимы из вершины S).2. Удалить из грамматики неотмеченные символы и правила, ихсодержащие.51Пример. Дана грамматикаG=({a, b, c, d, e}, {S, A, B, C, D}, P, S)P:S → aAB | CD → cDc | dC → aCDA → aA | a | εcB→bГраф грамматики G:CDSBaAbεde52Пример. Дана грамматикаG=({a, b, c, d, e}, {S, A, B, C, D}, P, S)P:S → aAB | CD → cDc | dC → aCDA → aA | a | εcB→bГраф грамматики G:CDSBaAbεdeНе отмеченные жирным кружком символы бесплодны.53Пример. Дана грамматикаG=({a, b, c, d, e}, {S, A, B, C , D}, P, S)P:S → aAB | CD → cDc | dC → aCDA → aA | a | εcB→bГраф грамматики G:CDSBaAbεdeНе отмеченные жирным кружком символы бесплодны.Удалив из G бесплодные символы, получим эквивалентную грамматикуG1 =({a, b, c, d, e}, {S, A, B, D}, P1 , S)P1 : S → aABD → cDc | dA → aA | a | εB→bG1 не содержит бесплодных символов.Находим недостижимые символыГраф грамматики G1 :SBaAcDbεde54G1 =({a, b, c, d, e}, {S, A, B, D}, P1 , S)P1 : S → aABD → cDc | dA → aA | a | εB→bГраф грамматики G1 :SBaAcDbεdЗдесь неотмеченные символы являются недостижимыми.e55G1 =({a, b, c , d , e }, {S, A, B, D }, P1 , S)P1 : S → aABD → cDc | d лA → aA | a | εB→bГраф грамматики G1 :SBaAcDbεdeЗдесь неотмеченные символы являются недостижимыми.Удалив из G1недостижимые символы, получимэквивалентнуюграмматику:G2 =({a, b}, {A, B}, P2 , S)G2 – приведенная грамматикаP2 : S → aABA → aA | a | εB→bL(G)=L(G1 )=L(G2 )={ an b | n≥1 }Задача.
Убедиться, что если в рассмотренном выше примере поменятьместами шаги (1) и (2) алгоритма приведения грамматики, то результатомбудет неприведенная грамматика.56Устранение правил с пустой правой частью из КС-грамматики1. Построить множество Х={A∈N | A⇒ε}.2. Удалить правила с пустой правой частью.3. Если S∈X, то S’ – новый начальный символ, S’→S | ε ∈P.4. ∀ A∈X правило вида B→α1A1α2A2...αnAnαn+1,где αi∈((N – X)∪T)*nзаменить 2 правилами, соответствующими всем возможнымкомбинациям вхождений А между αi:B→α1α2...αnαn+1B→α1α2...αnAnαn+1...B→α1α2A2...αnAnαn+1B→α1A1α2A2...αnAnαn+1Замечание: если все αi=ε ∀ i=1,...,n+1, то правило B→ε невключать в новую грамматику.5.
Удалить бесполезные символы и правила, их содержащие.57Пример.исходнаяграмматикаS→BC | AbB→εC→cA→Aa | εэквивалентнаяграмматикаS→C | b | AbC→cA→Aa | a.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
