LL(k)-граматики — це клас контекстно-вільних граматик з додатковими обмеженнями, а саме:
КВ-граматика називається LL(k)-граматикою, для деякого фіксованого k, якщо дія двох лівосторонніх виводів:
- ,
для яких з Firstk(x) = Firstk(y) випливає що ().
Неформально, граматика G буде LL(k)-граматикою, якщо для ланцюжка k перших символів (за умови, що вони існують) решти непроаналізованого ланцюжка визначають, що з існує не більше однієї альтернативи виведення ланцюжка, що починається з та продовжується наступними k термінальними символами.
Означення:
Властивості LL(k)-граматик
- Не існує алгоритму, який перевіряє належність КВ-граматики класу LL(k)-граматик.
- Існує алгоритм, який для конкретного k перевіряє, чи є задана граматика LL(k)-граматикою.
- Якщо граматика є LL(k)-граматикою, то вона є LL(k+p)-граматикою, (p>0).
- Клас LL(k)-граматик — це підклас КВ-граматик, який не покриває його.
На практиці найчастіше користуються найвужчим класом LL(1), і до недавнього часу взагалі вважалось, що побудувати аналізатор для LL(k)-граматики, де k>1 практично неможливо.
Див. також
Це незавершена стаття з математики. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
LL k gramatiki ce klas kontekstno vilnih gramatik z dodatkovimi obmezhennyami a same KV gramatika G N S P S displaystyle G langle N Sigma P S rangle nazivayetsya LL k gramatikoyu dlya deyakogo fiksovanogo k yaksho diya dvoh livostoronnih vivodiv S w 1 A w 2 w 1 a w 2 w 1 x displaystyle S Rightarrow omega 1 A omega 2 Rightarrow omega 1 alpha omega 2 Rightarrow omega 1 x S w 1 A w 2 w 1 b w 2 w 1 y displaystyle S Rightarrow omega 1 A omega 2 Rightarrow omega 1 beta omega 2 Rightarrow omega 1 y dlya yakih z Firstk x Firstk y viplivaye sho a b displaystyle alpha beta A a b displaystyle A to alpha beta Neformalno gramatika G bude LL k gramatikoyu yaksho dlya lancyuzhka w 1 A w 2 N S displaystyle omega 1 A omega 2 in N cup Sigma k pershih simvoliv za umovi sho voni isnuyut reshti neproanalizovanogo lancyuzhka viznachayut sho z A w 2 displaystyle A omega 2 isnuye ne bilshe odniyeyi alternativi vivedennya lancyuzhka sho pochinayetsya z w displaystyle omega ta prodovzhuyetsya nastupnimi k terminalnimi simvolami Oznachennya First k a w a w x w k x ϵ w lt k x ϵ displaystyle mbox First k alpha omega alpha Rightarrow omega x wedge omega k to x neq epsilon vee omega lt k to x epsilon Vlastivosti LL k gramatikNe isnuye algoritmu yakij pereviryaye nalezhnist KV gramatiki klasu LL k gramatik Isnuye algoritm yakij dlya konkretnogo k pereviryaye chi ye zadana gramatika LL k gramatikoyu Yaksho gramatika ye LL k gramatikoyu to vona ye LL k p gramatikoyu p gt 0 Klas LL k gramatik ce pidklas KV gramatik yakij ne pokrivaye jogo Na praktici najchastishe koristuyutsya najvuzhchim klasom LL 1 i do nedavnogo chasu vzagali vvazhalos sho pobuduvati analizator dlya LL k gramatiki de k gt 1 praktichno nemozhlivo Div takozhLL analizator Ce nezavershena stattya z matematiki Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi