Конспект: КС-грамматики, магазинные автоматы и разбор

Понятия

КС-грамматика - терминалы, нетерминалы, начальный нетерминал и правила «нетерминал → строка символов». Вывод - цепочка замен от начального нетерминала до строки терминалов. Дерево разбора - какое правило применено к какому нетерминалу. Неоднозначная грамматика - у какой-то строки два разных дерева.

Магазинный автомат - конечное управление и стек; шаг выбирается по состоянию, символу строки и верхушке стека. Детерминированный КС-язык - тот, у которого есть детерминированный магазинный автомат.

Токен - элемент текста после нарезки: число, знак, скобка. Рекурсивный спуск - по функции на нетерминал. Левая рекурсия - правило, начинающееся со своего же нетерминала.

Нормальная форма Хомского - правила только A → B C и A → a. CYK - таблица «какие нетерминалы выводят кусок с позиции i длины d».

Лемма о накачке для КС-языков - длинная строка режется на u v x y z, и u vⁱ x yⁱ z остаются в языке. Иерархия Хомского - четыре вложенных класса языков и четыре модели.

Что унести

ГРАММАТИКА
S → aSb | ε     aⁿbⁿ: количества равны из-за формы правила, счётчика нет
S → (S)S | ε    правильные скобки: 1, 1, 2, 5 строк длины 0, 2, 4, 6
регулярный язык - частный случай:  переход из Q по a в R = правило Q → aR

E → E + E | E * E | число    2 + 3 * 4 → 14 и 20;   8 - 3 - 2 → 3 и 7
деревьев при 1…7 знаках:     1  2  5  14  42  132  429

приоритет уровнями:  E → E + T | T    T → T * F | F    F → число | ( E )
чем ниже уровень, тем сильнее связывает операция;
E → E - T растёт влево: (8 - 3) - 2

МАГАЗИННЫЙ АВТОМАТ
( состояние, символ, верхушка ) → ( новое состояние, замена верхушки )
в начале в стеке дно $;  снять - заменить пустой строкой;
положить B на A - заменить A на AB

aⁿbⁿ:  2 состояния, стек считает a;  40 букв a - стек 41, состояний 2
скобки ( [: 1 состояние, стек помнит порядок;
            ([)] отвергнута: пришла ), на верхушке [
два счётчика строку ([)] принимают - нужен порядок, а не количество

недетерминированные = КС-грамматики;   детерминированные - строго меньше
чётные палиндромы: середину надо угадать; конфигураций около n/2;
                   детерминированного автомата нет
палиндромы с отметкой середины - детерминированный есть

РЕКУРСИВНЫЙ СПУСК
E → T { (+ | -) T }       цикл while, накопление слева    (8 - 3) - 2 = 3
T → F { * F }
F → число | ( E ) | - F   выбор правила по очередному токену;
                          скобка - вызов E заново
P → F ^ P | F             рекурсия справа:  2 ^ 3 ^ 2 = 2 ^ 9

левая рекурсия  A → A x | y     →     A → y { x }
дословно в код:  глубина 50, прочитано токенов 0
правой рекурсией вместо цикла:  8 - 3 - 2 = 7,  ошибок разбора нет

три проверки:  атом начинается с числа или скобки;
               после выражения в скобках стоит );
               после всего выражения - конец текста
каждый токен читается один раз - время линейно

ОБЩИЙ РАЗБОР: CYK, грамматика в нормальной форме Хомского
T[i][1] = { A :  A → символ в позиции i }
T[i][d] = { A :  A → B C,  B в T[i][s],  C в T[i + s][d − s]
                 для какого-то разреза s }
ответ: начальный нетерминал в T[0][n];  O(g · n³) времени, O(n²) клеток

скобки, 4 двойных правила:    n          4      8      16       32
                              проверок   40    336    2720    21824
                              стек - 32 шага
приведение:  терминалы в длинных правилах → свои нетерминалы;
             длинные правила разрезать;  правила «A → B» убрать
             подстановкой;   выражения: 6 правил → 16
работает с любой грамматикой: неоднозначной, леворекурсивной

ГРАНИЦА
дерево выше числа нетерминалов → повтор A → u vⁱ x yⁱ z, v x y короткий
aᵖbᵖcᵖ: v x y не достаёт от a до c → меняются не более двух количеств
        → не КС-язык
перебор при p = 4:  295 разрезов, выжило 0;   для a⁴b⁴ - 175, выжило 7

                                   регулярные    КС
объединение, сцепление, повтор        да         да
пересечение, дополнение               да         нет
                                      aⁿbⁿcᵐ ∩ aᵐbⁿcⁿ = aⁿbⁿcⁿ
пересечение с регулярным              да         да

конечный автомат ⊂ магазинный автомат ⊂ машина с памятью длины входа
                 ⊂ машина с лентой
есть алгоритм:  принадлежит ли строка;  пуст ли язык;  конечен ли
алгоритма нет:  однозначна ли грамматика;  равны ли две грамматики;
                пусто ли пересечение

Ловушки джокера

Описал язык и забыл про смысл. Грамматика E → E op E порождает правильные строки и не говорит, что с чем складывать.

Искал неоднозначность тестами. Разные деревья часто дают одно значение; общего алгоритма проверки нет.

Проверял скобки нескольких видов счётчиками. Количество сходится, порядок нет.

Решил, что магазинный автомат всегда можно сделать детерминированным. Это свойство конечных автоматов, а не магазинных.

Перенёс леворекурсивное правило в код дословно. Переполнение стека на любом входе.

Заменил левую рекурсию правой. Сложение работает, вычитание даёт неверный ответ без ошибок.

Не проверил конец текста после разбора. 2 3 и (1 + 2)) приняты как правильные.

Запустил CYK на грамматике с длинными правилами. Один разрез не покрывает правило из трёх символов.

Взял общий алгоритм для языка программирования. Сто тысяч токенов в кубе - 10¹⁵.

Потребовал от грамматики согласования имён. «Объявлено до использования» - не КС-свойство; это работа следующего прохода.

Соединил два КС-условия через «и». Пересечение может выйти из класса.

Проверь себя

Чем дерево разбора отличается от вывода и почему два дерева - это дефект? Как приоритет и направление группировки записываются в грамматике и как они выглядят в коде? Почему недетерминизм у магазинных автоматов не бесплатен? Откуда в оценке CYK куб и зачем ему нормальная форма? Почему накачиваются два куска, а не один, и что из этого следует для aⁿbⁿcⁿ?

Понятия

Что унести

Ловушки джокера

Проверь себя

Комментарии

Оставить комментарий