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