Gramatica analizând o expresie

O gramatică de analiză a expresiei (PB-gramatică) este un tip de gramatică formală analitică care descrie un limbaj formal în termenii unui set de reguli pentru recunoașterea șirurilor de limbă. O gramatică care parsează o expresie este, în esență, un parser de descendență recursiv într-o formă pur schematică care exprimă doar sintaxa și este independentă de implementarea sau utilizarea particulară a parserului. Gramaticile de analiză a expresiei sunt similare cu expresiile regulate și cu gramaticile fără context (CFG) în notația Backus-Naur , dar au o interpretare diferită.

Spre deosebire de gramaticile COP, gramaticile PB nu pot fi ambigue : dacă un șir este analizat, atunci există exact un arbore de analiză. Acest lucru face ca RE-gramaticile să fie adecvate pentru limbaje informatice, dar nu și pentru limbaje naturale.

Definiție

Formal, gramatica care analizează o expresie constă în:

Fiecare regulă de inferență din P are forma A ← e, unde A este un simbol non-terminal și e este o expresie de analiză. O expresie de analiză este o expresie ierarhică similară cu o expresie regulată care este construită astfel:

  1. O expresie de analiză atomică constă din:
    • orice caracter terminal,
    • orice simbol non-terminal sau
    • șir gol ε.
  2. Având în vedere expresiile de analiză e, e 1 și e 2 , următoarele instrucțiuni generează noi expresii de analizare:
    • Secvență: e 1 e 2
    • Selecție ordonată: e 1 / e 2
    • Zero sau mai multe: e*
    • Una sau mai multe: e+
    • Opțional: e?
    • Și predicat: &e
    • NU predicat: !e

Diferența fundamentală dintre o gramatică PB și o gramatică COP este că operatorul de alegere al gramaticii PB este ordonat . Dacă prima alternativă funcționează, atunci toate cele ulterioare sunt ignorate . Astfel, alegerea ordonată nu este comutativă, spre deosebire de definițiile din cărți ale gramaticilor fără context și ale expresiilor regulate. Selecția ordonată este similară cu operatorul soft cut în unele limbaje de programare logice.

În consecință, la conversia unui CFG direct într-un RTG, orice ambiguitate este rezolvată determinist în favoarea unuia dintre arborii de analiză posibil. Alegând cu atenție ordinea în care sunt specificate alternativele gramaticale, programatorul poate obține un control considerabil asupra arborelui de analiză ales.

La fel ca gramaticile booleene fără context, gramaticile RE au predicate AND- și NOT-. Ele ajută la dezambiguizarea în continuare dacă reordonarea alternativelor nu poate produce arborele de analiză dorit.

Interpretarea expresiilor analizate

Fiecare non-terminal dintr-o gramatică PB este în esență o funcție de parser într-un parser recursiv de descendență, iar expresia parser-ului corespunzătoare este „codul” acelei funcții. Fiecare funcție de analiză ia un șir ca intrare și produce unul dintre următoarele rezultate:

Un nonterminal poate reuși fără a absorbi intrarea, iar această stare este diferită de eșec.

O expresie de analiză atomică constând dintr-un singur terminal reușește dacă primul caracter al șirului de intrare se potrivește și îl consumă. În caz contrar, rezultatul este nereușit. O expresie atomică dintr-un șir gol reușește întotdeauna fără a fi consumată. O expresie atomică constând din non-terminalul A este un apel recursiv la funcția non-terminală A .

Operatorul de secvență e 1 e 2 apelează mai întâi e 1 și, dacă e 1 reușește, apoi apelează e 2 pe partea șirului rămas neconsumat de e 1 și returnează rezultatul. Dacă e 1 sau e 2 eșuează, atunci eșuează și operatorul de secvență e 1 e 2 .

Instrucțiunea de selecție e 1 / e 2 apelează mai întâi e 1 și, dacă e 1 reușește, returnează rezultatul său. În caz contrar, dacă e 1 eșuează, instrucțiunea select restabilește șirul de intrare la starea anterioară apelării e 1 și apelează e 2 , returnând rezultatul acestuia.

Operatorii zero sau mai mulți, unul sau mai mulți și opționali consumă zero sau mai mulți, unul sau mai mulți sau zero sau o apariție consecutivă a subexpresiei lor e , respectiv . Spre deosebire de CFG-uri și expresiile regulate, acești operatori sunt întotdeauna lacomi și consumă cât mai multe instanțe de intrare. (Expresiile obișnuite încep cu lăcomie, dar apoi revin la eșec și încearcă să găsească o secvență mai scurtă.) De exemplu, expresia a* va consuma întotdeauna toate a-urile disponibile, iar expresia (a* a) va eșua întotdeauna, deoarece după ce prima parte a a* este executată, nu mai există a-uri pentru a doua.

În cele din urmă, AND-predicate și NOT-predicate implementează predicate sintactice. Expresia & e apelează subexpresia e și returnează succes dacă e reușește și eșec în caz contrar, dar nu consumă niciodată intrarea. La fel, expresia ! e reușește dacă e eșuează și eșuează dacă e reușește, din nou fără a absorbi intrarea. Deoarece expresia e poate fi un construct arbitrar complex care poate fi evaluat „în avans” fără a consuma șirul de intrare, aceste predicate oferă instrumente puternice de pregătire și dezambiguizare sintactică.

Exemple

Următoarea gramatică RW recunoaște formule matematice cu patru operații pe numere întregi nenegative.

Valoare ← [0-9]+ / '(' Expr ')' Produs ← Valoare (('*' / '/') Valoare)* Sumă ← Produs (('+' / '-') Produs)* Expr ← Sumă

În exemplul de mai sus, caracterele terminale sunt caractere text reprezentate de caractere cu ghilimele simple, cum ar fi '('și ')'. Un interval [0-9]este o abreviere pentru zece caractere reprezentând numerele de la 0 la 9. (Aceasta este aceeași sintaxă ca și pentru expresiile regulate). Simbolurile non-terminale sunt simboluri pentru care există reguli de ieșire: Valoare , Produs , Sumă și Expr .

Exemplele de mai jos nu au ghilimele pentru a îmbunătăți lizibilitatea. Literele mici sunt caractere terminale, iar majusculele cursive sunt non-terminale. Analizoarele reale de gramatică PB necesită ghilimele.

Expresia de analiză (a/b)* se potrivește și consumă secvențe de lungime arbitrară de la a și b. Regula S ← a S ? b descrie un limbaj simplu, fără context . Următoarea gramatică RW descrie un limbaj clasic, fără context :

S ← &(A 'c') 'a'+ B !('a' / 'b' / 'c') A ← „a” A? 'b' B ← „b” B? 'c'

Următoarea regulă recursivă se potrivește cu o instrucțiune standard C if/then/else, astfel încât un bloc opțional else se potrivește întotdeauna cu cel mai interior if. (Într-o gramatică fără context, acest lucru ar duce la clasica ambiguitate de altfel.)

S ← „dacă” C „atunci” S „altfel” S / „dacă” C „atunci” S

Expresia de analiză foo &(bar) se potrivește și consumă textul „foo”, dar numai dacă este urmată de textul „bar”. Expresia de analiză foo !(bar) consumă textul „foo” doar dacă nu este urmat de „bar”. Expresia !(a+ b) a ia un singur caracter „a”, dar numai dacă nu este primul dintr-o succesiune de lungime arbitrară a lui a urmată de b.

Următoarea regulă recursivă corespunde unui comentariu Pascal imbricat. Caracterele comentariilor sunt cuprinse între ghilimele simple pentru a le distinge de operatorii RVG.

Începe ← „(*” Sfârșit ← '*)' C ← Început N* Sfârșit N ← C / (!Început !Sfârșit Z) Z ← orice caracter

Implementarea parserilor gramatici RW

Orice gramatică RH poate fi convertită direct într-un parser prin descendență recursivă. Datorită capacității de pregătire nelimitată, analizatorul rezultat poate rula, în cel mai rău caz, în timp exponențial.

Prin amintirea rezultatului pașilor intermediari de analiză și asigurându-vă că fiecare funcție de parser este apelată nu mai mult de o dată pentru o anumită poziție a datelor de intrare, este posibil să se transforme orice gramatică PB într-un parser packrat care rulează întotdeauna în timp liniar la costul unei creșteri semnificative a costurilor de memorie.

Un parser packrat este un fel de parser care funcționează într-un mod similar cu descendența recursivă, cu excepția faptului că, atunci când analizează, își amintește rezultatele intermediare ale tuturor apelurilor la funcțiile de parsare recursive reciproce. Din această cauză, analizatorul packrat este capabil să analizeze multe gramatici fără context și orice gramatică PB (inclusiv unele care generează limbaje fără context) în timp liniar [1] .

Este, de asemenea, posibil să construiți un parser LL și un parser LR pentru gramaticile RW, dar capacitatea de pre-parsare nerestricționată este pierdută în acest caz.

Avantaje

REGRAM-urile sunt substitute bune pentru expresiile regulate, deoarece sunt strict mai puternice. De exemplu, o expresie regulată este în mod fundamental incapabilă de a găsi perechi de paranteze care se potrivesc, deoarece este nerecursivă, spre deosebire de o gramatică RE.

Orice gramatică RH poate fi analizată în timp liniar folosind analizatorul packrat așa cum este descris mai sus.

Analizoarele pentru limbile reprezentate de gramatici COP, cum ar fi analizatorii LR, necesită un pas special de analiză lexicală care împarte intrarea în funcție de spații, punctuație și așa mai departe. Acest lucru este necesar deoarece acești analizatori folosesc pre-analizarea pentru a procesa unele CFG-uri în timp liniar. Gramaticile RW nu necesită un pas separat de analiză lexicală, iar regulile pentru aceasta pot fi stabilite împreună cu alte reguli gramaticale.

Multe gramatici COP conțin ambiguități semnificative, chiar și atunci când ar trebui să descrie limbaje cu o singură valoare. Problema „hanging else” în C, C++ și Java este un exemplu al acestui fenomen. Aceste probleme sunt adesea rezolvate prin aplicarea unei reguli externe gramaticii. Într-o gramatică PB, aceste ambiguități nu apar niciodată din cauza prioritizării.

Dezavantaje

Consumul de memorie

Analiza unei gramatici PB este de obicei realizată de un parser packrat care își amintește pașii suplimentari de analizare. O astfel de analizare necesită ca datele să fie stocate proporțional cu lungimea intrării, spre deosebire de adâncimea arborelui de analiză pentru analizatoarele LR. Acesta este un câștig semnificativ în multe domenii: de exemplu, codul scris de om tinde să aibă o adâncime de imbricare aproape constantă, indiferent de lungimea programului - expresiile mai profunde decât o anumită cantitate sunt de obicei refactorizate.

Pentru unele gramatici și unele intrări, adâncimea arborelui de analiză poate fi proporțională cu lungimea intrării, așa că pentru o evaluare care nu ia în considerare această măsură, un parser packrat poate apărea la fel de bun ca un parser LR. Aceasta este similară cu situația cu algoritmii grafici: Bellman-Ford și Floyd-Warshall au un timp de execuție ( ) dacă este luat în considerare numai numărul de vârfuri. Cu toate acestea, o analiză mai precisă, ținând cont de numărul de muchii, arată timpul de execuție al algoritmului Bellman-Ford , care este doar pătratic cu dimensiunea intrării, nu cubic.

Recursie la stânga indirectă

RE-gramaticile nu pot conține reguli recursive la stânga care se numesc fără avansare de linie. De exemplu, în gramatica aritmetică descrisă mai sus, aș dori să mutăm câteva reguli, astfel încât precedența produsului și a sumei să poată fi exprimate într-o singură linie:

Valoare ← [0-9.]+ / '(' Expr ')' Produs ← Expr (('*' / '/') Expr)* Sumă ← Expr (('+' / '-') Expr)* Expr ← Produs / Sumă / Valoare

Problema aici este că, pentru a obține un hit pentru Expr , trebuie să verificați dacă Product se declanșează , iar pentru a verifica Product , trebuie mai întâi să verificați Expr . Și acest lucru este imposibil.

Cu toate acestea, regulile recursive stânga pot fi întotdeauna rescrise pentru a elimina recursiunea stângă. De exemplu, o regulă recursiva la stânga poate repeta o anumită expresie la nesfârșit, ca în regula CF-gramatică:

șir-de-a ← șir-de-a „a” | 'A'

Acest lucru poate fi rescris într-o gramatică PB folosind operatorul +:

șir-de-a ← „a”+

Cu unele modificări, este posibil să se facă un parser packrat obișnuit să suporte recursiunea directă la stânga [1] [2] [3] .

Totuși, procesul de rescriere a regulilor indirecte recursive stânga este dificil, mai ales atunci când au loc acțiuni semantice. Deși teoretic este posibil, nu există un parser RW care să accepte recursiunea la stânga indirectă, în timp ce toți analizatorii GLR o fac.

Subtile erori gramaticale

Pentru a exprima o gramatică ca gramatică PB, autorul ei trebuie să convertească toate cazurile de alegere nedeterministă în alegere ordonată. Din păcate, acest proces este predispus la erori și adesea are ca rezultat gramaticile care analizează incorect o parte din input.

Expresivitatea

Analizatorii Packrat nu pot analiza unele gramatici clare, cum ar fi următoarele [4] :

S ← „x” S „x” | 'X'

Dezvoltare

Gramaticile RE sunt noi și nu sunt utilizate pe scară largă. Expresiile regulate și gramaticile COP, pe de altă parte, există de zeci de ani, codul care le analizează a fost îmbunătățit și optimizat, iar programatorii au experiență în utilizarea lor.

Link -uri

Note

  1. ↑ 1 2 Ford, Bryan Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking . Massachusetts Institute of Technology (septembrie 2002). Data accesului: 27 iulie 2007. Arhivat din original pe 2 aprilie 2012.
  2. ↑ Alessandro Warth, James R. Douglass, Todd Millstein. Analizoarele Packrat pot suporta recursiunea la  stânga . - Institutul de Cercetare Viewpoints, 2008. - Ianuarie.
  3. ↑ Ruedi Steinmann. Gestionarea recursiunii stângi în analizatoarele Packrat  (neopr.) . - 2009. - Martie. Arhivat din original pe 6 iulie 2011. Copie arhivată (link indisponibil) . Consultat la 17 iunie 2009. Arhivat din original pe 6 iulie 2011. 
  4. ↑ Bryan Ford. Perla funcțională: Packrat Analizare: simplă, puternică, leneșă, timp liniar  (engleză)  : jurnal. — 2002.