- •Построение матрицы операторного предшествования
- •Автомат с магазинной памятью (сокращенно мп-автомат)
- •Преобразователь с магазинной памятью (сокращенно мп - преобразователь)
- •Опишем lr(k)-алгоритм разбора.
- •Алгоритм построения управляющей таблицы для lr(0)-грамматики без -правил
- •Алгоритм построения управляющей таблицы для slr(1)-грамматики без -правил
- •Включение -правил в lr(0)- и slr (1)-грамматики
- •Алгоритм построения анализатора типа “перенос –свертка” для грамматик простого предшествования
- •Описание алгоритма
Включение -правил в lr(0)- и slr (1)-грамматики
г) если А – правило вывода с номером i и множество
СЛЕД (A) ={aj 1j m , где m – количество символов в T { } },
то f(aj) = (СВЕРТКА, i) в тех строках управляющей таблицы, для которых g(A) ОШИБКА.
Алгоритм построения анализатора типа “перенос –свертка” для грамматик простого предшествования
Вход
Грамматика простого предшествования G = < T, N, S, R >, в которой правила вывода занумерованы натуральными числами 1, 2, ... , р.
Выход
Алгоритм A = (f, g) типа “перенос – свертка” для грамматики G.
Функция переноса f зависит только от верхнего символа магазина и самого левого необработанного символа входной цепочки. Поэтому f определяется на множестве (V { }) (T { }) ( за исключением правила с), которое имеет приоритет над правилами а) и b), когда Х = S и a = ):
f(X, а) = ПЕРЕНОС, если Х <• а или Х а ;
f(X, а) = СВЕРТКА, если Х •> а ;
f(S, ) = ДОПУСК;
f(X, а) = ОШИБКА в остальных случаях.
2) Функция свертки g зависит от верхней части магазинной цепочки, включающей основу и еще один символ ниже нее. Необработанная часть входной цепочки на g не влияет, поэтому g задается только на (V { })*:
g(Xk+1XkXk-1 … X1, ) = i, если Xk+1 <• Xk, Xj+1 Xj для k>j1 и
A ХkХk-1 ... Х1 – правило вывода с номером i. Заметим, что функция g определяется только тогда, когда Х1 •> a – текущий входной символ;
b) g(, ) = ОШИБКА в остальных случаях.
Для КС-грамматики G = < T, N, S, R >отношения простого предшествования <• и определяются на (V { })(V { }), где –маркер дна магазина, следующим образом:
X Y,если вRесть правилоA XY.
a) X <• Y,если вRесть правилоA XB иB +Y;
б) <• Yдля всехY, для которыхS + Y;
Отношение • определяется на(V { })(T { }), так как непосредственно справа от правовыводимой цепочки может стоять только терминал.
a)X • a,если вRесть правилоA BY иB +X и Y a;
б) X • для всех, для которыхS + X.
пример
S aSSb
S c
f(X,a) |
a |
b |
c |
|
S |
П |
П |
П |
|
a |
П |
|
П |
|
b |
С |
С |
С |
С |
c |
С |
С |
С |
С |
|
П |
|
П |
|
S |
|
|
|
Д |
|
g() | |
S |
aSSb |
1 |
a |
aSSb |
1 |
|
aSSb |
1 |
S |
c |
2 |
a |
c |
2 |
|
c |
2 |
|
S |
a |
b |
c |
|
S |
|
<• |
|
<• |
|
a |
|
<• |
|
<• |
|
b |
|
• |
• |
• |
• |
c |
|
• |
• |
• |
• |
|
|
<• |
|
<• |
|
грамматики слабого предшествования.
Определение.
Пусть G = < T, N, S, R > – приведенная грамматика без -правил. Назовем G грамматикой слабого предшествования, если
1)отношение •> не пересекается с объединением отношений <• и ;
2)для AX и В из R, где XV, не выполняется ни Х <• В, ни Х В.
Вход
Обратимая грамматика слабого предшествования G = < T, N, S, R >, правила которой занумерованы натуральными числами от 1 до р.
Выход
Алгоритм A = (f, g) типа “перенос – свертка” для грамматики G.