Неоднозначность грамматик

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

Грамматика неоднозначна, если существует строка, у которой есть два или более различных деревьев разбора (равносильно — два левых вывода).

Классический пример

Грамматика выражений E → E + E | E * E | num неоднозначна. Строка «num + num * num» имеет два дерева:

Дерево 1 (умножение глубже — верно):    Дерево 2 (сложение глубже — неверно):

      E                                    E
    / | \                                / | \
   num + E                              E  *  num
        /|\                            /|\
       num * num                      num + num

= num + (num*num)                    = (num+num) * num

Два дерева — это два разных значения! Если num — это 2 + 3 * 4, то первое дерево даёт 2+12=14, второе 5*4=20. Грамматика не определяет, какое верно — это и есть неоднозначность. Для компилятора неприемлемо: смысл программы должен быть однозначен.

Как устранить неоднозначность

Приём — встроить приоритет и ассоциативность в грамматику, введя уровни нетерминалов. Умножение «глубже» сложения, поэтому ему — отдельный уровень:

E → E + T | T          (сложение — верхний уровень, левоассоциативно)
T → T * F | F          (умножение — ниже, связывает крепче)
F → ( E ) | num        (фактор — число или скобки)

Теперь «num + num * num» имеет единственное дерево: умножение обязательно соберётся в T раньше, чем сложение в E. Приоритет закодирован структурой грамматики — это стандартный способ описывать выражения в реальных языках.

Считаем число деревьев

Покажем неоднозначность численно: для неоднозначной грамматики E → E+E | num подсчитаем, сколько способов расставить скобки в сумме из n+1 числа — это число деревьев. Оно равно числу Каталана и быстро растёт.

from functools import lru_cache

# число деревьев для a+a+...+a (n операций +) в грамматике E->E+E|num
@lru_cache(maxsize=None)
def trees(n):              # n операций +
    if n == 0:
        return 1           # одно число — одно дерево
    return sum(trees(i) * trees(n-1-i) for i in range(n))

for n in range(6):
    expr = "+".join(["num"] * (n + 1))
    print(f"{expr:<28} деревьев: {trees(n)}")

Вывод:

num                          деревьев: 1
num+num                      деревьев: 1
num+num+num                  деревьев: 2
num+num+num+num              деревьев: 5
num+num+num+num+num          деревьев: 14
num+num+num+num+num+num      деревьев: 42

Уже три числа дают 2 дерева, шесть чисел — 42! Неоднозначная грамматика не определяет единственную группировку. Однозначная грамматика с уровнями E/T/F всегда даёт ровно 1 дерево.

Как работает под капотом

Существует и врождённая неоднозначность: некоторые КС-языки неоднозначны при любой грамматике — её нельзя устранить в принципе (пример — {aⁱb^jc^k | i=j или j=k}). Хуже того, проверить, неоднозначна ли произвольная КС-грамматика, — алгоритмически неразрешимая задача (привет седьмому разделу!). Поэтому на практике язык проектируют так, чтобы грамматика была заведомо однозначной (LL/LR-классы), а спорные места (вроде «висячего else») разрешают явными правилами.

Частые ошибки

Считать, что два вывода = неоднозначность. Нет: разные порядки подстановок (левый/правый) — норма. Неоднозначность — это два разных дерева (или два левых вывода).

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

Игнорировать «висячий else». Классическая неоднозначность `if-then-else` требует явного правила (else привязывается к ближайшему if).

Итог

• Грамматика неоднозначна, если у строки есть два разных дерева разбора — это даёт два разных смысла.
• Неоднозначность выражений устраняют уровнями нетерминалов (E/T/F), кодируя приоритет и ассоциативность.
• Число деревьев в неоднозначной сумме растёт как числа Каталана; однозначная грамматика даёт ровно одно дерево.
• Есть врождённо неоднозначные языки; проверка неоднозначности грамматики неразрешима.