Java-verkt?y for skanning og parsering

Dette dokumentet oppsummerer en gjennomgang av Java-verkt?y for skanning og parsering, utf?rt for INF5110-kurset (kompilatorteknikk) v?ren 2006.

Innhold

Noen fakta om skannerne

JLex

JFlex

H?ndskrevet skanner ved hjelp av JDK 1.5s nye Scanner-klasse

TBD, se her .

Parsere

Denne tabellen gir ett sammendrag av parserverkt?yene:

NavnBeskrivelseType Skanner Lisens Historie Dok. Fora Utbredelse Ekstra funksjoner
JavaCC "JavaCC is a parser/scanner generator for java" LL(1) default, LL(k) opsjon for deler av grammatikken Integrert, spek. i samme fil. BSD Fra 1996, o.s. siden 2003, versjon 4.0 jan. 2006 Noks? underdokumentert, ingen sammenhengende manual, guide, tutorial e.l. M? lese generert kode og hoppe rundt i eksempler og l?srevne "MiniTutorials". nyhetsgruppe, mailing-liste "thousands of downloads and estimate serious users in the many thousands" Trebyggings-preprosessor (JJTree), EBNF, sterk feilrapportering, mange eksempler, internasjonalisert (st?tter Unicode), Ant-task
Antlr "ANother Tool for Language Recognition, (formerly PCCTS)" LL(k), "linear approximate lookahead" Integrert "no restrictions", BSD-variant Siden 1989, versjon 2.7.6, des. 2005 Ganske god, omfattende, men noe tung, referansemanual, "Getting Started"-guide, samt flere tutorials. Wiki, mailingliste ~= 5,000 nedlastinger i m?neden Flerspr?klig: implementasjoner i Java, C#, C++, eller Python, St?tte for tre-konstruksjon, og -vandring, Eclipse-plugin, Ant-task
CUP LALR Parser Generator in Java LALR (bygger/ligner p? Yacc) JFlex Public Domain? (antakeligvis BSD, m? laste ned kilden og se etter) Fra 1996, "hull" mellom 1999 og 2005, versjon 11a beta 20050516 God manual, men litt snau med eksempler Ingen Snever, akademisk? (lite skryt p? nettsidene) Oppdatert for generics (Java 1.5). Ant-task
BYacc/J Utvidelse av Berkeley Yacc (BYACC) 1.8, ("-J*"-flagg for ? generere Java-kode). LALR H?ndskrevet, JFlex (if?lge JFlex) Public Domain, i f?lge SourceFourge (trolig BSD) P? SourceForge fra 2002-03-04, versjon 1.11, 2005-07-25 (dokumentasjon des. 2005). Tynn, hviler tungt p? gamle Yacc-manualer. Ingen Ca. 1200 nedlastinger i 2005. Porting fra eksisterende Yacc-grammatikker i C og C++ b?r er noks? greitt.
SableCC "... an object-oriented framework that generates compilers (and interpreters) in the Java programming language." LALR(1) Integrert GPL, LGPL Fra 1998 (masteroppgave), "hull" fra 2001 til des. 2005. Versjon 3.2, 2005-12-24 (trolig patch for "generics", Java 1.5). masteroppgaven er hoveddokumentasjonen, ellers tynn p? brukerdokumentasjon Wiki Snever, akademisk? EBNF, AST-generering, tre-vandring, Grammar-specified transformation of concrete syntax trees into abstract syntax trees, Eclipse plug-in (add-on)
Mork "a compiler tool with XML support" LALR(1) Integrert GPL, LGPL Fra ca. 2000, versjon 0.5, July 8, 2002 kompilatoreksempel som genererer Java byte-code mailingliste ? Attributtgrammtikker, EBNF, posisjon i feilmeldinger
jay "a yacc for Java" (modifisert BYACC, som BYacc/J) LR(1) JLex ? Siden 1997, versjon 0.8, 2001 p? tysk mailingliste anvendt i to kompilatorkurs, 1999 og 2002

Erfaringer fra noen av parserne

BYacc/J

Dette er en ganske enkel og brute-force modifikasjon av den gamle Berkeley Yacc ("... I just added the Java switch..."). Mangler fornuftig st?tte for yacc-direktivene %union og %type. Resultatet er svak typesikkerhet i aksjonene som bruker pseudovariable (Object, int, double, eller String). Ineffektiv (plassmessig) og uelegant kode for unioner av semantiske skanner-verdier (klassen har felter for alle alternativene). Mangler ogs? %error-verbose og %locations. Svake feilmeldinger (default), e.g. "syntax error" fulgt av en ArrayIndexOutOfBoundsException.

CUP

Dette er en rimelig grei Java-variant av yacc. Har ikke BYacc/Js problemer med svak typing av aksjonskode, siden man m? spesifisere semantiske typer for alle symboler, som brukes til ? type pseudovariablene i aksjonene.

Imidlertid er syntaksfeilmeldinger som genereres i utgangspunktet elendige, som BYacc/J, bare "syntax error" og stacktracer fra skanneren, uten posisjon. Men dette kan forbedres, i f?lge manualen (eget avsnitt om feilh?ndtering). Symbolske navn p? terminaler ? ett tegn ('!' o.l.) er p?krevd (valgfritt i de fleste andre verkt?y). Inputsyntaksen fraviker yacc i ganske stor grad, uten ? legge til egenskaper (bortsett fra kanskje navngiving av pseudo-variable, som er hardkodet i yacc). Runtime-biblioteket (man m? bruke klassen Symbol til semantiske verdier) er ikke skikkelig dokumentert, som gode Java-API-er pleier ? v?re. Navngiving i biblioteket og default generert kode er i strid med Sun's kodingkonvensjoner.

JavaCC

Generert kode er noks? intuitiv og grei ? lese (bortsett fra tabeller og funksjoner for h?rete LL(> 1)-h?ndtering). Ganske greitt ? lage en skanner, men samtidig ?pner integrasjonen for nye feil ved ? blande sammen skanning (regexps) og parsing (EBNF). God diagnostikk p? konflikter og venstrerekursjon. Man kan teste parseringen p? andre non-terminaler enn start-symbolet. Verkt?yene, b?de kommandolinja og Ant, er lette ? bruke.

Ulempene er at LL(k)-lookahead (tre former) er vanskelig ? forst? og bruke riktig. Ingen st?tte for automatisk fiksing av bevisst ambisi?se grammatikker (innstillinger for assosiativitet og presedens), man m? skrive om grammatikken for ? oppn? h?yrerekursivitet og venstrefaktorisering. Grammatikk-syntaksen er uvant og en noe rotete blanding av ?BNF og Java (ingen klar separasjon). Spillerom for subtile feil med den integrerte skanneren (f.eks. kan bokstavelige terminaler, "token", i grammatikkregler behandles forskjellig av parseren, avhengig av om de er definert som token eller ikke). Skanneren introduserer ogs? to nye avanserte tegnklassifikasjoner (utover gjenkjenning av symboler og utelatelese, eng: "skip"), MORE og SPECIAL_TOKEN, som b?r/m? forst?s

Antlr

Pro

Kontra

2006-01-30 07:08
Sven-J?rgen Karlsen