www.wikidata.uk-ua.nina.az

LL аналізатор алгоритм синтаксичного аналізу методом рекурсивного спуску для підмножини контекстно вільних граматик Він

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

LL-аналізатор — алгоритм синтаксичного аналізу методом рекурсивного спуску для підмножини контекстно-вільних граматик. Він обробляє вхід зліва направо (тому перша буква означає Left) та будує ліворекурсивне виведення рядка (тому його порівнюють з LR-аналізатором). Клас граматик, що розпізнаються цим аналізатором, називається LL-граматиками.

Далі описується табличний аналізатор — альтернатива алгоритму рекурсивного спуску, який зазвичай кодується вручну (хоча не завжди, дивіться наприклад ANTLR для генератора аналізаторів LL(*)-граматик методом рекурсивного спуску).

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

LL-аналізатор називається LL(*)-аналізатором, якщо він не обмежений скінченним числом токенів для попереднього перегляду, а може приймати рішення визначаючи чи належать вхідні токени регулярній мові (наприклад використовуючи ДСкА).

Існує конкуренція між «європейською школою» проектування мов, яка віддає перевагу LL-граматикам, та «американською», яка частіше використовує LR-граматики. Це багато в чому завдяки традиціям викладання та детальному опису методів та інструментів в літературі. Інший вплив іде від досліджень Ніклауса Вірта в Вищій технічній школі Цюріха, які описували багато способів оптимізації LL(1)-мов та компіляторів.

Загальний випадок ред.

Аналізатор працює на рядках з певної контекстно вільної граматики.

Аналізатор складається з

  • вхідного буфера, в якому зберігається вхідний рядок
  • стека, в якому зберігають термінальні та нетермінальні символи з граматики, що аналізується.
  • таблицю аналізу, яка каже яке (якщо існує ) правило граматики застосувати залежно від символів на вершині стеку, та наступного вхідного токена.

Аналізатор застосовує правило з таблиці, яке відповідає символу на вершині стеку (рядок таблиці) та символу з вхідного потоку (стовпець).

Коли аналізатор запускається, стек вже містить два символи: 

[ S, $ ]

де '$' — спеціальний термінал, що вказує на дно стека, та кінець вхідного потоку, а 'S' — аксіома граматики. Аналізатор спробує змінити вміст стека на те, що він знайде на вході. Тим не менш він тільки тримає в стеку те, що має бути переписаним.

Конкретний приклад ред.

Ініціалізація ред.

Щоб пояснити як це працює, ми візьмемо наступну невелику граматику:

  1. S → F
  2. S → ( S + F )
  3. F → a

яка аналізує наступний вхід:

Таблиця аналізу для цієї граматики виглядає так:

(Зауважте, що є також стовпчик для спеціального терміналу $, що позначає кінець вводу.)

Процедура аналізу ред.

На кожному кроці парсер читає наступний доступний символ з вхідного потоку, та символ на вершині стеку. Якщо вхідний символ та символ на вершині стеку збігаються, парсер відкидає їх обох, залишаючи тільки символи, що не збіглися.

Тому на першому кроці аналізатор читає вхідний символ '(' та символ на вершині стеку 'S'. Інструкції з таблиці аналізу приходять від колонки з заголовком '(' та рядком з заголовком 'S'; ця клітинка містить '2', що вказує аналізатору застосувати правило (2). Аналізатор має замінити 'S' на '( S + F )' на вершині стеку та вивести правило номер 2. Стек приймає вигляд: 

[ (, S, +, F, ), $ ]

Так як '(' з вхідного потоку не збігається з символом на вершині стеку, 'S', він не видаляється, та залишається як наступний доступний вхідний символ, для наступного кроку.

На другому кроці аналізатор видаляє ( з вхідного потоку, та з стеку, так як вони збігаються. Стек стає: 

[ S, +, F, ), $ ]

Тепер на вході 'a' та 'S' у стеку. Таблиця каже застосувати правило (1) граматики та вивести правило (1) у вихідний потік. Стек стає: 

[ F, +, F, ), $ ]

Аналізатор має 'a' на вході, та 'F' на вершині стеку. Таблиця каже застосувати правило (3). Стек стає: 

[ a, +, F, ), $ ]

На наступних двох кроках аналізатор читає 'a' та '+' з вхідного потоку, та, так як вони збігаються з символами в стеку теж видаляє їх звідти. Результат: 

[ F, ), $ ]

На наступних трьох кроках аналізатор замінить 'F' зі стеку на 'a, виведе правило 3 та видалить 'a' та ')' зі стеку та з вхідного рядка. Аналізатор таким чином завершить роботу коли '$' міститиметься як на вході, так і у стеку.

В такому випадку аналізатор скаже що він приймає вхідний рядок, та виведе наступний список номерів правил у вихідний потік:

Це насправді список правил для ліворекурсивного виведення вхідного рядка у даній контекстно-вільній граматиці, які утворюють такий ланцюжок:

Реалізація аналізатора на C++ ред.

Нижче дана реалізація на C++ табличного LL-аналізатора для мови, що була дана в прикладі:

Примітки ред.

Як можна було бачити на прикладі, аналізатор виконує три види кроків залежно від того чи на вершині стеку термінал, нетермінал, чи спеціальний символ $:

  • Якщо на вершині нетермінал, тоді він шукає в таблиці аналізу за базисом нетерміналу та символом у вхідному потоці яке граматичне правило варто використати, щоб замінити його у стеку. Номер правила записується у вихідний потік. Якщо таблиця каже що потрібного правила не існує, то виводиться помилка, і робота припиняється.
  • Якщо на вершині термінал, тоді він порівнюється з символом на вході, та якщо вони рівні, вони обидва видаляються. Якщо вони не рівні, аналізатор виводить помилку та зупиняється.
  • Якщо на вершині стеку $ та у вхідному потоці теж, тоді аналізатор доповідає про успішний аналіз вхідного потоку, інакше виводить помилку. В обох випадках аналіз зупиняється.

Ці кроки повторюються аж до зупинки аналізатора, і в результаті отримуємо або ланцюжок виведення, або повідомлення про помилку.

Побудова таблиці LL(1)-аналізатора ред.

Щоб заповнити таблицю аналізу, ми маємо з'ясувати яке правило використовувати, коли аналізатор бачить нетермінал A на вершині стеку та символ a на вході. Легко побачити що це правило має мати форму A -> w та що мова що відповідає w має мати хоч одне слово, що починається з w. З такою метою ми описуємо First-set для w що записується тут як Fi(w), як множину терміналів, що можуть знаходитись на початку будь-якого слова з w, плюс ε якщо порожнє слово теж належить w. Маючи граматику з правилами A1 → w1, …, An → wn, ми можемо обчислити Fi(wi) та Fi(Ai) для кожного правила так:

  1. ініціалізуємо кожне Fi(wi) та Fi(Ai) порожньою множиною.
  2. додаємо Fi(wi) до Fi(Ai) для кожного правила Ai → wi, де Fi описується так:
    • Fi(a w' ) = { a } для кожного теміналу a
    • Fi(A w' ) = Fi(A) для кожного такого нетерміналу A, що ε не належить Fi(A)
    • Fi(A w' ) = Fi(A) \ { ε } ∪ Fi(w' ) для кожного нетерміналу A, що ε належить Fi(A)
    • Fi(ε) = { ε }
  3. додаємо Fi(wi) до Fi(Ai) для кожного правила Ai → wi
  4. повторюємо кроки 2 та 3, аж поки всі множини Fi не стануть однаковими.

На жаль, множин Fi не достатньо, щоб вирахувати таблицю аналізу. Це тому, що права частина правила w може бути переписана в порожній рядок. Тому аналізатор також має використовувати правило A -> w якщо ε належить Fi(w) та видимий у вхідному потоці, як символ, що може йти за A. Тому ми також потребуємо множину Follow для A, яку запишемо як Fo(A) , яка описується як множина терміналів a таких що існує рядок символів αAaβ які можуть виводитись з початкового символу. Обчислення множини Follow для нетерміналів в граматиці може бути здійснене так:

  1. ініціалізувати кожне Fo(Ai) порожньою множиною
  2. якщо існує правило виду Aj → wAiw' , тоді
    • якщо термінал a належить Fi(w' ), то додати a до Fo(Ai)
    • якщо ε належить Fi(w' ), то додати Fo(Aj) до Fo(Ai)
  3. повторювати крок 2 поки всі Fo не стануть однаковими.

Тепер ми можемо описати точно, які правила де будуть зберігатись в таблиці аналізу. Якщо T[A, a] позначає місце в таблиці для нетерміналу A та терміналу a, тоді

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

Побудова таблиці аналізу для LL(k)-граматики ред.

До середини 1990-тих вважалось, що LL(k)-аналіз (для k > 1) є непрактичним, так як розмір таблиці аналізу буде (зазвичай в гіршому випадку) мати експоненційну складність від k. Таке сприйняття сильно змінилось з випуском PCCTS близько 1992, коли було показано, що багато мов програмування можуть ефективно аналізуватись синтаксичним аналізатором LL(k)-граматики без використання поведінки для гіршого випадку. Більше того, в деяких випадках LL-аналіз можливий навіть для необмеженого преперегляду. А традиційні генератори аналізаторів, як yacc використовують таблиці аналізу LALR(1) щоб створити обмежений LR-аналізатор з фіксованим, однотокеневим препереглядом.

Конфлікти ред.

Конфлікти LL(1) ред.

Є три типи LL(1)-конфліктів:

  • FIRST/FIRST
  • FIRST/FOLLOW
 S -> A 'a' 'b' A -> 'a' | ε
  • ліво-рекурсивний
 E -> E '+' term | alt1 | alt2

Розв'язання конфліктів LL(1) ред.

  • Лівостороннє винесення за дужки

Працює приблизно як 3x + 3y = 3(x+y). 

 A -> X | X Y Z

стає 

 A -> X B B -> Y Z | ε

Може застосовуватись коли дві альтернативи починаються з одного і того ж символу, як у конфлікті FIRST/FIRST.

  • Підстановка

Підстановка правила в інше правило, щоб вилучити непрямі конфлікти, чи конфлікти FIRST/FOLLOW. Зауважте, що це може спричинити конфлікт FIRST/FIRST.

  • Вилучення лівої рекурсії

Простий приклад вилучення лівої рекурсії:

Наступні продуктивні правила мають ліву рекурсію на E 

 E -> E '+' T -> T

Ці правила задають ніщо інше, окрім списку з T, розділених '+'. У формі регулярного виразу записується так: T ('+' T)*. Тому правила можна переписати так 

 E -> T Z Z -> '+' T Z -> ε

Тепер немає лівої рекурсії та конфліктів у жодному з правил.

Див. також ред.

Генератори синтаксичних аналізаторів:

Посилання ред.

Джерела ред.

  1. Modern Compiler Design, Grune, Bal, Jacobs and Langendoen
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
LL analizator algoritm sintaksichnogo analizu metodom rekursivnogo spusku dlya pidmnozhini kontekstno vilnih gramatik Vin obroblyaye vhid zliva napravo tomu persha bukva oznachaye Left ta buduye livorekursivne vivedennya ryadka tomu jogo porivnyuyut z LR analizatorom Klas gramatik sho rozpiznayutsya cim analizatorom nazivayetsya LL gramatikami Dali opisuyetsya tablichnij analizator alternativa algoritmu rekursivnogo spusku yakij zazvichaj koduyetsya vruchnu hocha ne zavzhdi divitsya napriklad ANTLR dlya generatora analizatoriv LL gramatik metodom rekursivnogo spusku LL analizatori nazivayutsya LL k analizatorami yaksho voni divlyatsya na k tokeniv vpered protyagom analizu virazu Yaksho takij analizator isnuye ta mozhe rozpiznavati virazi gramatiki bez bektrekingu todi gramatika nazivayetsya LL k gramatikoyu Z cih gramatik najpopulyarnishoyu gramatikoyu ye gramatika LL 1 bo nezvazhayuchi na yiyi obmezhenist vona maye duzhe prostij analizator Movi sho vidpovidayut LL k gramatikam z velikim k vvazhayutsya takimi sho vazhko analizuyutsya hocha sogodni ce ne zovsim virno cherez dostupnist ta poshirenist generatoriv sintaksichnih analizatoriv sho pidtrimuyut LL k gramatiki LL analizator nazivayetsya LL analizatorom yaksho vin ne obmezhenij skinchennim chislom tokeniv dlya poperednogo pereglyadu a mozhe prijmati rishennya viznachayuchi chi nalezhat vhidni tokeni regulyarnij movi napriklad vikoristovuyuchi DSkA Isnuye konkurenciya mizh yevropejskoyu shkoloyu proektuvannya mov yaka viddaye perevagu LL gramatikam ta amerikanskoyu yaka chastishe vikoristovuye LR gramatiki Ce bagato v chomu zavdyaki tradiciyam vikladannya ta detalnomu opisu metodiv ta instrumentiv v literaturi Inshij vpliv ide vid doslidzhen Niklausa Virta v Vishij tehnichnij shkoli Cyuriha yaki opisuvali bagato sposobiv optimizaciyi LL 1 mov ta kompilyatoriv Zmist 1 Zagalnij vipadok 2 Konkretnij priklad 2 1 Inicializaciya 2 2 Procedura analizu 2 3 Realizaciya analizatora na C 3 Primitki 4 Pobudova tablici LL 1 analizatora 5 Pobudova tablici analizu dlya LL k gramatiki 6 Konflikti 6 1 Konflikti LL 1 6 2 Rozv yazannya konfliktiv LL 1 7 Div takozh 8 Posilannya 9 DzherelaZagalnij vipadok red Analizator pracyuye na ryadkah z pevnoyi kontekstno vilnoyi gramatiki Analizator skladayetsya z vhidnogo bufera v yakomu zberigayetsya vhidnij ryadok steka v yakomu zberigayut terminalni ta neterminalni simvoli z gramatiki sho analizuyetsya tablicyu analizu yaka kazhe yake yaksho isnuye pravilo gramatiki zastosuvati zalezhno vid simvoliv na vershini steku ta nastupnogo vhidnogo tokena Analizator zastosovuye pravilo z tablici yake vidpovidaye simvolu na vershini steku ryadok tablici ta simvolu z vhidnogo potoku stovpec Koli analizator zapuskayetsya stek vzhe mistit dva simvoli S de specialnij terminal sho vkazuye na dno steka ta kinec vhidnogo potoku a S aksioma gramatiki Analizator sprobuye zminiti vmist steka na te sho vin znajde na vhodi Tim ne mensh vin tilki trimaye v steku te sho maye buti perepisanim Konkretnij priklad red Inicializaciya red Shob poyasniti yak ce pracyuye mi vizmemo nastupnu neveliku gramatiku S F S S F F ayaka analizuye nastupnij vhid a a Tablicya analizu dlya ciyeyi gramatiki viglyadaye tak a S 2 1 F 3 Zauvazhte sho ye takozh stovpchik dlya specialnogo terminalu sho poznachaye kinec vvodu Procedura analizu red Na kozhnomu kroci parser chitaye nastupnij dostupnij simvol z vhidnogo potoku ta simvol na vershini steku Yaksho vhidnij simvol ta simvol na vershini steku zbigayutsya parser vidkidaye yih oboh zalishayuchi tilki simvoli sho ne zbiglisya Tomu na pershomu kroci analizator chitaye vhidnij simvol ta simvol na vershini steku S Instrukciyi z tablici analizu prihodyat vid kolonki z zagolovkom ta ryadkom z zagolovkom S cya klitinka mistit 2 sho vkazuye analizatoru zastosuvati pravilo 2 Analizator maye zaminiti S na S F na vershini steku ta vivesti pravilo nomer 2 Stek prijmaye viglyad S F Tak yak z vhidnogo potoku ne zbigayetsya z simvolom na vershini steku S vin ne vidalyayetsya ta zalishayetsya yak nastupnij dostupnij vhidnij simvol dlya nastupnogo kroku Na drugomu kroci analizator vidalyaye z vhidnogo potoku ta z steku tak yak voni zbigayutsya Stek staye S F Teper na vhodi a ta S u steku Tablicya kazhe zastosuvati pravilo 1 gramatiki ta vivesti pravilo 1 u vihidnij potik Stek staye F F Analizator maye a na vhodi ta F na vershini steku Tablicya kazhe zastosuvati pravilo 3 Stek staye a F Na nastupnih dvoh krokah analizator chitaye a ta z vhidnogo potoku ta tak yak voni zbigayutsya z simvolami v steku tezh vidalyaye yih zvidti Rezultat F Na nastupnih troh krokah analizator zaminit F zi steku na a vivede pravilo 3 ta vidalit a ta zi steku ta z vhidnogo ryadka Analizator takim chinom zavershit robotu koli mistitimetsya yak na vhodi tak i u steku V takomu vipadku analizator skazhe sho vin prijmaye vhidnij ryadok ta vivede nastupnij spisok nomeriv pravil u vihidnij potik 2 1 3 3 Ce naspravdi spisok pravil dlya livorekursivnogo vivedennya vhidnogo ryadka u danij kontekstno vilnij gramatici yaki utvoryuyut takij lancyuzhok S S F F F a F a a Realizaciya analizatora na C red Nizhche dana realizaciya na C tablichnogo LL analizatora dlya movi sho bula dana v prikladi Realizaciya analizatora na C include lt iostream gt include lt map gt include lt stack gt enum Symbols the symbols Terminal symbols TS L PARENS TS R PARENS TS A a TS PLUS TS EOS in this case corresponds to 0 TS INVALID invalid token Non terminal symbols NTS S S NTS F Converts a valid token to the corresponding terminal symbol enum Symbols lexer char c switch c case return TS L PARENS break case return TS R PARENS break case a return TS A break case return TS PLUS break case 0 this will act as the terminal symbol return TS EOS break default return TS INVALID break int main int argc char argv using namespace std if argc lt 2 cout lt lt usage n t ll a a lt lt endl return 0 map lt enum Symbols map lt enum Symbols int gt gt table LL parser table maps lt non terminal terminal gt pair to action stack lt enum Symbols gt ss symbol stack char p input buffer initialize the symbols stack ss push TS EOS terminal ss push NTS S non terminal S initialize the symbol stream cursor p amp argv 1 0 setup the parsing table table NTS S TS L PARENS 2 table NTS S TS A 1 table NTS F TS A 3 while ss size gt 0 if lexer p ss top cout lt lt Matched symbols lt lt lexer p lt lt endl p ss pop else cout lt lt Rule lt lt table ss top lexer p lt lt endl switch table ss top lexer p case 1 1 S F ss pop ss push NTS F F break case 2 2 S S F ss pop ss push TS R PARENS ss push NTS F F ss push TS PLUS ss push NTS S S ss push TS L PARENS break case 3 3 F a ss pop ss push TS A a break default cout lt lt parsing table defaulted lt lt endl return 0 break cout lt lt finished parsing lt lt endl return 0 Primitki red Yak mozhna bulo bachiti na prikladi analizator vikonuye tri vidi krokiv zalezhno vid togo chi na vershini steku terminal neterminal chi specialnij simvol Yaksho na vershini neterminal todi vin shukaye v tablici analizu za bazisom neterminalu ta simvolom u vhidnomu potoci yake gramatichne pravilo varto vikoristati shob zaminiti jogo u steku Nomer pravila zapisuyetsya u vihidnij potik Yaksho tablicya kazhe sho potribnogo pravila ne isnuye to vivoditsya pomilka i robota pripinyayetsya Yaksho na vershini terminal todi vin porivnyuyetsya z simvolom na vhodi ta yaksho voni rivni voni obidva vidalyayutsya Yaksho voni ne rivni analizator vivodit pomilku ta zupinyayetsya Yaksho na vershini steku ta u vhidnomu potoci tezh todi analizator dopovidaye pro uspishnij analiz vhidnogo potoku inakshe vivodit pomilku V oboh vipadkah analiz zupinyayetsya Ci kroki povtoryuyutsya azh do zupinki analizatora i v rezultati otrimuyemo abo lancyuzhok vivedennya abo povidomlennya pro pomilku Pobudova tablici LL 1 analizatora red Shob zapovniti tablicyu analizu mi mayemo z yasuvati yake pravilo vikoristovuvati koli analizator bachit neterminal A na vershini steku ta simvol a na vhodi Legko pobachiti sho ce pravilo maye mati formu A gt w ta sho mova sho vidpovidaye w maye mati hoch odne slovo sho pochinayetsya z w Z takoyu metoyu mi opisuyemo First set dlya w sho zapisuyetsya tut yak Fi w yak mnozhinu terminaliv sho mozhut znahoditis na pochatku bud yakogo slova z w plyus e yaksho porozhnye slovo tezh nalezhit w Mayuchi gramatiku z pravilami A1 w1 An wn mi mozhemo obchisliti Fi wi ta Fi Ai dlya kozhnogo pravila tak inicializuyemo kozhne Fi wi ta Fi Ai porozhnoyu mnozhinoyu dodayemo Fi wi do Fi Ai dlya kozhnogo pravila Ai wi de Fi opisuyetsya tak Fi a w a dlya kozhnogo teminalu a Fi A w Fi A dlya kozhnogo takogo neterminalu A sho e ne nalezhit Fi A Fi A w Fi A e Fi w dlya kozhnogo neterminalu A sho e nalezhit Fi A Fi e e dodayemo Fi wi do Fi Ai dlya kozhnogo pravila Ai wi povtoryuyemo kroki 2 ta 3 azh poki vsi mnozhini Fi ne stanut odnakovimi Na zhal mnozhin Fi ne dostatno shob virahuvati tablicyu analizu Ce tomu sho prava chastina pravila w mozhe buti perepisana v porozhnij ryadok Tomu analizator takozh maye vikoristovuvati pravilo A gt w yaksho e nalezhit Fi w ta vidimij u vhidnomu potoci yak simvol sho mozhe jti za A Tomu mi takozh potrebuyemo mnozhinu Follow dlya A yaku zapishemo yak Fo A yaka opisuyetsya yak mnozhina terminaliv a takih sho isnuye ryadok simvoliv aAab yaki mozhut vivoditis z pochatkovogo simvolu Obchislennya mnozhini Follow dlya neterminaliv v gramatici mozhe buti zdijsnene tak inicializuvati kozhne Fo Ai porozhnoyu mnozhinoyu yaksho isnuye pravilo vidu Aj wAiw todi yaksho terminal a nalezhit Fi w to dodati a do Fo Ai yaksho e nalezhit Fi w to dodati Fo Aj do Fo Ai povtoryuvati krok 2 poki vsi Fo ne stanut odnakovimi Teper mi mozhemo opisati tochno yaki pravila de budut zberigatis v tablici analizu Yaksho T A a poznachaye misce v tablici dlya neterminalu A ta terminalu a todi T A a mistit pravilo A w todi i tilki todi kolia nalezhit Fi w abo e nalezhit Fi w i a nalezhit Fo A dd Yaksho tablicya mistit shonajbilshe odne pravilo v kozhnij klitinci todi analizator zavzhdi bude znati yake pravilo vin maye vikoristati i tomu mozhe analizuvati ryadki bez bektrekingu Ce tochno takij vipadok dlya gramatiki sho nazvana LL 1 gramatikoyu Pobudova tablici analizu dlya LL k gramatiki red Do seredini 1990 tih vvazhalos sho LL k analiz dlya k gt 1 ye nepraktichnim tak yak rozmir tablici analizu bude zazvichaj v girshomu vipadku mati eksponencijnu skladnist vid k Take sprijnyattya silno zminilos z vipuskom PCCTS blizko 1992 koli bulo pokazano sho bagato mov programuvannya mozhut efektivno analizuvatis sintaksichnim analizatorom LL k gramatiki bez vikoristannya povedinki dlya girshogo vipadku Bilshe togo v deyakih vipadkah LL analiz mozhlivij navit dlya neobmezhenogo prepereglyadu A tradicijni generatori analizatoriv yak yacc vikoristovuyut tablici analizu LALR 1 shob stvoriti obmezhenij LR analizator z fiksovanim odnotokenevim prepereglyadom Konflikti red Konflikti LL 1 red Ye tri tipi LL 1 konfliktiv FIRST FIRSTMnozhini FIRST dvoh riznih neterminaliv peretinayutsya FIRST FOLLOWMnozhini pravil gramatiki FIRST ta FOLLOW peretinayutsya Z e sho nalezhit mnozhini FIRST nevidomo yaku alternativu vibrati Priklad konfliktiv LL 1 S gt A a b A gt a e Mnozhina FIRST dlya A dorivnyuye a e ta mnozhina FOLLOW a livo rekursivnijLiva rekursiya sprichinit konflikt FIRST FIRST z usima alternativami E gt E term alt1 alt2 Rozv yazannya konfliktiv LL 1 red Livostoronnye vinesennya za duzhkiPracyuye priblizno yak 3x 3y 3 x y A gt X X Y Z staye A gt X B B gt Y Z e Mozhe zastosovuvatis koli dvi alternativi pochinayutsya z odnogo i togo zh simvolu yak u konflikti FIRST FIRST PidstanovkaPidstanovka pravila v inshe pravilo shob viluchiti nepryami konflikti chi konflikti FIRST FOLLOW Zauvazhte sho ce mozhe sprichiniti konflikt FIRST FIRST Viluchennya livoyi rekursiyi 1 Prostij priklad viluchennya livoyi rekursiyi Nastupni produktivni pravila mayut livu rekursiyu na E E gt E T gt T Ci pravila zadayut nisho inshe okrim spisku z T rozdilenih U formi regulyarnogo virazu zapisuyetsya tak T T Tomu pravila mozhna perepisati tak E gt T Z Z gt T Z gt e Teper nemaye livoyi rekursiyi ta konfliktiv u zhodnomu z pravil Div takozh red Sintaksichne derevo Analiz zverhu vniz Analiz znizu vverh JFLAPGeneratori sintaksichnih analizatoriv ANTLR Coco R JavaCCPosilannya red Proste poyasnennya mnozhin First ta Follow Arhivovano 3 sichnya 2019 u Wayback Machine angl sproba poyasniti proces stvorennya cih mnozhin u bilsh pryamolinijnij sposib Instrukciya realizaciyi LL 1 analizatora na C angl Simulyator analizatora Arhivovano 24 bereznya 2010 u Wayback Machine Dzherela red Modern Compiler Design Grune Bal Jacobs and Langendoen Otrimano z https uk wikipedia org w index php title LL analizator amp oldid 35520981