Jaka jest różnica między Left Factoring i Left Recursion? Rozumiem, że Left factoring jest predykcyjną metodą odgórnego parsowania. Ale denerwuję się, gdy słyszę te dwa terminy.Różnica między lewicowym czynnikiem a lewą rekurencją
ten sposób Widziałem dwa terminy używane:
lewa rekursja: = gdy lewy non-terminal jest taki sam jak prawy non-terminal. Przykład: A-> A & | B gdzie & jest alfa. Możemy usunąć lewy ricursion używając przepisać tę produkcję jak.
A-> BA” A '-> & A' | €
Lewa czynnik nie powinien oznaczać productn non deterministyczny. . Przykład: A-> & A | & B | & C
Lewy Faktoring to technika transformacji gramatyki. Składa się z prefiksów "faktoringowych", które są wspólne dla dwóch lub więcej produkcji.
Na przykład, począwszy od:
A -> α β | α y
do:
A -> alfa A '
A' -> β | γ
Lewy Recursion jest właściwością gramatyki ma kiedy można czerpać z danej zmiennej (bez zacisku) do prawa oś, która zaczyna się od tej samej zmiennej, w jednym lub kilku etapach.
Na przykład:
A -> A alfa
lub
A -> B α
B -> A γ
Istnieje technika transformacji gramatyki o nazwie Eliminacja lewej rekursji, która zapewnia metodę generowania, biorąc pod uwagę gramatykę lewej rekurencji, innej gramatyki, która jest równoważna i nie jest pozostawiona rekurencyjnie.
Relacja/pomylenie obu kategoriach prawdopodobnie wynika z faktu, że obie techniki transformacji może muszą być stosowane do gramatyki, zanim będzie mógł czerpać predykcyjną odgórne parser dla niego.
Lewa faktoring usuwa wspólny lewy współczynnik, który pojawia się w dwóch produkcjach tego samego nie-terminala. Ma to na celu uniknięcie śledzenia wstecznego przez analizator składni. Załóżmy, że analizator składni ma wyprzedzeniem, rozważ ten przykład:
A -> qB | qC
gdzie A, B, C są nie-terminalami, a q jest zdaniem. W takim przypadku analizator składni nie będzie wiedział, która z dwóch wersji do wyboru i może wymagać śledzenia wstecznego. Po lewej faktoringu gramatykę przekształca To-
A -> QD
D -> B | C
W tym przypadku parser z wyprzedzeniem zawsze wybierze odpowiednią produkcję.
Lewa rekursja to przypadek, w którym najbardziej lewostronna nie-końcowa w produkcji nie-końcowej jest sama nie-końcowa (bezpośrednia rekursja po lewej) lub przez inne nieterminalne definicje, przepisuje ją na nie-końcową. terminal ponownie (pośrednia lewa rekursja). rozważyć następujące przykłady -
(1) A -> Aq (bezpośrednie)
(2) A -> Bq B -> Ar (pośredniej)
lewej rekursji musi być usunięty, gdy parser wykonuje odgórne parsowania
Lewa rekursji: gramatyki pozostało rekurencyjne jeśli ma nieterminalowi A takie, że istnieje wyprowadzenie A -> Aa | β gdzie α i β są sekwencjami terminali i nieterminali, które nie zaczynają się od A.
Podczas projektowania analizatora w dół, jeśli lewa rekursja istnieje w gramatyce, to analizator składniowy wpada w nieskończoną pętlę, ponieważ A próbuje dopasować A, co nie jest możliwe. Możemy wyeliminować powyższą lewą rekursję, przepisując szkodliwą produkcję.As-
A -> βA '
A' -> αA”| epsilon
Lewe faktoring: Lewa faktoring jest wymagana w celu wyeliminowania niedeterminizmu gramatyki. Załóżmy, że gramatyka, S -> abS | aSb
W tym przypadku S wyprowadza ten sam terminal a w regule produkcji (dwa alternatywne wybory dla S), które wynikają z braku determinizmu. Możemy przerobić produkcję odroczyć decyzję S as-
S -> AS '
S' -> BS | Sb
Zatem S”może być zastąpione przez BS lub SB
lewo czynnika:
Niech daną gramatykę: A -> AB1 | ab2 | ab3
1) widzimy, że dla każdej produkcji istnieje wspólny przedrostek & jeśli wybierzemy dowolną produkcję tutaj, nie jest potwierdzone, że nie będziemy musieli się wycofywać.
2) nie jest deterministyczny, ponieważ nie możemy wybrać żadnej produkcji i możemy być pewni, że osiągniemy pożądany ciąg przez utworzenie właściwego drzewa parsowania. , ale jeśli zmienimy gramatykę w sposób deterministyczny i pozostawiamy nas na tyle elastycznego, aby stworzyć dowolny ciąg, który może być możliwy bez cofania ... będzie to:
A -> aA ' , A '-> b1 | b2 | b3 teraz, jeśli zostaniemy poproszeni o zrobienie drzewa parse dla ciągu ab2 .... nie potrzebujemy śledzenia wstecznego. Ponieważ zawsze możemy wybrać prawidłową produkcję, gdy otrzymamy A ', wygenerujemy poprawne drzewo analizy.
Lewa rekursja:
A -> Aa | b Tutaj jest jasne, że lewe dziecko z A zawsze będzie A, jeśli wybierzemy pierwszą produkcję, to jest lewostronna rekurencja, ponieważ A wywołuje się w kółko. wygenerowany ciąg znaków z tej gramatyki jest: ba * ponieważ to nie może być w gramatyce ... eliminujemy lewej rekursji pisząc:
A -> ba ' A' -> E | aA ' teraz nie będziemy mieli lewej rekursji, a także możemy wygenerować ba *.