Неограниченные грамматики

• В грамматиках типа 0 на правую и левую части продукции  не накладывается никаких ограничений, кроме   .

• Общего алгоритма распознавания не существует.

Контекстно зависимые грамматики

Грамматика типа 1 (НС-грамматики).

Контекстно-зависимые грамматики имеют продукции вида A, где А – некоторый нетерминальный символ; ,  - производные цепочки, которые образуют контекст, в котором A может быть заменён продукцией  ()

Пример:

• S aSBC | abC (1 тип)

• CB  BC (0 тип)

• bBbb (1 тип)

• cCcc (1 тип)

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

Грамматика типа 2 (КС – грамматики) – грамматики с правилами вида A, т.е. левая часть продукции содержит только один нетерминальный символ, т.е. говорят, что грамматика свободна от контекста. Для них существуют эффективные алгоритмы для синтаксического анализа. Такие грамматики часто используются для построения формальных языков.

Пример:

• G=<{a,b,c}, {S,T,M}, S, R>

• S  bT | a

• T aM |c

Автоматные грамматики

Грамматики типа 3 (регулярные языки) – грамматики, с правилами вида Аa; ABa; A. Имеют линейные по времени методы распознавания.

Пример:

• SaS |bA

• AaB|

• B bA|a

Эквивалентность грамматик

Любой язык может быть порождён бесконечным числом грамматик.

Определение 4. Грамматики называют эквивалентными, если они порождают один и тот же язык.

Таблица 2. Примеры порождения языка разными грамматиками.

G3^:SABC A  aA | a B b C Cc | c

G3^’:SAD A  aA |a D bC C Cc |c

G3^’’:SaA A  aA |bC C Cc |c

Однозначность грамматик

Определение 5. Грамматика называется однозначной, если для каждой цепочки символов языка, заданного этой грамматикой, можно построить единственный левосторонний (правосторонний) вывод. В противном случае грамматика называется неоднозначной.

G₄({+,-,*,/,(,),a,b}, {S}, S, R}

R: SS+S|S-S|S*S|S/S|(S)|a|b

Используя левосторонний вывод, построим цепочку a*b+a:

• SS+S S*S+S a*S+S a*b+S a*b+a

• S S*S a*S a*S+S a*b+S a*b+a

Рисунок 1. Деревья вывода однозначных грамматик

Доказано, что в общем случае не существует алгоритма доказательства эквивалентности и однозначности грамматик («проблема соответствий Поста»).

Правила, задающие неоднозначность в грамматиках

• AAA |

• A A  A | 

• A  A | A  | 

• A  A |  A A | 

Пример 1. Однозначная грамматика для арифметических выражений.

V = {+, -, *, /, (, ), digit}

• E  E + T | E – T |T

• T  T * F | T / F | F

• F  digit | (F)

Пример 2. 3 + 5 * 2

E  E + T  E + T * F  T + T * F  F + F * F  3 + 5 * 2

Пример 3. Грамматика для языка Мини-Паскаль

begin

m:=read; n:=read;

while (m <> n) do

if m>n then m:=m-n else n:=n-m;

write(m);

end

П – программа, L – список операторов, S – оператор, B – условие, Q – знак отношения, E – выражение, I – идентификатор, C – константа, n – цифра, e - буква.

• П  begin L end

• L  S | S;L

• S  I := | E | while B do L | if B then L else L | write(E)

• B E Q E

• Q = |< | > |<> | >= |<=

• E I | C | (E) | E + E | E * E | E – E | E / E | read

• I  e | Ie | In

C  n | Cn