Теория и реализация языков программирования

Курочкин В.М., Столяров Л.Н., Сушков Б.Г., Флёров Ю.А.

2

Предисловие

На протяжении ряда лет студентам факультета управления и прикладной математики МФТИ читался курс �Языки программирования�. Содержание этого курса постепенно установилось и в настоящее время он состоит из 4 разделов: Методы порождения языков программирования, грамматики, автоматы с магазинной памятью - глава 1; методы синтаксического анализа языка, использующие грамматики и автоматы - глава 2; методы перевода из одного языка на другой, в частности, перевод с помощью магазинного преобразователя и перевод, формально определяемый синтаксисом и семантикой (�синтаксически управляемая трансляция�) - глава 3; наконец, демонстрация на примере языка АЛГОЛА-60 методов реализации основных понятий и конструкций языка программирования на ЭВМ.

Как видно из этого перечисления, курс содержит не описание каких-либо конкретных языков программирования, а их теорию и по характеру изложения являются математическим, Исключение представляет лишь 4-ый раздел, носящий несколько �эвристический� характер и содержащий изложение конкретного способа реализации конкретного же языка (АЛГОЛ-60). По целому ряду соображений мы считали целесообразным включить этот материал в данный курс.

В МФТИ �языки программирования� читаются на 2-м курсе. Предполагается, что студенты знают к этому времени основные элементы языка АЛГОЛ-60, знакомы с ЭВМ (например, писали программы на АЛГОЛе-60 и языке ассемблера и пускали их на машине).

В оформлении книги большую помощь оказали мне преподаватели МФТИ Борис Григорьевич Сушков (глава I), Юрий Арсеньевич Флёров (глава II) и Лев Николаевич Столяров (глава III), просмотревшие конспекты лекций, написавших связный текст соответствующих глав, добавивших ряд примеров, поясняющих изложение, и задач.

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

В.М.Курочкин

Москва, 1973 г.

Оглавление

Предисловие 3

1. Определение формальных языков 6 1.1. Порождающие грамматики . . . . . . . . . 6

1.2. Языки и грамматики непосредственных состав-

ляющих . . . . . . . . . . . . . . . . . . . . . 9

1.3. Контекстно-свободные языки и грамматики 10 1.4. Операции над КС-языками . . . . . . . . . 14

1.5. Неоднозначные грамматики и неоднозначные

языки . . . . . . . . . . . . . . . . . . . . . . 16

1.6. Магазинные автоматы . . . . . . . . . . . . 20

2. Синтаксический анализ 31 2.1. Проблема принадлежности слова языку . 31 2.2. Анализ сверху-вниз и снизу-вверх . . . . . 34 2.3. Грамматики с отношением предшествования 37 2.4. Функции предшествования . . . . . . . . . 45 2.5. Детерминированные автоматы с магазинной

памятью . . . . . . . . . . . . . . . . . . . . 50 2.6. LR(k)-грамматики . . . . . . . . . . . . . . 60

Глава 1.

Определение формальных языков

1.1. Порождающие грамматики

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

Синтаксис формального языка - это совокупность признаков, позволяющая выделить правильные предложения из множества всех цепочек терминальных символов.

Семантика языка - это смысл, вкладываемый в предложение языка.

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

Одним из средств задания синтаксиса языка являются формальные (порождающие) грамматики.

\underline{Определение 1.1.1.} Порождающей грамматикой называется упорядоченная четвёрка G = (V, T, P, S), где V - конечное множество символов (алфавит грамматики), T ⊆ V - конечное множество терминальных символов (терминальный алфавит), P - конечное множество упорядоченных пар вида φ → ψ (множество правил вывода грамматики или подстановок).

Здесь φ и ψ - произвольные цепочки в алфавите V, т.е. φ, ψ ∈ V^{∗}. V^{∗} будет обозначать множество всех цепочек в алфавите V.

S - начальный символ (аксиома) из V.

Множество V_{n} = V − T называется нетерминальным (вспомогательным) алфавитом, а его элементы - вспомогательными (нетерминальными) символами.

Несколько соглашений относительно обозначений.

В дальнейшем будем использовать начальные строчные буквы латинского алфавита a, b, c, ... для обозначения отдельных терминальных символов.

Заглавными начальными буквами латинского алфавита A, B, C... будем обозначать символы, принадлежащие вспомогательному алфавиту.

На место начальных букв греческого алфавита α, β, γ, ... в формулах могут быть подставлены как символы нетерминального (вспомогательного), так и основного алфавита.

Для обозначения цепочек из терминальных символов используются конечные малые буквы латинского алфавита ... , u, v, w, x, y, z, для цепочек из нетерминальных символов - соответствующие заглавные латинские буквы ... , U, V, W, X, Y, Z.

Цепочки, в которые могут входить любые символы алфавита V, будем обозначать последними буквам греческого алфавита ... , σ, τ, φ, χ, υ, ψ, ω.

Буква S обычно используется для обозначения аксиомы грамматики.

Символ ∅ обозначает пустую цепочку. Иногда вместо �порождающая грамматика� будем писать �грамматика�.

\underline{Пример 1.1.2.} G = (\{a, b, c, S, A\}, \{a, b, c\}, P, S), где P = {S → ab, S → bSAaA, S → ∅, A → bScb, SA → Aab} G = ({a, b, c, A, B, S}, {a, b, c}, P, S), P = {S → AB, AB → AaB, AaB → AbcB, Ab → ab, cb → ca};

G - порождающая грамматика.

Рассмотрим теперь, как применяются правила.

\underline{Определение 1.1.3.} Пусть G = (V, T, P, S) - порождающая грамматика и χ, ω ∈ V^{∗}.

Будем писать χ ⇒ ω, если существуют σ, τ, φ и ψ ∈ V^{∗}, такие, что χ = σφτ, ω = σψτ и φ → ψ ∈ P.

Далее пишем χ ⇒^{∗} ω, если либо χ = ω, либо существуют ω_{0}, ω_{1}, ... , ω_{r}, такие, что ω_{0} = χ, ω_{r} = ω и ω_{i} ⇒ ω_{i+1} для всех i.

Последовательность ω_{1}, ... , ω_{r} называется выводом ω_{r} из ω_{0} (длины r) и записывается в виде

ω_{0} ⇒ ω_{1} ⇒ ... ⇒ ω_{r}.

\underline{Определение 1.1.4.} Пусть G = (V, T, P, S) - порождающая грамматика. Множество цепочек

L(G) = {x ∈ T^{∗}|S ⇒^{∗} x}

называется языком, порождаемым грамматикой G.

Иногда на вид правил φ → ψ порождающей грамматики накладываются ограничения

φ ∈ (V − T)^{∗} − {∅} (1)

Покажем, что такое ограничение не меняет класса языков, порождаемых грамматиками.

\underline{Теорема 1.1.5} . Для любой грамматики G_{1} существует грамматика G_{2}, удовлетворяющая ограничению (1), такая, что L(G_{1}) = L(G_{2}).

Доказательство. Пусть G_{1} = (V, T, P, S). Построим эквивалентную грамматику G_{2}. Поставим в соответствие каждому символу α ∈ V символ α′ ∈ V′, символу пустой цепочки ∅ поставим в соответствие символ A(A ∉ V_{N} ∪ T).

Обозначим V_{2} = V′ ∪ T ∪ {A}.

Тогда G_{2} = (V_{2}, T, P_{2}, S′),

где P_{2} = {φ′ → ψ′, если φ → ψ ∈ P, φ ≠ ∅,

1.2. Языки и грамматики непосредственных составляющих 9

φ′ ∪ ψ′ получаются из φ и ψ в силу соответствия V′ ↔ V }

∪ {A → ψ′, если φ → ψ ∈ P;

ψ′ получается из ψ как выше } ∪ {α′ → αA|α′ ∈ V′} ∪ {α′ → Aα′|α′ ∈ V′} ∪ {a′ → a|a ∈ T }. Ясно, что каждому выводу S ⇒^{∗} x в G можно поставить

в соответствие эквивалентный (т.е. заканчивающийся той же терминальной цепочкой) вывод в G_{2}. Для этого в первом выводе ставим всюду штрихи, в нужных местах помещаем символ A, затем все штрихи снимаем, применяя соответствующие правила из P_{2}. Таким образом, L(G_{1}) ⊆ L(G_{2}). Пусть существует вывод S′ ⇒^{∗} x в G_{2}. Сотрём все штрихи. Исключим выводы вида a → a (получившиеся из a′ → a) и α → αA, α → Aα (получившиеся в результате применения правил α′ → α′A и α′ → Aα′). Получаем эквивалентный вывод в G_{1}, т.е. L(G_{1}) = L(G_{2}). Ч.т.д.

1.2. Языки и грамматики непосредственных составляющих

Следующее ограничение приводит к возникновению семейства формальных языков, называемых языками непосредственных составляющих.

\underline{Определение 1.2.1.} Грамматика G = (V, T, P, S) называется грамматикой непосредственных составляющих (НСграмматикой), если каждое правило имеет вид

φAψ → φωψ

где φ, ψ ∈ V^{∗}, A ∈ V − T, ω ∈ V^{∗} − {∅}.

Иногда условие φ, ψ ∈ V^{∗} заменяется условием

φ, ψ ∈ (V − T)^{∗}.

Легко показать, что это ограничение не меняет класса языков, порождаемых НС-грамматиками.

\underline{Определение 1.2.2.} Длинной некоторой цепочки χ будем называть число символов в ней и обозначать эту величину |χ|. Грамматика G называется неукорачивающей, если в каждом её правиле длина левой части не больше длины правой.

Покажем, что для любой неукорачивающей грамматики G = (V, T, P, S) существует эквивалентная НС-грамматика.

Эта грамматика строится следующим способом. Для каждого правила φ → ψ, φ = α_{1}, ... , α_{k}, слово ψ

разобъём на k штук непустых подслов ψ = ψ_{1}ψ_{2} ... ψ_{k}.

Введём k штук новых нетерминальных символов C_{1}, ... , C_{k}, своих для каждого правила.

Заменим правило φ → ψ набором правил α_{1}α_{2} ... α_{k} → C_{1}α_{2} ... α_{k} C_{1}α_{2} ... α_{k} → C_{1}C_{2}α_{3} ... α_{k} ... C_{1} ... C_{k−1}α_{k} → C_{1} ... C_{k−1}C_{k} C_{1}C_{2} ... C_{k} → ψ_{1}C_{2} ... C_{k} ψ_{1}C_{2} ... C_{k} → ψ_{1}ψ_{2}C_{3} ... C_{k} ψ_{1}ψ_{2} ... ψ_{k−1}C_{k} → ψ_{1}ψ_{2} ... ψ_{k−1}ψ_{k}. Эквивалентность так построенной НС-грамматики и ис-

ходной неукорачивающей грамматики G очевидна.

Таким образом класс неукорачивающих грамматик и класс грамматик непосредственных составляющих порождают одно и то же множество языков (НС-языков).

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

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

\underline{Определение 1.3.1.} Грамматика G = (V, T, P, S) называется контекстно-свободной (КС-грамматикой), если каждое её правило имеет вид

A → φ, где A ∈ V − T, φ ∈ V^{∗}. Термин �контекстно-свободная� в названии граммати-

ки отражает тот факт, что замена нетерминального символа цепочкой не зависит от контекста, т.е. соседних символов.

\underline{Определение 1.3.2.} Язык L называется контекстносвободным, если существует КС-грамматика G, такая, что

L = L(G). Следующая теорема (теорема 2) позволяет во многих

задачах ограничиваться рассмотрением только неукорачивающих КС-грамматик, т.е. таких, которые не содержат правил вида A → ∅. Доказательству теоремы предпошлём следующую лемму.

Лемма 1.3.2. Пусть вывод φ ⇒^{∗} ψ в КС-грамматике G состоит из применения множества правил

F = {P_{1}, P_{2}, ... , P_{k}} и φ = φ_{1}, φ_{2}, ... , φ_{l}. Тогда ψ = ψ_{1}ψ_{2} ... ψ_{l}, φ_{i} ⇒ ψ_{i}, i = 1, ... , l и наборы правил F_{i} для этих выводов удовлетворяют

условию ⋃ F_{i} = F. Доказательство. Пусть φ = φ^{0} ⇒ φ^{1} ⇒ ... ⇒ φ^{k} = ψ в

КС-грамматике G = (V, T, P, S).

Рассмотрим G′ = (V ∪ {/}, T ∪ {/}, P, S) и слово φ′ = φ_{1}|φ_{2}|φ_{3}| ... |φ_{l}. Применим те же правила F к φ′. Получим (легко доказывается индукцией по длине вы-

вода), что

φ′ ⇒^{∗} ψ = ψ_{1}|ψ_{2}|ψ_{3}| ... |ψ_{l}.

Вывод φ_{i} ⇒^{∗} ψ_{i} делается применением набора F_{i}, i = 1, ... , l. Значит F = ⋃ F_{i}. Ч.т.д. \underline{Определение 1.3.3.} Пусть G = (V, T, P, S) - КС-

грамматика.

Символ A ∈ V − T называется сводимым к x, x ∈ (V − T)^{∗}, если существует вывод A ⇒^{∗} x.

\underline{Теорема 1.2.4.} (О неукорачивающих грамматиках). Пусть G_{1} = (V, T, P_{1}, S) есть КС-грамматика и множество P_{2} состоит из всех правил вида A → ψ(ψ ≠ ∅) таких, что в P_{1} найдётся правило A → φ и либо ψ = φ, либо ψ получается из φ выбрасыванием некоторых символов, сводимых к ∅.

Тогда КС-грамматика G_{2} = (V, T, P_{2}, S) - неукорачивающая и порождает язык L_{2} = L(G_{2}) = L(G_{1}) − ∅.

Доказательство. Если A → ψ ∈ P_{2}, то A ⇒^{∗} ψ в G_{1} и следовательно, если S ⇒^{∗} x в G_{2}, то тотже вывод существует и в G_{1}, т.е. L_{1} ⊇ L_{2}.

Обозначим теперь G_{0} = (V, T, P_{1} ∪ P_{2}, S) ∪ L_{0} = L(G_{0}). Очевидно, что L_{0} ⊇ L_{1} ⊇ L_{2}. Пусть x ∈ L_{0}, x ∉ L_{2} и S ⇒ φ_{1} ⇒ φ_{2} ⇒ ... ⇒ φ_{k} = x - кратчайший вывод слова x в G_{0}. Возьмём первое применение правила вида B → ∅. Пусть это будет в переходе φ_{j} ⇒ φ_{j+1}.

Найдём в выводе ближайшее слева к этому переходу место появления B.

Допустим, что это произошло в переходе

φ_{i} ⇒ φ_{i+1}. Пусть далее

φ_{i} = χ_{1}Aχ_{4}, A → χ_{2}Bχ_{3} и φ_{j} = ψ_{1}ψ_{2}Bψ_{3}ψ_{4}.

Тогда

φ_{i+1} = χ_{1}χ_{2}Bχ_{3}χ_{4},

φ_{j+1} = ψ_{1}ψ_{2}ψ_{3}ψ_{4},

χ_{l} ⇒^{∗} ψ_{l}, l = 1, 2, 3, 4

(здесь мы пользуемся леммой 1.3.2).

Пусть последние выводы осуществляются, соответственно, за π_{l}(l = 1, 2, 3, 4) шагов.

Значит φ_{i} сводится к φ_{i+1} в выводе S ⇒^{∗} x за

1 + π_{l} + π_{2} + π_{3} + π_{4} + 1 шагов.

В P_{2} есть правило A → χ_{2}χ_{3} (если χ_{2}χ_{3} = ∅, то прослеживаем назад A и проводим аналогичные рассуждения).

Следовательно, φ_{i} можно свести к φ_{j+1} за 1 + π_{l} + π_{2} + π_{3} + π_{4} шагов. Это противоречит тому, что рассматриваемый вывод S ⇒^{∗} x кратчайший в G_{0}.

Поэтому L_{0} = L_{2} и L_{2} = L_{1}. Ч.т.д.

Следующая теорема позволяет исключать из грамматики те нетерминальные символы, из которых выводится лишь конечное число слов языка.

\underline{Теорема 1.3.5.} Для всякой КС-грамматики G_{1} = (V, T, P_{1}, S) существует эквивалентная ей грамматика G_{2} = (V, T, P_{2}, S), в которой V_{2} ⊂ V_{1} и из каждого A ∈ V_{2}−(T ∪S) выводимо бесконечное множество слов языка.

Доказательство. Грамматику G_{2} построим следующим образом. Если правило p = A → φ ∈ P_{1} и A, φ ∈ V_{2}^{∗}, то включаем p в P_{2}. Правила p = A → φ, для которых A ∈ V_{2} вообще выбрасываем. Если p = A → φ, A ∈ V_{2} и φ ∈ V_{2}^{∗}, то включаем в P_{2} все правила, которые получаются из P следующим образом: в цепочке φ = α_{1}α_{2} ... α_{l} заменяем те α_{i}, i = 1, 2, ... , l, которые не входят в V_{2}, на какие-либо слова из T′, выводимые из них.

Покажем, что L_{1} ⊇ L_{2}. Действительно, пусть S ⇒ φ_{1} ⇒ φ_{2} ⇒ ... ⇒ φ_{k} = x в G_{2}. Поскольку φ_{i} ∈ V_{2}^{∗}, i = 1, 2, ... , k и V_{2}^{∗} ⊂ V_{1}^{∗}, то либо φ_{i} ⇒ φ_{i+1} в G_{1}, либо

φ_{i} ⇒^{∗} φ_{i+1} в G_{1}.

Значит S ⇒^{∗} x в G_{1} и L_{1} ⊇ L_{2}.

Докажем обратное включение, L_{1} ⊆ L_{2}. Для этого рассмотрим грамматику G_{3} = (V_{1}, T, P_{1} ∪ P_{2}, S) и, соответственно, язык L_{3} = L(G_{3}).

Возьмём самый короткий вывод в G_{3} со следующими свойствами:

φ ⇒^{∗} x, φ ∈ V_{2}^{∗}, x ∈ T^{∗}

и x невыводимо из φ в G_{2}. Пусть этот вывод имеет вид: φ = φ_{0} ⇒ φ_{1} ⇒ ... ⇒ φ_{k} = x Тогда φ_{1} ∈ V_{2}^{∗}, иначе вывод φ_{1} ⇒^{∗} x был бы короче.

Следовательно первое правило, применённое в рассматриваемом выводе P_{1} = A → ψ(= ψ_{1}ψ_{2} ... ψ_{l}) и P_{1} ∈ P_{2}.

Тогда φ_{0} = φ′A′φ′′_{x} φ_{1} = φ′φ_{1}φ_{2} ... φ_{l}φ′′, x = x′x_{1}x_{2} ... x_{l}x′′, где

φ′ ⇒^{∗} x′, φ′′ ⇒^{∗} x′′, ψ_{i} ⇒^{∗} x_{i} в G_{3}.

Заменив в правиле A → ψ те ψ_{m}, которых нет в V_{2}^{∗} на x_{m} получаем правило вывода из P_{2} и более короткий вывод цепочки x в G_{3}.

Значит L_{3} = L_{2} и L_{1} = L_{2}. Ч.т.д.

1.4. Операции над КС-языками

В этом параграфе мы рассмотрим некоторые операции над КС-языками, которые сохраняют контекстносвободную структуру языков. Основной результат формулируется в теореме 1.4.7.

Определение 1.4.6. Сопоставм каждому символу a ∈ T алфавит T_{α} и множество L_{a} ⊆ T_{α}^{∗}.

Пусть L_{∅} = ∅ и L_{a_{1},a_{2},...,a_{r}} = L_{a_{1}}L_{a_{2}} ... L_{a_{r}} для каждой цепочки a_{1}a_{2} ... a_{r} ∈ T^{∗}.

Тогда отображение Re множества T^{∗} во множество всех подмножеств множества (⋃_{α} T_{α})^{∗} называется подстановкой.

Таким образом из каждого слова x = a_{1} ... a_{k} ∈ L в результате подстановок a_{i} → x_{i} ∈ L_{a_{i}} получаем слово

z = x_{1} ... x_{k}. Пусть L̃{z = x_{1} ... x_{k}| x_{i} ∈ L_{a_{i}}; a_{1} ... a_{k} ∈ L}. \underline{Теорема 1.4.7.} (о подстановке). Если языки L и L_{a_{k}} -

КС-языки, то и язык L̃ - КС-язык.

Доказательство. Пусть L и L_{a_{k}}, k = 1, 2, ... , n - КСязыки.

L = L(G), G = (V, T, P, S), L_{a_{k}} = L(G_{a_{k}}), G_{a_{k}} = (V_{a_{k}}, T_{a_{k}}, P_{a_{k}}, S_{a_{k}}) Сделаем замены нетерминальных символов так, чтобы (V_{a} − T_{a}) ∩ (V_{b} − T_{b}) = ∅ и V ∩ V_{a} = ∅. Построим грамматику G̃:

G̃ = (V ∪ (⋃_{u} V_{a_{k}}), ⋃_{k} T_{a_{k}}, P ∪ (⋃_{k} P_{a_{k}}) ∪ {a_{k} → S_{a_{k}}}, S)

Докажем, что язык L̃ совпадает с языком L(G̃).

1^{0}. Имеет место включение L̃ ⊆ L(G̃).

Действительно, если x ∈ L̃, то z выводится из некоторого слова x ∈ L, которое имеет вид: x = a_{1} ... a_{3} ⇒^{∗} z, но слово x выводится и в L(G̃), а тогда из x существует вывод

x ⇒^{∗} S_{a_{1}} ... S_{a_{3}} ⇒^{∗} z в грамматике G̃.

2^{0}. Имеет место включение L′(G̃) ⊆ L̃.

Пусть z ∈ (⋃_{k} T_{a_{k}})^{∗}. Так как L(G̃) - КС-язык и не существует в G̃ правил, таких что из символов ⋃ V_{a_{k}} получаются символы из V, то существует вывод z такой, что до некоторого шага применяются только правила из P, а затем они не применяются, т.е. вывод в котором сначала применяются правила из ???, затем правила a_{k} → S_{a_{k}} и только потом остальные. В таком случае в момент t после окончания применения правил из P мы имеем слово из T^{∗}, а так как алфавит не пересекается с V ∪ (V_{a}˘ T_{a}) ∩ (V_{b}˘ T b) = ∅, тоиз каждого символа a_{k} выводится слово в алфавите V_{a_{k}}. Включение доказано.

Включения, доказанные в пунктах 1^{0}, 2^{0} доказывают равенство L̃ = L(G̃).

Следствие. Рассмотрим произвольные КС-языки L_{1} и L_{2}. Поскольку множества {a, b}, {ab} и {a}^{∗} (a и b - некоторые символы) являются КС-языками, то, согласно теореме 1.4.7, множества L_{1} и L_{2} L_{1}L_{2} и L_{1}^{∗} тоже являются КСязыками. Символом L_{1}L_{2} обозначено множество цепочек вида xy, где x ∈ L_{1}, y ∈ L_{2}.

Для построения примеров, опровергающих те или иные утверждения, полезно иметь примеры языков, не являющихся контекстно-свободными. Следующая теорема даёт такой пример.

\underline{Теорема 1.4.8.} Язык L = \{a^{n}b^{n}c^{n}|n ⩾ 1\} не порождается никакой КС-грамматикой.

Доказательство. Пусть L = L(G), где G = (V, T, P, S) есть КС-грамматика. Можно считать, что из каждого нетерминального символа A ∈ V −T выводится бесконечное множество слов языка.

Для каждого n зафиксируем последнее правило P_{i_{n}}, применённое при выводе a^{n}b^{n}c^{n}. Какое-то из правил встретится бесконечное число раз. Пусть это правило P = A → x и |x| = m. Возьмём n, такое, что n > m и P применялось последним при выводе a^{n}b^{n}c^{n}.

Возможны такие случаи:

xAb^{k}c^{n} ⇒ a^{n}b^{n}c^{n}

и

a^{n}b^{k}Ax ⇒ a^{n}b^{n}c^{n}, k ⩾ 1, |x| = 2n − k − m.

Рассмотрим первый случай. Так как из A выводится бесконечно много слов, то существует вывод A ⇒^{∗} y, такой, что |y| > m. Тогда |x|−|y|+k = 2n−k−m > 2n, что невозможно.

Во втором случае рассуждаем аналогично. Ч.т.д.

Упражнение 4.1.9. Показать, что пересечение КСязыков не всегда является КС-языком.

2. Показать, что разность двух КС-языков не всегда является КС-языком.

3. Показать, что язык L = {a, b, c}^{∗} − {a^{n}b^{n}c^{n}|n ⩾ 1} есть КС-язык.

1.5. Неоднозначные грамматики и неоднозначные языки

Применительно к языкам программирования, порождающие грамматики доставляют средства для определения того, правильно или неправильно написана данная программа, т.е. является ли эта программа выводимой цепочкой в соответствующей грамматике. Более того, некоторые системы трансляции явно используют вывод данной цепочки для построения программы на другом языке. В связи с этим необходимо дать ответ на вопрос: когда можно считать два вывода одной и той же цепочки языка существенно различными? Для наших целей будет удобно отождествить все выводы некоторой цепочки в данной КС-грамматике, различающиеся лишь порядком применения правил. Среди всех таких выводов следующее определение выделяет вывод, который часто будет играть роль канонического вывода данной цепочки.

\underline{Определение 1.5.1.} Пусть G = (V, T, P, S) - есть КСграмматика.

1.5. Неоднозначные грамматики и неоднозначные языки 17

Вывод S ⇒ φ_{0} ⇒ φ_{1} ⇒ ... ⇒ φ_{k} является левосторонним, если для всех i = 0, 1, ... , k − 1 выполнено условие φ_{i} = u_{i}A_{i}ψ_{i}, φ_{i+1} = u_{i}χ_{i}ψ_{i}, A_{i} → χ_{i} ∈ P и u_{i} ∈ T^{∗}.

Аналогично определяется правосторонний вывод.

Только что сформулированное определение приводит к весьма важному в практических приложениях понятию неоднозначности КС-грамматики.

\underline{Определение 1.5.2.} КС-грамматика G называется неоднозначной, если в языке L(G) найдётся по меньше мере одна цепочка, порождаемая двумя различными левосторонними выводами (из аксиомы S).

КС-грамматика, не являющаяся неоднозначной, называется однозначной.

Замечание. Рассматривая вывод некоторой цепочки в данной КС-грамматике G, часто используют понятие дерева вывода. Дерево вывода строится по выводу

S ⇒ α_{1} ... α_{k_{1}} ⇒ β_{1} ... β_{k_{2}} ⇒ ... ⇒ a_{1} ... a_{k} следующим образом: от вершины дерева (вершины уровня 1), помеченной символом S, отходит k_{1} ветвей, заканчивающихся вершинами (вершинами второго уровня), помеченными слева направо символами α_{1}α_{2} ... α_{k}. Если в процессе вывода к некоторому нетерминальному символу α_{i} было применено правило α_{i} → γ_{1} ... γ_{m}, то α_{i} становится вершиной поддерева, от него отходит m ветвей, вершины, к которым они ведут, помечаются символами γ_{1} ... γ_{m}. Аналогичное построение проводится для вершин всех достигнутых уровней, помеченных нетерминальными символами. Вершина дерева называется максимальной, если от неё не отходит ветвей к вершинам более высокого уровня. Построение дерева вывода заканчивается, когда все максимальные вершины оказываются помеченными терминальными символами. Совокупность соответствующих меток (при осмотре максимальных вершин слева направо) образует терминальную цепочку a_{1} ... a_{l} (пример дерева вывода см. на рис. стр. ???40).

Используя понятие дерева вывода можно сказать, что грамматика G является неоднозначной, если некоторая цепочка w ∈ L(G) имеет два различных дерева вывода.

18 Глава 1. Определение формальных языков

\underline{Определение 1.5.3.} КС-язык L называется существенно неоднозначным, если каждая порождающая его КСграмматика является неоднозначной. В противном случае язык L называется однозначным.

Примеры.

Пример 1.1. В АЛГОЛ-60 существуют следующие правила вывода. < простая переменная> ::= < именователь переменной> < именователь переменной> ::= < именователь> < именователь массива> ::= < именователь> < именователь процедуры > ::= < именователь> < метка> ::= < именователь > < именователь переключателя> ::= < именователь>

Добавив к этим правилам правила S → ПП S → ИМ S → ИП S → М S → И Перекл им → a (начальные символы АЛГОЛ-60 заменены здесь начальными буквами составляющих их слов), получим неоднозначную грамматику, для слова a в которой существует пять различных выводов. Источником неоднозначности являются правила с одинаковыми правыми частями.

Пример 1.2. Условный оператор в АЛГОЛ-60 может иметь вид < условный оператор> ::= IF < логическое выражение> THEN <безусловный оператор>

либо вид < условный оператор> ::= IF < логическое выражение> < безусловный оператор> ::= ELSE < оператор>

С чем связано ограничение на то, что после THEN следует безусловный оператор?

Пусть после THEN может следовать оператор.

Тогда допустима конструкция

IF x > 0 THEN IF x > 5 THEN x := x − 5 ELSE x := +5; печать (x). При этом возможны две её трактовки:

1) IF x > 0 THEN < оператор> ELSE x := x + 5, где <оператор> есть IF x > 5 THEN x := x − 5

2) IF x > 0 THEN < оператор>, где <оператор> есть IF x > 5 THEN x := x − 5 ELSE x := +5;

При x = −1 первая трактовка приведёт к печати значения x = 4, а вторая - x = −1.

При x = 1 первая трактовка даёт результат x = 1, вторая - x = 6.

Отмеченная неоднозначность требует применения конструкции, используемой в АЛГОЛ-60.

Пример 1.3. Пусть G_{1} = (V_{1}, T, P, S_{1}) есть КС-граммати-ка, причём T = {a}, P_{1} = {S → SS, S → a^{k}b^{k}}, и G_{2} = (V_{2}, T, P, S_{2}) - другая КС-грамматика, с правилами вывода P_{2} = {S → a^{k}b^{k}S, S → a^{k}b^{k}}.

Тогда L(G_{1}) = L(G_{2}) = {(a^{k}b^{k})^{n}, n ⩾ 1} при этом грамматика G_{2} - однозначная, а G_{1} - неоднозначная.

Пример 1.4. Язык {a^{n}b^{n}c^{m}}∪{a^{n}b^{m}c^{m}}, m, n ⩽ 1 является существенно неоднозначным – любая порождающая его грамматика неоднозначна.

Объединение однозначных КС-языков не обязательно является однозначным КС-языком, однако, если эти языки не пересекаются, то их объединение является КС-языком.

\underline{Теорема 1.5.3.} Если однозначные КС-языки L_{1}, ... , L_{r} попарно не пересекаются, то язык L = ⋃_{i=1}^{r} L_{i} является однозначным.

Доказательство. Не ограничивая общности, можно считать, что r = 2.

Пусть G_{1} = (V_{1}, T, P, S_{1}), G_{2} = (V_{2}, T, P, S_{2}) и L_{i} = L(G_{i}), i = 1, 2 - однозначные КС-языки.

Пусть также (V_{1} − T) ∩ (V_{2} − T) = ∅ (этого всегда можно добиться переобозначением символов вспомогательных алфавитов).

Рассмотрим КС-грамматику G_{1} = (V_{1}, T, P, S_{1}), где

S ∉ V_{1} ∪ V_{2}, V = V_{1} ∪ V_{2} ∪ S и

P = P_{1} ∪ P_{2} ∪ {S → S_{1}, S → S_{2}}.

Очевидно, что

L(G) = L_{1} ∪ L_{2}.

Пусть

S ⇒ φ_{1} ⇒ ... ⇒ φ_{k} = x и

S ⇒ ψ_{1} ⇒ ... ⇒ ψ_{l} = x -

левосторонние выводы цепочки x ∈ L(G).

Так как P содержит лишь два правила вида S → χ, то φ_{i} ∈ {S_{1}, S_{2}} и ψ_{i} ∈ {S_{1}, S_{2}}. Предположим, что φ_{1} = ψ_{1} = S_{1}. Из соотношения

(V_{1} − T) ∩ (V_{2} − T) = ∅

следует, что в обоих выводах применяются лишь правила P_{1}, и, поскольку грамматика G_{1} является однозначной, данные выводы совпадают.

Аналогично доказывается, что выводы совпадают в случае φ_{i} = ψ_{i} = S_{2}. Предположим, что φ_{i} = S_{1} и ψ_{1} = S_{2}. Тогда первый вывод (т.е. S ⇒ φ_{1} ⇒ ... ⇒ φ_{k} = x является выводом в грамматике G_{1}, а второй – выводом в грамматике G_{2}. Значит x ∈ L_{1} ∩ L_{2}, что противоречит условию L_{1} ∩L_{2} = ∅. Таким образом, оба вывода слова x совпадают и в этом случае. Грамматика G - однозначная. Ч.т.д.

1.6. Магазинные автоматы

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

Дано сначала наглядное неформальное описание автомата с магазинной памятью (МП-автомата). Такой автомат (рис ?) можно представлять себе состоящим из

а) входной ленты, на которой в начальный момент времени находится входная цепочка (слово в некотором алфавите T),

б) читающего устройства, которое может находится в конечном числе состояний p, q, r, ...

в) ленты магазина (ленты магазинной памяти), на которой в начальный момент находится символ z_{0} некоторого конечного алфавита Z.

Функционирование автомата во времени происходит следующим образом (см. рис. 1.1.):

Либо 1) входная лента вдвигается на одну позицию в читающее устройство и в зависимости

от последнего символа z, записанного на ленте магазина, состояния читающего устройства p и считанного с входной ленты символа a

автомат записывает на магазинную ленту, начиная с той позиции, где находится символ z, некоторую цепочку ω в алфавите Z и переходит в новое состояние q.

Либо 2) считывания с входной ленты не проиходит, а в зависимости от последнего символа магазина и состояния автомат записывает в магазин цепочку ω и переходит в новое состояние q.

Отметим, что переходы обоих видов могут совершаться автоматом недетерминированно, т.е. ситуации на предшествующем такте может соответствовать конечное число пар вида (ω, q) - цепочки, которая будет напечатана к следующему моменту времени на ленте магазина, и состояния.

Если в итоге работы получается положение, когда с входной ленты считаны все символы входной цепочки и выполнено некоторое условие остановки автомата, то говорят, что автомат допустил входную цепочку.

В качестве условий остановки мы будем брать следующие:

а) автомат находится в одном из отмеченных (заранее) состояний (мы в этом случае говорим о F -автомате), б) магазин автомата пуст (N-автомат). Дадим теперь формальное определение автомата с ма-

газинной памятью.

\underline{Определение 1.6.1.} N-автоматом (автоматом типа N) называется упорядоченная шестёрка

N ↔ N = (Z, K, T, δ, z_{0}, q_{0}), где

Z = {A, B, C, ... , D} - конечное множество символов (алфавит магазина),

K = {p, q, ... , r} - конечное множество (множество состояний автомата),

T = {a, b, ... , c} - конечное множество (входной алфавит автомата),

δ - заданное отображение множества Z × K × (T ∪ ∅ на множество всех подмножеств множества Z^{∗} × K (функция переходов автомата)

z_{0} ∈ Z - начальный символ в магазине (маркер магазина)

q_{0} ∈ K - начальное состояние автомата. F -автоматом (автоматом типа F) называется упорядо-

ченная семёрка

F = (Z, K, T, δ, z_{0}, q_{0}, F), где Z, K, T, δ, z_{0}, q_{0} имеют тот же смысл что и для Nавтомата, а F ⊆ K - множество отмеченных (заключительных) состояний.

Введём некоторые обозначения. Пусть в данный момент ▷ в магазине автомата находится слово vz, ▷ автомат находится в состоянии p, ▷ на входе автомата находится слово ax. Набор (vz, p, ax) будем называть ситуацией, в которой

находится автомат.

Пусть функция перехода автомата δ такова, что δ(z, p, a) ∋ (ω, q).

Совокупность этих условий будем обозначать (vx, p, ax) ⊢ (vw, q, x). Если

(w_{1}, p_{1}, x_{1}) ⊢ (w_{2}, p_{2}, x_{2}) ⊢ ... ⊢ (w_{n}, p_{n}, x_{n}), то будем писать

(w_{1}, p_{1}, x_{1}) ⊢^{∗} (w_{n}, p_{n}, x_{n}).

Иногда значки ⊢ и ⊢^{∗} мы будем употреблять для обозначения фактически совершённых автоматом переходов.

\underline{Определение 1.6.2.} Множество слов L(N) будем называть множеством слов, допускаемых N-автоматом, если

L(N) = {x|x ∈ T^{∗}, (z_{0}, q_{o}, x) ⊢^{∗} (∅, q, ∅), q ∈ K}.

Множество

L(F) = {x|x ∈ T^{∗}, (z_{0}, q_{o}, x) ⊢^{∗} (ω, P, ∅), ω ∈ Z^{∗}}

называется множеством слов, допускаемых F -автоматом.

Цель двух нижеследующих теорем показать, что классы языков, допускаемых N- и F -автоматами, совпадают.

\underline{Теорема 1.6.3.} (F N-теорема). Для каждого автомата типа F существует автомат типа N, такой, что L(F) = L(N).

Доказательство. Пусть дан F -автомат F = (Z, K, T, δ, z_{0}, q_{0}, F). Возьмём такой N-автомат N = (Z ∪ z̄_{0}, K ∪ q̄_{o} ∪ q̄_{1}, T, δ̄, z̄_{0}, q̄_{0}),

где

q̄_{o}, q̄_{1} ∉ K, z̄_{0} ∉ Z и функция переходов определена следующими равенствами:

1) δ̄(z̄_{0}, q̄_{0}, ∅) = (z̄_{0}, z_{0}, q_{0}),

2) δ̄(z, q, a) = δ(z, q, a) для всех z ∈ Z, q ∈ K,

3) δ̄(z, f, ∅) = (z, q̄_{1}) для f ∈ F, z ∈ Z ∪ z̄_{o},

4) δ̄(z, q̄_{1}, ∅) = (∅, q̄_{1}) для z ∈ Z ∪ z̄ Пусть x ∈ L(F), т.е.

(z_{0}, q_{0}, x) ⊢^{∗} (w, f, ∅).

Тогда

(z̄_{0}, q̄_{0}, x) ⊢ (z̄_{0}, q_{0}, x) ⊢^{∗} (z̄_{0}w, f, ∅) ⊢ (z̄_{0}w, q̄_{1}, ∅) ⊢^{∗} (∅, q̄_{1}, ∅),

т.е. x ∈ L(N) и L(F) ⊆ L(N).

Пусть x ∈ L(N). В F -автомате первый переход однозначен (z̄_{0}, q̄_{0}, x) ⊢ (z̄_{0}, q_{0}, x). Далее рассуждаем так: z̄_{0} может быть стёрто (в автомате N) лишь в состоянии q̄_{1} (см. выше п. 4) описания функции δ̄. В состояние q̄_{1} можно перейти только из состояния f.

Таким образом,

(z̄_{0}z_{0}, q_{0}, x) ⊢^{∗} (z̄_{0}w, f, ∅) ⊢ (z̄_{0}w, q̄_{1}, ∅) ⊢^{∗} (∅, q̄_{1}, ∅).

Поскольку при переходе из состояния f в состояние q̄_{1} и при всех переходах, совершаемых в состоянии q̄_{1}, с входной ленты ничего не считывается (см. п.п. 3 и 4 опсания δ̄), то

(z_{0}, q_{0}, x) ⊢^{∗} (w, f, ∅),

т.е. x ∈ L(F) и L(N) ⊆ L(F). Ч.т.д.

\underline{Теорема 1.6.4.} (NF -теорема). Для каждого автомата типа N существует автомат типа F, такой, что L(N) = L(F).

Доказательство. Пусть дан автомат N = (Z, K, T, δ, z_{0}, f_{0}). Возьмём F -автомат F = (Z ∪ z̄_{0}, K ∪ f̄∪ q̄_{0}, T, δ̄, z̄_{0}, q̄_{0}, f),

где

f ∉ K, z̄_{0} ∉ Z, а функция переходов δ̄ определяется следующими равенствами:

1) δ̄(z̄_{0}, q̄_{0}, ∅) = (z̄_{0}, z_{0}, q_{0}),

2) δ̄(z, q, a) = δ(z, q, a) для всех z ∈ Z, q ∈ K, a ∈ T ∪ ∅,

3) δ̄(z̄_{0}, q, ∅) = (∅, f) для q ∈ K.

Пусть слово x ∈ L(N), т.е. (z_{0}, q_{0}, x_{0}) ⊢^{∗} (∅, q, ∅). Тогда

(z̄_{0}, q̄_{0}, x) ⊢ (z̄_{0}z_{0}, q_{0}, x) ⊢^{∗} (z̄_{0}, q_{0}, ∅) ⊢ (∅, f, ∅).

Значит x ∈ L(F) и L(N) ⊆ L(F).

Пусть теперь x ∈ L(F), т.е. (z̄_{0}, q̄_{0}, x) ⊢^{∗} (w, f, ∅). Проследим этот переход пэтапно в обратную сторону. В состояние f можно перейти, только используя правило п. 3 описания функции δ̄, т.е.

(z̄_{0}, q̄_{0}, x) ⊢^{∗} (wz̄_{0}, q, ∅) ⊢ (w, f, ∅), q ∈ K.

Так как символ z̄_{0} никогда в магазин не пишется, то должно выполняться равенство w = ∅. Значит

(z̄_{0}, q̄_{0}, x) ⊢^{∗} (z̄_{0}, q_{0}, ∅).

Первый переход в F -автомате однозначен (см. п. 1 описания функции δ̄).

Поэтому выполнены соотношения:

(z̄_{0}, q̄_{0}, x) ⊢ (z̄_{0}z_{0}, q̄_{0}, x) ⊢^{∗} (z̄_{0}, q, ∅).

Те же шаги(см. п.2 описания δ̄) для N-автомата дают

(z_{0}, q_{0}, x) ⊢^{∗} (∅, q, ∅),

т.е. x ∈ L(N) и L(F) ⊆ L(N) Ч.т.д. Сейчас мы приступаем к доказательству двух тео-

рем, содержащих основное в этом параграфе утверждение об эквивалентности классов языков, порождаемых КСграмматиками и допускаемых автоматами с магазинной памятью.

\underline{Теорема 1.6.5.} (GN-теорема). Для любой КСграмматики G существует N-автомат такой, что L(G) = L(N).

Доказательство. Пусть G = (V, T, P, S). Определим автомат N = (V, {q}, T, δ, q, S), где функция переходов δ удовлетворяет следующим равенствам:

1) δ(a, q, a) = (∅, q) для всех a ∈ T

2) δ(A, q, ∅) = {(φ^{R}, q)}, для всех правил A → φ ∈ P ^{1} Пусть слово x ∈ L(G). Возьмём левосторонний вывод x S ⇒ x_{1}A_{1}φ_{1} ⇒ x_{1}x_{2}A_{2}φ_{2} ⇒ ... ⇒ x_{1}x_{2} ... A_{n−1}φ_{n−1} ⇒ ⇒ x_{1}x_{2} ... x_{n} = x Тогда

1Символом φ^{R} обозначается цепочка, состоящая из тех же символов, что и цепочка φ, но написанных в обратном порядке.

(S, q, x) ⊢ (φ_{1}^{R}A_{1}x_{1}^{R}, q, x) ⊢^{∗} (φ_{1}^{R}A_{1}, q, x_{1}x_{2} ... x_{n}) ⊢

(φ_{2}^{R}A_{2}, q, x_{2} ... x_{n})  ⊢^{∗}  (φ_{2}^{R}A_{2}, q, x_{3} ... x_{n})  ⊢

(φ_{n−1}^{R}A_{n−1}, q, x_{n} ... x_{n}) ⊢ (x_{n}^{R}, q, x_{n}) ⊢^{∗} (∅, q, ∅),

т.е. x ∈ L(N) и L(G) ⊆ L(N)

Пусть теперь x ∈ L(N), т.е. (S, q, x) ⊢^{∗} (∅, q, ∅). Пусть x = a_{1}a_{2} ... a_{n−1}a_{n}. Обозначим через ψ_{1}, ψ_{2}, ... , ψ_{n} состояния магазина до, а через φ_{1}, φ_{2}, ... φ_{n} после того, как будет согласно определению функции перехода δ из (1.6.1) считано, собственно, a_{1}a_{2} ... a_{n−1}a_{n}. Используя эти обозначения, можно записать следующую последовательность переходов:

(S, q, x) ⊢^{∗} (ψ_{1}, q, a_{1}a_{2} ... a_{n}) ⊢ (φ_{1}, q, a_{2} ... a_{n}) ⊢^{∗}

(ψ_{2}, q, a_{2} ... a_{n}) ⊢ (φ_{2}, q, a_{3} ... a_{n}) ⊢^{∗} ... ⊢^{∗} (ψ_{n−1}, q,

a_{n−1} ... a_{n}) ⊢ (φ_{n}, q, a_{n}) ⊢^{∗} (ψ_{n}, q, a_{n}) ⊢ (φ_{n}, q, ∅) ⊢^{∗} (∅, q, ∅)

Это значит, что

1) ψ_{i} = φ_{i}a_{i} для i = 1, 2, ... , n и

2) S ⇒^{∗} ψ_{i}^{R}, φ_{i}^{R} ⇒ ψ_{i+1}^{R} для i = 1, 2, ... , n и φ_{n}^{R} ⇒^{∗} ∅

Объединяя всё, получаем вывод цепочки x в грамматике G

S ⇒^{∗} ψ_{i}^{R} = a_{1}φ_{1}^{R} ⇒^{∗} a_{1}ψ_{2}^{R} = a_{1}a_{2}φ_{2}^{R} ⇒^{∗}

⇒^{∗} a_{1} ... a_{n−1}ψ_{n}^{R} = a_{1} ... a_{n−1}φ_{n}^{R} ⇒^{∗} a_{1} ... a_{n} = x

Значит

x ∈ L(G) и L(G) = L(N), ч.т.д.

\underline{Теорема 1.6.6} . (NG-теорема). Для любого N-автомата N существует КС-грамматика G, порождающая язык, допускаемый автоматом N.

Доказательство. Пусть N = (Z, K, T, δ, z_{0}, q_{0})

Построим КС-грамматику G = (V, T, P, S) следующим образом.

Алфавит грамматики V = {A_{zpq} ∪ T ∪ S, p, q ∈ K, z ∈ Z. Смысл A_{zpq} следующий: слова x ∈ T^{∗}, выводимые из

нетерминального символа A_{zpq} в грамматике G (т.е. A_{zpq} ⇒^{∗} x), это те слова, которые переводят автомат N из состояния p в состояние q так, что при этом стирается записанный в магазин последний (до начала перехода) символ z, т.к. Эти цепочки обладают свойством

(z, p, x) ⊢^{∗} (∅, q, ∅).

Множество P правил вывода грамматики G построим из следующих правил:

1) S → A_{z_{0}p_{0}q_{i}} для всех p_{i} ∈ K,

2) A_{zpq} → a, если δ(z, p, a) ∋ (∅, q), т.е. (z, p, a) ⊢ (∅, q, ∅)

3) Если δ(z, p, a) ∋ (z_{1}z_{2} ... z_{k}, r), т.е.

(z, p, a) ⊢ (z_{1}z_{2} ... z_{k}, r, ∅), то для каждой последовательности состояний

r_{k}, r_{k−1}, ... , r_{0} такой, что r_{k} = r и

(z_{k}, r_{k}, y_{k}) ⊢^{∗} (∅, r_{k−1}, ∅),

(z_{k−1}, r_{k−1}, y_{k−1}) ⊢^{∗} (∅, r_{k−2}, ∅),

...

(z_{2}, r_{2}, y_{2}) ⊢^{∗} (∅, r_{1}, ∅),

(z_{1}, r_{1}, y_{1}) ⊢^{∗} (∅, r_{0}, ∅)

для подходящих цепочек y_{i} ∈ T^{∗}, i = 1, 2, ... , K в множество P добавляется правило

A_{zpr_{0}} → aA_{z_{k}rr_{k−1}}A_{z_{k−1}r_{k−1}r_{k−2}} ... A_{z_{2}r_{2}r_{1}}A_{z_{1}r_{1}r_{0}}

Можно включить в P �бесполезные� правила, т.е. выписать правила вида

A_{zpr_{0}} → aA_{z_{k}r_{k}r_{k−1}}A_{z_{k−1}r_{k−1}r_{k−2}} ... A_{z_{2}r_{2}r_{1}}A_{z_{1}r_{1}r_{0}} для каждой последовательности r_{k}, r_{k−1}, ... , r_{1}r_{0} из k + 1 состояний).

А) Докажем, что L(N) ⊆ L(G), т.е. что из условия

(z_{0}, q_{0}, x) ⊢^{∗} (∅, q, ∅)

следует, что существует вывод

S ⇒ A_{z_{0}q_{0}q} ⇒^{∗} x.

Первый шаг вывода * - это применение правила вида 1). Для того, чтобы доказать существование остальной ча-

сти вывода, докажем более общее утверждение:

если (z, p, x) ⊢^{∗} (∅, q, ∅), то

A_{zpq} ⇒^{∗} x

(для любых P и z, а не только для q_{0}, z_{0}).

Доказательство этого утверждения проведём индукцией по числу n тактов работы автомата.

Если n = 1, то x = a

(z, p, a) ⊢ (∅, q, ∅)

Но тогда A_{zpq} → a есть правило (типа 2) из P. Пусть наше утверждение доказано для всех случаев, когда число тактов работы автомата меньше n. Докажем его для случая, когда число тактов равно n.

Первый такт имеет видов

(z, p, ax′) ⊢ (z_{1} ... z_{k}, r, x′).

Зафиксируем моменты τ_{k}, τ_{k−1}, τ_{1}, когда будут исчезать из магазина последовательно символы z_{k}, z_{k−1}, ... , z_{1}. Пусть автомат при этом будет переходить в состояния

r_{k−1}, r_{k−2}, ... , r_{1}, r_{0} = q.

Положим r_{k} = r. Обозначим через y_{k}, y_{k−1}, ... , y_{1} те части слова x′, которые считываются автоматом, соответственно, к моменту τ, между моментами τ_{k} и τ_{k−1} и так далее, до интервала [τ_{2}, τ_{1}]. Используя эти обозначения можно записать равенство

x′ = y_{k}, y_{k−1}, ... , y_{2}, y_{1}, а также следующим образом описать ситуации в моменты времени

0, τ_{k}, τ_{k−1}, τ_{2}, τ_{1}:

в начале работы (z_{1}, ... , z_{k}, r, y_{k}, y_{k−1}, ... , y_{2}, y_{1}) в момент τ_{k} (z_{1}, ... , z_{k−1},r_{k−1},y_{k−1}, ... , y_{2}, y_{1}) в момент τ_{k−1} (z_{1}, ... , z_{k−2},r_{k−2},y_{k−2}, ... , y_{2}, y_{1})

в момент τ_{2}  (z_{1},  r_{1}, y_{1})
в момент τ_{1}  (∅,  r_{0}, ∅)

Таким образом, справедливы соотношения

(z, p, ay_{k} ... y_{1}) ⊢

(z_{1} ... z_{k}, r_{k}, y_{k} ... y_{1}) ⊢^{∗}

(z_{1} ... z_{k−1}, r_{k−1}, y_{k−1} ... y_{1}) ⊢^{∗}

(z_{1}, r1, y_{1}) ⊢^{∗}

(∅, r_{0}, ∅) Каждый из переходов от состояния r_{i} к состоянию

r_{i−1}, i = k, k − 1, ... , 1 эквивалентен такому

(z_{i}, r_{i}, y_{i}) ⊢^{∗} (∅, r_{i−1}, ∅)

Число тактов работы автомата в этом переходе меньше n, поэтому существует вывод в грамматике G

A_{z_{i}r_{i}r_{i−1}} ⇒^{∗} y_{i} (∗)

Переход автомата от состояния p в состояние r_{k} эквивалентен

(z, p, a) ⊢ (z_{1} ... z_{k}, r_{k}, ∅). Применяя правило вывода типа 3, получаем A_{zpr_{0}} → aA_{z_{k}r_{k}r_{k−1}}A_{z_{k−1}r_{k−1}r_{k−2}} ... A_{z_{2}r_{2}r_{1}}A_{z_{1}r_{1}r_{0}} Вместе с соотношениями (*) это показывает существо-

вание вывода

A_{zpq} ⇒^{∗} ay_{k}y_{k−1} ... y_{2}y_{1} = x

Пункт А) доказан. В) Докажем, что L(G) ⊆ L(N) Сначала докажем вспо-

могательное утверждение, обратное тому, которое было показано в пункте А):

если A_{zpq} ⇒^{∗} x, то (z, p, x) ⊢^{∗} (∅, q, ∅).

Доказательство этого утверждения проведём индукцией по длине n вывода x.

Если n = 1, то x = a и A_{zpq} → a. Следовательно, возможен переход

(z, p, a) ⊢ (∅, q, ∅). Пусть наше утверждение доказано для выводов с дли-

нами, меньше n. Докажем его для случая, когда вывод цепочки совершается за n шагов.

Первый шаг имеет вид A_{zpq} → aA_{z_{k}r_{k}r_{k−1}} ... A_{z_{2}r_{2}r_{1}}A_{z_{1}r_{1}q} Это соответствует разбиению x на подслова x = ax_{k}x_{k−1} ... x_{1}

и переходу автомата (z, p, a) ⊢ (z_{1}z_{2} ... z_{k}, r_{k}, ∅), причём существуют выводы A_{z_{i}r_{i}r_{i−1}} ⇒^{∗} x_{i}, i = 1, 2, ... , k длины меньшей n.

Но тогда существуют переходы автомата

(z_{i}, r_{i}, x_{i}) ⊢^{∗} (∅, r_{i−1}, ∅), i = 1, 2, ... , k.

Значит существует и нужный нам переход автомата

(z, p, x) = (z, p, ax_{k} ... x_{1}) ⊢ (z_{1} ... z_{k}, r_{k}, x_{k} ... x_{1}) ⊢^{∗}

(z_{1} ... z_{k−1}, r_{k−1}, x_{k−1} ... x_{1}) ⊢^{∗} ... ⊢^{∗} (z_{1}z_{2}, r_{2}, x_{2}x_{1}) ⊢^{∗}

(z_{1}, r_{1}, x_{1}) ⊢^{∗} (∅, q, ∅)

Пусть теперь x ∈ L(G) и S ⇒ φ_{1} ⇒ ... ⇒ φ_{k} = x его вывод.

Поскольку первый шаг этого вывода состоит в применении правила вида 1), то φ_{1} = A_{z_{0}q_{0}p}.

Так как существует вывод A_{z_{0}q_{0}p} ⇒^{∗} x, то существует (по доказанному выше) переход автомата

(z_{0}, q_{0}, x) ⊢^{∗} (∅, q, ∅), т.е. x ∈ L(N).

Теорема доказана полностью.

Глава 2.

Синтаксический анализ

2.1. Проблема принадлежности слова языку

При заданной порождающей грамматике G можно произвольно порождать слова языка L(G) и деревья их выводов, исходя из начального символа S. С другой стороны, например, трансляторы выполняют противоположную задачу:

1) по заданному слову x в грамматике G определить принадлежит ли это слово языку L(G).

2) восстановить вывод этого слова в случае положительного ответа на первый вопрос. Поставленную задачу будем называть задачей синтаксического анализа.

Формально, для решения задачи синтаксического анализа в случае КС-языка L, порождаемого КС-грамматикой G, можно использовать эквивалентность КС-языков и магазинных автоматов: по заданной грамматике G построить эквивалентный N-автомат, допускающий лишь слова, порождаемые грамматикой G. Неэффективность такого подхода очевидна – построенный по GN-теореме автомат будет недетерминированным, требующим возвратов в работе. Поэтому мы ограничимся лишь такими процессами решения задачи синтаксического анализа, которые осуществляются некоторым детерминированным устройством согласно заданной конечной системе чётких предписаний. Такое интуитивное понятие процесса решения формализуется в математической логике с помощью понятия алгоритма. Общего алгоритма решения поставленной задачи нет, но для языков, порождаемых неукорачивающими грамматикам, это сделать можно. Ниже также будет показано, что проблема принадлежности слова x КС-языку L(G) алгоритмически разрешима – иными словами, существует алгоритм, позволяющий определить принадлежит ли заданное произвольное слово заданному произвольному КС-языку.

\underline{Теорема 2.1.1} . Пусть задана произвольная неукорачивающая грамматика G(V, T, P, S), порождаемый ею язык L(G) и слово x длины l ⩾ 1 в алфавите T. Проблема принадлежности слова x языку L(G) алгоритмически разрешима.

Доказательство теоремы основано на возможности ограничиться просмотром всех выводов конечной длины, зависящей от длины слова x. Чтобы сделать это, нужно из всех выводов исключить цикл типа:

S → α → \underbrace{β → γ → α} → abc.

В противном случае для любого слова с возможностью цикла при выводе можно получить вывод сколь угодно длинный. Легко видеть, что для произвольного вывода в любой грамматике существует равносильный ему (т.е. имеющий те же первую и последнюю цепочки) бесповторный вывод, в котором никакая цепочка не встречается более одного раза.

Доказательство теоремы. Пусть алфавит V содержит m символов, множество P состоит из n правил подстановки. Рассмотрим произвольный вывод слова y ∈ T^{∗} длины l :

S → φ_{1} ⇒^{∗} ψ_{1} → φ_{2} ⇒^{∗} ψ_{2} → φ_{3} ⇒^{∗} ... → φ_{l} ⇒^{∗} ψ_{l} = y,

в котором φ_{i}ψ_{i} - цепочки длины i, а бесповторные выводы ⇒^{∗} не увеличивают длину цепочки.

Рассмотрим бесповторный вывод ⇒^{∗}; так как грамматика неукорачивающая, а |φ_{i}| = |ψ_{i}| по построению вывода, следовательно, в выводе применяются лишь правила вида φ → ψ, у которых |φ| = |ψ|.

Правила α → α_{1}, α, α_{1} ∈ V порождают не более (n + 1)^{i} различных цепочек, правила αβ → α_{1}β_{1}; α, β, α_{1}, β_{1} ∈ V, порождают не более (n+1)^{i−1} различных цепочек, поэтому длина вывода (количество подстановок в выводе) φ_{i} ⇒^{∗} ψ_{i} не превышает

(n + 1)^{i} + (n + 1)^{i−1} + ... + 1 < (n + 1)^{i+1}.

Стрелок без знака ∗, увеличивающих длину слова на единицу, будет не больше l − 1. Таким образом общая длина вывода слова y не больше

N = l − 1 + ∑_{i=1}^{l}(n + 1)^{i+1}.

Имея слово x длины l нужно просмотреть все бесповторные выводы, длина которых не больше N.

Если среди порождённых такими выводами слов есть слово x, то x ∈ L(G) и одновременно получен вывод этого слова. Нами доказано существование алгоритма решения задачи синтаксического анализа для неукорачивающей грамматики G.

\underline{Теорема 2.1.2} . Существует алгоритм, позволяющий узнать, принадлежит ли данное слово x произвольному данному КС-языку.

Доказательство. Пусть x ∈ T^{∗}, L = L(G), где G - некоторая КС-грамматика G = G(V, T, P, S). Если x = ∅, то алгоритм, решающий вопрос о принадлежности x ∈ L(G) состоит в следующем. Рассмотрим последовательность множеств w_{i}, определяемых реккурентно:

w_{1} = {A|A → ∅, A ∈ V }

⋮ w_{k+1} = {A|A → φ, φ ∈ w_{k}^{∗}} ∪ {w_{k}},

k = 1, 2, ... , n ⩽ m − 1, где m - число нетерминальных символов.

Нетрудно показать, что w_{k} ⊆ w_{k+1} для всех k и ∅ ∈ L(G) тогда и только тогда, когда S ∈ w_{n}.

Пусть x ≠ ∅. Тогда по грамматике G можно эффективно построить неукорачивающую КС-грамматику G′ = (V, T, P′, S) такую, что L(G′) = L(G) − ∅. Для грамматики G′ задача синтаксического анализа алгоритмически разрешима. Грамматику G′ легко построить, используя описанное множество w_{n}: каждое правило A → φ, φ ≠ ∅ исходной грамматики G порождает совокупность правил A → φ′ грамматики G′, таких что φ′ получено из φ удалением всевозможных вхождений символов из w_{n}. Доказательство теоремы закончено.

2.2. Анализ сверху-вниз и снизувверх

Существуют две разные стратегии синтаксического анализа, называемые анализом снизу-вверх (восходящий) и анализом сверху-вниз. Будем в дальнейшем рассматривать левосторонний анализ, закрепив общий порядок обработки символов в цепочке – слева направо.

Анализ сверху-вниз называется так по способу построения дерева вывода. На каждом этапе анализа в дереве создаются некоторые дуги (быть может, неправильные), при этом двигаются вниз по дереву от вершины, помеченной начальным символом, к слову из терминальных символов, расположенному снизу. Первым шагом является проверка того, нельзя ли анализируемую цепочку привести к виду правой части α_{1}α_{2} ... α_{n} некоторого правила S → α_{1}α_{2} ... α_{n}.

Это делается следующим образом: чтобы вывод был правильным в том случае, если α_{1} - терминальный символ, цепочка должна начинаться этим терминальным символом.

Если α_{1} - нетерминальный символ, ставится и проверяется подцель – посмотреть, нельзя ли начало некоторой цепочки привести к α_{1}. Если это оказывается возможным, то α_{2} проверяется таким же образом, затем α_{3} и т.д. Если не удастся найти ничего подходящего для некоторого α_{i}, то пробуют применить другое порождающее правило S → α′_{1}α′_{2} ... α′_{m}.

Подцели A проверяются также: пробуют применить порождающее правило A → α_{1}α_{2} ... α_{n}. Так постоянно генерируются и испытываются новые подцели. Если не находят новой подцели, то передаётся сообщение о неудаче на следующий, более высокий уровень, где проверяется другая альтернатива.

Пример 2.2.1. Рассмотрим для примера грамматику G = (V, T, P,<программа>) V = (<программа>,⊥, B, T, Π, I, +, ×, (,)} T = {I, +, ×, (,), ⊥}. P = {1. <программа>→ ⊥B⊥

2. B → T

3. B → B + T

4. T → Π

5. T → T × Π

6. Π → I

7. Π → (B) } Порождаемые грамматикой G слова можно рассматри-

вать как упрощённые арифметические выражения (соответственно раскрывается смысл нетерминальных символов: B - выражение, T - терм, П – первичное выражение, I - идентификатор).

Рассмотрим слово ⊥I + I × I⊥. Из начального символа <программа> можно вывести лишь ⊥B⊥. Теперь можно было бы поробовать применить правило B → T, появляется подцель – получить из T символ I, что достижимо последовательностью правил T → Π, Π → I, но при этом никак невозможно получить ⊥I+, даже использовав вместо T → Π правило T → T × Π. Следовательно, нужно использовать другое правило вместо B → T, заменим его правилом B → B + T. Продолжая дальше получим дерево вывода слова ⊥I + I × I⊥:

[figure: <программа>; ⊥; B; ⊥; B; +; T; T; T; ×; П; П; П; I; I; I]

При анализе снизу-вверх, наоборот, в цепочке ищут подцепочки, являющиеся правыми частями порождающих правил. Они заменяются соответствующей левой частью правила. Например, для слова ⊥I + I × I⊥ из описанной выше грамматики G, получим при левостороннем анализе снизу-вверх следующую последовательность восстановления дерева вывода:

П ⊥ I1.  T П ⊥ I2.  B T П ⊥ I3.  B T П П ⊥ I + I 4.  B T T П П ⊥ I + I 5.

[figure: B; T; T; П; П; П; ⊥; I; +; I; ×; I; 6.; B; T; T; T; П; П; П; ⊥; I; +; I; ×; I; 7.; B; B; T; T; T; П; П; П; ⊥; I; +; I; ×; I; 8.; <программа>; B; B; T; T; T; П; П; П; ⊥; I; +; I; ×; I; ⊥; 9.]

Как правило, описанный анализ снизу-вверх и сверхувниз, будет иногда делать шаги, которые впоследствии оказываются неверными, а иногда нужно совершать возврат для продолжения анализа. Хотя возможно строить анализаторы снизу-вверх, допускающие возврат, делается это редко. Существуют весьма изящные способы синтаксического анализа снизу-вверх, при которых никаких возвратов не требуется и цепочка, заменяемая левой частью соответствующего правила, определяется однозначно. Естественно, что на грамматику при этом накладываются ограничения, обеспечивающие её эффективное (без возвратов) выявление самой левой основы каждой цепочки. При этом мы получаем более узкие классы КС-грамматик, для которых задача синтаксического анализа эффективно разрешима. Среди таких классов выделяются своей широтой и практической применимостью простые грамматики с отношением предшествования и LR(k)-грамматики, описанию свойств которых отведены следующие два раздела.

2.3. Грамматики с отношением предшествования

Отношение предшествования устанавливается между двумя символами грамматики (как терминальными, так и нетерминальными), которые могут встретиться рядом в выводимой цепочке. Существуют следующие три соотношения:

⋖ (меньше)

≐ (равно)

⋗ (больше)

Определение 2.3.1.

Для заданной КС-грамматики G = (V, T, P, S) отношение предшествования между произвольными символами устанавливается следующим образом:

1. α ≐ β, если существует порождающее правило A → φαβψ среди правил P.

2. α ⋖ β, если существует правило A → φαA_{1}ψ и вывод A_{1} ⇒^{∗} βψ_{1} для некоторого ψ_{1} ∈ V^{∗}.

3. α⋗β, если а) существует правило A → φA_{1}βψ и вывод

A_{1} ⇒^{∗} φ_{1}α,

либо б) существует правило A → φA_{1}A_{2}ψ и выводы

A_{1} ⇒^{∗} φ_{1}α, A_{2} ⇒^{∗} βφ_{2} для некоторых ψ_{1}, ψ_{2}, φ_{1}, φ_{2} ∈ V^{∗}.

Между двумя символами грамматики может существовать от одного до трёх отношений предшествования или не существовать ни одного. Последнее имеет место, когда эти символы не встречаются рядом ни в одной из цепочек, выводимых данной грамматикой. Отношение равенства (≐) двух символов соответствует возможности их одновременного появления рядом друг с другом. Отношение α⋖β соответствует появлению сначала α, а позднее β в выводимой цепочке φαβψ. Аналогично истолковывается смысл отношения ⋗.

Пример 2.3.2. Рассмотрим грамматику G = (V, T, P, S), T = {�, �, a} V = T ∪ {S, h} P : S → H �, H → Ha H → �, H → HS Грамматика порождает строки символов a с открываю-

щими � и закрывающими � кавычками. Отношение предшествования удобно задавать в виде матрицы

S H � � a
S ⋗ ⋗ ⋗ ⋗ ⋗
H ≐ ⋖ ⋖ ≐ ≐
� ⋗ ⋗ ⋗ ⋗ ⋗
� ⋗ ⋗ ⋗ ⋗ ⋗
a ⋗ ⋗ ⋗ ⋗ ⋗

В такой матрице справа сверху вниз стоят левые силы отношения, а сверху – правые символы отношения.

Знак отношения между H и � стоит на пересечении строки H и столбца � (H⋖ �).

Рассмотрим строку �a�a�� и попытаемся восстановить её вывод. Расставим отношения предшествования между символами:

� ⋗ a ⋗ � ⋗ a ⋗ � ⋗ �

Начнём сворачивание нашей строки слева.

Так как � ⋗a, следовательно, символ a был получен позже символа � и символ � можно заменить левой частью правила H → �. Получим цепочку H ≐ a⋗ � ⋗a ⋗ � ⋗ �. H ≐ a, и a⋗ �, следовательно, сегмент Ha получен в результате применения какого-то правила вывода. Правую часть Ha имеет единственное правило H → Ha, поэтому нашу цепочку можно свернуть к виду

H ⋖ � ⋗ a ⋗ � ⋗ �

Теперь сегментом, который можно свернуть, является символ �, который появился �позже� и H и a, стоящих с ним рядом. Продолжая так дальше получим следующую последовательность сворачивания (подчёркиванием выделен сворачиваемый сегмент):

сворачиваемая цепочка используемое правило
\underline{�} ⋗ a �a��  H → �
H ≐ a �a��  H → Ha
H⋖ \underline{�} ⋗ a��  H → �
H⋖ \underline{H ≐ a} ⋗��  H → Ha
H⋖ \underline{H ≐ �} ⋗ �  S → H�
\underline{H ≐ S} ⋗ �  H → HS
H ≐ �  S → H�

Используя выписанные справа правила легко восстанавливаем вывод слова �a�a��.

Алгоритм установления отношений предшествования.

Заполнение матрицы отношений предшествования существенно упрощается, если использовать множества L(U) самых левых символов, которые можно получить из символа U, и множество R(U) самых правых символов.

Точнее, множества L(U) и R(U) определяются для произвольных U ∈ V соотношениями:

L(U) = {α|α ∈ V, ∃ (φ ∈ V^{∗}), такое, что U →^{∗} αφ}

R(U) = {α|α ∈ V, ∃ (φ ∈ V^{∗}), такое, что U →^{∗} φα}

Для каждого правила A → α_{1}α_{2} ... α_{m} грамматики необходимо для каждой пары символов α_{i}α_{i+1} проставить в матрице предшествования

1) отношение α_{i} ≐ α_{i+1}

2) отношение α_{i} ⋖ β, β ∈ L(α_{i+1})

3) отношение β ⋗ α_{i+1}, β ∈ R(α_{i})

4) отношение β_{1} ⋗ β_{2}, β_{1} ∈ R(α_{i}), β_{2} ∈ R(α_{i+1})

Пример 2.3.3. Для грамматики G = (V, T, P, S)

V = {S, H, ⊥, a} T = {⊥, a}

P: 1) S → H⊥ 2) H → ⊥

3) H → Ha 4) H → HS

Множества левых и правых символов следующие:

\begin{matrix}U & L(U) & R(U) \\ S & ⊥, H & ⊥ \\ H & ⊥, H & a, ⊥, S \end{matrix}

Первое правило грамматики даёт отношения: H ≐ ⊥ и β ⋗ ⊥, где β ∈ R(H), т.е. a ⋗ ⊥, ⊥ ⋗ ⊥, S ⋗ ⊥. Третье правило приводит к отношениям: H ≐ a, и β ⋗ a, где β ∈ R(H), т.е. a ⋗ a, ⊥ ⋗ a, S ⋗ a. Наконец, четвёртое правило грамматики индуцирует

отношения:

H ≐ S H ⋖ L(S), т.е. H ⋖ H, H ⋖ ⊥ R(H) ⋗ S, т.е. a ⋗ S, ⊥ ⋗ S, S ⋗ S, R(H)⋗L(S), т.е. a⋗⊥, ⊥⋗⊥, S ⋗⊥, a⋗H, ⊥⋗H, S ⋗H. Заполнив таким образом матрицу отношений предше-

ствования получим:

\begin{matrix}S & H & a & ⊥ \\ ⋗ & ⋗ & ⋗ & ⋗ \\ ≐ & ⋖ & ≐ & ⋖, ≐ \\ ⋗ & ⋗ & ⋗ & ⋗ \\ ⋗ & ⋗ & ⋗ & ⋗ \end{matrix}

Между символами H и ⊥ два отношения H ≐ ⊥ и H ⋖ ⊥, что является отражением двойственной роли символа ⊥, отмечающего как начало, так и конец строки. Наличие нескольких отношений предшествования для пары символов делает невозможным однозначное выделение сегмента сворачивания.

\underline{Определение 2.3.4.} Грамматика называется грамматикой с отношением предшествования (ОП-грамматикой), если меду любыми символами существует не более одного отношения предшествования.

\underline{Теорема 2.3.5} . Для любой КС-грамматики G можно построить эквивалентную ей грамматику с отношением предшествования.

Доказательство. Пусть G = (V, T, P, S) - КС-грамма-тика. Построим грамматику G′ = (V′, T, P′, S) с тем же множеством терминальных символов T и аксиомой S. Каждое правило грамматики G A → α_{1}α_{2} ... α_{l} ∈ P заменим следующей совокупностью правил грамматики G′, расширив нужным образом множество V:

а) A → α_{P_{1}} ... α_{P_{l}},

б) α_{P_{i}} → α_{i}, i = 1, 2, ... , l. α_{P_{1}} ... α_{P_{l}} - новые нетерминальные символы грамматики G′, т.е. каждый символ α_{i} в правой части правила дублируется новым нетерминальным символом α_{P_{i}}, причём если даже и встречаются символы α_{i} = α_{j}, то им ставятся в соответствие разные новые нетерминальные символы α_{P_{i}}, α_{P_{j}}.

Совершенно очевидно, что грамматики G и G′ эквивалентны. Докажем, что G′ - ОП-грамматика.

Рассмотрим любую пару стоящих рядом символов и покажем, что между ними отношение предшествования определяется однозначно. Обозначим эту пару αβ.

1^{0}. α ∈ V, β ∈ V. Но старые символы можно получить лишь после применения правил типа (б), а это случай 3-б определения отношения предшествования, поэтому α ⋗ β.

2^{0}. α ∈ V, β_{P} ∈ V′ − V, т.е. β = β_{P}. Это случай либо 3-а, либо 3-б определения отношения предшествования, поэтому α ⋗ β.

3^{0}. α ∈ V′ − V, т.е. α = α_{P_{l}}, β ∈ V. Знак ≐, очевидно, вообще не может появиться. Знак ⋖ может появиться лишь так:

A →^{∗} φα_{P_{i}}Bψ и B →^{∗} βz, поэтому α_{P_{i}} ⋖ β, при этом α_{P_{i}}

- не последний символ в последовательности α_{P_{1}} ... α_{P_{l}}, т.е. i < l(∗). Отношение ⋗ может появиться по определению лишь

следующим образом: A → φ_{1}Bxφ_{2} и B →^{∗} ψ_{1}α_{P_{i}}, а символ x мог либо совпадать с β, т.е. x = β, либо из x выводится

β справа: x →^{∗} βψ_{2}.

Из того, что A →^{∗} φ_{1}ψ_{1}α_{P_{i}}, получается, что α_{P_{i}} = α_{P_{l}}(∗∗), т.е. α_{P_{i}} - последний символ правила.

Условия (*) и (**) не могут выполняться одновременно, поэтому неоднозначности в отношениях α_{P_{i}} и β не возникает.

4^{0}. α, β ∈ V′ = V, т.е. и α и β новые нетерминальные символы, α = α_{P_{i}}, β = β_{q_{i}}.

Рассмотрим все возможные случаи отношения предшествования между α и β.

4.1. α_{P_{i}} ≐ β_{q_{i}}. Это возможно лишь при P = q, j = i = 1. 4.2. α_{P_{i}} ⋖ β_{q_{i}}. Это возможно лишь при j = 1, i < l_{p}. 4.3. α_{P_{i}} ⋗ β_{q_{j}}. Это возможно в двух случаях

i = l_{p}, j ⩾ 2, либо

i = l_{p}, j = 1

Условия, при которых определяются разные знаки отношений предшествования не пересекаются. Это указывает на однозначность отношений и в случае 4^{0}.

Таким образом доказано, что в грамматике G′ отношение предшествования определяется однозначно, т.е.

G′ - ОП-грамматика.

Вообще говоря, вовсе не обязательно следовать изложенному алгоритму построения грамматике G′.

G

\begin{matrix}S → H⊥ & S → H_{1}⊥, H_{1} → H_{1}⊥_{1} → ⊥ & S → H̄⊥, H̄ → H \\ H → ⊥ & H → ⊥ & H → ⊥ \\ H → HS & H → H_{2}a_{2}, H_{2} → H, a_{2} → a & H → Ha \\ H → Ha & H → H_{3}S_{3}, H_{3} → H, S_{3} → & H → ĤS, Ĥ → H \end{matrix}

Грамматика G′ по доказанной теореме является ОПграмматикой, эквивалентной G. Нетрудно убедиться, что и грамматика G′′ эквивалентна G и является ОПграмматикой. Однако, как в грамматике G′, так и в грамматике G′′ встречаются правила с одинаковыми правыми частями, что крайне неудобно при синтаксическом анализе – неизвестно, когда какое правило применять. Так при выделении сегмента H в грамматике G′′ его можно свернуть к виду H̄ и Ĥ, а в грамматике G′ неоднозначность ещё больше (H_{1}, H_{2}, H_{3}).

\underline{Определение 2.3.6} . КС-грамматику с отношением предшествования будем называть простой (КСП), если правые части всех её правил различны, т.е. никакая пара правил не имеет вида A → φ, B → φ, A ≠ B.

Опишем теперь более точно алгоритм левостороннего анализа в КСП-грамматике.

Будем называть сегментом цепочку α_{1}α_{2} ... α_{n}, входящую в цепочку φβ_{H}α_{1}α_{2} ... α_{n}β_{H}ψ, если имеют место отношения φβ_{H} ⋖ α_{1} ≐ α_{2} ≐ ... ≐ α_{n} ⋗ β_{k}ψ, α_{i}, β_{H}, β_{k} ∈ V. Алгоритм левостороннего анализа в КСП-грамматике состоит в последовательном нахождении самого левого сегмента σ анализируемой цепочки и замене его вхождения (т.е. сворачиванию) левой частью правила грамматики A → σ. Если в результате сворачивания мы придём к символу S, то анализируемое слово порождается грамматикой и мы восстановим его правосторонний вывод.

Если на некотором шаге, не достигнув S, алгоритм не сможет продолжать работу, то исходное слово не принадлежит языку.

\underline{Теорема 2.3.7} . Если в КСП-грамматике дан вывод A →^{∗} φ и ψ - самый левый сегмент φ, то существует правило

B → ψ и вывод A →^{∗} ψ′Bψ′′ → ψ′ψψ′′ = φ такой, что

последний вывод эквивалентен первоначальному.

Доказательство проведём индукцией по длине вывода

A →^{∗} φ.

1. Пусть длина вывода n = 1. Тогда A → φ и это и есть искомое правило.

2. Предположим, что теорема верна для всех k < n, n > 1.

3. Докажем теорему для длины вывода n.

Пусть вывод A →^{∗} φ имеет длину n. Разобъём φ на части следующим образом. Пусть на первом шаге вывода A →^{∗} φ получена цепочка α_{1} ... α_{k}, т.е. A → α_{1} ... α_{k}. Затем α_{i} →^{∗} φ_{i}. Тогда φ = φ_{1}φ_{2} ... φ_{k}. Выделим двигаясь от начала цепочки φ те φ_{i}, для которых α_{i} = φ_{i}, т.е. φ = α_{1} ... α_{m}Dφ_{m+2} ... φ_{k}, где D = α_{m+1} - нетерминальный символ, такой что D →^{∗} β_{1} ... β_{t}. Тогда φ = α_{1} ... α_{m}β_{1} ... β_{t}β_{t+1} ... β_{t_{k}}.

Покажем, что искомый сегмент ψ находится в цепочке β_{1} ... β_{t}. Рассмотрим отношение предшествования между α_{m} и β_{1} : α_{m} ⋖β_{1} с другой стороны β_{t} ⋗β_{t+1}, следовательно ψ является самым левым сегментом в цепочке β_{1} ... β_{t}, т.е.

β_{1} ... β_{t} = φ̃ и D →^{∗} φ̃ = ψ̃′ψψ̃′′, но вывод D →^{∗} φ̃ короче

n, следовательно, правило B → ψ существует по предложению индукции, но это же правило должно быть и для ψ в цепочке φ, следовательно вывод будет:

A → α_{1}α_{2} ... α_{m}Dα_{m+2} ... α_{k} →^{∗} α_{1} ... α_{m}Dφ_{m+2} ... φ_{k} →^{∗}

→^{∗} α_{1} ... α_{m}ψ̃′Bψ̃′′φ_{m+2} ... φ_{k} →

→ α_{1} ... α_{m}ψ̃′β_{1} ... β_{t}φ_{m+2} ... φ_{k} = φ,

что и требовалось доказать.

Таким образом в КСП-грамматике описанный алгоритм анализа, работающий по отношению предшествования, однозначно восстанавливает правосторонний вывод, При практической реализации алгоритма анализа символы анализируемой цепочки записывают в магазин до тех пор, пока между входящим символом a и последним символом магазина α_{i} имеет место отношение ⋖ или ≐, т.е. α_{i} ⋖ a, или α_{i} ≐ a. Если α_{i} ⋗ a, то в магазине ищем сегмент.

α_{j−1} ⋖ α_{j} ≐ ... ≐ α_{i−1} ≐ α_{i}.

Цепочка α_{j} ... α_{i} заменяется левой частью единственного правила A → α_{j} ... α_{i}.

Всякую ли грамматику можно преобразовать в эквивалентную КСП-грамматику? Из последней доказанной теоремы легко усмотреть, что грамматика КСП – однозначная (существует единственный правосторонний вывод, который мы и восстанавливали).

Таким образом, ответ на поставленный вопрос – отрицательный, вследствие алгоритмической неразрешимости проблемы распознавания однозначности языка.

2.4. Функции предшествования

В развитых языках программирования число терминальных и нетерминальных символов слишком велико, чтобы можно было хранить матрицу отношений предшествования в памяти ЭВМ в процесе трансляции. Пусть алфавит V состоит из m символов. Оказывается, что вместо m значений отношений предшествования можно ограничиться 2m числами – значениями функций предшествования f и g, подобранными так, чтобы отношения между числами

– значениями f(α) и g(β) давали отношение между α и β. Точнее, \underline{Определение 2.4.1} . Функции f и g, определён-

ные на символах множества V со значениями во множестве целых чисел называются функциями предшествования, если из отношения

α ≐ β следует f(α) = g(β)

α ⋖ β ⇒ f(α) < g(β)

α ⋗ β ⇒ f(α) > g(β)

Не для всякой ОП-грамматики существует функции предшествования. Это связано с транзитивностью значений функций предшествования и нетранзитивностью отношений предшествования. Пусть, например, отношения предшествования таковы, что A ⋖ B, B ⋗ B, B ≐ C, A ⋗ C, тогда f(A) < g(B) < f(B) = g(C) < f(A), полученное неравнство противоречиво и не может выполняться. Чтобы убедиться в возможности существования такой цепочки отношений предшествования, достаточно взглянуть на пример.

Пример 2.4.2.

S → AO� L(α) R(α)  S A O � a �
S →��  A �  �  S  ⋗
A →�  �  �  A ⋖ ⋖ ≐ ⋖ ⋖
O → a  aSA � a� O  ≐
O → aS  � ⋗ ⋗ ⋗ ⋗ ⋗ ≐
O → S a ≐ ⋖ ⋖ ⋗
�  ⋗

f(a) < g() < f() = g() < f(A).

Покажем, что существует алгоритм, позволяющий построить функции предшествования, либо выяснить, что их нет.

Возьмём 2n точек, если в алфавите V n символов.

\overbrace{….}^{n}

P P_{α}  Каждой точке из строк P и Q
…. ставится в соответствие
\underbrace{Q  Q_{β}}_{n} элемент из V.

Точки верхнего ряда будем обозначать P_{α}, P_{β}, ..., а точки нижнего ряда Q_{α}, Q_{β}, ...; α, β ∈ V.

1. Соединим Q_{β} с P_{α} дугой, направленной от Q_{β} к P_{α}, если α ≐ β, либо α ⋖ β.

Q_{β} ⟶ P_{α}

2. Соединим P_{α} с Q_{β} дугой, направленной от P_{α} к Q_{β}, если α ≐ β, либо α ⋗ β.

P_{α} ⟶ Q_{β}

3. Если между α и β отношения предшествования нет, то вершины P_{α} и Q_{β} не связаны.

Подсчитаем, во сколько различных вершин, включая P_{α} можно попасть, двигаясь из P_{α} по графу по направлению стрелок от вершины к вершине, обозначим это число f(α).

Подсчитаем, во сколько вершин, считая Q_{β}, можно попасть, двигаясь аналогично, исходя из Q_{β}, обозначим это число g(β). Докажем, что если в грамматике существуют функции отношения предшествования f^{0} и g^{0}, то определённые выше функции f и g также будут функциями отношений предшествования.

Предположим противное: функции f^{0} и g^{0} существуют, но f(α) и g(β) не согласуются с отношением предшествования. Выясним, где может появиться это несогласование.

1. Если α ≐ β, то f(α) = g(β), так как вершины P_{α} и Q_{β} соединены следующим образом:

P_{α} ⟷ Q_{β}

2. Если α⋖β, то f(α) ⩽ g(β), так как P_{α} и Q_{β} соединены дугой вида

P_{α} ⟵ Q_{β}

и мы можем попасть из вершины Q_{β} во все вершины, куда можно попасть, исходя из P_{α}.

Таким образом, единственный случай несоответствия может получиться, если α ⋖ β, а f(α) = g(β).

Это случай, если P_{α} и есть путь в Q_{β}:

P_{α_{1}}Q_{β_{1}}P_{α_{2}}Q_{β_{2}} ... Q_{β_{n−1}}P_{α_{n}}Q_{β_{n}}, α_{1} = α, β_{1} = β.

По построению графа имеем отношения:

α_{1}⋗ = β_{1} α_{2}⋗ = β_{2} ... α_{n}⋗ = β_{n}, так как из P_{α_{i}} пришли в Q_{β_{i}}

α_{2}⋖ = β_{2} ... α_{n}⋖ = β_{n−1}, т.к. из Q_{β_{i}} пришли в P_{α_{i+1}} Тогда для функций f^{0} и g^{0} имеем: f^{0}(α_{1}) ⩾ g^{0}(β_{1}) ... f^{0}(α_{n}) ⩾ g^{0}(β_{n}) f^{0}(α_{2}) ⩽ g^{0}(β_{1}) ... f^{0}(α_{n}) ⩽ g^{0}(β_{n−1})

или переписывая все неравенства в строку:

f^{0}(α_{1}) ⩾ g^{0}(β_{1}) ⩾ ... ⩾ f^{0}(α_{n}) ⩾ g^{0}(β_{n}), т.е.

f^{0}(α_{1}) ⩾ g^{0}(β_{n}) и так как α_{1} = α, β_{n} = β,

то f^{0}(α) ⩾ g^{0}(β), что противоречит условию α ⋖ β.

3. Случай α⋗β рассматривается совершенно аналогично случаю 2.

Таким образом, мы доказали, что функции f(α) и g(β) либо согласуются с отношением предшествования и являются функциями предшествования, либо функций предшествования не существует.

Для практического нахождения функций предшествования удобно пользоваться следующим алгоритмом:

1^{0}. f(α) := g(α) := 1 для всех α ∈ V.

2^{0}. Для всех α, β ∈ V проделать следующие операции:

если α ⋗ β и f(α) ⩽ g(β), то f(α) := g(β) + 1;

если α ⋖ β и f(α) ⩾ g(β), то g(β) := g(α) + 1;

α ≐ β min{f(α, g(β)} := max{f(α, g(β)}

3^{0}. Если значение какой-либо функции, полученное на очередном этапе согласования в пункте 2^{0} больше 2n, то функций предшествования не существует.

Указанный алгоритм аналогичен описанной процедуре поиска числа проходимых вершин и потому достигает нужного результата, либо сигнализирует об отсутствии функций предшествования (число пройденных вершин не может быть больше 2n).

При синтаксическом анализе с помощью отношения предшествования мы одновременно контролировали выводимость цепочки: если встречались два символа, стоящие рядом, между которыми нет отношения предшествования, то из S такое слово заведомо получить нельзя. Заменив отношения предшествования функциями предшествования, мы тем самым потеряли возможность синтаксического контроля, поскольку функции предшествования определены для любой пары символов, и ошибка выяснится лишь при попытке свернуть цепочку.

Замечание 2.4.3. Метод отношения предшествования применим и к грамматикам общего типа, правила которых имеют вид:

φ → ψ, φ, ψ ∈ V^{∗}, φ ≠ ∅.

Множества L(α) самых левых и R(α) самых правых символов, выводимых из символов α определяются совершенно аналогично случаю КС-грамматик:

L(α) = {β : αφ → βψ ∈ P, либо αφ → β_{1}ψ ∈ P и β ∈ L(β_{1})}

R(α) = {β : φα → ψβ ∈ P, либо

φα → ψβ_{1} ∈ P и β ∈ R(β_{1})},

здесь φ и ψ - цепочки, возможно пустые, в алфавите V. α, β, β_{1} ∈ V.

Отношение предшествования определяется следующим образом:

α ≐ β, если φ → ψ_{1}αβψ_{2} ∈ P α ⋖ β, если φ → ψ_{1}αβ_{1}ψ_{2} ∈ P и β ∈ L(β_{1}) α ⋗ β, если

1. φ → ψ_{1}α_{1}βψ_{2} ∈ P α ∈ R(α_{1})

2. φ → ψ_{1}α_{1}β_{1}ψ_{2} ∈ P α ∈ R(α_{1}), β ∈ L(β_{1}).

Пример 2.4.4. G = (V, T, P, S) T = {a, b} V = T ∪ {S, D, H, B, A}

Множество P правил: \begin{matrix}S → ASD & B → b \\ S → Aba & bD → bBa \\ aD → Ha & A → a \\ H → D \end{matrix}

Порождаемый язык есть {a^{n}b^{n}a^{n}|n ⩾ 1}. Матрица отношений предшествования для грамматики

G имеет вид:

L(α)  F (α)  S B A H D a b
A, H, D, a D, a S  ≐
b  b  B  ⋖ ⋖ ≐
a, H, D  a  A ≐ ≐ ⋖ ⋖ ⋖ ⋖ ⋖
D  D, a H  ⋖ ⋖ ≐
a  D  ⋗ ⋗ ⋗
H, D  a ⋗ ⋗ ⋗ ⋗ ⋗ ⋗ ⋗
b  b  ≐  ⋗ ⋗ ⋗ ⋖

Синтаксический анализ производится в точности как и ранее.

2.5. Детерминированные автоматы с магазинной памятью

Для генерации (порождения или допущения) правильных предложений (слов) языка имеются две конструкции: грамматики и автоматы. Грамматику можно использовать для анализа, если существует отношение предшествования. Пусть язык порождается (допускается) автоматом. Как в этом случае эффективно решается задача синтаксического анализа? Рассмотренные ранее автоматы с магазинной памятью были недетерминированными и могли зайти в тупик, что ещё не означает недопустимости слова автоматом.

Рассмотрим теперь некоторый специальный тип магазинных автоматов, называемых детерминированными. Говоря неформально, речь идёт о таких автоматах, в которых для каждой ситуации однозначно определяется следующая. Эти автоматы представляют практический интерес, поскольку обычно они отвергают или допускают цепочку быстрее, чем недетерминированные автоматы. Языки, допускаемые такими автоматами, легче поддаются грамматическому анализу.

\underline{Определение 2.5.1.} Магазинный автомат ДНА = {Z, K, T, δ, z_{0}, q_{0}, &}, где & - закон окончания работы, соответствующий окончанию работы F − или N− автомата, называется детерминированным, если для всех q ∈ K выполняются следующие условия:

либо 1) δ(z, q, ∅) = (z′, r)

однозначная функция, т.е. множество (δ, q, ∅)

состоит из одного элемента, и (δ, q, ∅) = ∅ для всех a ∈ T.

либо 2) δ(z, q, a) = (z′, r) - однозначная функция для всех a ∈ T

и (z, q, ∅) = ∅,

2.5. Детерминированные автоматы с магазинной памятью51

z′ ∈ Z^{∗}, r ∈ K. \underline{Определение 2.5.1} утверждает, что автомат, находясь в

определённом состоянии q и обозревая определённый символ z в магазинной памяти, либо всегда читает входной символ – и при этом, прочтя определённый символ, может перейти лишь в одну ситуацию, зависящую от этого символа (условие 2),- либо вообще может перейти лишь в одну ситуацию и не может читать никакого входного символа. В магазинной памяти детерминированного автомата всегда должна быть записана некоторая цепочка, чтобы был возможен следующий такт работы автомата.

Лемма 2.5.2. Для каждого детерминированного автомата ΔHA можно построить эквивалентный ему детерминированный автомат ΔHA′, такой, что символ ẑ_{0} магазина всегда находится в начале магазина до окончания работы автомата.

Доказательство. Действительно, каждому правилу δ(z_{0}, q_{0}, a) = (z_{1} ... z_{k}, r), либо δ(z_{0}, q_{0}, ∅) = (z_{1} ... z_{k}, r), автомата ДНА поставим в соответствие правила δ′(z_{0}, q_{0}, a) = (ẑ_{0}z_{1} ... z_{k}, r), либо δ′(z_{0}, q_{0}, ∅) = (ẑ_{0}z_{1} ... z_{k}, r). Дополним определение функции δ′ правилами

δ′(ẑ_{0}, q_{0}, ∅) = (∅, q) для всех q ∈ K. Для остальных ситуаций функция δ′ совпадает с функцией δ. Если ДНА F -автомат, то для допустимого им слова x имеем работу:

(z_{0}, q_{0}, x) ⊢ (z′, q, x′) ⊢^{∗} (z′′, q_{F} , ∅).

Соответствующая работа ДНА’-автомата будет:

(z_{0}, q_{0}, x) ⊢ (ẑ_{0}z′, q, x′) ⊢^{∗} (ẑ_{0}z′′, q_{F} , ∅).

следовательно, слово x допустимо и ДНА′-автоматом. Аналогично доказывается и обратное утверждение, т.е. F - автоматы ДНА и ДНА′ эквивалентны.

Если ДНА N-автомат, то для допустимого им слова имеем работу

(z_{0}, q_{0}, x) ⊢ (z′, q, x′) ⊢^{∗} (∅, r, ∅).

однозначно определяемая соответствующая работа автомата ДНА′

(z_{0}, q_{0}, x) ⊢ (ẑ_{0}z′, q, x′) ⊢^{∗} (ẑ_{0} ... ẑ_{0}, r, ∅) ⊢^{∗} (∅, r, ∅),

следовательно, слово x допускается и ДНА′-автоматом. Очевидно и обратное. Таким образом произвольные автоматы ДНА и ДНА′ эквивалентны.

В силу доказанной эквивалентности будем в дальнейшем рассматривать лишь детерминированные автоматы, у которых до окончания работы в магазине записана непустая цепочка.

\underline{Теорема 2.5.3} . Любой детерминированный автомат эквивалентен детерминированному автомату, совершающему только элементарные действия, а именно

1. δ(z, q, a) = (z, r) - читает один символ и переходит в новое состояние.

2. δ(z, q, ∅) = (∅, r) - стирает один символ.

3. δ(z, q, ∅) = (zz′, r), z′ ∈ Z - записывает один символ в магазин.

Доказательство. Построим по заданному детерминированному автомату ДНА = {Z, K, T, δ, z_{0}, q_{0}, &} элементарный детерминированный автомат (ДЭА-автомат).

ДЭА = {Z, K′, T, B′, z_{0}, q_{0}, &}.

Для этого каждое правило функционирования ДНА заменим строго определённой последовательностью правил ДЭ-автомата.

I. Пусть в состоянии q, читая символ x в магазине ДНА работал согласно правилу:

δ(z, q, ∅) = (z′, r), z′ = z_{1} ... z_{k}.

Тогда правила ДЭ-автомата будут:

δ′(z, q, ∅) = (z, q_{z_{1}...z_{k}r}),

δ′(z, q_{z_{1}...z_{k}r}, ∅) = (∅, q_{z_{1}...z_{k}r})

1. δ′(z_{−1}, q_{z_{1}...z_{k}r}, ∅) = (z_{−1}z_{1}, q_{z_{2}...z_{k}r}), ∀ z_{−1} ∈ Z

2. δ′(z_{1}, q_{z_{2}...z_{k}r}, ∅) = (z_{1}z_{2}, q_{z_{3}...z_{k}r})

⋮

k. δ(z_{k−1}, q_{z_{k}r}, ∅) = (z_{k−1}z_{k}, q_{r}) k+1. δ(z_{k}, q_{r}, ∅) = (z_{k}, r) q_{z_{i}z_{i+1}...z_{k}r} ∉ K, i = 1, 2, ... , k - новые введённые состоя-

ния автомата ДЭА.

Таким образом, работе

(z′′z, q, ∅) ⊢ (z′′z_{1} ... z_{k}, r, ∅) автомата ДНА соответствует единственно возможная последовательность работ ДЭ-автомата:

(z′′z, q, ∅) ⊢ (z′′z, q_{z_{1}...z_{k}r}, ∅) ⊢

⊢ (z′′, q_{z_{1}...z_{k}r}, ∅) ⊢ (z′′z_{1}, q_{z_{2}...z_{k}r}, ∅) ⊢^{∗}

⊢^{∗} (z′′z_{1} ... z_{k}, q_{r}, ∅) ⊢ (z′′z_{1} ... z_{k}, r, ∅)

и, наоборот, любой работе

(z, q, ∅) ⊢^{∗} (z′′, r, ∅)(q, r ∈ K)

(т.е. не являются новыми введёнными состояниями автомата ДЭА) соответствует в точности одна последовательность ситуаций автомата ДНА.

II. Пусть в состоянии q, читая символ z в магазине, ДНА работал согласно правилу:

δ(z, q, a) = (z′, r), z′ = z_{1} ... z_{k}, т.е. -

ДНА всегда читал входной символ.

Тогда правила ДЭА-автомата будут:

δ′(z, q, a) = (z, q_{z_{1}...z_{k}r}).

Остальные правила в точности повторяют правила, записанные в пункте I: правила 1, 2, ... , k, k + 1.

Эквивалентность автоматов ДНА и ДЭА вполне очевидна.

Вообще говоря детерминированные F и N автоматы не эквивалентны, так как детерминированный N-автомат не допускает язык, содержащий наряду со словом x ≠ ∅ слово xy(y ≠ ∅), т.е. допустимое детерминированным Nавтоматом слово x не может быть начальным словом другого допустимого слова.

Замечание 2.5.4. От подобного ограничения легко избавиться введением специального символа конца слова ω, не принадлежащего терминальным символам языка, добавив к правилам грамматики правило S_{0} → Sω, где S, ω ∉ V. Так как ω не может стоять нигде внутри слова, то никакое слово уже не может быть начальным словом другого слова.

Детерминированные F -автоматы свободны от такого недостатка. Автоматы, допускающие языки L_{ω} с символом конца слова, обозначим F_{ω} и N_{ω}.

\underline{Теорема DNF 2.5.5} . Для всякого детерминированного N-автомата существует эквивалентный ему F -автомат. Действительно, в этом случае, аналогично лемме 2.5.2., легко ввести символ z̃_{0}, стоящий перед z_{0} в магазине (т.е. магазин содержит символы - z̃_{0}z_{0} ..., а символ z_{0} всегда находится в магазине по соглашению 2.5.2). Когда N-автомат окончит работу, в магазине останется символ z̃_{0} и тогда применяется дополнительно введённое правило

z̃_{0}, p, ∅) ⊢ (∅, q_{F} , ∅), p ∈ K, q_{F} ∈ F.

Так построенный автомат будет детерминированным F - автоматом, эквивалентным исходному N-автомату.

Теорема о существовании детерминированного Nавтомата эквивалентного детерминированному F -автомату неверно по указанным выше соображениям, однако на множестве L_{ω} КС-языков эти автоматы эквивалентны.

\underline{Теорема DF_{ω}N_{ω} 2.5.6} . Для всякого детерминированного F_{ω}-автомата существует эквивалентный ему N_{ω}-автомат.

Сохранив все правила F_{ω}-автомата F_{ω} = {Z, K, T, δ, F, z_{0}, q_{0}} добавим переход в состояние стирания магазина (q̄) после чтения символа ω.

δ_{1} : (z, q, ω) ⊢ (z, q̄, ∅) и правила, обеспечивающие стирание содержимого магазина

δ_{2} : (z, q̄, ∅) ⊢ (∅, q̄, ∅)

Построенный N_{ω}-автомат

N_{ω} = {Z, K, T, δ′, z_{0}, q_{0}} будет детерминированным и эквивалентным F_{o}megaавтомату.

Обладают ли языки, допускаемые детерминированными автоматами какими-нибудь дополнительными свойствами, упрощающими их анализ? Оказывается, что языки, допускаемые ДНА – однозначные. Сейчас по заданному ДНА будет построена грамматика, порождающая язык L(ДНА) и доказана её однозначность.

\underline{Теорема 2.5.7} . Для любого детерминированного Nавтомата существует однозначная КС-грамматика G, такая, что L(N) = L(G).

Доказательство: В NG-теореме было уже доказано существование КС-грамматики G, такой, что L(N) = L(G). Нам фактически нужно сейчас доказать лишь однозначность построенной там КС-грамматики для случая детерминированного N-автомата.

Итак, пусть N = {Z, K, T, δ, F, z_{0}, q_{0}} - детерминированный N-автомат. Построим КС-грамматику G = (V, T, P, S), V = T ∪{A_{zpq}}∪{S}, где A_{zpq} - нетерминальный символ (z - символ магазинной памяти автомата, p, q ∈ K). Смысл этого нетерминального символа, как и раньше, заключается в

том, что A_{zpq} →^{∗} x, если (z, p, x) ⊢^{∗} (∅, q, ∅), т.е. автомат в состоянии p, имея в магазине символ z, прочитывает слово x и обнуляет магазин, то слово x должно выводиться из нетерминального символа A_{zpq}. Для этого множество P правил грамматики определим следующим образом:

P_{1}. S → A_{zpq} для всех p ∈ K.

P_{2}. A_{zpq} → a, если (z, p, a) ⊢ (∅, q, ∅), a ∈ T.

P_{3}. A_{zpq} → aA_{z_{k}r_{k}r_{k−1}} ... A_{z_{2}r_{2}r_{1}}A_{z_{1}r_{1}q}, если

(z, p, a) ⊢ (z_{1} ... z_{k}, r_{k}, ∅) и существует y_{k} ∈ T, такой что

(Z_{k}, r_{k}, y_{k}) ⊢^{∗} (∅, r_{k−1}, ∅)

y_{k−1} ∈ T (Z_{k−1}, r_{k−1}, y_{k−1}) ⊢^{∗} (∅, r_{k−2}, ∅)

… …

y_{1} ∈ T (Z_{1}, r_{1}, y_{1}) ⊢^{∗} (∅, q, ∅)

В частности

A_{zpq} → ∅, если (z, p, ∅) ⊢ (∅, q, ∅).

1. Пусть (Z_{0}, r_{0}, y_{0}) ⊢^{∗} (∅, q, ∅), x ∈ T^{∗}. Докажем, что

тогда S →^{∗} x.

Имеем S → A_{z_{0}p_{0}q_{0}}.

Докажем, что если (Z, p, x) ⊢^{∗} (∅, q, ∅), то A_{zpq} →^{∗} x и указанный вывод – единственно возможный. Приведём для этого индукцию по числу n тактов работы автомата.

1. n = 1, т.е. (z, p, a) ⊢ (∅, q, ∅), a ∈ T, z ∈ Z.

Тогда по пункту 2 построения множества P существует правило A_{zpq} → a. Рассматриваемый автомат – детерминированный, следовательно переход из ситуации (z, p, a) в ситуацию (∅, q, ∅) один и только один, поэтому и соответствующий ему вывод в грамматике – однозначно определён.

2. Пусть утверждение справедливо для любой работы автомата, содержащей менее n тактов.

3. Докажем справедливость утверждения для работы длины n.

Если n > 1, то это означает, что первый такт работы имеет вид:

(z, p, ax) ⊢ (z_{1} ... z_{k}, r_{k}, x′), где

ax′ = x ∈ T^{∗} - слово на входе автомата.

Тогда слово x′ = y_{k}y_{k−1} ... y_{1} состоит из таких символов

y_{i}, для которых (z_{i}, r_{i}, y_{i}) ⊢^{∗} (∅, r_{i−1}, ∅).

Следовательно, имеем цепочку (единственную, в силу детерминированности автомата)

(z, p, ax′) ⊢ (z_{1} ... z_{k}, r_{k}, y_{k} ... y_{1}) ⊢^{∗} (z_{1} ... z_{k−1}, r_{k−1},

y_{k−1}y_{k−2} ... y_{1}) ⊢^{∗} ... ⊢^{∗} (z_{1}, r_{1}, y_{1}) ⊢^{∗} (∅, q, ∅), и переход

(z_{i}, r_{i}, y_{i}) ⊢^{∗} (∅, r_{i−1}, ∅) занимает менее n − 1 тактов, поэтому существует единственный вывод

A_{a_{i}r_{i}r_{i−1}} →^{∗} y_{i}

соответственно, единственный вывод

A_{zpq} → aA_{z_{k}r_{k}r_{k−1}} ... A_{z_{1}r_{1}q} есть

A_{zpq} →^{∗} ay_{1}y_{k−1} ... y_{2}y_{1} = x.

2. Пусть S →^{∗} x. Тогда (z_{0}, p(?)_{0}, x) ⊢^{∗} (∅, q, ∅).

Первый шаг вывода непременно имеет вид

S → A_{z_{0}p_{0}q_{0}}

Надо доказать, что если A_{z_{0}p_{0}q_{0}} →^{∗} x, то существует единственная работа автомата такая, что

(z_{0}, q_{0}, z) ⊢^{∗} (∅, p, ∅).

Снова будем применять индукцию по длине n вывода.

1. n = 1, т.е. A_{zpq} → x, но тогда x = a ∈ T и (z, p, a) ⊢ (∅, q, ∅) единственно возможная работа автомата.

2. Предположим, что утверждение справедливо для всех выводов длины, меньше n.

3. Докажем справедливость утверждения для вывода длины n.

Пусть x = ax′.

Тогда первый шаг вывода имеет вид

A_{zpq} → aA_{z_{k}r_{k}r_{k−1}}A_{z_{k−1}r_{k−1}r_{k−2}} ... A_{z_{1}r_{1}q}

При этом в автомате существуют символы y_{k} ... y_{1} такие,

что y_{k} выводится из A_{z_{k}r_{k}r_{k−1}}, A_{z_{k}r_{k}r_{k−1}} →^{∗} y_{k}.

Но указанные выводы короче n, поэтому существует переход

(z_{k}, r_{k}, y_{k}) ⊢^{∗} (∅, r_{k−1}, ∅).

А тогда

(z, p, x) ⊢ (z_{1} ... z_{k}, r_{k}, x′) ⊢^{∗} (z_{1} ... z_{k−1}, r_{k−1}, y_{k−1} ... y_{1}) ⊢^{∗}

⊢^{∗} (z_{1}, r_{1}, y_{1}) ⊢^{∗} (∅, q, ∅).

Вследствие детерминированности автомата выписанная последовательность переходов – единственная.

3. Итак, доказано, что каждой работе автомата соответствует единственный вывод и наоборот. Установленное взаимно-однозначное соответствие работ автоматаи выводов в грамматике непосредственно приводит к однозначности построенной грамматики, так как автомат детерминированный (что неоднократно использовалось в пунктах 1 и 2 доказательства).

Замечание 2.5.3. Особенно простой получается однозначная грамматика, соответствующая элементарному детерминированному N-автомату. Действительно, в этом случае существуют три типа правил функционирования автомата.

1. (z, p, a) ⊢ (z, q, ∅)

2. (z, p, ∅) ⊢ (∅, q, ∅)

3. (z, p, ∅) ⊢ (zz′, q, ∅), z, z′ ∈ Z. и правила вывода имеют вид:

α. S → A_{z_{0}p_{0}q} для всех p ∈ K.

β. A_{zpq} → aA_{zpq}, если (z, p, a) ⊢ (z, q, ∅) ⊢^{∗} (∅, r, ∅)

γ. A_{zpq} → ∅, если (z, p, ∅) ⊢ (∅, q, ∅)

δ. A_{zpq} → A_{z′qs}A_{zsr}, если

(z, p, ∅) ⊢ (zz′, q, ∅) ⊢^{∗} (z, s, ∅) ⊢^{∗} (∅, r, ∅).

2.5.9. Интересно более подробно выяснить порядок восстановления дерева вывода по работе элементарного автомата, чтобы убедиться в его единственности. Дерево вывода восстанавливается не сразу. Действительно, в момент применения правила перехода

(z, p, a) ⊢ (z, q, ∅) то есть в момент появления вершин A_{zpq}, мы не можем определить неизвестные нам нетерминальные символы (отмеченные звёздочкой)

[figure: A_{zpq}; a; A_{zp∗}]

Будем фиксировать этапы работы автомата по правилам типов 1, 2, 3. 1, 3, 1,\underline{2}, 1, 1, 2 – соответствующая работа со словом x на входе цепочка переходов автомата. До тех пор, пока не встретилось правило типа 2, мы ничего не можем сказать о вершинах дерева. После применения правила 2 до ближайшего слева правила 3 дерево восстанавливается. Последнее правило 3, стоящее перед 2, превратится в правило 1, либо 2, следующее правило 2 восстанавливает дерево до ближайшего правила 3 и так далее.

В ОП-грамматике, двигаясь по слову, мы расставляли отношения символами и выделяли сегменты сворачивания. Аналогичная конструкция присутствует и в рассматриваемом случае.

2.5.10. Если внимательно проследить доказательство теоремы 2.5.7, то нетрудно заметить, что однозначность грамматики вытекает не столько из детерминированности автомата, сколько из единственности цепочки переходов при допущении каждого слова. Можно доказать, что язык тогда и только тогда однозначен, когда существует допускающий его автомат такой, что существует единственно возможная цепочка переходов при допущении каждого слова.

Пример. L = {xx^{R}}, x ∈ {a, b}^{∗}. Построим N-автомат, допускающий язык L_{1} = L − ∅. Автомат построим недетерминированный с двумя состояниями: в состоянии q_{w} автомат записывает в магазин читаемый им символ; в любой момент он может либо сохранить состояние q_{w}, либо перейти в состояние q_{er}, в котором символ магазина сравнивается с входным символом и стирается, если символы совпадают. Точнее.

N = {{a, b}, {q_{w}, q_{er}}, {a, b}, δ, z_{0}, q_{w}}

δ : δ1. (z_{0}, q_{w}, α) ⊢ (α, q_{w}, ∅)  α ∈ T
δ2. (α, q_{w}, β) ⊢ (αβ, q_{w}, ∅) α, β ∈ T
δ3. (α, q_{w}, α) ⊢ (∅, q_{er}, ∅) α ∈ T
δ4. (α, q_{er}, α) ⊢ (∅, q_{er}, ∅) α ∈ T

Следуя NG-теореме построим грамматику G.

G = (V, T, P, S)

V = T ∪ {S} ∪ {A_{zpq}}

P: S → A_{z_{0}q_{w}q_{w}} - непродуктивное правило
S → A_{z_{0}q_{w}q_{er}}
A_{z_{0}q_{w}q_{er}} → αA_{αq_{w}q_{er}}  - из правила δ 1
A_{αq_{w}q_{er}} → βA_{βq_{w}q_{er}}A_{αq_{er}q_{er}}  - из правила δ 2
A_{αq_{w}q_{er}} → α  - из правила δ 3
A_{αq_{er}q_{er}} → α  - из правила δ 4

Устраняя непродуктивные правила и переобозначая нетерминальнгые символы, получим:

S → aA

S → bB

A → bBA′

A → aAA′

B → aAB′

B → bBB′

A → a B → b A′ → a B′ → b

Легко увидеть, что полученная грамматика однозначна – следствие �однозначной� работы автомата по допущению каждого слова.

2.6. LR(k)-грамматики

LR(k)-грамматики – это наиболее общий вид грамматики для которых существует эффективный левосторонний анализ снизу-вверх, конструкцию которого можно получить механически из грамматики.

Грамматика является LR(k)-грамматикой в том случае, если правило сворачивания подцепочки однозначно определяется всей слева от неё расположенной частью цепочки и k справа расположенными терминальными символами.

В ОП-грамматике мы заглядываем вперёд на один символ, чтобы проставить отношение предшествования и выделить сворачиваемый сегмент. ДЛЯ ДНА этого не нужно. Допускаемый ДНА язык – это LR(0) язык. Язык, порождаемый КСП-грамматикой – LR(1)-язык.

Что же можно получить, заглядывая на k символов вперёд?

\underline{Определение 2.6.1.} Пусть в КС-грамматике имеется правосторонний вывод некоторой цепочки (не обязательно в терминальных символах) и пусть в этом выводе

S →^{∗} α_{1} ... α_{j}A_{p}a_{1} ... a_{k}b_{1} ... b_{m} → \underline{α_{1} ... α_{n}} \underline{\underline{a_{1} ... a_{k}}}

на последнем шаге применялась подстановка A_{p} → α_{j+1} ... α_{n}. Пусть дан вывод некоторой другой цепочки (тоже пра-

восторонний), имеющий вид

S →^{∗} α_{1} ... α_{j}A_{p}a_{1} ... a_{k}c_{1} ... c_{m} → \underline{α_{1} ... α_{n}} \underline{a_{1} ... a_{k}}

2.6. LR(k)-грамматики 61

и части α_{1} ... α_{n} совпадают, и совпадают следующие за ними k символов. Тогда на последнем шаге применялась та же подстановка, что и в первом случае. Такая грамматика называется LR(k)-грамматикой, порождаемый ею язык - LR(k)-языком.

Выполняя анализ слова с использованием магазина, левосторонний анализатор должен просматривать весь магазин (не только фиксированное число символов в нём) и следующие k символов слова, при этом правосторонний вывод восстанавливается однозначно. Фактически язык, эффективно анализируемый любым ранее рассмотренным способом, является LR(k)-языком для некоторого k. Таким образом, соответствие грамматики условиям LR(k) является так же наиболее общим тестом однозначности, который сейчас имеется.

Пример 2.5.2.

1. P: S → Ac T = {a, c, d}
S → Bd V_{N} = {A, B, S}
V = V_{N} ∪ T
A → Aa G_{1} = (V, T, P, S)
B → Ba
A → a  L(G_{1}) = {a^{n}d} ∪ {a^{n}c}n ⩾ 1
B → a.

G_{1} не является LR(k)-грамматикой ни для какого k = 1, 2, .... Действительно, чтобы восстановить вывод слова x, нужно обязательно знать, какой символ стоит в конце. С другой стороны, грамматика G_{2} с правилами

S → aA

A → aA

A → c

A → d

порождающая тот же язык, является LR(0)-грамматикой. Поэтому можно сказать, что {a^{n}d} ∪ {a^{n}c} - LR(0)-язык.

2. Грамматика G_{3} с правилами

1. S → SS

2. S → Ac

3. S → Bd

4. A → aA_{1} 5. A_{1} → aa

6. B → aB_{1}

7. B_{1} → aa

порождает язык L = {(a^{3}α)^{2n}}, где α есть либо c, либо d. G_{3} является LR(4)-грамматикой, возможность заглянуть на 4 символа вперёд однозначно определяет по значению α = c применение правила 2, а по значению α = d - правила 3.

3. Простая грамматика с отношением предшествования – LR(1)-грамматика. Заглядывая на один символ вперёд, и сравнивая его по предшествованию с символом магазина, однозначно определяем сегмент и правило сворачивания.

4. У LR(k)-грамматики ярко проявляется свойство �нессиметричности�:

язык {a^{n}b^{n}ω} ∪ {a^{n}b^{2n}cω} не порождается никакой LR(k)-грамматикой и LR(0)-грамматикой;

язык {ωb^{n}a^{n}} ∪ {ωcb^{2n}a^{n}} - LR(0)-язык.

Ниже будет доказано, что для всякой LR(k)-грамматики можно построить детерминированный автомат, допускающий тот же язык (в предположении, что в языке каждое слово кончается символом ω – конца слова). Это может показаться на первый взгляд удивительным, поскольку в общем случае существует бесконечное множество цепочек α_{1}α_{2} ... α_{n}, которые могут появиться в магазине; таким образом, существует бесконечное число цепочек, которые необходимо использовать для вынесения решения при анализе, в то время как автомат использует только последний элемент магазина, состояние и входной символ.

Всё же благодаря тому, что число порождающий правил конечно, на каждом шаге анализа существует только конечное число возможных действий, независимо от символов α_{1}α_{2} ... α_{n−1} магазина. Поэтому необходимо только классифицировать возможные цепочки в классы, называемые �состояниями� γ_{p}, и показать, что если грамматика является LR(k)-грамматикой, можно задать однозначное отображение (α_{i}, γ_{p}, a_{j}) ⊢ (α′, γ_{a}) Здесь мы, конечно, упростили процесс, чтобы лучше

разобраться в идее; символы α_{i} в магазине должны быть сами сложными множествами, чтобы сделать возможным определение однозначного отображения.

\underline{Теорема 2.6.3} . Для всякой LR(k)-грамматики G можно построить детерминированный автомат, допускающий язык L(G) (в предположении 2.5.4).

Доказательство.

1. Будем называть состоянием тройку (p, j, x), где p : A_{p} → α_{p_{1}} ... α_{p_{np}} - правило, x - слово длины k (если действительной длины не хва-

тает, то дополним символами ω).

1 ⩽ j ⩽ n_{p} - индекс символа в правой части правила p. Каждому p можно поставить в соответствие несколько

троек.

Пусть γ = {(p, j, x)} - некоторое множество состояний. Построим множество γ_{ψ} для слова ψ следующим образом. Пусть слово ψ возникает при некотором правостороннем выводе

S →^{∗} α_{1} ... α_{i}A_{p}xx′ → α_{1} ... α_{i}α_{p_{1}} ... α_{p_{n}}xx′ =

= ψα_{p_{j+1}} ... α_{p_{n}}xx′ ψ - это правая часть слова, включающая j символов от

цепочки, выведенной из A_{p}. Тогда состояние (p, j, x) включается в множество γ_{ψ}.

Хотя количество слов ψ бесконечно, количество различных множеств γ_{ψ} конечно, так же существует лишь конечное число правил с конечным числом букв. Будем теперь строить множество для слова ψα_{j+1}.

Если α_{j+1} не входит в α_{p_{1}} ... α_{p_{n}}, то p не входит в γ_{ψα_{j+1}}. Если же α_{j+1} входит в α_{p_{1}} ... α_{p_{n}}, то в γ_{ψα_{j+1}} входит

тройка (p, j + 1, x).

Далее процесс продолжается аналогично.

Возможна ситуация, когда α_{j+1} - это символ d_{1} из цепочки d_{1} ... d_{t}, полученной из нетерминального символа α_{j+2} при подстановке q.

В таком случае в γ_{ψα} включается (q, 0, y).

y - первые k символов из цепочки α_{j+3} ... α_{n_{p}}x. Это означает, что нужно свернуть по правилу q следующие ? символов, но прежде проверить, нет ли там другого состояния (r, 0, z). Каждой паре γ и p поставим в соответствие множество слов x, таких, что (p, n_{p}, x) ∈ γ и обозначим это множество H_{γ_{p}}

H_{γ_{p}} = {x : (p, n_{p}, x) ∈ γ}. Очевидно, что H_{γ_{p}} ∩ H_{γ_{q}} = ∅, если p ≠ q.

2. Строим автомат. Пусть дано слово a_{1} ... a_{n} = w. Сначала мы находимся в нулевой позиции отмеченной

точкой для каждого правила .a_{1} ... a_{n}, затем движемся по слову a_{1} ... a_{i}.a_{i+_{1}} ... a_{n}, в конце w - пустое слово.

Автомат D. Начальное состояние (p_{S}, 0, ∅). Z = {γ} ∪ V K = {(x)} ∪ {r_{px}}, (x) - слово длины k в терминальных

символах.

T = T q_{0} - начальное состояние, z_{0} = γ_{0} В начале работы (т.е. преобразования ситуации

(γ_{0}, q_{0}, w) в ситуацию (γ_{0}, (x), w′) автомата

(γ_{0}, q_{0}, w) ⊢^{∗} (γ_{0}, (x), w′)

считывается k символов из слова w. Затем начинается его �нормальное� функционирование. Рассмотрим среднее звено работы:

... ⊢^{∗} (γ_{0}α_{1}γ_{1}α_{2}γ_{2} ... α_{n}γ_{n}, (x), w′′) ⊢^{∗} ...

Автомат работает следующим образом. γ_{1} = γ_{α_{1}} - это множество γ_{ψ} от ψ = α_{1}, γ_{2} = γ_{α_{1}α_{2}} от

ψ = α_{1}, α_{2}, ... , γ_{n} = γ_{ψ} от ψ = α_{1} ... α_{n}.

Автомат совершает преобразования: а) если x ∉ H_{γ_{n}p}, то в магазин записывается символ из

x (левый) и γ_{ψx} и в x справа добавляется символ из w′′, а первый символ x исчезает (он уже перешёл в магазин).

б) если же x ∈ H_{γ_{n}p}, то это значит, что надо сворачивать, а это делается с помощью служебного состояния r_{px}.

(γ_{0}α_{1}γ_{1} ... α_{n}γ_{n}, (x), w′′) ⊢

(γ_{0}α_{1}γ_{1} ... α_{n}γ_{n}, r_{px}, w′′) ⊢ ...

автомат стирает нужные α, γ и затем пишет:

... ⊢ (γ_{0}α_{1}γ_{1} ... α_{i}γ_{i}A_{p}γ_{p}, (x), w′′)

и после этого всё делается снова.

В силу единственности правостороннего вывода в LR(k)-грамматике и детерминированности автомата эквивалентность языков L(G) и L(D) можно считать доказанной.

Заинтересованный читатель, руководствуясь описанной конструкцией детерминированного автомата, легко построит элементарный детерминированный автомат, допускающий все слова простой грамматики с отношением предшествования, где при выводе нужно заглядывать вперёд на один символ.

Для доказательства того, что язык допускаемый детерминированным автоматом есть LR(0)-язык, нам понадобится следующая лемма.

Пусть G_{N} - грамматика, построенная в теореме 2.5.7. (грамматика эквивалентная детерминированному автомату).

Лемма 2.6.4. Пусть A_{zpq} →^{∗} x и некоторое подслово слова ???. Тогда эквивалентны следующие утверждения:

а) в дереве вывода A_{zpq} →^{∗} x содержится поддерево вы-

вода A_{z′p′q′} →^{∗} x′;

б) при работе автомата (z, p, x) ⊢^{∗} (∅, q, ∅) осуществля-

ется подработа (z′, p′, x′) ⊢^{∗} (∅, q′, ∅).

Доказательство ведётся индукцией по длине n вывода A_{zpq} →^{∗} x, равной, как отмечалось выше, числу тактов при

работе автомата (z, p, x) ⊢^{∗} (∅, q, ∅).

Ясно, что детального анализа требуют лишь случаи, когда (при выводе в) из а)) поддерево вывода A_{z′p′q′} →^{∗} x′ не совпадает с деревом вывода A_{zpq} →^{∗} x и (при выводе а) из б)) подработа (z′, p′, x′) ⊢^{∗} (∅, q′, ∅) не совпадает со всей

работой (z, p, x) ⊢^{∗} (∅, q, ∅).

При n = 1 дерево вывода A_{zpq} → x не имеет отличных от него самого поддеревьев с нетерминальной вершиной, а работа автомата (z, p, x) ⊢ (∅, q, ∅) не индуцирует отличных от неё самой подработ вида (z′, p′, x′) ⊢ (∅, q′, ∅).

Пусть утверждение леммы справедливо для всех выводов A_{zpq} →^{∗} x, длина которых меньше n, докажем его для n.

Пусть верно а) Вывод A_{zpq} →^{∗} x имеет вид

(∗) A_{zpq} → aA_{z_{k}q_{k}q_{k−1}}A_{z_{k−1}q_{k−2}q_{k−2}}A_{zq_{1}q} ⇒^{∗}

⇒^{∗} x = ax_{k}x_{k−1} ... x_{1},

где каждое x_{i} получается при этом выводе из соответствующего A_{z_{i}q_{i}q_{i−1}} (считаем, что q = q_{0}). Поддерево вывода A_{z′p′q′} →^{∗} x′ является поддеревом одного из деревьев

A_{z_{i}q_{i}q_{i−1}} →^{∗} x_{i}, однако длина вывода A_{z_{i}q_{i}q_{i−1}} →^{∗} x_{i} меньше

n, следовательно, работа автомата (z_{i}, p_{i}, x_{i}) ⊢^{∗} (∅, q_{i−1}, ∅)

индуцирует подработу (z′, p′, x′) ⊢^{∗} (∅, q′, ∅). В силу (*) и детерминированности автомата первый такт его работы в конфигурации (z, p, x) имеет вид

(z, p, x) ⊢ (z_{1}z_{2} ... z_{k}, q_{k}, x_{k}x_{k−1} ... x_{2}x_{1}), а дальнейшая работа должна протекать по следующей схеме:

(z_{1}z_{2} ... z_{k−1}z_{k}, q_{k}, x_{k}x_{k−1} ... x_{2}x_{1}) ⊢^{∗}

(z_{1}z_{2} ... z_{k−1}, q_{k−1}, x_{k−1} ... x_{2}x_{1}) ⊢^{∗} ... ⊢^{∗}

(z_{1}z_{2}, q_{2}, x_{2}x_{1}) ⊢^{∗} (z_{1}, q_{1}, x_{1}) ⊢^{∗} (∅, q, ∅)

Следовательно, работа (z, p, x) ⊢^{∗} (∅, q, ∅) индуцирует подработу

(z_{1} ... z_{i}, q_{i}, x_{i} ... x_{1}) ⊢^{∗} (z_{1} ... z_{i−1}, q_{i−1}, x_{i−1} ... x_{1}),

эквивалентную ей подработу (z_{i}, p_{i}, x_{i}) ⊢ (∅, q_{i−1}, ∅) и, следовательно, и подработу (z′, p′, x′) ⊢ (∅, q′, ∅).

Пусть верно в). Первый шаг работы автомата имеет вид (z, p, x) ⊢ (z_{1} ... z_{k}, r_{3}, y), где x = ay, а схема последующей его работы такова (зафиксированы моменты, когда в магазине стираются символы z_{k}, z_{k−1}, ... , z_{1}):

(z_{1} ... z_{k−1}z_{k}, q_{k}, y_{k}) ⊢^{∗} (z_{1} ... z_{k−1}, q_{k−1}, y_{k−1}) ⊢^{∗} ... ⊢^{∗}

(z_{1}, q_{1}, y_{1}) ⊢^{∗} (∅, q_{0}, ∅)

Здесь считается r = q_{k}, q = q_{0}, y = y_{k}y_{k−1} ... y_{1}. Так как

подработа (z′, p′, x′) ⊢^{∗} (∅, q′, ∅) стирает в магазине только символ z′, то она является подработой одной из работ

(z_{1} ... z_{i}, q_{i}, y_{i}) ⊢^{∗} (z_{1} ... z_{i−1}, q_{i−1}, y_{i−1}).

\underline{Теорема 2.6.5} . Грамматика G_{N}, построенная в 2.5.7., есть LR(0)-грамматика.

Доказательство. Пусть

S →^{∗} α_{1}α_{2} ... α_{i}Ab_{1}b_{2} ... b_{k} → α_{1}α_{2} ... α_{m}b_{1}b_{2} ... b_{k} = φ

S →^{∗} α_{1}α_{2} ... α_{m}c_{1}c_{2} ... c_{l} = ψ

два правосторонних вывода, а

α_{1}α_{2} ... α_{m} →^{∗} u

какой-либо вывод слова, состоящего лишь из терминальных символов, из слова α_{1}α_{2} ... α_{m}. Этим выводом порождается вывод и некоторого слова x′ из слова α_{i+1} ... α_{m}, а, следовательно, и из символа A:

A → α_{i+1} ... α_{m} →^{∗} x′

Обозначим ub_{1} ... b_{k} = x_{1}, uc_{1}c_{2} ... c_{l} = x_{2}.

A есть некоторое A_{z′p′q′}. Теперь дважды применяем лемму 2.6.4. Для некоторого q_{1} дерево вывода

(S →)A_{z_{0}p_{0}q_{0}} →^{∗} x_{1}

содержит поддерево A_{z′p′q′} → x′. Следовательно, рабо-

та автомата (z_{0}, p_{0}, x_{1}) ⊢^{∗} (∅, q_{1}, ∅) индуцирует подработу

(z′, p′, x′) ⊢^{∗} (∅, q′, ∅). В силу детерминированности автомата и совпадения начала u слов x_{1} и x_{2}, содержащего

подслово x′, та же подработа (z′, p′, x′) ⊢^{∗} (∅, q′, ∅) осуществится и при чтении автоматом слова x_{2}, т.е. при работе

(z_{0}, p_{0}, x_{2}) ⊢^{∗} (∅, q_{2}, ∅). Следовательно, в дереве вывода

(S →)A_{z_{0}p_{0}q_{2}} →^{∗} α_{1} ... α_{i}α_{i+1} ... α_{m}c_{1} ... c_{l} →^{∗} vx′c_{1} ... c_{l} = x_{2}

содержится поддерево вывода

(A =)A_{z′p′q′} → α_{i+1} ... α_{m} →^{∗} x′

В силу того, что мы ограничились правосторонним выводом слова ψ, последний раз в этом выводе должно применяться правило

A → α_{i+1} ... α_{m} из чего следует, что грамматика G_{N} есть LR(0)-грам-матика.

Таким образом, показано (теорема 2.6.3), что для всякой LR(k)-грамматики, порождающей слова с маркером конца слова, можно построить детерминированный автомат, допускающий тот же язык. Например, КСП-грамматика есть LR(1)-грамматика, используя теорему 2.6.3 можно построить эффективный анализатор для КСП в виде детерминированного автомата. С другой стороны, теорема 2.5.5. утверждает, что всякий детерминированный Nавтомат допускает LR(0) язык. Таким образом, доказано, что LR(k)грамматики, k ⩾ 1, эквивалентны LR(0) грамматикам для языков с отметкой конца слова.