7. Формальные языки и методы трансляции

7.1. Право- и леволинейные грамматики. Регулярные (автоматные) грамматики. Регулярные множества и праволинейные грамматики

Определение. Грамматика G = (A, V, P, s) называется праволинейной (леволинейной), если каждое правило имеет вид u Φ или u Φv (u vΦ), где u,v  V, Φ  A*.

Определение. Праволинейная грамматика называется регулярной (автоматной), если |Φ| = 1 и если s  e  P, то s не встречается в правых частях правил.

Язык определяется праволинейной грамматикой тогда и только тогда, когда он является регулярным множеством. Для {a} грамматика Ga = ({a}, {s},{u a}, s).

Если языки L₁ и L₂ порождаются регулярными грамматиками, можно построить регулярные грамматики и для языков L₁L₂, L₁L₂ и L₁*.

Обратное доказывается возможностью решения стандартной системы уравнений с регулярными коэффициентами.

[АУ], п.2.2.2.

[M] гл.1

7.2. Автоматы с магазинной памятью (мп-автоматы). Детерминированные и недетерминированные мп-автоматы. Построение эквивалентного мп-автомата по кс-грамматике

Определение. МП-автомат P = (Q, A, Г, δ, q₀, z₀, F), где Q – множество состояний, A – алфавит, δ: Q×(A{e})×Г  2^Q×Г* – функция перехода, q₀ Q – начальное состояние, F – конечные состояния, Г – множество символов МП, z₀Г – маркер. Если всегда |δ(q,a,b)|1, автомат детерминированный, в противном случае – недетерминированный.

Определение. Такт работы – смена конфигураций (q, aΦ, bΨ) |- (q’, Φ, γΨ), если (q’γ)  δ(q,a,b), где Φ – непрочитанная часть цепочки на входной ленте, bГ, ΨГ*. Возможен пустой такт (q, aΦ, bΨ) |- (q’, aΦ, γΨ), если (q’γ)  δ(q,e,b), где e – пустой символ.

Определение. Цепочка Φ допускается автоматом, если (q₀, Φ, z₀) |-*(q’, e, Ψ), где q’  F.

Определение. Цепочка Φ допускается опустошением магазина, если (q₀, Φ, z₀) |-*(q’, e, e).

Для любой КС-грамматики G = (A, V, P, s) можно построить МП-автомат, множество допускаемых цепочек которого будет совпадать с языком, порождаемым грамматикой: P = (V, A, AV, δ,q₀, s, Ø). Правила построения:

1) δ(q₀,e,u) = {(q₀, γ)}, для всех правил u  γ.

2) δ(q₀,a,a) = {(q₀, e)} для всех aA.

[АУ], п.2.5.1, 2.5.3

7.3. Восходящий анализ кс-языков без возвратов. Lr(k)-грамматики. Грамматики простого предшествования. Алгоритм «перенос-свертка» для грамматики простого предшествования

В алгоритме восходящего анализа дерево вывода строится снизу вверх. Алгоритм моделирует расширенный МП-автомат. Производятся действия переноса (входной символ переносится в МП) или свертки (часть символов в МП заменяется нетерминалом).

Определение. КС-грамматика G = (A, V, P, s) называется LR(k)-грамматикой, если решение о действии на каждом шаге алгоритма «перенос-свертка» принимается на основе k символов входной цепочки.

Грамматика простого предшествования – это LR(1)-грамматика с управляющей таблицей в виде матрицы предшествования. Строки и столбцы помечены символами грамматики. Элемент таблицы может содержать символ отношения предшествования (отношения Вирта-Вебера) «=», «<» или «>»:

(1) x = y   z  xy  P, где , (A  V)*

(2) x <∙y   z  xv  P, такое, что v => + yγ, где ,,γ (A  V)*

(3) x ∙> a   z  vz  P, такое, что v => + γx и z =>*a, где aA; ,,γ,  (A  V)*

При работе алгоритма рассматривается отношение символа в вершине стека и текущего символа. Если отношение = или <∙, выполняется перенос. Если ∙>, выполняется свертка. Грамматика пополняется правилом s’  #s#, где s – начальный символ. Например, для грамматики с правилами s  0s|1 алгоритм для цепочки 001 приводит к следующей последовательности конфигураций: (#, 001#) - (#0,01#) - (#00, 1#) - (#001,#)- (#00s,#)- (#0s, #)-(#s,#). Сначала 3 переноса, затем 3 свертки. Отношения предшествования, использованные по шагам: #<∙0, 0<∙0, 0<∙1, 1∙># , s∙>#, s∙>#. При свертке выбирается подцепочка в вершине стека, символ слева от которой находится в отношении <∙ с первым символом подцепочки (на 4-м шаге 0<∙1 и 1∙>#, поэтому 1 сворачивается в s).

Если при вычислении отношений возникает коллизия – некоторая пара символов оказывается в двух разных отношениях, грамматика не является грамматикой простого предшествования. При коллизии отношений = и < грамматика называется грамматикой слабого предшествования. Существуют и другие классы грамматик предшествования.

На грамматику простого предшествования накладывается еще одно ограничение – грамматика должна быть обратимой (не должно быть двух правил с одинаковыми правыми частями).

[АУ] п.5.2.1, п.5.2.2, п.5.3.2.

[M] гл.4. [Х] гл 5. [K] 6.3