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
- A Lexical Analyzer Generator for Java(TM)
- Versjon: 1.2.6, feb. 2003
- Lisens: OS (http://www.opensource.org/licenses/historical.php) og Standard ML of New Jersey Copyright License (variant av GPL)
- Parserbruk: CUP
- E-postliste
JFlex
- "Fast" JLex, omskriving av JLex.
- Versjon: 1.4.1, nov. 2004
- Lisens: GPL
- Parserbruk: CUP, BYacc/J, Antlr
- Ganske omfattende manual, med integrasjon mot CUP og BYacc/J.
- E-postliste
- Ant-integrasjon: Ja
H?ndskrevet skanner ved hjelp av JDK 1.5s nye Scanner-klasse
TBD, se her .
Parsere
Denne tabellen gir ett sammendrag av parserverkt?yene:
| Navn | Beskrivelse | Type | 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
- Generert kode lettlest og grei, mer konsis og ryddig enn JavaCCs p.g.a. referert rammeverk-kode. LL(> 1)-forviklinger h?rete.
- Verkt?yene, b?de Ant (bortsett) og kommandolinja, er greie ? bruke (bortsett fra at de bare aksepterer ?n inputfil av gangen, og heller ikke stdin).
- Inputsyntaksen mer leselig og ryddig (mer rendyrka ENBF) enn JavaCC.
- Integrert AST-generering fungerte tilsynelatende ganske greitt ved f?rste fors?k.
Kontra
- Konstruksjon av skanner (Lexer-klasse) vrient. Mange feilkilder, s?rlig flere m?ter ? bruke tokens ('c' vs. "c" vs MY_TOKEN) p? i grammatikken, hvor bare noen f? er riktige. Svak diagnostikk, muliggj?r at kompilerbar kode genereres for udefinerte token-symboler i grammatikken. Manuell linjetelling er n?dvendig for ? forsterke syntaksfeil fra parseren. Enda en reg.uttr.s-dialekt. Problemer om ambisi?se uttrykk med samme prefiks, som andre verkt?y l?ser automatisk med gr?dig (den lengste mulig matchen foretrekkes) match.
- LL(k > 1)-lookahead (syntaktiske og semantiske predikater i ref.manualen) vanskelig ? forst? ? bruke riktig, s?rlig syntaktisk.
- Ingen st?tte for automatisk fiksing av ambisi?se grammtikker. M? venstrefaktorisere (kan trolig delvis unng?s med LL(k)) og bruke h?yrerekursjon.
-
TBD:
Brukbarheten til AST-nodene vs. presist typede og designede meta-klasser?
Er alt instanser av en generell
Node-type, eller?
Sven-J?rgen Karlsen