Ляво-рекурсивни граматики. Разбор Премахване на лява рекурсия онлайн
Основната трудност при използването на прогнозен анализ е намирането на граматика за входния език, която може да се използва за изграждане на таблица за анализ с уникално дефинирани входове. Понякога, с някои прости трансформации, не-LL(1) граматика може да бъде редуцирана до еквивалентна LL(1) граматика. Сред тези трансформации най-ефективните са лявото факторизиране и отстраняване лява рекурсия. Тук трябва да се направят две забележки. Първо, не всяка граматика става LL(1) след тези трансформации и второ, след такива трансформации получената граматика може да стане по-малко разбираема.
Непосредствената лява рекурсия, тоест рекурсията на формата , може да бъде премахната по следния начин. Първо, групираме A-правилата:
където нито един от редовете не започва с A. Тогава заместваме този набор от правила с
където A" е нов не-терминал. Същите вериги могат да бъдат получени от не-терминал A, както преди, но сега няма лява рекурсия. Тази процедура премахва всички незабавни леви рекурсии, но лявата рекурсия, включваща две или повече стъпки, не се премахва. По-долу алгоритъм 4.8ви позволява да премахнете всички леви рекурсииот граматиката.
Алгоритъм 4.8. Премахване лява рекурсия.
Вход. COP-граматика G без е-правила (от формата A -> e).
Изход. COP-граматика G" без лява рекурсия, еквивалентно на G.
Метод. Следвайте стъпки 1 и 2.
(1) Подредете нетерминалите на граматиката G в произволен ред.
(2) Изпълнете следната процедура:
След (i-1)-та итерация на външния цикъл в стъпка 2 за всяко правило от формата 
, където k< i, выполняется s >к. В резултат на това при следващата итерация (с i), вътрешният цикъл (с j) последователно увеличава долната граница с m във всяко правило 
докато m >= i. След това, след премахване на незабавното лява рекурсияза A i -правила, m става по-голямо от i.
Алгоритъм 4.8приложимо, ако граматиката няма e - правила (правила от формата A -> e). Наличните в граматиката e - правила могат да бъдат изтрити предварително. Получената граматика без лява рекурсияможе да има електронни правила.
Ляво факторизиране
Основната идея зад лявото факторизиране е, че когато не е ясно коя от двете алтернативи трябва да се използва за разгръщане на нетерминал А, трябва да се променят А-правилата, така че да се отложи решението, докато има достатъчно информация, за да се вземе правилното решение .
Ако 
- две A -правила и входната верига започва с непразен низ изход от не знаем дали да разширим с първото правило или с второто. Можете да отложите решението, като разширите . След това, след като анализирате това, от което е получено, можете да разширите на или на . Левите факторизирани правила приемат формата
Алгоритъм 4.9. Ляво факторизиране на граматиката.
Вход. COP-граматика G.
Изход. Ляво факторизирана CF-граматика G", еквивалентна на G.
Метод. За всеки нетерминален A намерете най-дългия префикс, общ за две или повече от неговите алтернативи. Ако , т.е. съществува нетривиален общ префикс, заменете всички A-правила
където z означава всички алтернативи, които не започват с .
където A" е нов нетерминал. Прилагайте тази трансформация, докато няма две алтернативи с общ префикс.
Пример 4.9. Разгледайте отново граматиката на условните изрази от пример 4.6:
S -> ако E тогава S | if E then S else S | a E -> b
След ляво факторизиране граматиката приема формата
S -> if E then SS" | a S" -> else S | e E -> b
За съжаление, граматиката остава двусмислена и следователно не е LL(1) граматика.
LL (k)-граматика, ако за дадения низ и първите k знака (ако има такива), получени от, има най-много едно правило, което може да се приложи към A, за да се получи резултатът от някакъв терминален низ,
Ориз. 4.4.
започвайки и продължавайки със споменатите k терминали.
Една граматика се нарича LL(k)-граматика, ако е LL(k)-граматика за някакво k.
Пример 4.7. Помислете за граматиката G = ((S, A, B), (0, 1, a, b), P, S), където P се състои от правила
S -> A | B, A -> aAb | 0, B -> aBbb | 1.
Тук . G не е LL(k)-граматика за всяко k. Интуитивно, ако започнем с четене на достатъчно дълъг низ от знаци a, ние не знаем кое от правилата S -> A и S -> B е приложено първо, докато не срещнем 0 или 1.
Обръщайки се към точната дефиниция на LL (k)-граматиката, задаваме и y = a k 1b 2k . След това изводите
отговарят на изводи (1) и (2) от определението. Първите k знака на низовете x и y съвпадат. Заключението обаче е невярно. Тъй като k е избрано произволно тук, G не е LL граматика.
Следствия от дефиницията на LL(k)-граматиката
Теорема 4.6. CS граматика е LL(k)-граматика тогава и само ако за две различни правилаи от R кръстовище празен за всички такива , Какво 
.
Доказателство. Необходимост. Да приемем, че и отговаря на условията на теоремата и съдържа x . Тогава, по дефиницията на FIRST, за някои y и z има заключения
(Имайте предвид, че тук използвахме факта, че N не съдържа безполезни нетерминали, както се предполага за всички разглеждани граматики.) Ако |x|< k ; то y = z = e . Так как , то G не LL (k)- грамматика .
Адекватност. Да приемем, че G не е LL(k)-граматика.
След това изводите са два
че низовете x и y съвпадат в първите k позиции, но . Следователно и са различни правила от P и всяко от множествата 
И 
съдържа низа FIRST k (x), който съответства на низа FIRST k (y).
Пример 4.8. Граматика G, състояща се от две правила S -> aS | a , няма да бъде LL(1)-граматика, тъй като
ПЪРВИ 1 (aS) = ПЪРВИ 1 (a) = a.
Интуитивно това може да се обясни по следния начин: когато анализираме низ, който започва със знака a , виждаме само този първи знак, не знаем кое от правилата S -> aS или S -> a трябва да се приложи към S . От друга страна, G е LL(2)-граматика. Наистина, в обозначението на току-що представената теорема, ако , тогава A = S и . Тъй като за S са дадени само две определени правила, тогава и . Тъй като FIRST2(aS) = aa и FIRST2(a) = a, тогава според последната теорема G е LL (2)-граматика.
Премахване на лява рекурсия
Основната трудност при използването на прогнозен анализ е намирането на граматика за входния език, която може да се използва за изграждане на таблица за анализ с уникално дефинирани входове. Понякога, с някои прости трансформации, не-LL(1) граматика може да бъде редуцирана до еквивалентна LL(1) граматика. Сред тези трансформации лявото факторизиране и премахването на лява рекурсия са най-ефективни. Тук трябва да се направят две забележки. Първо, не всяка граматика става LL(1) след тези трансформации и второ, след такива трансформации получената граматика може да стане по-малко разбираема.
Непосредствената лява рекурсия, тоест рекурсията на формата , може да бъде премахната по следния начин. Първо, групираме A-правилата:
където нито един от редовете не започва с A . След това заместваме този набор от правила с
където A" е нов не-терминал. Същите вериги могат да бъдат извлечени от не-терминал A, както преди, но сега няма лява рекурсия. Тази процедура премахва всички непосредствени леви рекурсии, но не премахва лява рекурсия, включваща две или повече стъпки Дадени по-долу алгоритъм 4.8ви позволява да премахнете всички леви рекурсии от граматиката.
Алгоритъм 4.8. Премахване на лява рекурсия.
Вход. COP-граматика G без е-правила (от формата A -> e ).
Изход. COP-граматика G" без лява рекурсия, еквивалентна на G .
Метод. Следвайте стъпки 1 и 2.
(1) Подредете нетерминалите на граматиката G в произволен ред.
(2) Изпълнете следната процедура:
След (i-1)-та итерация на външния цикъл в стъпка 2 за всяко правило от формата 
, където k< i
, выполняется s >к. В резултат на това при следващата итерация (с i), вътрешният цикъл (с j) последователно увеличава долната граница с m във всяко правило 
докато m >= i . След това, след премахване на непосредствената лява рекурсия за A i -правила, m става по-голямо от i.
LL(k)-свойство налага големи ограничения върху граматиката. Понякога е възможно да се трансформира граматика, така че получената граматика да има свойство LL(1) . Такава трансформация в никакъв случай не е успешна, но ако сте успели да получите LL(1) граматика, тогава можете да използвате метода на рекурсивно спускане без връщане назад, за да изградите анализатор.
Да предположим, че трябва да изградим анализатор за езика, генериран от следната граматика:
д → д + T | д – T | T
T→T*F | T/F | Е
Е → бр | (д)
Задайте клеми ПЪРВИ(Т)също принадлежат към комплекта ПЪРВИ (E+T), така че не е възможно недвусмислено да се определи последователността от извиквания на процедури, които трябва да бъдат изпълнени при анализиране на входния низ. Проблемът е, че нетерминалният дсе среща в първата позиция на дясната страна на правило, чиято лява страна също е д. В такава ситуация нетерминалният дсе нарича директно ляво рекурсивен.
Нетерминален А COP-граматики ЖНаречен ляво рекурсивен ако граматиката има производна А =>* ах.
Граматика, която има поне едно ляво-рекурсивно правило, не може да бъде LL(1)-граматика.
От друга страна, известно е, че всеки CS-език се определя от поне една неляворекурсивна граматика.
Алгоритъм за ляво рекурсивно елиминиране
Позволявам G = (N, T, P, S)– CS-граматика и правило A→Aw 1 | ах 2 | … | ах н | v 1 | v 2 | … | v мпредставлява всички правила от Псъдържащи Аот лявата страна и нито една от веригите v азне започва с не-терминал А.
Да добавим към комплекта ндруг нетерминален а"и заменете правилата, съдържащи Аот лявата страна, към следното:
A→v 1 | v 2 | … | v м | v 1 а' | v 2 А' | … | v м а"
A' → w 1 | w 2 | … | w н | w 1 А' | w 2 А' | …| w н а"
Може да се докаже, че получената граматика е еквивалентна на оригиналната.
В резултат на прилагане на тази трансформация към горната граматика, описваща аритметични изрази, получаваме следната граматика:
д → T | TE"
д" → + T | + TE"
T → Е | FT"
T"→ * Е | * FT"
Е → (д) | бр
Лесно е да се покаже, че получената граматика има свойството LL(1).
Друг подобен проблем е свързан с факта, че две правила за един и същ нетерминал започват с едни и същи знаци.
Например,
S → if E then S else S
С → ако д тогава С
В този случай нека добавим друг нетерминал, който ще съответства на различните окончания на тези правила. Получаваме следните правила:
С → ако д тогава С С’
С" →
С"→ друго С
За получената граматика може да се приложи методът на рекурсивно спускане.
9.1.4. Рекурсивно спускане с обратно проследяване.
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ПЪРВОне се пресичат, което е сложен процес, така че на практика трик, наречен рекурсивно спускане с обратно проследяване .
За да направите това, лексикалния анализатор е представен като обект, който освен традиционните методи има сканиране, следващияи т.н., има и конструктор за копиране. След това, във всички ситуации, в които може да възникне двусмислие, преди да започнете синтактичния анализ, трябва да запомните текущото състояние на лексикалния анализатор (т.е. да направите копие на лексикалния анализатор) и да продължите парсването на текста, като се има предвид, че имаме работа с първия възможен строителство в тази ситуация. Ако този анализ е неуспешен, тогава възстановете състоянието на лексния инструмент и опитайте да анализирате отново същия фрагмент със следващата граматика и т. н. Ако всички анализи са неуспешни, се съобщава за грешка.
Този метод на синтактичен анализ е потенциално по-бавен от рекурсивното спускане без връщане назад, но в този случай е възможно да се запази граматиката в оригиналната й форма и да се спестят усилията на програмиста.
Особеността на формалните граматики е, че те позволяват да се дефинира безкраен набор от езикови вериги, използвайки краен набор от правила (разбира се, наборът от езикови вериги също може да бъде краен, но дори за прости реални езици това условие обикновено е не е доволен). Горната примерна граматика за десетични цели числа със знак дефинира безкраен набор от цели числа, използвайки 15 правила.
Способността да се използва краен набор от правила се постига в тази форма на писане на граматика чрез рекурсивни правила. Рекурсията в граматичните правила се изразява в това, че един от нетерминалните символи се дефинира чрез себе си. Рекурсията може да бъде директна (явна) - тогава символът се дефинира сам чрез себе си в едно правило или непряка (имплицитна) - тогава същото се случва чрез верига от правила.
В граматиката G, обсъдена по-горе, директната рекурсия присъства в правилото:<чс>-»<чс><цифра>, а в еквивалентната граматика G" - в правилото: T-VTF.
За да не бъде рекурсията безкрайна, за нетерминалния символ на граматиката, участваща в нея, трябва да има и други правила, които я дефинират, заобикаляйки себе си и позволяващи избягване на безкрайна рекурсивна дефиниция (в противен случай този символ просто не би са необходими в граматиката). Тези правила са<чс>-»<цифра>- в граматика G и T->F - в граматика G".
Нищо повече не може да се каже за рекурсията в теорията на формалните езици. Но за да разберем по-добре значението на рекурсията, можем да прибегнем до семантиката на езика - в примера, разгледан по-горе, това е езикът на целите десетични числа със знак. Нека разгледаме значението му.
Дефиниция на граматиката. Формата на ekusa-maura "ZO /
Ако се опитате да дефинирате какво е число, тогава можете да започнете с факта, че всяка цифра сама по себе си е число. Освен това можете да видите, че всеки две цифри също са число, след това три цифри и т.н. Ако изградите дефиниция на число по този начин, тогава тя никога няма да бъде завършена (в математиката битовият капацитет на числото не е ограничен от каквото и да било). Можете обаче да видите, че всеки път, когато генерираме ново число, ние просто добавяме едифрата отдясно (тъй като сме свикнали да пишем отляво надясно) към вече написаната поредица от числа. И тази поредица от цифри, започваща от една цифра, също е число на свой ред. Тогава дефиницията за понятието "число" може да бъде конструирана по следния начин: "число е всяка цифра или друго число, към което отдясно е добавена която и да е цифра." Това е, което представлява основата на граматичните правила G и G" и е отразено във втория ред на правилата в правилата<чс>-><цифра> [ <чс><цифра>и T->F | TF. Други правила в тези граматики ви позволяват да добавите знак към числото (първият ред от правила) и да дефинирате понятието "цифра" (третият ред от правила). Те са елементарни и не изискват обяснение.
Принципът на рекурсията (понякога наричан "принцип на итерация", който не променя същността) е важна концепция в идеята за формалните граматики. По един или друг начин, изрично или неявно, рекурсията винаги присъства в граматиките на всички реални езици за програмиране. Именно тя ви позволява да изградите безкраен брой вериги на езика и е невъзможно да се говори за тяхното поколение, без да се разбере принципът на рекурсията. Като правило, в граматиката на истински език? програмирането съдържа не едно, а цял набор от правила, изградени с помощта на рекурсия.
Други начини за дефиниране на граматики
Формата Backus-Naur е удобен, от формална гледна точка, но не винаги разбираем начин за писане на формални граматики. Рекурсивните дефиниции са добри за формален анализ на езикови вериги, но не са удобни от човешка гледна точка. Например какви правила<чс>-><цифра> | <чс><цифра>отразява способността да се изгради число за добавяне на произволен брой цифри отдясно, като се започне от едно, не е очевидно и изисква допълнително обяснение.
Но при създаването на език за програмиране е важно неговата граматика да бъде разбрана не само от тези, които ще създават компилатори за този език, но и от потребителите на езика - бъдещите разработчици на програми. Следователно има други начини за описание на правилата на формалните граматики, които са насочени към по-голяма разбираемост за човек.
Записване на граматически правила
използване на метасимволи
Записването на граматични правила с помощта на метасимволи предполага, че специални знаци могат да се появят в низа на граматичните правила - мета-
358 Глава 9. Официални езици и граматики
Символи – които имат специално значение и се третират по специален начин. Най-често използваните метасимволи са () (скоби), (квадратни скоби), () (къдрави скоби), "," (запетая) и "" (кавички). Тези метазнаци имат следното значение:
□ скобите означават този от всички низове, изброени вътре в тях
символите на дадено място от граматическото правило могат да бъдат само един
пъпка;
□ квадратни скоби означават, че посоченият в тях низ може да се срещне
Xia и може да не се срещат на това място правилата на граматиката (т.е.
може да бъде в него веднъж или нито веднъж);
□ къдрави скоби означават, че посоченият в тях низ може да не се среща
срещат се на дадено място граматически правила не веднъж, срещат се веднъж
веднъж или произволно много пъти;
□ запетая се използва за разделяне на поредици от знаци в кръг
скоби;
□ кавички се използват, когато е необходим един от метасимволите
включете във веригата по обичайния начин - тоест, когато една от скобите или извън нея
петият трябва да присъства в низа от знаци на езика (ако самият цитат
трябва да се включи във веригата от знаци, след което трябва да се повтори два пъти - това
принцип, познат на разработчиците на софтуер).
Ето как трябва да изглеждат правилата на G граматиката, обсъдени по-горе, ако са написани с помощта на метазнаци:
<число> -» [(+.-)]<цифра>{<цифра>}
<цифра> ->0|1|2|3|4|5|6|7|8|9
Вторият ред от правилата не се нуждае от коментари, а първото правило гласи така: „числото е низ от знаци, който може да започва със знаците + или -, трябва да съдържа още една цифра, която може да бъде последвана от последователност от произволен брой цифри." За разлика от формата на Backus-Naur, във формата на писане с помощта на метасимволи, както можете да видите, първо, неясен нетерминален символ се премахва от граматиката<чс>, и второ, беше възможно напълно да се премахне рекурсията. Граматиката е по-разбираема.
Метасимволната форма на правила е удобен и разбираем начин за представяне на граматически правила. В много случаи ви позволява напълно да се отървете от рекурсията, като я замените със символа за итерация () (къдрави скоби). Както ще стане ясно от следващия материал, тази форма се използва най-често за един от видовете граматики - обикновените граматики.
Писане на граматически правила графично
При писане на правила в графична форма, цялата граматика се представя под формата на набор от специално изградени диаграми. Тази форма беше предложена при описание на граматиката на езика Паскал и след това стана широко разпространена в литературата. Не е наличен за всички видове граматики, а само
Дефиниция на граматиката. Формуляр Backus-Naur 359
За контекстно-свободни и редовни типове, но това е достатъчно, за да се използва за описание на граматиките на известни езици за програмиране.
В тази форма на писане всеки нетерминален символ на граматиката съответства на диаграма, изградена под формата на насочен граф. Графът има следните типове върхове:
□ входна точка (не е обозначена по никакъв начин на диаграмата, просто започва
входната дъга на графиката);
□ нетерминален символ (обозначен с правоъгълник на диаграмата, в който
въведено е обозначението на символа);
□ верига от терминални символи (обозначени на диаграмата с овал, кръг
или правоъгълник със заоблени ръбове, вътре в който е вписано
пъпка);
□ опорна точка (обозначена с удебелена точка или запълнена
кръг);
□ изходна точка (не е отбелязана по никакъв начин, включва само изходната дъга на графиката).
Всяка диаграма има само една входна точка и една изходна точка, но колкото желаете върхове от останалите три типа. Върховете са свързани помежду си чрез насочени дъги на графа (линии със стрелки). Дъгите могат да излизат само от входна точка и да влизат само във входна точка. Дъгите могат както да влизат, така и да излизат от други върхове (в една добре оформена граматика всеки връх трябва да има поне един вход и поне един изход).
За да се конструира низ от символи, съответстващ на някакъв нетерминален символ на граматиката, трябва да се разгледа диаграмата за този символ. След това, започвайки от входната точка, е необходимо да се движите по дъгите на графиката на диаграмата през всякакви върхове до изходната точка. В този случай, преминавайки през върха, обозначен с нетерминален символ, този символ трябва да бъде поставен в получената верига. При преминаване през връх, посочен от низ от терминални символи, тези символи също трябва да бъдат поставени в резултантния низ. При преминаване през възловите точки на диаграмата над получената верига не е необходимо да се извършват никакви действия. През всеки връх на графиката на диаграмата, в зависимост от възможния път на движение, можете да преминете веднъж, не веднъж или толкова пъти, колкото искате. Веднага щом стигнем до изходната точка на диаграмата, изграждането на получената верига е завършено.
Полученият низ от своя страна може да съдържа нетерминални знаци. За да ги замените с вериги от терминални символи, трябва отново да разгледате диаграмите, съответстващи на тях. И така нататък, докато във веригата останат само крайни знаци. Очевидно, за да се изгради верига от символи на даден език, трябва да се започне с диаграмата на целевия символ на граматиката.
Това е удобен начин за описание на правилата на граматиката, работещи с изображения и следователно фокусирани изключително върху хората. Дори простото представяне на основните му принципи тук се оказа доста тромаво, докато същността
Глава 9
Методът е доста прост. Това може лесно да се види, ако погледнете описанието на понятието "число" от граматиката G, като използвате диаграмите на фиг. 9.1.
Ориз. 9.1. Графично представяне на граматиката на целите десетични числа със знак: най-отгоре - за понятието "число"; по-долу - за понятието "цифра"
Както бе споменато по-горе, този метод се използва главно в литературата при представяне на граматиките на езиците за програмиране. За потребителите - разработчици на софтуер - това е удобно, но практическо приложениевсе още не съществува в компилаторите.
Класификация на езиците и граматики
По-горе вече бяха споменати различни видове граматики, но не беше посочено как и на каква основа те се разделят на видове. За един човек езиците могат да бъдат прости и сложни, но това е чисто субективно мнение, което често зависи от личността на човека.
За компилаторите езиците също могат да бъдат разделени на прости и сложни, но в този случай има строги критерии за това разделение. Както ще бъде показано по-долу, в зависимост от това към какъв тип принадлежи определен език за програмиране,
Дефиницията зависи от сложността на разпознавателя за този език. Колкото по-сложен е езикът, толкова по-високи са изчислителните разходи на компилатора за анализ на веригите на изходната програма, написана на този език, и следователно, толкова по-сложен е самият компилатор и неговата структура. За някои видове езици по принцип е невъзможно да се изгради компилатор, който да анализира изходните текстове на тези езици за приемливо време въз основа на ограничени изчислителни ресурси (поради което все още е невъзможно да се създават програми на естествени езици, например на руски или английски).
Граматическа класификация.
Граматика, съдържаща лява рекурсия, не е LL(1) граматика. Обмислете правилата
А→ аа(лява рекурсия в A)
А→ а
Тук азнак предшественик и за двата нетерминални варианта А. По същия начин, граматика, съдържаща ляв рекурсивен цикъл, не може да бъде LL(1) граматика, например
А→ пр.н.е
б→ CD
° С→ AE
Граматика, съдържаща ляв рекурсивен цикъл, може да бъде преобразувана в граматика, съдържаща само директна лява рекурсия, и освен това, чрез въвеждане на допълнителни нетерминали, лявата рекурсия може да бъде напълно елиминирана (всъщност тя се заменя с дясна рекурсия, която не е проблем по отношение на LL(1) -свойства).
Като пример, разгледайте граматика с генеративни правила
С→ аа
А→ bb
б→ вв
° С→ Dd
° С→ д
д→ аз
който има ляв рекурсивен цикъл, включващ A, B, C, D. За да заменим този цикъл с директна лява рекурсия, подреждаме нетерминалите, както следва: S, A, B, C, D.
Обмислете всички правила за генериране на формата
Xi→ Xj γ,
Където XiИ Xjса нетерминални и γ – низ от крайни и нетерминални знаци. По отношение на правилата, за които j ≥ i, не се предприемат действия. Това неравенство обаче не може да се приложи за всички правила, ако има ляв рекурсивен цикъл. С реда, който сме избрали, имаме работа с едно правило:
д→ аз
защото Апредшестван дв този ред. Сега нека започнем с подмяната А, използвайки всички правила, които имат Аотляво. В резултат на това получаваме
д→ bbz
Тъй като бпредшестван дпри подреждане процесът се повтаря, като се дава правилото:
д→ ccbz
След това се повтаря още веднъж и дава две правила:
д→ ecbz
д→ Ddcbz
Сега преобразуваната граматика изглежда така:
С→ аа
А→ bb
б→ вв
° С→ Dd
° С→ д
д→ Ddcbz
д→ ecbz
Всички тези правила за генериране имат необходимата форма и левият рекурсивен цикъл се заменя с директна лява рекурсия. За да елиминираме директната лява рекурсия, въвеждаме нов нетерминален символ Зи промени правилата
д→ ecbz
д→ Ddcbz
д→ ecbz
д→ ecbzZ
З→ dcbz
З→ dcbzZ
Имайте предвид, че преди и след трансформацията дгенерира регулярен израз
(ecbz) (dcbz)*
Обобщавайки, може да се покаже, че ако нетерминал Асе появява от лявата страна r+ сгенериране на правила, rот които използват директна лява рекурсия и с- не, т.е.
А→ Aα 1, А→ Aα 2,..., А→ Aα r
А→ β 1, А→ β 2,..., А→ β с
тогава тези правила могат да бъдат заменени със следното:
Неформално доказателство е, че преди и след трансформацията Агенерира регулярен израз ( β 1 | β 2 |... | β с) ( α 1 | α 2 |... | α r)*
Трябва да се отбележи, че като елиминираме лявата рекурсия (или левия рекурсивен цикъл), все още не получаваме LL(1) граматика, тъй като за някои нетерминали, от лявата страна на правилата на получените граматики, има алтернативни десни части, които започват със същите знаци. Следователно, след елиминиране на лявата рекурсия, трябва да се продължи трансформацията на граматиката във формата LL(1).
17. Преобразуване на граматики във форма LL(1). Факторизация.
Факторизация
В много ситуации граматиките, които нямат функцията LL(1), могат да бъдат преобразувани в граматики LL(1), като се използва процесът на факторизиране. Нека разгледаме пример за такава ситуация.
П→ начало д; СЪСкрай
д→ д, д
д→ д
СЪС→ с; СЪС
СЪС→ с
В процеса на факторизация заместваме няколко правила за един нетерминал от лявата страна, чиято дясна страна започва със същия символ (низ от символи) с едно правило, където от дясната страна общото начало е последвано от допълнително въведен нетерминал. Граматиката е допълнена и с правила за допълнителен нетерминал, според който от него се извличат различни „остатъци“ от оригиналната дясна страна на правилото. За граматиката по-горе това би дало следната LL(1) граматика:
П→ начало д; СЪСкрай
д→ dX х)
х→ , д(според 1-во правило за доригинална граматика за дследва, д)
х→ ε (според 2-ро правило за доригинална граматика за днищо (празен низ)
СЪС→ s Y(въвеждаме допълнителен нетерминал Y)
Y→ ; СЪС(според 1-во правило за ° Соригинална граматика за сследва; ° С)
Y→ ε (според 2-ро правило за ° Соригинална граматика за снищо (празен низ)
По същия начин, генериране на правила
С→ aSb
С→ аск
С→ ε
могат да бъдат преобразувани чрез факторизация в правила
С→ aSX
С→ ε
х→ b
х→ ° С
и получената граматика ще бъде LL(1). Процесът на факторизиране обаче не може да бъде автоматизиран чрез разширяването му към общия случай. Следващият пример показва какво може да се случи. Обмислете правилата
1. П→ Qx
2. П→ Рай
3. Q→ кв.м
4. Q→ р
5. Р→ sRn
6. Р→ r
И двата комплекта водещи знаци за две опции Псъдържат с, и се опитва да „издържи сизвън скоби", заместваме QИ Рв десните части на правила 1 и 2:
П→ sQmx
П→ sRny
П→ qx
П→ ри
Тези правила могат да бъдат заменени със следното:
П→ qx
П→ ри
П→ sp 1
П 1 → Qmx
П 1 → Rny
Правила за P1подобни на оригиналните правила за Пи имат припокриващи се набори от водещи знаци. Можем да трансформираме тези правила по същия начин като правилата за П:
П 1 → sQmmx
П 1 → qmx
П 1 → sRny
П 1 → rny
Факторинг, получаваме