GLR risorse algoritmo di analisi

Question

Sto scrivendo un GLR generatore di parser e vorrei qualche consiglio su risorse relative a questo algoritmo sia su internet e della varietà dead-tree ( libri per chi non conosce il geek-parlare).

Lo so Bison può generare parser GLR, e dato che è sotto la licenza GPL che può esaminare il suo codice, ma sarebbe bello avere una descrizione completa dell'algoritmo.

Così, qualcuno sa di eventuali buone risorse là fuori che posso fare uso di? Grazie.

Answer 1

Alcune cose buone che ho incontrato prima linea:

• Elkhound , un altro open source GLR parser: Scott McPeak, George C. Necula. Elkhound: un veloce, pratico generatore di parser GLR . In Atti del Convegno sul compilatore Constructor (CC04), aprile 2004.

e per ulteriori dettagli:

• UCB / CSSD-2-1214 tecnico rapporto , che è una versione ampliata del sopra di carta;
• la carta fa riferimento nel documentazione Bison : Elizabeth Scott, Adrian Johnstone e Shamsa Sadaf Hussain. Tomita-Style generalizzate LR Parser . TR-00-12, Royal Holloway, Università di Londra, Dipartimento di Informatica, dicembre 2000.

E so di una terza open source GLR parser:. DParser

Answer 2

Adrian Johnstone pubblica un sacco di lavoro sulle versioni avanzate di algoritmi GLR. Il suo pubblicazioni sito sarà probabilmente una risorsa interessante.

Answer 3

La migliore descrizione che io abbia mai visto, con le immagini che illustrano ogni passo dell'algoritmo, è contenuta in questo libro:

http://books.google.ca/books?id=05xA_d5dSwAC&lpg=PA381&dq=generalized%20deterministic%20parsers&pg=PA381#v=onepage&q=generalized%20deterministic%20parsers&f=false

Per pseudocodice, andare alla fonte: Generalized LR Parsing da Tomita, pagina 70 o giù di lì. carta di Farshi contiene una descrizione compatta.

http :? //books.google.ca/books id = PvZiZiVqwHcC & LPG = PP1 & dq = generalizzata% 20lr% 20parsing & pg = PA70 # v = onepage & q = & f = false

E 'una delle tecniche che ho provato per qb.js ( qbasic in javascript ).

Answer 4

Da quello che io sappia, funziona lo stesso come un parser LALR -. Tranne quando incontra un'ambiguità

Quando lo fa, si divide sostanzialmente in analizza separati corrispondenti alle possibili opzioni in quel punto, e continua con loro in tandem - quando un parse fallisce (a causa di incontrare un elemento illegale), è semplicemente caduto, perché deve sono stati una supposizione sbagliata al un'ambiguità precedente.

Alla fine, tutti tranne uno parse sarebbe dovuto morire -. Ed il superstite è il parse "corretto" di quei punti ambigui