Грамматика: правила, которые порождают язык, и дерево разбора

Если ты выведешь строку по грамматике, нарисуешь её дерево разбора и перепишешь неоднозначную грамматику выражений так, чтобы умножение связывало сильнее сложения, - листай до «Теперь сам».

Как думаешь, сколькими способами можно прочитать 8 - 3 - 2

Правило из школьной тетради: «выражение - это число или два выражения со знаком между ними». По нему 8 - 3 - 2 - выражение. Но каких два выражения соединяет второй минус?

Ответь себе до чтения: сколько у этой строки разборов по такому правилу и сколько разных ответов? Разборов два: (8 - 3) - 2 и 8 - (3 - 2), ответы 3 и 7. У строки с семью знаками разборов уже 429. Правило описывает, какие строки являются выражениями, и ничего не говорит о том, что они значат, - а компилятору нужно второе.

На что это похоже

Правила сборки матрёшки. «Матрёшка - это две половинки, между которыми ничего нет, или две половинки, между которыми матрёшка». Правило короткое и ссылается на само себя, а описывает матрёшки любой глубины. Собранную игрушку можно разобрать обратно и увидеть, какое правило применялось на каждом уровне.

У автомата из прошлой главы такого «внутри» нет: он идёт по строке слева направо и помнит одно состояние. Грамматика описывает не путь по строке, а её устройство: из каких частей она сложена и из чего сложены части.

Механизм: правила, вывод, дерево

Контекстно-свободная грамматика, КС-грамматика, - это четыре вещи:

терминалы     буквы, из которых состоят строки:        a b ( ) + число
нетерминалы   имена частей, в готовой строке их нет:   S E T
правила       нетерминал → строка из терминалов и нетерминалов;
              правая часть может быть пустой, ε
начальный нетерминал, с которого начинается вывод

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

Терминал - не обязательно одна буква. В грамматиках выражений терминалом считают целое число: текст заранее режут на числа и знаки, и грамматика видит 23 как один символ число. Какое именно это число, ей безразлично.

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

Грамматика из двух правил S → aSb и S → ε:

S  ⇒  aSb  ⇒  aaSbb  ⇒  aaaSbbb  ⇒  aaabbb

Одинарная стрелка → стоит в правиле и читается «можно заменить на». Двойная стрелка ⇒ соединяет две строки вывода и означает, что вторая получена из первой одной заменой.

На последнем шаге применено правило S → ε: нетерминал заменён пустой строкой, то есть исчез. Каждое применение первого правила добавляет одну a слева и одну b справа, одновременно. Отсюда и равенство количеств: его обеспечивает не счётчик, а форма правила. Язык этой грамматики - aⁿbⁿ, тот самый, которого не принимает ни один конечный автомат.

«Контекстно-свободная» значит: нетерминал заменяется по своему правилу независимо от того, что стоит вокруг него. Слева в правиле всегда один нетерминал, без соседей.

Дерево разбора записывает вывод без лишнего: в корне начальный нетерминал, у каждого нетерминала дети - символы правой части применённого правила, листья слева направо читаются как строка (лист ε - пустая строка, он ничего не добавляет). Вывод aabb:

        S
      / | \
     a  S  b
      / | \
     a  S  b
        |
        ε

Одному дереву может соответствовать много выводов - они отличаются только порядком, в котором раскрывались нетерминалы. Здесь выбирать не из чего: в строке всегда один нетерминал. А в грамматике S → (S)S из строки (S)S можно раскрыть сначала левую S, а можно правую: выводов два, дерево одно. Если всегда раскрывать самый левый, вывод получается один на дерево; он называется левым.

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

Любой регулярный язык контекстно-свободен. Автомат переписывается в грамматику дословно: состояние - нетерминал (начальное состояние - начальный нетерминал), переход из Q по букве a в R - правило Q → aR, принимающее состояние - правило Q → ε. Обратное неверно, как показывает aⁿbⁿ.

Правило

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

Разбор: что порождают два правила

Функция porodit перебирает выводы в ширину. Нетерминалы в ней - ключи словаря, и имя каждого - одна буква: строка просматривается посимвольно. Она берёт очередную строку из терминалов и нетерминалов, находит самый левый нетерминал и подставляет вместо него каждую правую часть по очереди. Строки без нетерминалов готовы. Чтобы перебор закончился, строки, в которых терминалов больше dlina, отбрасываются. Этого хватает для грамматик, где каждое правило либо добавляет терминал, либо убирает нетерминал, - как у обеих грамматик ниже; правило вроде S → SS растит строку, не добавляя терминалов, и на нём перебор не остановился бы: пришлось бы ограничивать ещё и число нетерминалов.

def porodit(pravila, start, dlina):
    gotovye = []
    ochered = [start]
    videli = {start}
    i = 0
    while i < len(ochered):
        forma = ochered[i]
        i = i + 1
        mesto = -1
        for j in range(len(forma)):
            if forma[j] in pravila:
                mesto = j
                break
        if mesto == -1:
            gotovye.append(forma)
            continue
        for pravaya in pravila[forma[mesto]]:
            novaya = forma[:mesto] + pravaya + forma[mesto + 1:]
            bukv = 0
            for simvol in novaya:
                if simvol not in pravila:
                    bukv = bukv + 1
            if bukv <= dlina and novaya not in videli:
                videli.add(novaya)
                ochered.append(novaya)
    return gotovye

print(porodit({"S": ["aSb", ""]}, "S", 6))
skobki = porodit({"S": ["(S)S", ""]}, "S", 6)
print(len(skobki))
po_dline = [0, 0, 0, 0]
for s in skobki:
    po_dline[len(s) // 2] = po_dline[len(s) // 2] + 1
print(po_dline)
print(skobki[:5])
print(skobki[5:])

['', 'ab', 'aabb', 'aaabbb']
9
[1, 1, 2, 5]
['', '()', '(())', '()()', '((()))']
['(()())', '(())()', '()(())', '()()()']

Первая грамматика дала ровно aⁿbⁿ до длины 6. Вторая, S → (S)S | ε (черта разделяет два правила с одной левой частью), - правильные скобочные записи: девять строк не длиннее шести символов, из них одна пустая, одна длины 2, две длины 4 и пять длины 6. Ни одной лишней: )( или (() в списке нет.

Правило S → (S)S читается так: правильная запись либо пуста, либо начинается со скобки, внутри которой правильная запись, а после закрывающей скобки идёт ещё одна правильная запись. Это описание устройства, а не способ проверки, и именно поэтому оно короткое.

Разбор: одна строка, несколько деревьев

Грамматика из школьной тетради: E → E + E | E - E | E * E | число. Функция znacheniya перебирает все деревья разбора куска выражения: выбирает знак, который окажется в корне, и для каждого дерева левой части и каждого дерева правой вычисляет результат. Токены - элементы выражения, числа и знаки, - лежат в списке: на чётных местах числа, на нечётных знаки.

def znacheniya(t, i, j):
    if i == j:
        return [t[i]]
    vse = []
    for k in range(i + 1, j, 2):
        for levoe in znacheniya(t, i, k - 1):
            for pravoe in znacheniya(t, k + 1, j):
                if t[k] == "+":
                    vse.append(levoe + pravoe)
                elif t[k] == "-":
                    vse.append(levoe - pravoe)
                else:
                    vse.append(levoe * pravoe)
    return vse

for t in [[2, "+", 3, "*", 4], [8, "-", 3, "-", 2],
          [1, "+", 2, "+", 3], [2, "*", 3, "+", 4, "*", 5]]:
    z = znacheniya(t, 0, len(t) - 1)
    print(len(z), sorted(set(z)))
kolichestva = []
for operacij in range(1, 8):
    t = [1]
    for povtor in range(operacij):
        t.append("+")
        t.append(1)
    kolichestva.append(len(znacheniya(t, 0, len(t) - 1)))
print(kolichestva)

2 [14, 20]
2 [3, 7]
2 [6]
5 [26, 46, 50, 70]
[1, 2, 5, 14, 42, 132, 429]

В каждой строке - число деревьев и разные значения, которые они дают. У 2 + 3 * 4 два дерева и два ответа, 14 и 20. У 8 - 3 - 2 тоже два: 3 и 7. У 1 + 2 + 3 деревьев два, а ответ один: сложению порядок безразличен, и неоднозначность здесь не видна по результату, хотя никуда не делась. У 2 * 3 + 4 * 5 деревьев пять, а значений четыре: 70 получается двумя способами. Два дерева строки 2 + 3 * 4:

      E                    E
    / | \                / | \
   E  +  E              E  *  E
   |   / | \          / | \   |
   2  E  *  E        E  +  E  4
      |     |        |     |
      3     4        2     3

 2 + (3 * 4) = 14    (2 + 3) * 4 = 20

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

Лечится это грамматикой, в которой приоритет записан уровнями:

E → E + T | E - T | T         выражение: слагаемые через + и -
T → T * F | F                 слагаемое: множители через *
F → число | ( E )             множитель: число или выражение в скобках

Умножение лежит уровнем глубже сложения. По правилу T → T * F слева и справа от звёздочки стоят только T и F, а они без скобок плюса не содержат. Поэтому в 2 + 3 * 4 сумма 2 + 3 не может оказаться множителем, и произведение 3 * 4 собирается в одно T раньше, чем встретится с плюсом: дерево одно, ответ 14. Правило E → E - T ставит вложенное выражение только слева от минуса: в 8 - 3 - 2 справа от последнего минуса может стоять лишь T, то есть 2, а 8 - 3 целиком уходит в левое E. Получается (8 - 3) - 2. Язык остался прежним (если не считать добавленных скобок), а деревьев у каждой строки стало ровно одно.

Что ломается без этого

Грамматика описывает язык, а смысл выбирают молча. Классический случай - «висячее else»: в if a then if b then x else y ветка else может относиться к любому из двух if. Грамматика допускает оба дерева, и язык обязан отдельным правилом сказать, какое из них верное.

Приоритет операций «подразумевается». В грамматике вида E → E op E, где op - любой из знаков, приоритета нет вообще. Он появляется либо уровнями правил, либо отдельной таблицей приоритетов, которую читает разборщик - программа, строящая дерево разбора по тексту.

Неоднозначность ищут тестами. По результату её не видно, когда разные деревья дают одно значение. А общего алгоритма, который по грамматике говорит, однозначна ли она, не существует - это доказанный факт, до него дойдёт четвёртая главаРазбирается в разделе 21, глава «Проблема останова и неразрешимые задачи»: Неразрешимое вне программ: домино Поста, уравнения и усердные бобры.

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

Зачем это в работе

Спецификации. Синтаксис языков программирования, форматов данных и сетевых протоколов записывают грамматикой: в стандарте JSON она занимает полстраницы. Привычная запись с ::= и вертикальной чертой, форма Бэкуса-Наура, появилась в описании Алгола 60 и с тех пор почти не изменилась.

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

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

Теперь сам

1. Выведи строку (())() по грамматике S → (S)S | ε: запиши цепочку замен, раскрывая самый левый нетерминал.
2. Напиши грамматику для языка «сколько-то букв a, потом вдвое больше букв b».
3. Сколько деревьев разбора у 1 - 2 - 3 - 4 в грамматике E → E - E | число?
4. Как изменить грамматику с уровнями, чтобы вычитание выполнялось справа налево?
5. Запиши грамматикой регулярный язык a*b.