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

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

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

1. ${\displaystyle S\Rightarrow ^{*}\omega _{1}A\omega _{2}\Rightarrow \omega _{1}\alpha \omega _{2}\Rightarrow ^{*}\omega _{1}x}$
2. ${\displaystyle S\Rightarrow ^{*}\omega _{1}A\omega _{2}\Rightarrow \omega _{1}\beta \omega _{2}\Rightarrow ^{*}\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 \Sigma )}$ k перших символів (за умови, що вони існують) решти непроаналізованого ланцюжка визначають, що з ${\displaystyle A\omega _{2}}$ існує не більше однієї альтернативи виведення ланцюжка, що починається з ${\displaystyle \omega }$ та продовжується наступними k термінальними символами.

Означення: ${\displaystyle {\mbox{First}}_{k}(\alpha )=\{\omega |\alpha \Rightarrow ^{*}\omega x\wedge ((|\omega |=k\to x\neq \epsilon )\vee (|\omega |<k\to x=\epsilon ))\}}$