Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм Кока-Янгера-Касами)
Строка 29: Строка 29:
  
 
= Алгоритм Кока-Янгера-Касами =
 
= Алгоритм Кока-Янгера-Касами =
Алгоритм является универсальным для всех КС-грамматик, которые должны быть приведены в нормальную форму Хомского без &epsilon;-правил. Правила такой грамматики имеют вид либо А&rarr;а, либо А&rarr;BC, где a - терминал, B и C нетерминалы ,не являющиеся начальными. Алгоритм имеет сложность <tex>O(n^3)</tex> и использует <tex>O(n^2)</tex> памяти.
+
Алгоритм является универсальным для всех КС-грамматик, которые должны быть приведены в нормальную форму Хомского без &epsilon;-правил. Правила такой грамматики имеют вид либо А&rarr;а, либо А&rarr;BC, где a - терминал, B и C нетерминалы ,не являющиеся начальными. Алгоритм использует только квадратную матрицу, т.е. <tex>O(n^2)</tex> памяти.  <tex>O(n^3)</tex> и использует <tex>O(n^2)</tex> памяти.
  
 
Сам алгоритм состоит в построении треугольной матрицы разбора T по заданной входной строке '''<tex>a_1,  a_2,  \ldots,  a_n</tex>'''. В каждый элемент этой матрицы <tex>t_{ik}</tex> помещаются все нетерминалы, из которых можно вывести отрезок входной строки длины k, начинающийся  i-ым символом: '''<tex>a_i,  \ldots,  a_{i+k-1}</tex>'''.
 
Сам алгоритм состоит в построении треугольной матрицы разбора T по заданной входной строке '''<tex>a_1,  a_2,  \ldots,  a_n</tex>'''. В каждый элемент этой матрицы <tex>t_{ik}</tex> помещаются все нетерминалы, из которых можно вывести отрезок входной строки длины k, начинающийся  i-ым символом: '''<tex>a_i,  \ldots,  a_{i+k-1}</tex>'''.
Строка 36: Строка 36:
 
:: <tex>\forall</tex>i < j  <tex>t_{ij}</tex> = {A | A&rarr;BC и <tex>1 \leqslant k < j : B \in t_{ik}, C \in t_{i+k, j-k}</tex>}.
 
:: <tex>\forall</tex>i < j  <tex>t_{ij}</tex> = {A | A&rarr;BC и <tex>1 \leqslant k < j : B \in t_{ik}, C \in t_{i+k, j-k}</tex>}.
 
Действительно, в каждый элемент <tex>t_{i1}</tex> (в данном случае удобнее рассматривать первой нижнюю строку) помещаются все нетерминалы, для которых существует правило A &rarr; <tex>a_i</tex>. Пусть теперь заполнены все строки до j-1-й включительно.  
 
Действительно, в каждый элемент <tex>t_{i1}</tex> (в данном случае удобнее рассматривать первой нижнюю строку) помещаются все нетерминалы, для которых существует правило A &rarr; <tex>a_i</tex>. Пусть теперь заполнены все строки до j-1-й включительно.  
Рассмотрим элемент <tex>t_{ij}</tex>, соответствующий фрагменту &lt;<tex>a_1,\ldots, a_j </tex>&gt; входной строки. Разобьём его всеми способами на пары соседних строк '''<tex> <a_i> и <a_{i+1}...a_j>; <a_ia_{i+1}> и <a_{i+2} ...a_j></tex>''', и т.д. Каждому варианту разбиения соответствует пара элементов матрицы, в которых стоят нетерминалы, из которых могут быть выведены соответствующие строки. Пусть эта пара элементов – (t',t"). В рассматриваемый элемент <tex>t_{ij}</tex> помещаем нетерминал А, если среди правил грамматики есть правило А&rarr;ВС, и нетерминал В входит в элемент t', а С – входит в элемент t".
+
Рассмотрим элемент <tex>t_{ij}</tex>, соответствующий фрагменту &lt;<tex>a_1,\ldots, a_j </tex>&gt; входной строки. Разобьём его всеми способами на пары соседних строк &lt;<tex>a_i</tex>&gt; и &lt;<tex>a_{i+1}...a_j</tex>&gt;; &lt;<tex>a_ia_{i+1}</tex>&gt; и &lt;<tex>a_{i+2} ...a_j</tex>&gt;, и т.д. Каждому варианту разбиения соответствует пара элементов матрицы, в которых стоят нетерминалы, из которых могут быть выведены соответствующие строки. Пусть эта пара элементов – (t',t"). В рассматриваемый элемент <tex>t_{ij}</tex> помещаем нетерминал А, если среди правил грамматики есть правило А&rarr;ВС, и нетерминал В входит в элемент t', а С – входит в элемент t".
  
 
Входная строка принадлежит языку, порождаемому грамматикой, если в элементе <tex>t_{1n}</tex> встретится начальный нетерминал.
 
Входная строка принадлежит языку, порождаемому грамматикой, если в элементе <tex>t_{1n}</tex> встретится начальный нетерминал.

Версия 08:42, 15 января 2011

Контекстно-свободная грамматика

Контекстно-свободная грамматика (КС-грамматика, бесконтекстная грамматика) — частный случай формальной грамматики, у которой левые части всех правил являются одиночными нетерминалами. Для того, чтобы определить контекстно-свободную грамматику, необходимо:

  • 1) Задать конечное множество A - алфавит; его

элементы называют символами, а конечные последовательности симво- лов называют словами (в данном алфавите);

  • 2) Разделить все символы алфавита A на две группы: терми-

нальные ("окончательные") и нетерминальные ("промежуточные");

  • 3) Выбрать один из нетерминальных символов, который будет считаться начальным;
  • 4) Указать конечное число правил грамматики(продукций) вида:
    K → X

где K - некоторый нетерминальный символ, а X - слово, которое может состоять как из терминальных, так и не из терминальных символов. Выводом в контекстно-свободной грамматике называется последовательность слов X[0], X[1], ... ,X[n], где X[0] состоит только из начального символа, а каждое слово X[i+1] получается из X[i] заменой какого-либо нетерминального символа на слово по одному из правил грамматики.

Пример

Пусть алфавит состоит из символов a, b и S, при этом S - стартовый символ, а и b - терминальные. Пусть в этой грамматике определены следующие правила:

  • S → SS;
  • S → ab;
  • S → aSb;

Тогда в ней можно вывести слово ababab следующим образом:

  S → SS → Sab → SSab → abSab → ababab

При этом, например, слово bab невозможно вывести в этой грамматике.

Задача о выводе

Задача вывода в контекстно-свободной грамматике состоит в том, чтобы выяснить, можно ли вывести данное слово в этой КС-грамматике, т.е. выяснить принадлежность этого слова определяемому грамматикой языку. Для решения этой задачи существуют несколько способов, например, нисходящий анализ методом линейного спуска. Также применяется восходящий алгоритм синтаксического анализа Кока - Янгера - Касами.

Алгоритм Кока-Янгера-Касами

Алгоритм является универсальным для всех КС-грамматик, которые должны быть приведены в нормальную форму Хомского без ε-правил. Правила такой грамматики имеют вид либо А→а, либо А→BC, где a - терминал, B и C нетерминалы ,не являющиеся начальными. Алгоритм использует только квадратную матрицу, т.е. [math]O(n^2)[/math] памяти. [math]O(n^3)[/math] и использует [math]O(n^2)[/math] памяти.

Сам алгоритм состоит в построении треугольной матрицы разбора T по заданной входной строке [math]a_1, a_2, \ldots, a_n[/math]. В каждый элемент этой матрицы [math]t_{ik}[/math] помещаются все нетерминалы, из которых можно вывести отрезок входной строки длины k, начинающийся i-ым символом: [math]a_i, \ldots, a_{i+k-1}[/math]. Элементы матрицы вычисляются следующим образом:

[math]\forall[/math]i [math]t_{i1}[/math] = { A | A → [math]a_i[/math]};
[math]\forall[/math]i < j [math]t_{ij}[/math] = {A | A→BC и [math]1 \leqslant k \lt j : B \in t_{ik}, C \in t_{i+k, j-k}[/math]}.

Действительно, в каждый элемент [math]t_{i1}[/math] (в данном случае удобнее рассматривать первой нижнюю строку) помещаются все нетерминалы, для которых существует правило A → [math]a_i[/math]. Пусть теперь заполнены все строки до j-1-й включительно. Рассмотрим элемент [math]t_{ij}[/math], соответствующий фрагменту <[math]a_1,\ldots, a_j [/math]> входной строки. Разобьём его всеми способами на пары соседних строк <[math]a_i[/math]> и <[math]a_{i+1}...a_j[/math]>; <[math]a_ia_{i+1}[/math]> и <[math]a_{i+2} ...a_j[/math]>, и т.д. Каждому варианту разбиения соответствует пара элементов матрицы, в которых стоят нетерминалы, из которых могут быть выведены соответствующие строки. Пусть эта пара элементов – (t',t"). В рассматриваемый элемент [math]t_{ij}[/math] помещаем нетерминал А, если среди правил грамматики есть правило А→ВС, и нетерминал В входит в элемент t', а С – входит в элемент t".

Входная строка принадлежит языку, порождаемому грамматикой, если в элементе [math]t_{1n}[/math] встретится начальный нетерминал.

Литература