Перейти до вмісту

LL(k)-граматика

Матеріал з Вікіпедії — вільної енциклопедії.

LL(k)-граматики — це клас контекстно-вільних граматик з додатковими обмеженнями, а саме:

КВ-граматика називається LL(k)-граматикою, для деякого фіксованого k, якщо дія двох лівосторонніх виводів:

  1. ,

для яких з Firstk(x) = Firstk(y) випливає що ().

Неформально, граматика G буде LL(k)-граматикою, якщо для ланцюжка k перших символів (за умови, що вони існують) решти непроаналізованого ланцюжка визначають, що з існує не більше однієї альтернативи виведення ланцюжка, що починається з та продовжується наступними k термінальними символами.

Означення:

Властивості LL(k)-граматик

[ред. | ред. код]
  1. Не існує алгоритму, який перевіряє належність КВ-граматики класу LL(k)-граматик.
  2. Існує алгоритм, який для конкретного k перевіряє, чи є задана граматика LL(k)-граматикою.
  3. Якщо граматика є LL(k)-граматикою, то вона є LL(k p)-граматикою, (p>0).
  4. Клас LL(k)-граматик — це підклас КВ-граматик, який не покриває його.

На практиці найчастіше користуються найвужчим класом LL(1), і до недавнього часу взагалі вважалось, що побудувати аналізатор для LL(k)-граматики, де k>1 практично неможливо.

Див. також

[ред. | ред. код]