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

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

КВ-граматика ${\displaystyle G=⟨N,\mathrm{\Sigma },P,S⟩}$ називається LL(k)-граматикою, для деякого фіксованого k, якщо дія двох лівосторонніх виводів:

1. ${\displaystyle S{\Rightarrow }^{\ast }{\omega }_{1}A{\omega }_2\Rightarrow {\omega }_1\alpha {\omega }_2{\Rightarrow }^{\ast }{\omega }_{1}x}$
2. ${\displaystyle S{\Rightarrow }^{\ast }{\omega }_{1}A{\omega }_2\Rightarrow {\omega }_1\beta {\omega }_2{\Rightarrow }^{\ast }{\omega }_{1}y}$,

для яких з First_k(x) = First_k(y) випливає що ${\displaystyle \alpha =\beta }$ (${\displaystyle A\to \alpha |\beta }$).

Неформально, граматика G буде LL(k)-граматикою, якщо для ланцюжка ${\displaystyle {\omega }_{1}A{\omega }_2\in (N\cup \mathrm{\Sigma })}$ k перших символів (за умови, що вони існують) решти непроаналізованого ланцюжка визначають, що з ${\displaystyle A{\omega }_2}$ існує не більше однієї альтернативи виведення ланцюжка, що починається з ${\displaystyle \omega }$ та продовжується наступними k термінальними символами.

Означення: ${\displaystyle {\text{First}}_k(\alpha )=\{\omega |\alpha {\Rightarrow }^{\ast }\omega x\wedge ((|\omega |=k\to x\ne ϵ)\vee (|\omega |<k\to x=ϵ))\}}$

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

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

• LL-аналізатор