Съставители: Каква е разликата между LL (0) и LR (0) парсери. Има ли такова нещо като LL (0) парсери?


Отговор 1:

Този въпрос изглежда е фокусиран върху LL (0) парсери, така че нека ги дефинираме. LL (0) анализатор, анализира отляво надясно, използвайки 0 символа в началото на производството, за да определи коя продукция да се приложи. Какво означава това 0 токена, това означава, че анализаторът не може да използва анализирания текст, за да определи коя продукция да приложи. Това означава, че анализаторът не може да направи никакъв избор. Той трябва да знае, преди да започне да анализира точно последователността на маркери, които ще анализира. Последователността на маркери трябва да бъде фиксирана, което означава, че може да има само една последователност, която анализаторът ще анализира. Така бихте могли да имате анализатор, който приема „Здравей свят!“ с граматика като тази:

цел: удивителен знак „Здравей“, бяло пространство „свят“;

Обърнете внимание, че единствените разрешени варианти са как лексерът съответства на маркерите.

(Надявам се, че обозначението е очевидно - това е по същество този, който използвам в Yacc ++. Цитираните низове са символи, както и всички идентификатори, които не са дефинирани.)

Анализаторът винаги очаква точно същата последователност на маркери. Не е необходимо да има само едно правило, както направи първият ни пример. Може да изглежда така.

цел: здрава част бяла област крайна част;

здравей част: здравей1;

здравей1: "Здравей";

крайна част: световна част последна част;

world-part: „свят“;

последна част: "!";

Все пак забележете как нито едно от правилата няма оператори "или" (|) и има само едно правило за нетерминален. Това позволява на парсера да знае как да съпостави всяко правило, без да използва никакви дискриминиращи маркери (маркери, които избират по кой път се анализира), което прави граматиката LL (0).

Възможно ли е да се използва рекурсивна продукция и все пак да има LL (0) граматика? Отговорът е „не“. Нека видим какво ще стане, ако имаме рекурсивно правило.

цел: "x" цел "y";

Не забравяйте, че ни е разрешено само едно правило за нетерминални оператори и няма оператори "или". По този начин, когато стигнем до рекурсивното извикване на целта, трябва да ни отведем по път, по който отново ще стигнем до онзи рекурсивен призив, безкраен цикъл. Докажете на себе си, няма значение как да вложим това извикване или дали рекурсията е косвена. Това винаги ще доведе до безкраен цикъл.

По този начин граматиката на LL (0) трябва да анализира ограничен списък от символи, точно един краен списък (един и същ списък всеки път).

Забележете разликата в значението на LR (0). LR (k) анализаторът може да използва всякакви (колкото иска) токени в рамките на продукцията, за да дискриминира, плюс до k жетони от контекста, когато производството намалява, за да определи дали трябва да намали. В случая LR (0) той не може да използва допълнителни символи, за да определи дали трябва да намали. Трябва просто да вземе решение въз основа на жетоните в правилото, които са намалени. Ето една проста LR (0) граматика:

цел: "x" | "(" цел ")";

Тази граматика анализира „х“, заобиколена от някакъв брой скоби. Обърнете внимание, че той може да използва токена "x" и токена "(", за да реши кое правило да приложи. 0 в LR (0) не ограничава използването на маркери в рамките на правило, както 0 в LL (0) прави. Единственото нещо, което ограничава, е използването на маркери (на контекста, след правилото при някаква употреба на нетерминала), когато решите да намалите. Тази граматика не се нуждае от контекст, за да реши да намали. При първата алтернатива, тя намалява, когато виждате "x" на секундата, тя намалява, след като види ")". Токените в рамките на правило определят точно кога правилото трябва да се намали.


Отговор 2:

LL (0) парсери означава, че обработват токеновия поток отляво надясно, използвайки деривация отляво, без да гледат напред. Теоретично, LL (0) парсери са възможни, но дори и да съществуват, не виждам голяма полза за тях. LL (0) анализаторите ще трябва да предвидят кои производства да се прилагат въз основа на текущия не-терминал с нулев поглед напред. В такива граматики всеки не терминал може да има само едно производство, свързано с него и не трябва да има рекурсия.

LR (0) парсери означават, че обработват токеновия поток отляво надясно, като използват дериват на дясно с нулев поглед напред. Това означава, че те изграждат дървото на анализа отдолу нагоре, докато LL (0) парсерите изграждат дървото на анализа отгоре надолу.