КС-грамматика для языка L, построение дерева вывода и левосторонней для цепочки aabbbcccc. Метод восходящего разбора

Если допустить в правилах вывода грамматики пустую альтернативу

A ® a a |…| a a|e

то метод рекурсивного спуска может оказаться не применим.

Грамматика G = (VT, VN, P, S) называется контекстно-свободной ( КС), если каждое правило из Р имеет вид A →β, где A € VN, β € (VT U VN).

Грамматика G = (VT, VN, P, S) называется укорачивающей контекстно-

свободной ( УКС ), если каждое правило из Р имеет вид A →β, где A Î VN,

β Î(VT U VN)*.

Решение:

G:

S -> A┴

A -> B { aB } B

B -> b

По данной грамматике анализ методом рекурсивного спуска вести можно, так грамматика имеет правила имеют вид  A®.a ; A®a_ia_i, i=1…n  .  В регулярной грамматики правила вида:                                   A -> a

A -> aA

A -> Aa  

2.2.13. Записать в ПОЛИЗе следующий оператор языка Си, используя стек, выполнить его при указанных начальных значениях переменных:

S = 0;

for ( I = 1; I <= k; I = I + 1) S = S +i*i;

при k = 3.

ПОЛИЗ(ПОЛьская Инверсная Запись) – внутренне представление программы. В ПОЛИЗе операнды выписываются слева направо в порядке их использования, знаки стоят таким образом, что знаку операции непосредственно предшествуют операнды, учтено старшинство операций, а скобок нет. В ПОЛИЗе всегда подразумевается по умолчанию, что любая операция бинарная.

При решении используется алгоритм Дейкстры по переводу выражений в ПОЛИЗ.

Так же ПолИЗу соответствует так называемое дерево ПолИЗа.

Распознавателями для КС-языков служат автоматы с магазинной памятью.МП-автомат имеет стек (магазин), в который можно помещать специальные «магазинные символы»(обычно это терминальные и нетерминальные символы грамматики языка). Переход из одного состояния в другое зависит не только от входного символа, но и от символа на верхушке стека.

Магазинный автомат

Контекстно-свободными называются языки, определяемые грамматиками типа G(VT, VN, P, S), в которых правила P имеют вид: A®b, где AÎ VN и bÎV^*, V =VT ÈVN. Распознавателями КС-языков служат автоматы с магазинной памятью (МП-автомат).

В общем виде МП-автомат можно определить следующим образом:

R(Q, V, Z, d, q₀, z₀, F), где Q – множество состояний автомата;

V – алфавит входных символов автоматаж

Z – специальныйконечный алфавит магазинных символов автомата, VÍZ;

d - функция переходов автомата, которая отображает множество Qx(VÈ{l})xZ на конечное множество подмножеств P(QxZ^*);

q₀ ÎQ – начальное состояние автомата;

z₀ ÎZ – начальный символ магазина;

FÍ Q – множество конечных состояний.

МП-автомат имеет стек (магазин), в который можно помещать специальные «магазинные символы»(обычно это терминальные и нетерминальные символы грамматики языка). Переход из одного состояния в другое зависит не только от входного символа, но и от символа на верхушке стека. Конфигурация автомата определяется тремя параметрами: состоянием автомата, текущим символом входной цепочки(положением указателя в цепочке) и содержанием стека.

Решение:

S 0 =

I 1 +

p0 :    I k  <=

p1

!F

S S I I * + =

I I 1 + =

p0

!

p1:                             

Реализация стека:

1)  S=0, I=1, k=3

2)  I=1, S=0+ 1*1 = 1

3)  I=2, S=1+2*2=5

4)  I=3, S=5+3*3=14

2.2.14. Записать в ПОЛИЗе следующий оператор языка Си, используя стек, выполнить его при указанных начальных значениях переменных:

switch (k) {

case 1: a = not a; break;

case 2: b = a or not b;

case 3: a = b;

}

ПОЛИЗ(ПОЛьская Инверсная Запись) – внутренне представление программы. В ПОЛИЗе операнды выписываются слева направо в порядке их использования, знаки стоят таким образом, что знаку операции непосредственно предшествуют операнды, учтено старшинство операций, а скобок нет. В ПОЛИЗе всегда подразумевается по умолчанию, что любая операция бинарная.

Распознавателями для КС-языков служат автоматы с магазинной памятью.МП-автомат имеет стек (магазин), в который можно помещать специальные