Zastanawiam się, czy ANTLR v3, który przedstawia swój wewnętrzny algorytm analizy parsowania jako "LL (*)", jest w pełni reprezentatywny dla analizatorów PEG (analizowanie składni PEG).LL (*) kontra parowniki PEG: jaka jest różnica?
Czy jest jakaś różnica?
ANTLR article nie spełniał warunków PEG.
LL (*) jest podzbiorem DCFG (deterministycznej gramatyki bezkontekstowej), która jest podzbiorem CFG (Gramatyka bezkontekstowa).
PEG może wyrazić kontekstową gramatyk jak A{n}B{n}C{n}, w których A i B i C wszystkich występujących n razy. Oto definicja:
s := &(x C) A+ y/ε
x := A x B/A B
y := B y C/B C
Ale nie ma sposobu, aby określić taką gramatykę w CFG (dowód lematu polega pompy). Tak więc PEG nie jest podzbiorem CFG. Czy PEG jest nadzbiorem CFG? Nie wiem
Dwie główne różnice między LL (*) i PEG:
LL (*) mogą tylko uprzedzona wzór DFA, a PEG może uprzedzona rekurencyjnego wzoru. Na przykład w PEG możesz wczytać parens zagnieżdżone, podczas gdy LL (*) nie może.
Operator wybór / w PEG jest priorytetem wybór (lub „zaborczy”), co oznacza, że jeśli masz regułę A/AB, nigdy nie osiągnie prawą stronę AB. W LL (*) dla reguły A | AB możliwe jest dopasowanie AB.
Jeśli masz gramatyki PEG bez uprzedzona, czy Twój wzór uprzedzona może być zmniejszona do DFA, to można przełożyć na LL (*). Jeśli nie, to nie jest możliwe.
Zgodnie z narzędzi wymienionych here ANTLR jest pełnoprawnym przedstawicielem PEG parsera:
antlr, ugruntowanym parser generator Terence Parr, obsługuje rozbudowane funkcje PEG i łączy packrat parsowania z technik analizowania LL .
Istnieje kilka lewicowo-rekurencyjnych rozszerzeń Packrat, które najwyraźniej nie są obsługiwane przez ANTLR. –
W antlr można włączyć globalną wycofywania wszystkich zasad produkcji w swojej gramatyki, tak że dla k >= 1 można przetworzyć niemal tak samo jak PEG. Oczywiście, ze względu na cały potencjalny backtrack, czas działania parsera ulega degradacji. Kosztem (pewnej) pamięci można również włączyć zapamiętywanie, dzięki czemu zachowuje się jak analizator Packrat, który potrafi analizować dane wejściowe w czasie liniowym.
Tak, nie ma dużej różnicy w.r.t ANTLR i PEG/Packrat (z odpowiednimi prawymi opcjami!).
ANTLR i PEG to nie to samo. To jest dość teoretyczne pytanie i myślę, że najlepiej będzie, jeśli powinieneś zapoznać się z artykułem autorstwa Terrence'a Parra, w którym dokładnie wskazuje on na różnice między ANTLR i PEG oraz niektóre zalety strategii analizy ANTLR LL (*). Nie chcę dać sobie wolności do parafrazowania tego, co tam napisał, ale lepiej, żebyś przeczytał całą gazetę.
404-ed. Czy możesz podać zaktualizowany link? – chakrit
Gramatyka PEG nie jest jeszcze poprawna. Spowoduje również zanalizowanie A {n} B {n + 1} C {n + 1}. – CoronA
@CoronA Dzięki za wskazanie, zredagowałem odpowiedź z poprawioną gramatyką, aby upewnić się, że C ma miejsce tuż po A {n} B {n}. – luikore