Материалы (3) (Материалы к лекциям)

34(1)Примеры грамматик и языковS  ABCSBA  AB| ABcCA  ACCB  BCCc  ccBc  bcBb  bbAb  abAa  aaТип 1. Неукорачивающая, но не КЗ{a nbn c 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Левый (левосторонний) вывод цепочки   T* из S  N в КСграмматике G = (T, N, P, S) :в этом выводе каждая очередная сентенциальная форма получаетсяиз предыдущей заменой самого левого нетерминала.Правый (правосторонний) вывод цепочки   T* из S  N в КСграмматике G = (T, N, 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}.