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

Определение 12.1.1. Будем говорить, что два перехода МП-автомата и являются совместными, если

1. p₁ = p₂;

2. или ;

3. или .

Определение 12.1.2. МП-автомат называется детерминированным (deterministic), если он имеет ровно одно начальное состояние и все переходы этого автомата попарно несовместны.

Пример 12.1.3. МП-автомат M из примера 10.2.8 не является детерминированным, так как переходы и совместны.

Определение 12.1.4. Язык L над алфавитом называется детерминированным контекстно-свободным языком, если существует детерминированный МП-автомат, распознающий язык над алфавитом , где - дополнительный символ, не принадлежащий множеству . Символ называется маркером конца строки.

Пример 12.1.5. Рассмотрим алфавит . Язык - детерминированный контекстно-свободный язык, так как язык порождается детерминированным МП-автоматом (хотя язык L не порождается никаким детерминированным МП-автоматом).

Пример 12.1.6. Язык L, распознаваемый МП-автоматом M из примера 10.2.8, является детерминированным контекстно-свободным языком, так как язык порождается детерминированным МП-автоматом

где

Упражнение 12.1.7. Является ли детерминированным контекстно-свободный язык ?

12.2*. Свойства класса детерминированных языков

Теорема 12.2.1. Каждый автоматный язык является детерминированным контекстно-свободным языком.

Доказательство. Утверждение следует из теоремы 2.7.1.

Лемма 12.2.2. Каждый детерминированный МП-автомат эквивалентен некоторому детерминированному МП-автомату , где для каждого перехода выполняется неравенство .

Доказательство. Пусть дан детерминированный МП-автомат . Назовем избытком перехода

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

Шаг индукции. Пусть существует переход

с положительным избытком. Рассмотрим четыре случая.

Случай 1. . Обозначим первый символ слова x₀ через a₀. Преобразуем МП-автомат M в эквивалентный ему детерминированный МП-автомат с меньшей суммой избытков всех переходов. Для этого добавим новое состояние r и переход . Каждый переход вида заменим на переход . К полученному таким образом детерминированному МП-автомату применимо предположение индукции.

Случай 2. . Обозначим первый символ слова через C₀. Преобразуем МП-автомат M в эквивалентный ему детерминированный МП-автомат с меньшей суммой избытков всех переходов. Для этого добавим новое состояние r и переход . Каждый переход вида заменим на переход . К полученному таким образом детерминированному МП-автомату применимо предположение индукции.

Случай 3. Существует переход . Тогда переходы и совместны. Противоречие.

Случай 4. Существуют переход и переход , где и . Тогда переходы и совместны. Противоречие.

Лемма 12.2.3. Каждый детерминированный МП-автомат эквивалентен некоторому детерминированному МП-автомату , где каждый переход удовлетворяет условиям и .

Доказательство. Сначала применим лемму 12.2.2, затем преобразуем МП-автомат так, чтобы для каждого перехода выполнялось неравенство (см. пример 10.2.4), и в заключение заменим каждый переход вида на два последовательных перехода (см. пример 10.2.5).

Лемма 12.2.4. Пусть , и язык порождается некоторым детерминированным МП-автоматом. Тогда этот язык порождается также некоторым детерминированным МП-автоматом , где , ,

, и каждый переход

удовлетворяет условиям и .

Доказательство. Применив лемму 12.2.3, получим детерминированный МП-автомат . Построим искомый МП-автомат , положив , , , , , ,

Теорема 12.2.5. Язык является детерминированным контекстно-свободным языком тогда и только тогда, когда найдется такой детерминированный МП-автомат , что

Доказательство. Достаточность проверяется легко. Докажем необходимость. Рассмотрим МП-автомат

о котором говорится в лемме 12.2.4.

Для любых и введем обозначение

Очевидно, что для любых , и .

Построим искомый МП-автомат , положив

(Напоминаем, что через обозначается множество всех подмножеств множества Q₂.)

Индукцией по количеству тактов работы можно доказать, что

тогда и только тогда, когда

и

для каждого .

Теорема 12.2.6. Пусть L - детерминированный контекстно-свободный язык. Тогда язык L не является существенно неоднозначным.

Доказательство. Пусть дан детерминированный контекстно-свободный язык L. Рассмотрим МП-автомат

о котором говорится в лемме 12.2.4. Применив к этому МП-автомату конструкцию из доказательства теоремы 10.2.7, получим однозначную контекстно-свободную грамматику G, порождающую язык . Стирая в этой грамматике все вхождения символа , получим контекстно-свободную грамматику G', порождающую язык L.

Так как МП-автомат M не содержит переходов, ведущих из Q₂ в Q₁, а символ встречается только на переходах, ведущих из Q₁ в Q₂, то в каждом G' -выводе однозначно определяется правило, которому в G соответствует правило, содержащее . Поэтому существует естественное однозначное соответствие между деревьями вывода в грамматике G' и деревьями вывода в грамматике G (при этом кроны соответствующих друг другу деревьев различаются только символом ). Следовательно, грамматика G' тоже является однозначной.

Теорема 12.2.7. Дополнение каждого детерминированного контекстно-свободного языка является детерминированным контекстно-свободным языком.

Доказательство можно найти в [7, c. 110-116] или [2, c. 212-217].

Пример 12.2.8. Язык над алфавитом {a,b,c} не является детерминированным контекстно-свободным языком, так как его дополнение не является контекстно-свободным.

Теорема 12.2.9. Неверно, что для любых детерминированных контекстно-свободных языков L₁ и L₂ язык тоже является детерминированным контекстно-свободным языком.

Доказательство. Достаточно рассмотреть детерминированные контекстно-свободные языки L₁ и L₂ из доказательства теоремы 9.5.1.

Теорема 12.2.10. Неверно, что для любых детерминированных контекстно-свободных языков L₁ и L₂ язык тоже является детерминированным контекстно-свободным языком.

Доказательство. Утверждение следует из теорем 12.2.7 и 12.2.9 и закона де Моргана.

Упражнение 12.2.11. Является ли детерминированным контекстно-свободный язык ?

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

Нисходящий разбор

Определение 13.1.1. Процесс нахождения дерева вывода слова w в заданной контекстно-свободной грамматике называется синтаксическим разбором или синтаксическим анализом (parsing).

Определение 13.1.2. Протоколом левостороннего вывода в контекстно-свободной грамматике будем называть последовательность правил, примененных в этом выводе. Формально говоря, протоколом левостороннего вывода

является последовательность

где для каждого i < n, если и для некоторых , , , , то A_i+1 = B и .

Пример 13.1.3. Рассмотрим контекстно-свободную грамматику

Дереву вывода

соответствует левосторонний вывод

Протоколом этого вывода является последовательность

Лемма 13.1.4. Разным левосторонним выводам в одной и той же контекстно-свободной грамматике соответствуют разные протоколы.

Замечание 13.1.5. Протокол левостороннего вывода в контекстно-свободной грамматике является естественным описанием соответствующего дерева вывода в порядке префиксного обхода (preorder traversal). (При префиксном обходе упорядоченного дерева первым посещается корень этого дерева, затем выполняется префиксный обход первого непосредственного потомка корня, затем второго и т. д.)

Например, протокол левостороннего вывода из примера 13.1.3 задает процесс постепенного конструирования дерева вывода, изображенный ниже.

Определение 13.1.6. Левым разбором (left parse) слова w в контекстно-свободной грамматике G называется протокол любого левостороннего вывода слова w в грамматике G.

Пример 13.1.7. Левым разбором слова

aceaacecbecbb

в грамматике из примера 13.1.3 является последовательность

Определение 13.1.8. Процесс нахождения левого разбора слова w в заданной контекстно-свободной грамматике Gназывается нисходящим разбором (top-down parsing).

Определение 13.1.9. Вычислительным процессом МП-автомата M будем называть конечную последовательность его конфигураций, каждая из которых (кроме первой) получается из предыдущей одним тактом работы автомата M.

Пример 13.1.10. Рассмотрим МП-автомат

из примера 10.2.8. Последовательность

является вычислительным процессом этого МП-автомата.

Определение 13.1.11. Если в некотором вычислительном процессе МП-автомата первая конфигурация имеет вид , где и , а последняя конфигурация имеет вид , где , то будем говорить, что этот вычислительный процесс допускает слово w.

Пример 13.1.12. Вычислительный процесс из примера 13.1.10 допускает слово bab.

Замечание 13.1.13. МП-автомат M допускает слово тогда и только тогда, когда некоторый вычислительный процесс МП-автомата M допускает слово w.

Определение 13.1.14. Протоколом вычислительного процесса МП-Автомата будем называть последовательность переходов, примененных в этом вычислительном процессе. Формально говоря, протоколом вычислительного процесса

является последовательность переходов

где для каждого i между 1 и n слово x_i определяется равенством , а через и обозначены кратчайшие слова из , удовлетворяющие условиям

для некоторого слова .

Пример 13.1.15. Протоколом вычислительного процесса из примера 13.1.10 является последовательность

Определение 13.1.16. Для каждой контекстно-свободной грамматики обозначим через контекстно-свободную грамматику , где и - два различных новых символа, не принадлежащие множеству , и . Грамматику будем называть грамматикой с маркером конца строки. Терминальный алфавит грамматики (то есть множество ) будем обозначать через . Нетерминальный алфавит будем обозначать через .

Пример 13.1.17. Рассмотрим контекстно-свободную грамматику G с терминальным алфавитом , вспомогательным алфавитом N = {S,A,B,C} и правилами

Ей соответствует следующая грамматика с маркером конца строки:

Замечание 13.1.18. Очевидно, что .

Лемма 13.1.19. Если , где и , то .

Доказательство. Очевидно, что если , то слово не содержит символа .

Теперь докажем индукцией по длине вывода, что если , то . Пусть на последнем шаге в этом выводе применялось правило .

Если , то , что невозможно (очевидно, что если , то слово не содержит символа ).

Если , то рассмотрим два случая. При

равенство обеспечивается предположением индукцией. Случай

невозможен, так как предположение индукции дает .

Определение 13.1.20. Пусть даны контекстно-свободная грамматика и МП-автомат . Будем говорить, что МП-автомат M - нисходящий магазинный анализатор (или предсказывающий анализатор, top-down, left-to-right parser, predictive parser) для грамматики G, если и существует такой гомоморфизм , что для каждого вычислительного процесса (МП-автомата M), допускающего слово , образ протокола этого вычислительного процесса при гомоморфизме является протоколом некоторого левостороннего вывода слова w в грамматике . (При задании гомоморфизма rконечные множества и рассматриваются как два алфавита.)

Пример 13.1.21. Рассмотрим контекстно-свободную грамматику из примера 13.1.17. Язык распознается недетерминированным МП-автоматом , где

и

Легко убедиться, что МП-автомат M является нисходящим магазинным анализатором для грамматики G из примера 13.1.17.

Определение 13.1.22. Сентенциальной формой (sentential form) грамматики называется любое слово в алфавите , выводимое из начального символа S.

Пример 13.1.23. Слова S, aSeaceSbb, aceaacecbecbb являются сентенциальными формами грамматики из примера 13.1.3.

Определение 13.1.24. Пусть дана контекстно-свободная грамматика . Определим три функции , и , связанные с грамматикой G. Для краткости будем писать просто FIRST, FOLLOW и DIRECTOR.

Функция FIRST ставит в соответствие каждому слову множество тех терминальных символов, с которых начинаются слова, выводимые из , то есть

Функция FOLLOW ставит в соответствие каждому нетерминальному символу A множество тех терминальных символов, которые могут встречаться в сентенциальных формах непосредственно справа от A, то есть

Функция DIRECTOR ставит в соответствие каждому правилу множество терминальных символов, определяемое следующим образом: если , то

иначе

Пример 13.1.25. Рассмотрим контекстно-свободную грамматику из примера 13.1.3. Очевидно, что

Пример 13.1.26. Рассмотрим контекстно-свободную грамматику из примера 13.1.17. Очевидно, что

Пример 13.1.27. Пусть контекстно-свободная грамматика не содержит бесполезных символов. Пусть даны правило и символ . Тогда утверждение

равносильно тому, что найдутся такие , и , что

Теорема 13.1.28. Пусть дана контекстно-свободная грамматика . Пусть - соответствующая контекстно-свободная грамматика с маркером конца строки, приведенная в определении 13.1.16. Обозначим через M МП-автомат , где

, и

Тогда МП-автомат M является нисходящим магазинным анализатором для грамматики G.

Доказательство. Индукцией по количеству тактов можно доказать, что если , где , то . Следовательно, .

С другой стороны, докажем, что если в грамматике выводится и , где , , , , то .

Проведем доказательство индукцией по сумме длины слова bw и длины вывода . Случай |bw| = 1, образует базис индукции (очевидно, что ). Проверим теперь шаг индукции. Так как и , то . Если , где , то вывод имеет вид

где и в силу леммы 13.1.27 . Отсюда получаем, что , и остается применить предположение индукции для левосторонних выводов и . Если же , где , то, очевидно, a = b и . Если , то и в силу леммы 13.1.19 , но этот случай уже рассмотрен в базисе индукции. Пусть . Тогда w = b'w' для некоторых и . Обозначим u' = ub. Применяя предположение индукции для левосторонних выводов и , получаем . Согласно построению МП-автомата M имеем

Шаг индукции доказан. Теперь легко проверить, что выполняется .

Гомоморфизм задается соотношениями

Пример 13.1.29. Рассмотрим контекстно-свободную грамматику из примера 13.1.3. Грамматика с маркером конца строки имеет правила

Соответствующий нисходящий магазинный анализатор M, построенный в теореме 13.1.28, имеет приведенный ниже вид.

Определение 13.1.30. Контекстно-свободная грамматика принадлежит классу LL(1), если для любых двух правил и , где , множества и не пересекаются.

Замечание 13.1.31. Первая буква L в названии класса LL(1) означает, что входное слово читается слева направо (left-to-right). Вторая буква L означает, что строится левосторонний вывод (leftmost derivation). Число 1 указывает на то, что на каждом шаге для принятия решения используется один символ неразобранной части входного слова.

Пример 13.1.32. Грамматика из примера 13.1.3 принадлежит классу LL(1), а грамматика из примера 3.1.17 этому классу не принадлежит.

Теорема 13.1.33. МП-автомат M, построенный в теореме 13.1.28 по контекстно-свободной грамматике G, является детерминированным тогда и только тогда, когда грамматика G принадлежит классу LL(1).

Теорема 13.1.34. Грамматики из класса LL(1) порождают только детерминированные контекстно-свободные языки.

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

1. если , то для всех и ;

2. если , то для всех и ;

3. если , то .

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

1. если и , то ;

2. если , и , то

Замечание 13.1.37. Теоремы 13.1.35 и 13.1.36 дают алгоритм проверки принадлежности контекстно-свободной грамматики G классу LL(1). Можно предположить, что грамматика G не содержит бесполезных символов (их можно устранить).

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

Затем необходимо вычислить значения параллельно для всех вспомогательных символов A. Для этого постепенно пополняем множества (начав с пустых множеств), используя условия, приведенные в теореме 13.1.35.

В заключение вычислим значения для всех правил , следуя определению функции , и проверим условия из определения 13.1.30.

Теорема 13.1.38. Пусть даны контекстно-свободная грамматика и символ . Пусть

где множество P₀ не содержит правил с левой частью A и ни одно из слов не начинается с символа A. Тогда грамматика G эквивалентна контекстно-свободной грамматике , где A' - новый символ, не принадлежащий множеству , и

Пример 13.1.39. Если к контекстно-свободной грамматике из примера 13.1.17 два раза применить преобразование из теоремы 13.1.38 (для вспомогательного символа A и для вспомогательного символа B), то получим эквивалентную грамматику G' с правилами

После упрощения получаем грамматику G'' с правилами

Язык L(G'') распознается детерминированным МП-автоматом , где , , , и

Можно доказать, что МП-автомат M является нисходящим магазинным анализатором для грамматики

Пример 13.1.40. Пусть и . Рассмотрим контекстно-свободную грамматику G с правилами

Грамматика с маркером конца строки имеет правила

Соответствующий нисходящий магазинный анализатор M, построенный в теореме 13.1.28, имеет приведенный ниже вид.

Легко убедиться, что грамматика G принадлежит классу LL(1) и МП-автомат M является детерминированным.

Упражнение 13.1.41. Существует ли детерминированный нисходящий магазинный анализатор для грамматики

Упражнение 13.1.42. Принадлежит ли грамматика

классу LL(1)?

Упражнение 13.1.43. Принадлежит ли грамматика

классу LL(1)?

Восходящий разбор

Определение 13.2.1. Протоколом правостороннего вывода в контекстно-свободной грамматике будем называть обращенную последовательность правил, примененных в этом выводе. Формально говоря, протоколом правостороннего вывода

является последовательность

где для каждого i<n, если и для некоторых , , , , то A_n-i = B и .

Пример 13.2.2. Рассмотрим контекстно-свободную грамматику

и дерево вывода

из примера 13.1.3. Этому дереву вывода соответствует правосторонний вывод

Протоколом этого вывода является последовательность