From: Subject: The JavaCC FAQ Date: Mon, 14 Sep 2009 09:28:50 -0500 MIME-Version: 1.0 Content-Type: multipart/related; type="text/html"; boundary="----=_NextPart_000_0000_01CA351D.C4D99D00" X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.5579 This is a multi-part message in MIME format. ------=_NextPart_000_0000_01CA351D.C4D99D00 Content-Type: text/html; charset="Windows-1252" Content-Transfer-Encoding: quoted-printable Content-Location: http://www.idevelopment.info/data/Programming/java/JavaCC/The_JavaCC_FAQ.htm The JavaCC = FAQ

The JavaCC FAQ

Maintained by Theodore S. Norvell
Computer and = Electrical=20 Engineering
Memorial University of Newfoundland
Email: theo at = engr.mun.ca=20

Typeset on Jul 2, 2002 .

Contents

1 =20 General Information on JavaCC and = Parsing
    1.1 =20 What is JavaCC?
    1.2 =20 Could you explain that in more detail?
    1.3 =20 What does JavaCC not do?
    1.4 =20 What can JavaCC be used for?
    1.5 =20 Is there a newsgroup or mailing list?
    1.6 =20 Should I send my question to the newsgroup or mailing=20 list?
    1.7 =20 Who wrote JavaCC and who maintains it?
    1.8 =20 Is the source code for JavaCC publicly=20 available?
    1.9 =20 Where can I get JavaCC?
    1.10 =20 What legal restrictions are there on = JavaCC?
    1.11 =20 Are there books or tutorials on = JavaCC?
    1.12 =20 Are there books or tutorials on parsing theory?
2 =20 General Issues
    2.1 =20 Is there any documentation?
    2.2 =20 What files does JavaCC produce?
    2.3 =20 I changed option x; why am I having=20 trouble?
    2.4 =20 How do I put the generated classes in a package?
3 =20 The Token Manager
    3.1 =20 What is a token manager?
    3.2 =20 How do I read from a string instead of a = file?
    3.3 =20 What if more than one regular expression matches a prefix of the = remaining=20 input?
    3.4 =20 What if no regular expression matches a prefix of the remaining=20 input?
    3.5 =20 How do I match any character?
    3.6 =20 How do I match exactly n repetitions of a regular=20 expression?
    3.7 =20 What are TOKEN, SKIP, and SPECIAL_TOKEN? =
    3.8 =20 What are lexical states all about?
    3.9 =20 Can the parser force a switch to a new lexical=20 state?
    3.10 =20 Is there a way to make SwitchTo safer?
    3.11 =20 What is MORE?
    3.12 =20 Why do the example Java and C++ parsers report an error when the last = line of a=20 file is a single line comment?
    3.13 =20 What is a lexical action?
    3.14 =20 What is a common token action?
    3.15 =20 How do I throw a ParseException instead of a=20 TokenMgrError?
    3.16 =20 Why are line and column numbers not recorded?
4 =20 The Parser and Lookahead
    4.1 =20 Where should I draw the line between lexical analysis and=20 parsing?
    4.2 =20 What is recursive descent parsing?
    4.3 =20 What is left-recursion and why can't I use = it?
    4.4 =20 What is ``lookahead''?
    4.5 =20 I get a message saying ``Warning: Choice Conflict ... ''; what should I=20 do?
    4.6 =20 I added a LOOKAHEAD specification and the warning went away; does = that mean=20 I fixed the problem?
    4.7 =20 Are semantic actions executed during syntactic=20 lookahead?
    4.8 =20 Are nested syntactic lookahead specifications evaluated during syntactic = lookahead?
    4.9 =20 Are parameters passed during syntactic=20 lookahead?
    4.10 =20 Are semantic actions executed during syntactic=20 lookahead?
    4.11 =20 Is semantic lookahead evaluated during syntactic=20 lookahead?
    4.12 =20 Can local variables (including parameters) be used in semantic=20 lookahead?
    4.13 =20 How does JavaCC differ from standard LL(1)=20 parsing?
    4.14 =20 How do I communicate from the parser to the token=20 manager?
    4.15 =20 How do I communicate from the token manager to the=20 parser?
    4.16 =20 What does it mean to put a regular expression within a=20 BNF production?
    4.17 =20 When should regular expressions be put directly into a=20 BNF production?
    4.18 =20 How do I parse a sequence without allowing=20 duplications?
    4.19 =20 How do I deal with keywords that aren't=20 reserved?
    4.20 =20 There's an error in the input, so why doesn't my parser throw a=20 ParseException?
5 =20 Semantic Actions
    5.1 =20 I've written/found a parser, but it doesn't do=20 anything?
    5.2 =20 How do I capture and traverse a sequence of tokens?
6 =20 JJTree and JTB
    6.1 =20 What are JJTree and JTB?
    6.2 =20 Where can I find JJTree?
    6.3 =20 Where can I find JTB?
7 =20 Applications of JavaCC
    7.1 =20 Where can I find a parser for = x?
    7.2 =20 How do I parse arithmetic expressions?
    7.3 =20 I'm writing a programming language interpreter; how do I deal with=20 loops?
8 =20 Comparing JavaCC with other tools
    8.1 =20 Since LL(1) =CC LALR(1), = wouldn't a tool=20 based on LALR parsing be better?
    8.2 =20 How does JavaCC compare with Lex and = Flex?
    8.3 =20 How does JavaCC compare with other Yacc and Bison?

Acknowledgments: Your maintainer would like to thank the = following for=20 help with the FAQ: Ken Beesley, Tom Davies, Brian Goetz, Tony = LaPaso, Eric=20 Nickell, Phil Robare, David Rosenstrauch, and Michael Welle.=20



The latest copy of this FAQ can be found at The JavaCC FAQ.=20

In citing or linking to this FAQ, please use the following URI:=20


http://www.engr.mun.ca/= ~theo/JavaCC-FAQ

Chapter 1
General Information on JavaCC = and=20 Parsing

"DRAGONS DREAD=20

GO BACK TO BED!!"=20

Sheree Fitch, Sleeping Dragons All Around.=20



1.1  What is JavaCC?

JavaCC stands for "the Java Compiler Compiler"; it is a parser = generator and=20 lexical analyzer generator. JavaCC will read a description of a language = and=20 generate code, written in Java, that will read and analyze that = language. JavaCC=20 is particularly useful when the input language has a complex structure = that=20 makes hand-crafting an input module a difficult job.=20

This technology originated to make programming language = implementation easier=20 -hence the term "compiler compiler"- but make no mistake that JavaCC is = of use=20 only to programming language implementors.=20

1.2  Could you explain that in = more=20 detail?

Figures 1.1 and 1.2 show the relationship between a JavaCC = generated=20 lexical analyzer (called a "token manager" in JavaCC parlance) and = a JavaCC=20 generated parser. The figures show the C as the input language. But = JavaCC=20 can handle any language -and not only programming languages- if you can = describe=20 the rules of the language to JavaCC.=20

The token manager reads in a sequence of characters and produces a = sequence=20 of objects called "tokens". The rules used to break the sequence of = characters=20 into a sequence of tokens obviously depend on the language; they are = supplied by=20 the programmer as a collection of "regular expressions".=20

The parser consumes the sequence of tokens, analyses its structure, = and=20 produces ... . Well what the parser produces is up to you; JavaCC is = completely=20 flexible in this regard1. The figure shows an "abstract syntax = tree",=20 but you might want to produce, say, a number (if you are writing a = calculator),=20 a file of assembly language (if you were writing a one-pass compiler), a = modified sequence of characters (if you were writing a text processing=20 application), and so on. The programmer supplies a collection of = "Extended=20 BNF production rules"; JavaCC uses these productions to generate = the parser=20 as a Java class. These production rules can be annotated with = snippets of=20 Java code, which is how the programmer tells the parser what to produce. =

3D"picture
Figure 1.1 The token manager converts a sequence of characters = to a=20 sequence of Token objects.

3D"picture
Figure 1.2 The parser analyzes the sequence of=20 tokens.

1.3  What does JavaCC not = do?

JavaCC does not automate the building of trees (or any other specific = parser=20 output), although there are at least two tree building tools JJTree and = JTB (see=20 Chapter 6.)=20  based on JavaCC, and building trees "by hand"with a JavaCC based = parser is=20 easy.=20

JavaCC does not build symbol-tables, although if you want a = symbol table=20 for a language, then a JavaCC based parser may provide a good framework. =

JavaCC does not generate output languages. However once you have a = tree, it=20 is easy to generate string output from it.=20

1.4  What can JavaCC be used = for?

JavaCC has been used to create parsers for: RTF, Visual Basic, = Python,=20 Rational Rose mdl files, XML, XML DTDs, HTML, C, C++, Java, JavaScript, = Oberon,=20 SQL, VHDL, VRML, ASN1, email headers, and lots of proprietary languages. = It also=20 get used for configuration file readers, calculators, and on and on.=20

1.5  Is there a newsgroup or = mailing=20 list?

comp.compilers.tools.javacc is a usenet newsgroup for discussing the = JavaCC=20 and related technologies, like JJTree and JTB.=20

There is also a mail-list. To subscribe send a message to=20 javacc-interest-request@mack.eng.sun.com containing, in its body, the = single=20 word "subscribe".=20

Eventually the mailing list and comp.compilers.tools.javacc will be=20 gatewayed.=20

1.6  Should I send my = question to the=20 newsgroup or mailing list?

Yes, but only if your question relates in some way to JavaCC, JJTree, = or JTB.=20

The newsgroup and mailing list are not suitable fora for discussing = the Java=20 programming language or javac, which is Sun's Java compiler, or any = other topic=20 that does not relate directly to the Java Compiler Compiler.=20

Questions on parsing theory or parser generation in general might be = better=20 addressed to comp.compilers.=20

Questions directly answered in the FAQ need not be asked again in the = newgroup or mailing list.=20

1.7  Who wrote JavaCC and who = maintains=20 it?

JavaCC was created by Sreeni Viswanadha and Sriram Sankar when they = worked=20 for Sun. They then formed their own company, Metamata, which is now a = wholly=20 owned subsidiary of WebGain. Through all these changes, they've kept = improving=20 JavaCC. Because of this history, JavaCC is owned by Sun Microsystems and = is=20 distributed by WebGain.=20

1.8  Is the source code for = JavaCC publicly=20 available?

Currently (June 2002) the answer is no. However in a letter to the = JavaCC=20 mailing list on 22 March 2002, Michael Van De Vanter of Sun indicated = that Sun=20 plans to make JavaCC open source.=20

1.9  Where can I get JavaCC?

JavaCC is available from WebGain as a = free=20 download. The precise URL may change.=20

1.10  What legal restrictions = are there on=20 JavaCC?

There are essentially no restrictions on the use of JavaCC. In = particular you=20 may use the Java files that JavaCC produces in any way, including = incorporating=20 them into a product that you sell. However, you are not allowed to = redistribute=20 JavaCC itself; it is free, but it is not shareware. Furthermore various = .jj=20 files that are distributed with JavaCC or that you may find on the net, = may have=20 restrictions on their use - read the copyright notices carefully.=20

1.11  Are there books or = tutorials on=20 JavaCC?

At the moment there are no books on JavaCC.=20

There are some tutorial examples in the JavaCC documentation.=20

A couple of articles have been published in JavaWorld. See ar= ticle by=20 Chuck McManis and article=20 by Oliver Enseling.=20

Your maintainer is currently writing tutorial on JavaCC, which may = become a=20 book one day.=20

1.12  Are there books or = tutorials on=20 parsing theory?

Yes many. Most text-books on compiler technology contain more than = enough=20 background on parsing theory. Here are some suggestions=20

  • Alfred V. Aho, Ravi Sethi and Jeffrey D. Ullman, Compilers:=20 Principles, Techniques, and Tools, Addison-Wesley, 1985.=20

  • Charles N. Fischer and Richard J. Leblanc, Jr., Crafting a = Compiler=20 With C, Addison-Wesley, 1991.=20

Chapter 2
General Issues

2.1  Is there any = documentation?

Yes. Follo= w this=20 link.=20

The on-line documentation is currently a bit out of date. You = should also=20 read the release notes that come with the JavaCC download.=20

The documentation is rather terse and is much easier to read if you = already=20 know a bit about parsing theory. Nevertheless, the documentation is an=20 indispensable resource that is in no way superceded by this FAQ.=20

It used to be possible to download the documentation in a big ZIP = file. At=20 the moment your maintainer does not know where the documentation can be=20 downloaded from, but you can certainly view it on-line.=20

2.2  What files does JavaCC = produce?

JavaCC is a program generator. Based on its input (a .jj file) = version 2.1=20 (or later) will produce the following Java source files:=20

  • Boiler-plate files=20

    • SimpleCharStream.java - represent the stream of input=20 characters.=20

    • Token.java - represents a single input token=20

    • TokenMgrError.java - an error thrown from the token = manager.=20

    • ParseException.java - an exception indicating that the = input=20 did not conform to the parser's grammar.=20

  • Custom files (XXX is whatever name you choose).=20

    • XXX.java - the parser class=20

    • XXXTokenManager.java - the token manager = class.=20

    • XXXConstants.java - an interface associating = token=20 classes with symbolic names.=20

If you use the option JAVA_UNICODE_ESCAPE then=20 SimpleCharStream.java will note be produced, but rather=20 JavaCharStream.java.  (Prior to version 2.1, one of four = possible=20 files was generated: ASCII_CharStream.java=20 ASCII_UCodeESC_CharStream.java, UCode_CharStream.java, = or=20 UCode_UCodeESC_CharStream.java).=20

If you use the option USER_CHAR_STREAM, = then=20 CharStream.java (an interface) will be produced instead of the = class=20 SimpleCharStream.java. Similarly the option USER_TOKEN_MANAGER will cause the generation of = an=20 interface TokenManager.java, rather than a concrete token = manager.=20

The boiler plate files will only be produced if they don't already = exist.=20 There are two important consequences: First, you should delete them = prior=20 to running JavaCC, if you make any changes that might require changes to = these=20 files. (See Question 2.3,=20 "I changed option x; why am I having trouble?" .) Second, if you = really=20 want to, you can modify these files and be sure that JavaCC won't = overwrite=20 them.=20

Modifying any generated files should be used only as a last resort, = since=20 someday you will likely want to regenerate them and then you'll have to=20 re-modify them. Some people have written scripts (in, say, Perl) to do = the=20 modifications for them.=20

The custom files are produced every time you run JavaCC.=20

2.3  I changed option x; = why am I=20 having trouble?

Try deleting all files generated by JavaCC (see Question 2.2,=20 `` What files does JavaCC produce?'' ) and then rerunning JavaCC. This = issue=20 usually comes up when the STATIC option is = changed;=20 JavaCC needs to generate new files, but it will not generate = boiler-plate files=20 unless they aren't there already.=20

2.4  How do I put the = generated=20 classes in a package?

Put a package declaration right after = the PARSER_BEGIN(XXX)=20 declaration in the .jj file.=20

Chapter 3
The Token Manager

3.1  What is a token = manager?

In conventional compiling terms, a token manager is a lexical = analyzer. If=20 that is Greek to you, here is an explanation. The token manager analyzes = the=20 input stream of characters breaking it up into chunks called tokens and=20 assigning each token a "token kind". For example suppose the input is a=20 C file=20

int main() {=20

/*a short program */=20
return 0 ; } =

Then the token manager might break this into chunks as follows:=20

"int", " ", "main", "(", = ")",=20 " ", "{", "\n",=20 "        ", "/*a short = program=20 */", ...

White space and comments are typically discarded, so the chunks are = then=20

"int", "main", "(", ")",=20 "{", "return", "0", ";", = "}"=20

Each chunk of text is classified as one of a finite set of = "token=20 kinds".2 For example the chunks above could be = classified as, respectively,=20

KWINT, = ID, LPAR, RPAR, LBRACE, = KWRETURN, OCTALCONST, = SEMICOLON, RBRACE

Each chunk of text is represented by an object of class Token, each = with the=20 following attributes:=20

  • .kind the token kind encoded as an = int,=20

  • .image the chunk of input text as a = string,=20

and a few others.=20

This sequence of Token objects is produced based on regular = expressions=20 appearing in the .jj file.=20

The sequence is usually sent on to a parser object for further = processing.=20

3.2  How do I read from a string = instead of=20 a file?

Here is one way=20

java.io.StringReader sr =3D new java.io.StringReader( str = );=20

java.io.Reader r =3D new java.io.BufferedReader( sr );=20

XXX parser =3D new XXX( r ); =

3.3  What if more than one = regular=20 expression matches a prefix of the remaining input?

First a definition: If a sequence x can be constructed by = catenating=20 two other sequences y and z, i.e., x=3Dyz, = then=20 y is called a "prefix" of x.=20

There are three golden rules for picking which regular expression to = use to=20 identify the next token:=20

  1. The regular expression must describe a prefix of the remaining = input=20 stream.=20

  2. If more than one regular expression describes a prefix, then the = regular=20 expression that describes the longest possible prefix of the input = stream is=20 used. (This is called the "maximal munch rule".)=20

  3. If more than one regular expression describes the longest possible = prefix,=20 then the regular expression that comes first in the .jj file is used.=20

For example, suppose you are parsing Java, C, or C++. The following = three=20 regular expression productions might appear in the .jj file=20

TOKEN : {  < PLUS : "+" > }=20

TOKEN : {  < ASSIGN : "=3D" > }=20

TOKEN : { < PLASSIGN : "+=3D"  > }=20

Suppose the remaining input stream starts with=20

"+=3D1; ..."      . =

Rule 1 rules out the second production. Rule 2 says that the third = production=20 is preferred over the first. The order of the productions has no effect = on this=20 example.=20

Sticking with Java, C, or C++, suppose you have regular expression=20 productions=20

TOKEN : {  < KWINT : "int" > }=20

TOKEN : {  < IDENT : ["a"-"z","A"-"Z", "_"] = (["a"-"z","A"-"Z","0"-"9","_"])* > } =

Suppose the remaining input steams starts with=20

"integer i; ..."      , =

then the second production would be preferred by the maximal munch = rule (rule=20 2). But if the remaining input stream starts with=20

"int i; ..."      , =

then the maximal munch rule is no help, since both rules match a = prefix of=20 length 3. In this case the KWINT = production is=20 preferred (by rule 3) because it comes first in the .jj file.=20

3.4  What if no regular = expression matches=20 a prefix of the remaining input?

Then a TokenMgrError is thrown.=20

3.5  How do I match any = character?

Use ~[] .=20

3.6  How do I match exactly = n=20 repetitions of a regular expression?

If X is the regular expression, write

(X){n}
You=20 can also give a lower and upper bound on the number of repetitions:
(X){l,u}

3.7  What are TOKEN, SKIP, and=20 SPECIAL_TOKEN?

Regular expression productions are classified as one of four kinds:=20

  • TOKEN means that when the = production is=20 applied, a Token object should be = created and=20 passed to the parser.=20

  • SKIP means that when the = production is=20 applied, no Token object should be = constructed.=20

  • SPECIAL_TOKEN means that when = the=20 production is applied a Token object = should be=20 created but it should not be passed to the parser. Each of these = "special=20 tokens" can be accessed from the next Token=20 produced (whether special or not), via its specialToken field.=20

  • MORE is discussed in Question = 3.11,=20 "What is MORE?" .=20

3.8  What are lexical states all = about?

Lexical states allow you to bring different sets of regular = expression=20 productions in-to and out-of effect.=20

Suppose you wanted to write a JavaDoc processor. Most of Java is = tokenized=20 according to regular ordinary Java rules. But between a = "/**" and=20 the next "*/" a different set of rules applies in which = keywords=20 like "@param" must be recognized and where newlines are=20 significant. To solve this problem, we could use two lexical states. One = for=20 regular Java tokenizing and one for tokenizing within JavaDoc comments. = We might=20 use the following productions:=20

// When a /** is seen in the DEFAULT state, switch to = the=20 IN_JAVADOC_COMMENT state=20

TOKEN : {=20

< STARTDOC : "/**" > =  : IN_JAVADOC_COMMENT=20 }

      =20

// When @param is seen in the = IN_JAVADOC_COMMENT state, it is=20 a token.=20

// Stay in the same state.=20

< IN_JAVADOC_COMMENT > TOKEN : {=20

< PARAM : "@param" > }

...=20

      =20

// When a */ is seen in the IN_JAVADOC_COMMENT state,=20 switch=20

// back to the DEFAULT state=20

< IN_JAVADOC_COMMENT > TOKEN : {=20

< ENDDOC: "*/" > : DEFAULT }=20

Productions that are prefixed by < = IN_JAVADOC_COMMENT=20 > apply when the lexical analyzer is in the IN_JAVADOC_COMMENT state. Productions that have = no such=20 prefix apply in the DEFAULT state. It=20 is possible to list any number of states (comma separated) before a = production. The special prefix < * > = indicates=20 that the production can apply in all states.=20

Lexical states are also useful for avoiding complex regular = expressions.=20 Suppose you want to skip C style comments. You could write a regular = expression=20 production:=20

SKIP : {  < "/*"(~["*"])* "*"(~["/"]=20 (~["*"])* "*")* "/" > }

But how confident are you that this is right?3 The following version uses a = lexical state=20 called IN_COMMENT to make things much = clearer:=20

// When a /* is seen in the DEFAULT state, skip it and = switch=20 to the IN_COMMENT state=20

SKIP : {=20

"/*": IN_COMMENT }

      =20

// When any other character is seen in the = IN_COMMENT state,=20 skip it.=20

< IN_COMMENT > SKIP : {=20

<  ~[] > }

      =20

// When a */ is seen in the IN_COMMENT state, skip it = and=20 switch back to the DEFAULT state=20

< IN_COMMENT > SKIP : {=20

"*/": DEFAULT }

The previous example also illustrates a subtle behavioural difference = between=20 using lexical states and performing the same task with a single, = apparently=20 equivalent, regular expression. Consider tokenizing the = C "statement":=20

i =3D j/*p ;

Assuming that there are no occurrences of */=20 later in the file, this is an error (since a comment starts, but doesn't = end)=20 and should be diagnosed. If we use a single, complex, regular expression = to find=20 comments, then the lexical error will be missed and, in this example at = least, a=20 syntactically correct sequence of seven tokens will be found. If we use = the=20 lexical states approach then the behaviour is different, though again = incorrect;=20 the comment will be skipped; an EOF token will be produced after the = token for=20 "j"4; no error will be reported. We can = correct the=20 lexical states approach, however, with the use of MORE; see Question 3.11,=20 "What is MORE?" .=20

3.9  Can the parser force a = switch to a new=20 lexical state?

Yes, but it is very easy to create bugs by doing so. You can call the = token=20 manager's method SwitchTo from within a = semantic=20 action in the parser like this=20

{ token_source.SwitchTo(name_of_state) ; }=20

However, owing to look-ahead, the token manager may be well ahead of = the=20 parser. Consider Figure 1.2; at any point in the parse, there are a = number of=20 tokens on the conveyer belt, waiting to be used by the parser; = technically the=20 conveyer belt is a queue of tokens held within the parser object. Any = change of=20 state will take effect for the first token not yet in the queue. = Syntactic=20 look-ahead usually means there is at least one token in the queue, but = there may=20 be many more.=20

If you are going to force a state change from the parser be sure = that, at=20 that point in the parsing, the token manager is a known and fixed number = of=20 tokens ahead of the parser, and that you know what that number is.=20

If you ever feel tempted to call SwitchTo from=20 the parser, stop and try to think of an alternative method that is = harder to get=20 wrong.=20

3.10  Is there a way to make = SwitchTo=20 safer?

Brian Goetz submitted the following code to make sure that, when a = SwitchTo=20 is done, any queued tokens are removed from the queue. There are three = parts to=20 the solution:=20

  • In the parser add a subroutine SetState to=20 change the state. This subroutine can be found at http://www.= engr.mun.ca/~theo/JavaCC-FAQ/SetState.txt.=20 Use this subroutine to change states within semantic actions of the = parser.=20

  • In the token manager add a subroutine:=20

    TOKEN_MGR_DECLS : {=20

    // Required by SetState=20
    void backup(int n) { input_stream.backup(n); }

    }

  • Use the USER_CHAR_STREAM option and = use BackupCharStream as the CharStream class. BackupCharStream can be found at http://www.webmacro.org/cvs/cvsweb.cgi/webm= acro/src/org/webmacro/parser/BackupCharStream.java.=20

3.11  What is MORE?

Regular expression productions are classified as one of four kinds:=20

  • TOKEN, SKIP, and SPECIAL_TOKEN are discussed in Question = 3.7,=20 "What are TOKEN, SKIP, and SPECIAL_TOKEN?" .=20

  • MORE.=20

MORE means that no token should = be=20 produced yet. Rather the characters matched will form part of the next = token to=20 be recognized. MORE means that = there will be=20 more to the token. After a sequence of one or more MORE productions have been applied, we = must reach a=20 production that is marked TOKEN, = SKIP, SPECIAL_TOKEN. The token produced (or not = produced=20 in the case of SKIP) will contain = the saved=20 up characters from the preceding MORE=20 productions. Note that if the end of the input is encountered when the = token=20 manager is looking for more of a token, then a TokenMgrError is thrown. The assumption made by = JavaCC is=20 that the EOF token should correspond = exactly to the=20 end of the input, not to some characters leading up to the end of the = input.=20

Let's revisit and fix the comment example from Question 3.8,=20 "What are lexical states all about?" . The problem was that unterminated = comments were simply skipped rather than producing an error. We can = correct this=20 problem using MORE productions to = combine the=20 entire comment into a single token.=20

// When a /* is seen in the DEFAULT state, skip it and = switch=20 to the IN_COMMENT state=20

MORE : {=20

"/*": IN_COMMENT }

      =20

// When any other character is seen in the = IN_COMMENT state,=20 skip it.=20

< IN_COMMENT > MORE : {=20

<  ~[] > }

      =20

// When a */ is seen in the IN_COMMENT state, skip it = and=20 switch back to the DEFAULT state=20

< IN_COMMENT > SKIP : {=20

"*/": DEFAULT }

Suppose that a file ends with "/*a". Then no token can be=20 recognized, because the end of file is found when the token manager only = has a=20 partly recognized token. Instead a TokenMgrError=20 will be thrown.=20

3.12  Why do the example Java = and C++=20 parsers report an error when the last line of a file is a single line=20 comment?

The file is likely missing a newline character (or the = equivalent) at=20 the end of the last line.=20

These parsers use lexical states and MORE type regular = expression=20 productions to process single line comments thusly:=20

MORE : {=20

"//": IN_SINGLE_LINE_COMMENT }

      =20

< IN_SINGLE_LINE_COMMENT > SPECIAL_TOKEN : {=20

< SINGLE_LINE_COMMENT: "\n"|"\r"|"\r\n" > : DEFAULT }

      =20

< IN_SINGLE_LINE_COMMENT > MORE : {=20

<  ~[] > } =

Clearly if an EOF is encountered while the token manager is still = looking for=20 more of the current token, there should be a TokenMgrError thrown.=20

Both the Java and the C++ standards agree with the example .jj files, = but=20 some compilers are more liberal and do not insist on that final newline. = If you=20 want the more liberal interpretation, try=20

SPECIAL_TOKEN : {=20

< SINGLE_LINE_COMMENT: "//"(~["\n","\r"])* ("\n"|"\r"|"\r\n")? = > }=20

3.13  What is a lexical = action?

Sometimes you want some piece of Java code to be executed immediately = after a=20 token is matched. Lexical actions are placed immediately after the = regular=20 expression in a regular expression production. For example:=20

TOKEN : {=20

< TAB : "\t" >  { tabcount+=3D1; } =

}

The Java statement { tabcount+=3D1; } = will be=20 executed after the production is applied.=20

3.14  What is a common token = action?

A common token action is simply a subroutine that is called after = each Token is matched. Note that this does not apply = to=20 "skipped tokens" nor to "special tokens".=20

3.15  How do I throw a = ParseException=20 instead of a TokenMgrError?

If you don't want any TokenMgrErrors being thrown, try putting a = regular=20 expression production at the very end of your .jj file that will match = any=20 character:=20

< * > TOKEN :=20

{=20

< UNEXPECTED_CHAR : ~[] >=20

}

However, this may not do the trick. In particular, if you use MORE, = it may be=20 hard to avoid TokenMgrErrors altogether. It is best to make a policy of = catching=20 TokenMgrErrors as well as ParseExceptions, whenever you call an entry = point to=20 the parser.=20

3.16  Why are line and column = numbers not=20 recorded?

In version 2.1 a new feature was introduced. You now have the option = that the=20 line and column numbers will not be recorded in the Token objects. The = option is=20 called KEEP_LINE_COLUMN. The default is = true, so not knowing about this option = shouldn't=20 hurt you.=20

However, there appears to be a bug in the GUI interface to = JavaCC=20 (javaccw.exe), which sets this option to false (even=20 if you explicitly set it to true in the = .jj file).=20

The solution is to delete all generated files (see Question 2.3,=20 `` I changed option x; why am I having trouble?'' ) and = henceforth to not=20 use the GUI interface to JavaCC.=20

Chapter 4
The Parser and Lookahead

4.1  Where should I draw the line = between=20 lexical analysis and parsing?

This question is dependant on the application. A lot of simple = applications=20 only require a token manager. However, many people try to do too much = with the=20 lexical analyzer, for example they try to write an expression parser = using only=20 the lexical analyzer.=20

4.2  What is recursive descent=20 parsing?

JavaCC's generated parser classes work by the method of "recursive = descent".=20 This means that each BNF production in the .jj file is translated into a = subroutine with roughly the following mandate:=20

If there is a prefix of the input sequence of tokens = that=20 matches this nonterminal's definition,=20

then remove that prefix from the input sequence=20

else throw a ParseException

4.3  What is left-recursion and = why can't I=20 use it?

Left-recursion is when a nonterminal contains a recursive reference = to itself=20 that is not preceded by something that will consume tokens.=20

The parser class produced by JavaCC works by recursive descent.=20 Left-recursion is banned to prevent the generated subroutines from = calling=20 themselves recursively ad-infinitum. Consider the following obviously = left=20 recursive production=20

void A() : {} {=20

A() B()

|=20

C()

}

This will translate to a Java subroutine of the form=20

void A() : {} {=20

if( some condition ) {=20

A() ;=20
B() ; }
else {=20

C() ; }

}

Now if the condition is ever true, we have an infinite recursion.=20

Luckly JavaCC will produce an error message, if you have = left-recursive=20 productions.=20

4.4  What is "lookahead"?

To use JavaCC effectively you have to understand how it looks ahead = in the=20 token stream to decide what to do. Your maintainer strongly recommends = reading=20 the lookahead mini-tutorial in the JavaCC documentation. (See = Section2.1)=20 . The following questions of the FAQ address some common problems and=20 misconceptions about lookahead. Ken Beesley has kindly contributed some = supplementary=20 documentation.=20

4.5  I get a message saying = "Warning:=20 Choice Conflict ... "; what should I do?

Some of JavaCC's most common error messages goes something like this=20

Warning: Choice conflict ...=20

Consider using a lookahead of 2 for ...

Read the message carefully. Understand why there is a choice conflict = (choice=20 conflicts will be explained shortly) and take appropriate action. The=20 appropriate action, in my experience, is rarely to use a lookahead of 2. =

So what is a choice conflict. Well suppose you have a BNF production=20

void a() : {} {=20

< ID >  b() 

|=20

< ID >  c()

}

When the parser applies this production, it must choose between = expanding it=20 to < ID >  b() and expanding it = to < ID >  c(). The default method of = making such=20 choices is to look at the next token. But if the next token is of kind = ID then either choice is appropriate. So you = have a=20 "choice conflict". For alternation (i.e. |) = the default=20 choice is the first choice.=20

To resolve this choice conflict you can add a "LOOKAHEAD = specification"to the=20 first alternative. For example, if nonterminal b and=20 nonterminal c can be distinguished on the = basis of=20 the token after the ID token, then the = parser need=20 only lookahead 2 tokens. You tell JavaCC this by writing:=20

void a() : {} {=20

LOOKAHEAD( 2 )=20
< ID >  b() 

|=20

< ID >  c()

}

Ok, but suppose that b and c can start out the same and are only = distinguishable by=20 how they end. No predetermined limit on the length of the lookahead will = do. In=20 this case, you can use "syntactic lookahead". This means you have the = parser=20 look ahead to see if a particular syntactic pattern is matched before = committing=20 to a choice. Syntactic lookahead in this case would look like this:=20

void a() : {} {=20

// Take the first alternative if an < ID > = followed by a=20 b() appears next=20
LOOKAHEAD(  < ID >  b() )=20
< ID >  b() 

|=20

< ID >  c()

}

Another way to resolve conflicts is to rewrite the grammar. The above = nonterminal can be rewritten as=20

void a() : {} {=20

< ID >=20

(=20

b() 
|=20

c()
)

}

which may resolve the conflict.=20

Choice conflicts also come up in loops. Consider=20

void paramList() : {} {=20

param()=20
(=20

< COMMA >=20

param()
)*=20
(=20

( < COMMA > )?  < ELLIPSIS >=20

)?

}

There is a choice of whether to stay in the * loop or to exit it and = process=20 the optional ELLIPSIS. But the default = method of=20 making the choice based on the next token does not work; a COMMA token could be the first thing seen in the = loop=20 body, or it could be the first thing after the loop body. For loops the = default=20 choice is to stay in the loop.=20

To solve this example we could use a lookahead of 2 at the = appropriate choice=20 point (assuming a param can not be empty and that one can't start with = an ELLIPSIS.=20

void paramList() : {} {=20

param()=20
(=20

LOOKAHEAD(2)=20
< COMMA >=20

param()
)*=20
(=20

( < COMMA > )?  < ELLIPSIS >=20

)?

}

We could also rewrite the grammar, replacing the loop with a = recursion.=20

Sometimes the right think to do is nothing. Consider this classical = example,=20 again from programming languages=20

void statement() : {}=20

{=20

< IF >  exp() < THEN > =  statement() =20
(  < ELSE >  statement() )?

|=20

...other possible statements...

}

Because an ELSE token could = legitimately follow a=20 statement, there is a conflict. The fact = that an=20 ELSE appears next is not enough to = indicate that the=20 optional " < ELSE > =  statement()"should=20 be parsed. Thus there is a conflict. The default for parsers is to take = an=20 option rather than to leave it; and that turns out to be the right=20 interpretation in this case (at least for C, C++, Java, Pascal, etc.). = If you=20 want, you can write:=20

void statement() : {}=20

{=20

< IF >  exp() < THEN > =  statement() =20
( LOOKAHEAD(  < ELSE > )  < ELSE = >=20  statement() )?

|=20

...other possible statements...

}

to suppress the warning.=20

4.6  I added a LOOKAHEAD = specification=20 and the warning went away; does that mean I fixed the problem?

No. JavaCC will not report choice conflict warnings if you use a = LOOKAHEAD specification. The absence of a warning doesn't mean that = you've=20 solved the problem correctly, it just means that you added a LOOKAHEAD=20 specification.=20

Consider the following example:=20

void eg() : {}=20

{=20

LOOKAHEAD(2)=20
< A >   < B >   < C >=20

|=20

< A >   < B >   < D >=20

}

Clearly the lookahead is insufficient (lookahead 3 would do the = trick), but=20 JavaCC produces no warning. When you add a LOOKAHEAD specification, = JavaCC=20 assumes you know what you are doing and suppresses any warnings.=20

4.7  Are semantic actions = executed during=20 syntactic lookahead?

No.=20

4.8  Are nested syntactic = lookahead=20 specifications evaluated during syntactic lookahead?

No!=20

This can is a bit surprising. Consider a grammar=20

void start( ) : { } {=20

LOOKAHEAD( a() )=20
a()=20
< EOF >=20

|=20

w()=20
< EOF >=20

}=20

void a( ) : { } {=20

(=20

LOOKAHEAD( w() y() )=20
w()
|=20

w() x()
)=20
y()

}=20

void w() : {} { ''w'' }=20

void x() : {} { ''x'' }=20

void y() : {} { ''y'' }

and an input sequence of "wxy". You might expect that this string = will be=20 parsed without error, but it isn't. The lookahead on a() fails so the parser takes the second (wrong) = alternative in start. So why does the = lookahead on=20 a() fail? The lookahead specification = within=20 a() is intended to steer the parser to the = second=20 alternative when the remaining input starts does not start with "wy". = However=20 during syntactic lookahead, this inner syntactic lookahead is ignored. = The=20 parser considers first whether the remaining input, "wxy", is = matched by=20 the alternation (w() | w() x()). First it tries the first = alternative=20 w(); this succeeds and so the alternation = (w() | w() x())=20 succeeds. Next the parser does a lookahead for y() on a remaining input of "xy"; this of course = fails, so=20 the whole lookahead on a() fails. = Lookahead does not=20 backtrack and try the second alternative of the alternation. Once one=20 alternative of an alternation has succeeded, the whole alternation is = considered=20 to have succeeded; other alternatives are not considered. Nor does = lookahead pay=20 attention to nested synactic LOOKAHEAD specifications.=20

This problem usually comes about when the = LOOKAHEAD specification looks=20 past the end of the choice it applies to. So a solution to the above = example is=20 to interchange the order of choices like this:=20

void a( ) : { } {=20

(=20

LOOKAHEAD( w() x() )=20
w() x()
|=20

w()
)=20
y()

}

Another solution sometimes is to distribute so that the earlier = choice is=20 longer. In the above example, we can write=20

void a( ) : { } {=20

LOOKAHEAD( w() y() )=20
w() y()
|=20

w() x() y()

}

Generally it is a bad idea to write syntactic look-ahead = specifications that=20 look beyond the end of the choice they apply to. If you have a = production

a=AE A=20 | = B
and you=20 transliterate it into JavaCC as=20

void a() : {} { LOOKAHEAD(C) A = | B } =

then it is a good idea that L(C) (the language of = strings=20 matched by C) is a set of prefixes of L(A). That is =

"u = =CE L(C)=B7$v =CE S*=B7uv=20 =CE=20 = L(A)
In = some=20 cases to accomplish this you can put the ``longer'' choice first (that = is, the=20 choice that doesn't include prefixes of the other); in other cases you = can use=20 distributivity to lengthen the choices.=20

4.9  Are parameters passed during = syntactic=20 lookahead?

No.=20

4.10  Are semantic actions = executed during=20 syntactic lookahead?

No.=20

4.11  Is semantic lookahead = evaluated=20 during syntactic lookahead?

Yes. It is also evaluated during evaluation of LOOKAHEAD( n ), = for=20 n > 1.=20

4.12  Can local variables = (including=20 parameters) be used in semantic lookahead?

Yes to a point.=20

The problem is that semantic lookahead specifications are evaluated = during=20 syntactic lookahead (and during lookahead of more than 1 token). But the = subroutine generated to do the syntactic lookahead for a nonterminal = will not=20 declare the parameters or the other local variables of the nonterminal. = This=20 means that the code to do the semantic lookahead will fail to compile = (in this=20 subroutine) if it mentions parameters or other local variables.=20

So if you use local variables in a semantic lookahead specification = within=20 the BNF production for a nonterminal n, make sure that n = is not=20 used in syntactic lookahead, or in a lookahead of more than 1 token.=20

This is a case of three rights not making a right! It is right that = semantic=20 lookahead is evaluated in during syntactic lookahead, it is right (or at = least=20 useful) that local variables can be mentioned in semantic lookahead, and = it is=20 right that local variables do not exist during syntactic lookahead. Yet = putting=20 these three features together tricks JavaCC into producing uncompilable = code.=20 Perhaps a future version of JavaCC will put these interacting features = on a=20 firmer footing.=20

4.13  How does JavaCC differ = from standard=20 LL(1) parsing?

Well first off JavaCC is more flexible. It lets you use multiple = token=20 lookahead, syntactic lookahead, and semantic lookahead. If you don't use = these=20 features, you'll find that JavaCC is only subtly different from=20 LL(1) parsing; it does not calculate "follow sets"in the standard = way - in=20 fact it can't as JavaCC has no idea what your starting nonterminal will = be.=20

4.14  How do I communicate from = the parser=20 to the token manager?

It is usually a bad idea to try to have the parser try to influence = the way=20 the token manager does its job. The reason is that the token manager may = produce=20 tokens long before the parser consumes them. This is a result of = lookahead.=20

Often the work-around is to use lexical states to have the token = manager=20 change its behaviour on its own.=20

In other cases, the work-around is to have the token manager not = change its=20 bevhaviour and have the parser compensate. For example in parsing C, you = need to=20 know if an identifier is a type or not. If you were using lex or yacc, = you would=20 probably write your parser in terms of token kinds ID and TYPEDEF_NAME. = The=20 parser will add typedef names to the symbol table after parsing each = typedef=20 definition. The lexical analyzer will look up identifiers in the symbol = table to=20 decide which token kind to use. This works because with lex and yacc, = the=20 lexical analyzer is always one token ahead of the parser. In JavaCC, it = is=20 better to just use one token kind, ID, and use a nonterminal in place of = TYPEDEF_NAME:=20

void typedef_name() : {} {=20

LOOKAHEAD( { getToken(1).kind =3D=3D ID && = symtab.isTypedefName(=20 getToken(1).image ) } )=20
< ID > }

But you have to be careful using semantic look-ahead like this. It = could=20 still cause trouble. Consider doing a syntactic lookahead on nonterminal = `statement'. If the next statement is something = like=20

{ typedef int T ; T i ; i =3D 0 ; return i ; }=20

The lookahead will fail since the semantic action putting T in the = symbol=20 table will not be done during the lookahead! Luckly in C, there should = be no=20 need to do a syntactic lookahead on statements.=20

[TBD. Think through this example very carefully.]=20

4.15  How do I communicate from = the token=20 manager to the parser?

As with communication between from the parser to the token manager, = this can=20 be tricky because the token manager is often well ahead of the parser.=20

For example, if you calculate the value associated with a particular = token=20 kind in the token manager and store that value in a simple variable, = that=20 variable may well be overwritten by the time the parser consumes the = relevant=20 token. Instead you can use a queue. The token manager puts information = into the=20 queue and the parser takes it out.=20

Another solution is to use a table. For example in dealing with=20 #line directives in C or C++, you can have the token manager = fill a=20 table indicating on which physical lines the #line directives occur and what = the value=20 given by the #line is. Then the parser can use this table to = calculate=20 the "source line number"from the physical line numbers stored in the = Tokens.=20

4.16  What does it mean to put a = regular=20 expression within a BNF production?

It is possible to embed a regular expression within a = BNF production.=20 For example=20

//A regular expression production=20

TOKEN : {  < ABC : "abc"  > }=20

      =20

//A BNF production=20

void nonterm() : {} {=20

"abc"=20

"def"=20

< (["0"-"9"])+ >=20

"abc"=20

"def"=20

< (["0"-"9"])+ >=20

}

There are six regular expressions within the BNF production. The = first=20 is simply a Java string and is the same string that appears in the = earlier=20 regular expression production. The second is simply a Java string, but = does not=20 (we will assume) appear in a regular expression production. The third is = a=20 "complex regular"expression. The next three simply duplicate the first = three.=20

The code above is essentially equivalent to the following:=20

//A regular expression production=20

TOKEN : {  < ABC : "abc"  > }=20

TOKEN : {  < ANON0 : "def"  > = }=20

TOKEN : {  < ANON1 :  < = (["0"-"9"])+ > }=20

TOKEN : {  < ANON2 :  < = (["0"-"9"])+ > }=20

      =20

//A BNF production=20

void nonterm() : {}=20

{=20

< ABC >=20

< ANON0 >=20

< ANON1 >=20

< ABC >=20

< ANON0 >=20

< ANON2 >=20

}

In general when a regular expression is a Java string and identical = to=20 regular expression occurring in a regular expression production5, then the Java string is = interchangeable with=20 the token kind from the regular expression production.=20

When a regular expression is a Java string, but there is no = corresponding=20 regular expression production, then JavaCC essentially makes up a = corresponding=20 regular expression production. This is shown by the "def"which becomes an anonymous regular = expression=20 production. Note that all occurrences of the same string end up = represented by a=20 single regular expression production.=20

Finally consider the two occurrences of the complex regular = expression < (["0"-"9"])+ > . Each one is turned into = a=20 different regular expression production. This spells trouble, as the = ANON2 regular expression production will never = succeed.=20 (See Question 3.3.=20 `` What if more than one regular expression matches a prefix of the = remaining=20 input?'' )=20

See also Question 4.17,=20 `` When should regular expressions be put directly into a = BNF production?''=20 .=20

4.17  When should regular = expressions be=20 put directly into a BNF production?

First read Question 4.16,=20 `` What does it mean to put a regular expression within a = BNF production?''=20 .=20

For regular expressions that are simply strings, you might as well = put them=20 directly into the BNF productions, and not bother with defining = them in a=20 regular expression production.6 For more complex regular expressions, = it is=20 best to give them a name, using a regular expression production. There = are two=20 reasons for this. The first is error reporting. If you give a complex = regular=20 expression a name, that name will be used in the message attached to any = ParseExceptions generated. If you don't give it a name, JavaCC will make = up a=20 name like " < token of kind 42 > ". The second is perspicuity. = Consider=20 the following example:=20

void letter_number_letters() : {=20

Token letter, number, letters; }

{=20

letter=3D < ["a"-"z"] >=20

number=3D < ["0"-"9"] >=20

letters=3D < (["a"-"z"])+ >=20

{ return some function of letter, number and = letters ; }

}

The intention is to be able to parse strings like "a9abc". = Written=20 this way it is a bit hard to see what is wrong. Rewrite it as=20

TOKEN :  < =  LETTER : ["a"-"z"] >=20 }=20

TOKEN :  <  NUMBER : ["0"-"9"] = > }=20

TOKEN :  < =  LETTERS : (["a"-"z"])+=20 > }=20

      =20

void letter_number_letters() : {=20

Token letter, number, letters; }

{=20

letter=3D < LETTER >=20

number=3D < NUMBER >=20

letters=3D < LETTERS >=20

{ return some function of letter, number and = letters ; }

}

and it might be easier to see the error. On a string like = "z7d"the=20 token manager will find a LETTER, a NUMBER and then another LETTER; the BNF production can not succeed. = (See=20 Question 3.3,=20 `` What if more than one regular expression matches a prefix of the = remaining=20 input?'' )=20

4.18  How do I parse a sequence = without=20 allowing duplications?

This turns out to be a bit tricky. Of course you can list all the=20 alteratives. Say you want A, B, C, each optionally, in any order, with = no=20 duplications; well there are only 16 possibilities:=20

void abc() : {} {=20

[ < A >  [ < B >  [ < C > =  ] ] ]=20

|=20

< A >   < C > [ < B >  ] =

|=20

< B >  [ < A >  [ < C >  ] = ]=20

|=20

< B >   < C > [ < A >  ] =

|=20

< C >  [ < A >  [ < B >  ] = ]=20

|=20

< C >   < B >  [  < A > =  ]=20

}

This approach is already ugly and won't scale.=20

A better approach is to use semantic actions to record what has been = seen=20

void abc() : {} {=20

(=20

< A >=20

{ if( seen an A already ) throw=20 ParseException("Duplicate A");=20
else record an A }
|=20

< B >=20

{ if( seen an B already ) throw=20 ParseException("Duplicate B");=20
else record an B }
|=20

< C >=20

{ if( seen an C already ) throw=20 ParseException("Duplicate C");=20
else record an C }
)*

}

The problem with this approach is that it will not work well with = syntactic=20 lookahead. Ninety-nine percent of the time you won't care about this = problem,=20 but consider the following highly contrived example:=20

void toughChoice() : {}=20

{=20

LOOKAHEAD( abc() )=20
abc()

|=20

< A > < A > < B > < B >=20

}

When the input is two A's followed by = two B's, the second choice should be taken. If you = use the=20 first (ugly) version of abc, above, then = that's what=20 happens. If you use the second (nice) version of abc, then the first choice is taken, since = syntactically=20 abc is ( < A = >=20  |  < B >  |  < C > )*.=20

4.19  How do I deal with = keywords=20 that aren't reserved?

In Java, C++, and many other languages, keywords, like "int", "for",=20 "throw"and so on are reserved, meaning that you can't use them = for any=20 purpose other than that defined by the language; in particular you can = use them=20 for variable names, function names, class names, etc. In some = applications,=20 keywords are not reserved. For example, in the PL/I language, the = following is a=20 valid statement=20

if if =3D then then then =3D else ; else else =3D if ;=20

For a more modern example, in parsing URL's, we might want to treat = the word=20 "http"as a keyword, but we don't want to prevent it being used as a host = name or=20 a path segment. Suppose we write the following productions7:=20

TOKEN : {  < HTTP : "http" > }=20

TOKEN : { < LABEL :  < ALPHANUM > = | < ALPHANUM > ( < ALPHANUM > = |"-")* < ALPHANUM > }=20

void httpURL() : {} { < HTTP > =  ":""//"host()=20 port_path_and_query() }=20

void host() : {} {  < LABEL > ("." < = LABEL >=20 )* }

Both the regular expressions labelled HTTP and=20 LABEL, match the string "http". = As covered=20 in Question 3.3,=20 `` What if more than one regular expression matches a prefix of the = remaining=20 input?'' the first rule will be chosen; thus the URL=20

http://www.http.org/

will not be accepted by the grammar. So what can you do? There are = basically=20 two strategies: replace keywords with semantic lookahead, or put more = choices in=20 the grammar.=20

Replacing keywords with semantic lookahead. Here we eliminate = the=20 offending keyword production. In the example we would eliminate the = regular=20 expression production labelled HTTP. Then we have to rewrite httpURL as=20

void httpURL() : {} {=20

LOOKAHEAD( {getToken(1).kind =3D=3D LABEL=20 && getToken(1).image.equals("http")} )=20
< LABEL >  ":""//"host() port_path_and_query() }=20

The added semantic lookahead ensures that the URL really begins = with a=20 LABEL which is actually the keyword "http". [TBD Check this = example.]=20

Putting more choices in the grammar. Going back to the = original=20 grammar, we can see that, the problem is that where we say we expect a = LABEL we actually intended to expect either a = LABEL or a HTTP. = We can=20 rewrite the last production as=20

void host() : {} { label() ("."label())* }=20

void label() : {} {  < LABEL > =  |  < HTTP >  }=20

4.20  There's an error in the = input, so=20 why doesn't my parser throw a ParseException?

Perhaps you forgot the < EOF > in = the=20 production for your start nonterminal.=20

Chapter 5
Semantic Actions

5.1  I've written/found a parser, = but it=20 doesn't do anything?

You need to add semantic actions. Semantic actions are bits of Java = code that=20 get executed as the parser parses.=20

5.2  How do I capture and = traverse a=20 sequence of tokens?

Each Token object has a pointer to the next Token object. Well that's = not=20 quite right. There are two kinds of Token objects. There are regular = token=20 objects, created by regular expression productions prefixed by the = keyword TOKEN. And, there are special token objects, = created by=20 regular expression productions prefixed by the keyword SPECIAL_TOKEN. Each regular Token object has a = pointer to=20 the next regular Token object. We'll deal with the special tokens later. =

Now since the tokens are nicely linked into a list, we can represent = a=20 sequence of tokens occurring in the document with a class by pointing to = the=20 first token in the sequence and the first token to follow the sequence.=20

class TokenList {=20

private Token head ;=20
private Token tail ;

      =20

TokenList( Token head, Token tail ) {=20

this.head =3D head ;=20
this.tail =3D tail ; }
...

}

We can create such a list using semantic actions in the parser like = this:=20

TokenList CompilationUnit() : {=20

Token head ;

} {=20

{ head =3D getToken( 1 ) ; }=20
[ PackageDeclaration() ] ( ImportDeclaration() )* (=20 TypeDeclaration() )*=20
< EOF >=20

{ return new TokenList( head, getToken(0) ) ; } =

}

To print regular tokens in the list, we can simply traverse the list=20

class TokenList {=20

...=20
void print( PrintStream os ) {=20

for( Token p =3D head ; p !=3D tail ; p =3D p.next = ) {=20

os.print( p.image ) ; } }
...

}

This method of traversing the list of tokens is appropriate for many=20 applications.=20

Here is some of what I got from printing the tokens of a Java = file:=20


=
publicclassToken{publicintkind;= publicintbeginLine,
Obviously=20 this is not much good for either human or machine consumption. I could = just=20 print a space between each pair of adjacent tokens. A nicer solution is = to=20 capture all the spaces and comments using special tokens. Each Token object (whether regular or special) has a = field=20 called specialToken, which points to the = special=20 token that appeared in the text immediately prior, if there was one, and = is null=20 otherwise. So prior to printing the image of each token, we print the = image of=20 the preceding special token, if any:=20

class TokenList {=20

...=20
private void printSpecialTokens( PrintStream = ps, Token=20 st ) {=20

if( st !=3D null ) {=20

printSpecialTokens( ps, st.specialToken ) ;=20
ps.print( st.image ) ; } } =

      =20

void printWithSpecials( PrintStream ps ) {=20

for( Token p =3D head ; p !=3D tail ; p =3D p.next = ) {=20

printSpecialTokens( ps, p.specialToken ) ;=20
ps.print( p.image ) ; } }

}

If you want to capture and print a whole file, don't forget about the = special=20 tokens that precede the EOF token.=20

Chapter 6
JJTree and JTB

TBD. Your maintainer knows little about either of these tools and = would=20 especially appreciate volunteers to contribute to this part of the FAQ.=20

6.1  What are JJTree and = JTB?

These are preprocessors that produce .jj files. The .jj files = produced will=20 produce parsers that produce trees.=20

6.2  Where can I find = JJTree?

JJTree comes with JavaCC. See Question 1.9,=20 `` Where can I get JavaCC?''. .=20

6.3  Where can I find JTB?

See JTB: The Java Tree = Builder=20 Homepage..=20

Chapter 7
Applications of JavaCC

7.1  Where can I find a parser = for=20 x?

First look in Dongwon Lee's JavaCC Grammar = Repository.=20

Then ask the newsgroup or the mailing list.=20

7.2  How do I parse arithmetic=20 expressions?

See the examples that come with JavaCC.=20

See any text on compiling.=20

See Parsing= =20 Epressions by Recursive Descent.=20

7.3  I'm writing a programming = language=20 interpreter; how do I deal with loops?

A lot of people who want to write an interpreter for a programming = language=20 seem to start with a calculator for expressions, evaluating during = parsing, as=20 is quite reasonable. Then they add, say, assignments and if-then-else=20 statements, and all goes well. Now they want to add loops. Having = committed to=20 the idea that they are evaluating while parsing they want to know how = back up=20 the token manager so that loop-bodies can be reparsed, and thus = reevaluated,=20 over and over and over again.=20

It's an interesting idea, but it's clear that JavaCC will not make = this=20 approach pleasant. Your maintainer suggests translating to an = intermediate code=20 during parsing, and then executing the intermediate code. A tree makes a = convenient intermediate code. Consider using JJTree or JTB (see Chapter = 6=20 ).=20

If you still want to back up the token manager. I suggest that = you start=20 by tokenizing the entire file, capturing the tokens in a list (see = Question 5.2,=20 `` How do I capture and traverse a sequence of tokens?''. ) or, better, = a=20 Vector. Now write a custom token manager that delivers this captured = sequence of=20 tokens, and also allows backing up.=20

Chapter 8
Comparing JavaCC with other = tools

[TBD. Your maintainer would welcome comparisons with ANTLR, CUP, = JLex,=20 JFlex, and any others that users can contribute. My limited = understanding is=20 that CUP is similar to Yacc and Bison, and that JLex and JFlex are = similar=20 to Lex and Flex.]=20

8.1  Since LL(1) =CC LALR(1), wouldn't a tool based on = LALR parsing=20 be better?

It's true that there are strictly more languages that can be = described by=20 LALR(1) grammars than by LL(1) grammars. Furthermore almost every = parsing=20 problem that arises in programming languages has an = LALR(1) solution and=20 the same can not be said for LL(1).=20

But the situation in parser generators is a big more complicated. = JavaCC is=20 based on LL(1) parsing, but it allows you to use grammars that are not = LL(1). As=20 long as you can use JavaCC's look-ahead specification to guide the = parsing where=20 the LL(1) rules are not sufficient, JavaCC can handle any grammar = that is=20 not left-recursive. Similarly tools based on LALR(1) or = LR(1) parsing=20 generally allow input grammars outside those classes.=20

A case in point is the handling of if-statements in C, Java, and = similar=20 languages. Abstracted, the grammar is

S=AE x=20 | iS | = iSeS
The=20 theoretical result is that there is no LL(1) grammar that can handle the = construct, but there is an LALR(1) grammar. Experienced parser generator = users=20 ignore this result. Both users of LALR(1) based parser generator = (such as=20 yacc) and users of LL(1) based parser generators (such as JavaCC) = generally=20 use the same ambiguous set of grammar rules, which is neither LALR(1) = nor LL(1),=20 and use other mechanisms to resolve the ambiguity.=20

8.2  How does JavaCC compare with = Lex and=20 Flex?

Lex is the lexical analyzer supplied for many years with most = versions of=20 Unix. Flex is a freely distributable relative associated with the GNU = project.=20 JavaCC and lex/flex are actually quite similar. Both work essentially = the same=20 way, turning a set of regular expressions into a big finite state = automaton and=20 use the same rules (for example the maximal munch rule). The big = difference is=20 the lex and flex produce C, whereas JavaCC produces Java.=20

One facility that lex and flex have, that JavaCC lacks, is the = ability to=20 look ahead in the input stream past the end of the matched token. For a = classic=20 example, to recognize the Fortran keyword "DO", you have to look forward = in the=20 input stream to find a comma. This is because=20

DO 10 I =3D 1,20=20

is a do-statement, whereas=20

DO 10 I=20

is an assignment to a variable called DO10I (Fortran totally = ignores=20 blanks). Dealing with this sort of thing is easy in lex, but very hard = in=20 JavaCC.=20

However JavaCC does have some nice features that Lex and Flex=20 lack: Common token actions, MORE rules, SPECIAL_TOKEN rules.=20

8.3  How does JavaCC compare with = other=20 Yacc and Bison?

Yacc is a parser generator developed at Bell labs. Bison is a freely=20 distributable reimplementation associated with the GNU project. = Yacc and=20 Bison produce C whereas JavaCC produces Java.=20

The other big difference is that Yacc and Bison work bottom-up, = whereas=20 JavaCC works top-down. This means that Yacc and Bison make choices after = consuming all the tokens associated with the choice, whereas JavaCC has = to make=20 its choices prior to consuming any of the tokens associated with the = choice.=20 However, JavaCC's lookahead capabilities allow it to peek well ahead in = the=20 token stream without consuming any tokens; the lookahead capabilities = ameliorate=20 most of the disadvantages of the top-down approach.=20

Yacc and Bison require BNF grammars, whereas JavaCC accepts=20 EBNF grammars. In a BNF grammar, each nonterminal is described as = choice of=20 zero or more sequences of zero or more terminals and = nonterminals.=20 EBNF extends BNF with looping, optional parts, and allows choices = anywhere,=20 not just at the top level. For this reason Yacc/Bison grammars tend to = have more=20 nonterminals than JavaCC grammars and to be harder to read. For example = the=20 JavaCC production=20

void eg() : {} {a() (b() [","])* }=20

might be written as=20

eg : a eg1=20

;=20

eg1 : /* empty */=20

|eg1 b optcomma

;=20

optcomma : /* empty */=20

| ','

;

More importantly, it is often easier to write semantic actions for = JavaCC=20 grammars than for Yacc grammars, because there is less need to = communicate=20 values from one rule to another.=20

Yacc has no equivalent of JavaCC's parameterized nonterminals. While = it is=20 fairly easy to pass information up the parse-tree in Yacc (and JavaCC), = it is=20 hard to pass information down the tree in Yacc. For example, if in the = above=20 example, if we computed information in parsing the a=20 that we wanted to pass to the b, this is = easy in=20 JavaCC, using parameters, but hard in Yacc.=20

As the example above shows, Yacc has no scruples about left-recursive = productions.=20

My assessment is that if your language is totally unsuitable for = top-down=20 parsing, you'll be happier with a bottom-up parser like Yacc or Bison. = However,=20 if your language can be parsed top-down without too many appeals to = lookahead,=20 then JavaCC's combination of EBNF and parameters can make life much more = enjoyable.=20

Footnotes:

1Another=20 way of looking at it is that JavaCC is of little help in this regard. = However,=20 if you want to produce trees there are two tools, based on JavaCC, that = are less=20 flexible and more helpful, these are JJTree and JTB. See Chapter 6=20 .=20

2JavaCC's=20 terminology here is a bit unusual. The conventional name for what JavaCC = calls a=20 "token kind" is "terminal" and the set of all token kinds is = the=20 =E4lphabet" of the EBNF grammar.=20

3This=20 example is quoted from

examples/JJTreeExamples/eg4.jjt
Your=20 maintainer inspected it carefully before copying it into another .jjt = file. As=20 testing revealed, it is not, however, correct, which shows that even the = experts=20 can be befuddled by complex regular expressions, sometimes. Can you spot = the=20 error? A correct regular expression is=20

< "/*"(~["*"] |("*")+ ~["/"])* = ("*")+ "/"=20 >

... I think.=20

4The=20 rule that an EOF token is produced at the = end of the=20 file applies regardless of the lexical state.=20

5And=20 provided that regular expression applies in the DEFAULT lexical state.=20

6Ok=20 there are still a few reasons to use a regular expression production. = One is if=20 you are using lexical states other than DEFAULT. Another is if you want = to=20 ignore the case of a word. Also, some people just like to have an = alphabetical=20 list of their keywords somewhere.=20

7This=20 example is based on the syntax for HTTP URLs in RFC: 2616 of the = IETF by=20 R. Fielding, et. al. However, I've made a number of=20 simplifications and omissions for the sake of a simpler example. =

File translated from TEX by TTH, version 3.11.
On 2 Jul 2002, = 10:50.=20 ------=_NextPart_000_0000_01CA351D.C4D99D00 Content-Type: image/png Content-Transfer-Encoding: base64 Content-Location: http://www.idevelopment.info/data/Programming/java/JavaCC/token-manager.png iVBORw0KGgoAAAANSUhEUgAAAycAAAJsAQAAAADPOuEfAAAABlBMVEUAAAAAAAClZ7nPAAAAAnRS TlMAAQGU/a4AAAACYktHRAAB3YoTpAAAAAlwSFlzAAASdAAAEnQB3mYfeAAAETVJREFUeNrt3U+P 48h1AHDKfVACBEMjewqwGNqnvWY9lxmgV7RPPu5HyAI+7NGz6MPsYNtd3RgjnUOQRk7BAOPhxwgM O2YPGrByaAw/QAxTDRlDBDaGlImAJFisl6oiKVESSbEokjutLe5Oo5ui+BNZ9V79ISUpAP0vRAGp SEUqUpGKVAZXfADLh4h8qVsAuo/pXxj0R9gA/jt95BvDAScC/pMg44pt8MjfQ5n4OGA7mTzC9lI5 WVNeH7ENPm2poOKxHPuVyqso3WAP5TMfx5liVSi/Stoo8OkcYAHgAJ5CAhCzdRjA/RTglj9yDeQM wUsgP2MPJXQbg20goLgAP3gDcI6YcsGIJFd+gOC/KYEy5d+B/LitQo/j4W/p03SmPC8qzkMEU/6I z5UrIMfsoQhnGwgo9IRMTmmpcwWvKXQdLSnTzBSD/2yn4FQhGwr9EWSKUaoQ0dhnyixT/OxVRrTu pYqilSuohXK5ofi7FNBFlF+lirmtxKmiw4aSJOLKi/XSL5yxekXsjM3L6xj9EVWUfpKI1zEvVSbb NTlJFR4vcLxScCSsxH9BXLmoVGjs01fyvZVCjoRjP4SPuTI1txScKgu2Efx+pdAkIKpg9Gbt70K2 rFtswXLR74ZQNjemmaWBAt0oRN+x4aKF4m+fyR1H4Ysr5G+U5st43LI/9kao6xXqrZSdhbCxTFsp kWA/MmqlBKK91VaKK9opRm0UQ1Qx2ihIVHFbKER4GBG0UCJhJWqhBMIKEVOIys8yUQTiknadSkqy VtF5YxGxRrHhgmmjCqb4GTNpyvAbKz5roFsp+u5Wa7nwLpotriBS255sNzxWScDUKt6IVpiEF07z 6hWIKnP2vFggl7FXFJdU/lrFYc8LBIImhvwZAorLnuNmz26aXJKSrXcpMS+TRCBRElHFYYopkDJ5 LUGCSsAUJKqYiZhCO28BEWlkeNTbgspsJKjwzWwiHPtBsnqRDRW3ZyXdfQvFTVbF2lAJWiixuLJd irvaSiElaaXQPO4GAl2/JEtmSPiMDaLYH65iSuUwlEOKl4GU3vPYMDm50Ir13L4M01YO1O636MMk PStmS6VN3zJuofTeT+aB1nufH9qNXwJhhfQ/Flsef9NpBcyH/GKjVz5DgnDPI3E+Q8JmFZrPXtkt ZxVM+uKaz1457KS1mCGx6Yhs2lgJ2RxBC8UF8rHAzNUD8ZkrOuJj1XIuMAW3EJ6FW4aA2JK0UBJh JW6hDDMHC7qoYoF47DeeG1tvygRjn03GCC0EtTljw1wZIUhMcVopohctjHbKnRASonYKUUSWttf4 OlikIhWpSEUqUjk8BTdoZ/dXkp193y4Usj1dcG+VjWGbfa8Vc9doQSrbcx2VpXTfFHe/gfJ3UAn2 m8D4oJR4x9TKfVKSDhux74ZCOmwqv21lLUHaUmmgmN01ld+6YnfXVH7rittdI1apnCtqcaO2i1qv 7Fve6ydEKlKRilSkIhWpSEUqUpGKVKQilUNSZgp7T+vq1p0Z+2gYqYgoOpz3UPocGFq50+D7Utml eChEL+ASLi+pckX+ka34GrFPkVBVtlrrRLnWQjTGI/hnJVPOx+EXKlG08Eilq3/ZjaKMw1PVU9Av FQR3FnlKlKPwx+NQUb0RX92JQtQX4dfaDOsXHlWm+CnWb0Jt7IE6C1W2upNyIdpN+BTNif4izBR0 F+qXC7i8wypb3YmC9bvwC5iCdol1uHOwF1IF3dzB5Q1R2epuFLQIf7JU5qFH6wBVAC6n0K1ytK68 4cq4SyVEHlXOFZUrfuRBOGLKbHwJKlvdg7JYeHDOFKJ0royKClFYuYRHl10rX9BMAlwJ5x7WmOIh prDVnSlPUVHRuQKdKqyOfY2mK2UZL7yOdaic6rmCf9qTQk/QqXaTxQtX3nBlTGP/pqt4YXnsTLsj mTKmygVTyJjmMbYausrJiCVfrhCVlj6LFw+P05zcjcLaF3TpKStF+SFTlEvevnSlsLbyBVYgV4jy FYvK0ZS1lUpHpc/b/RvWwDMFNA9uPLaClnza7vfe59cGGFlcHpByQ4ZQ3tDq0L8yU9AAiqcMMXol qhyJS0UqUpGKVKQiFalIRSpSkYpUDlQ5b3PPc+FdmM3ugm61FN70sT7J0KniVp3xe6jYpb/ee8Xt TzEPUwn6U9DQStybUnxrySEpSW9KMrhCelPiwZX1Zuz+KcHwitmX4g6v2PdbsYdX3PutmJXV+v4p qDLddKmsjTKOeutdVLei3SrJEApJysZInR9L+n1pJOlXMXltTnpW7FSJ+1Vcezgl7lkJ3CGULLsE gyjWEErfGWYY5TrLyD1HZVlfXCpSkYpUpHLIyvWIqKFy1rsSHvWvWDAPo97PmAUOHkKxyPMBFBsO Rbk+MuCxchiKBQY8gUNRhqljw8TLMLE/RB5jOXkIBbRItshSkYpU7rXy8qVUPkRF1mSpfAeU9Kux +lYWb4ZQrkS/FauN0omxU0kGKf1YxsuHqXhHQygWHkIxBzljSNYxqUjlQ1OCQZT/HUR5j4ZQbKMD Zef1fduF3paVYvqDKHgIBYl/F664Qvb/boxmitO/koh/F247paMeeZ3COspG7wpLlu4git+7wo4D D6I0jktFVx4gq4ViFxL3bkVVHuitlaZxqVsRaaXw3jiPy3B1X663ukdXn2W/sKDSnYj8U5mSP2FU 1xvncbkaYhbvAjTdwoZM+bxMCaB0MLzR5zebKz9voWQttdVQoeXyZXvFb6YoakROWijZatxQQRH5 pr3C9rGmKPq5viC0YpluBOdnSqpMqPK8hZLv2thU1HOVKlqqPFT0VNEjclqqYIWMsFKl5C/CYYqB R3BFh+ZU0S3D+hNBBleM1yhVdKqcVSgT5VTRdyhRqijoylO44hgOVaxUeUs5rhhU+bxUgcnZKVQp ednSuGQKQZ/4OFferyvXW1+HtKa8Rsdg7FBoXDIF9E98gjLl7dmaYqfxgq5Kmr0dyjIbW0mqPMsU iyvFcmHKdE/FJ1yZnKSKohqWfZbXsYmSKTTDsPbFFSyX5QQJhm8yhZeLgs41Y6JArgBXYNX0eYho 10r+Jgtex3BlHVt1khBTyFmc1rEJOkfm704hK5fnG8qylQDkqZ5KAjwiCo2DnYrxG1aTceSNuaIb oDw8TWPfeH+6ocSgTecL0Akgx5nOqUJP5XFUoRQGTw5TjpLEd3hN5spZprw721J0x4m4YgWWT5WQ oN+Gu5WIKbTB9OdcMWjd/SOtWpmCNhSCfAunik9DNcA01F7hCiVZJX7yP5nic+XKIOgt0jIlq8kF BWJW55hCaxBVyBl6RVC5kmVIj4FciYkfZXmMKUYelSWKkSoO7WcxZUIVvVbBKFd8chJyZWoQOny+ okp4dP4gi/2VgiHKFA9xhdbK46p4CVaxGf85U/I8huEdzzBUOatRsJoqD5Vj0GqVKfA3SZx/TFec YFTeVlYoME2V1yNclWGyXcwZyBUHHpEqhe03WClZ6UPASr+2rXSXrQtT6tt9rjiFOpZwxfDNeIey HmkiCo2XXDF2KYXZZFtIodXDzWPf9rtUaIFfXeiPHmlZHvO5MnWmzg6lMG41GygPjy70H/1ozJRr jaZVpszUmdpMmTdTQhw5+qcLhykhEC2NFx3r9UqeLNkXIaAGx5Ikjv6IJrplTSHZmKGR8grRX5so uI2SrzS1ZkqotFHyjc0pfXxD8XVfTxVs3VqdKE6m3NL/cuWzlfKvmRJBtXJr3VYo2UsgJgO5Et+W HctxE2Vao/wL+0NbKoVjmWwrdaV/61cptGQNuitDZSBXgqWSVUBe+npW+jReXosrLHnTf8aUgfHy HGZ1DG0p5OjuorL0fahWEBu5LJaKW6vA1WIurpjpRG9I2327gbLdSjRVaP4GPNmhoBLlSXh2wpSI 9qPqFQSJzx7Q0vHLhqLnCilVZg/XlbhaIb9I0t5FplhlCoYyxXq7rkQVCqur5i/ojwUDhZX36wqu UNg69yU9FH43brVSesb4ZQhW+jgr/TqFdr7hAkqV+tIH21lXqs4YLy/64zF/WLQmG0Gzmhxn+/pa b6U4zZQgjX/yjcqIXhX6e3xVpmxny3ZK/olnAQc3s2VXSn5l7hkHN5WkTHmHtmpyQwWemUslLlWu 9lHy/qtjMnBTKfRhrDLFstaV6S5FXyq1PaV6xapQ8l6yh8BsqBRKf6atxz7UK364PW/ZQGFfB9VA WeslrymlM/DFWbhiW0nqlXzVW52DBWXnZYIWiq3tpezowS53NuWPiiiFmSu+t5prFsud+VwJyz+x ZNeFn7Ir7kUlWF3o6ejGuxIlr6NE7ejmi1oF/7RXJQuzZNHbddGiQoO4N8U1s2SZEL2vS/wF5f/A 7FNBq+lEsz/FSGetWG5F/Snp/FB4pufKzg9Q3fViohIlXUf0q6wN8HYe0c6XoW4rJJvum2eKuv8p 8rYUO+3Uz7Nk2c1Vfn1TyTr4izzVz7tQptuKv3ZB1OhCibaVZO2iZie1efMTDoPCjTABdHbzhb6l LE+SC13fQZ4rMazuhHChsybG3VaiwgvoKPkH1fOWJnR2f1fZJ7bpK8VskmJ2LG82emSZYq2u9NF/ JV9FKFaNJ+p6Vc4Uf6nQR8N97yRbsP2hqqtvJP3N2fdOMosFXYmS7jZTjH2zjM7+N7eVdLdpL5mJ e93ih/nh2CWKk9e+YKNH3rISB6VKvHq4ZBZNPCDjtejOFZw/nM6Okn2VpFThcZkqe6d/l7/MoEyx sofd9EXs0zHjJYJKlfweRTvdaB+FPxfFZUqUvQg73WifnJnOdJUqLErSZIn2VLI5qKRMYXFZUAo1 ZDbKW2k/L0GH7emkVrHLFSc91GUfsFZh8xRVSlKnxGtKsJaWWihuuYLTQ0VdKaRUyW4wKFNCHIV4 GiJfW8BVaE3xl95EDz+if73T5/5EW0TGVltcpVhFpVgP9dnxYnZ8MdP+Or4+PfI+H4WfeI/V8O/H 1+hPmvLXx+Pr59qWElQo6YX9MsV6NbdePbeshWMcR86/nfpT7DvkK8fQ59bkK983HkNjJapU7D84 9h+wBb5v/jpy35LAwUFATnzTdN6fnfhg/rq5wqZgqZJsK8atZd+mirGw3pIvHez4TDEcBzPlZYlS TLjF97/8R7VinP8dnlFF0UbWrZIriuY41yehrvyDgOJWKypVPI0qHz/ZUB6c4LGQAtXKzw2MgSp6 Ell/ASdIFR0c5+wEpnrUjeIwxaJKtKG8o4pfqlSUPr88VlHHfFb6VDFfsjr2LK9jBq9jfmnpk6pW jCpuebz41ivs2DQyniyW8XLi03h5e3oSBcaTpsoz3sNI3PLYj2bHeEbL5fr0b3ns48cq+chnsf+9 k5DGvoASF5SNPIbZ/8j3F+QznsfIRIePfJrH0NUJoXkMGuax/wQY0y3sksxfsziCmf836esYRAns 7baynWLXK1vtvqhS1+7/V6bYQn2YaqW8p7RS+uyPpYprul31LUt7sH9cKn32k1dKn33+XAl6Hb+s Kz2NxXKFDggw7PkOpYhXcbteYcMyax+FDR+McqWQH6x958gNVnvMHYq/79yFUzF3sZYfMFrsOzU6 r1Bm+aQ2ffR8z3lr9u6PsjmlZRJ2u3ozX1Sv9DejWFT6mR3dVDp6L6dRr5BuFFSv9DMDv6UYnVex MsXtvIqVKZ28Y9TapfRyLWlL6eW62LbiKXsv6m6l+0Uq+ynqIMr4QM5YMJgyHkTRDuiMBaRvhTUr Ae5b8WgiVZQhztj5aJByOaA6digK+4GVIZRwkGPxYYioDA5EYXm//zPG3lob96+ErCPeuzJnPeTe lekgsa8NoaQzPH0r4SDZkg2fnipDxL4cv3xXR0ms9Mcg69iHOK7UZLxIRSpSkYpUulVmFZ9b1q3S 63JQyv8D76Zr4QKIjIoAAAAASUVORK5CYII= ------=_NextPart_000_0000_01CA351D.C4D99D00 Content-Type: image/png Content-Transfer-Encoding: base64 Content-Location: http://www.idevelopment.info/data/Programming/java/JavaCC/parser.png iVBORw0KGgoAAAANSUhEUgAAAssAAANiAQAAAAC/F7nkAAAABlBMVEUAAAAAAAClZ7nPAAAAAnRS TlMAAQGU/a4AAAACYktHRAAB3YoTpAAAAAlwSFlzAAASdAAAEnQB3mYfeAAAFrBJREFUeNrs3d9v 40Z+AHD5fKgaIFgB3ZcuujAX6MM+djd+uDVO1iBP7UPR/AfNAVvUr9f6IXbXEbUI0PTplD41i/o8 /Q/y2AYJTgq2iHKA4XnoQ1s0XcrQ1oPiilAKcSUJDmc6wx8SSZESJc24UY5MdteWrY+o73znO8Mh JdUYU7QNa2yb6XFdGY0cZTRguiKaqou1r472qrzO0FRdXk88dV2GKKN76mKtV8lX0d9H2lZH/7c6 +htdGW1AdbSpjO5Z6miijNZl19XZ2MgYVEdjRTSfPrnqaKqI9oLZqhJaVCekjrbV0KKbu+poWrbT dLROHeCytCH+KttpOvVOXVuNLlv8ICasPB3M+coWP2gR9gel6SDMQfFzavG2M/uypg2jL0BEP8yj p3eYn07qqcMaPzHnno4UvYj+UR7tzSpS9uAOlqR5rPdXpHE5ulMn7KAsHR03uiVpQNjhijTN0h2t rzmMt51huqyj1/QwIJxulqW96aF6hq7365xuhLRW00JaI6x1VJKOKxMSP4Zkh3XHu4KGGOFvdYAC GkIAQxoSBnJpWtNr/E8ebYd0Te+OawFtIYvTOKQRf4yA5sdr4GE+rdVaNS1Jx43khjTVH/LUjWg7 Tfdn/ag+T+sQtHSYR/PiJ2i+TxbVIxqDFG2EeQ0GOQWe0whc6ChJG9PyENHvRTQO6GSsBT1ahzb9 gG4dh3SnjrDZizMEiAwxwo4u6nUpenqwa9GYDmLdAf0GgjydI1oP6JzpficI/rOcWE/HF8KeiWZs e1GGgD4wjJYexbrJ0vSs0vUIIIA9ExnSTmfIbOjSPxPJR9xxPaA1xDqNVtgbodnK7LXHhg2yM6y1 WW/cGDcEzTid7DKJ2Q38D07v+r6FAxoKGkQ0BnN0dzQhjAegh/FgxOkzBi7OCmgsaF7TrVFAI55u Jk+MiAZZGlq8vQWNbGQJWgevzpK9MbFg5v4qoq2AHiCeC6Ab0zBLAxczENAWdDnd1sFVO0lHZUWM jTSgPWq5UQ0RNIq7zByt+7y3BbTIMp4hAFzpYJ4eiycQ0BY9dgJ6hJhu8+5hmM4uDzqap1FIY1E1 Oa1xOpkhUYISPUHHNYTqVtDROa3P0VQnET3WQxryLgPnaXEvj/eT+/yGY6LnjzIFNGmEdLe2p3cT dHS/wZTGbJ+uRrNBSKMaTXX06H6jMH6Lx0bDhfHTDOioGZktmnF+lDFmo65ZisbJDAnyGlo9L49O LMWtSIu8jmi4jDZWoxO90bDyaH0Vmrmw+xzs72upGjLAA7yAnoi7lqD3dp+Dt96qx5UvoIeNYSOH jqvTUC9FO8TF4PEEC5r3skaY10G9LqSveGrqJfba9zHY5/XLnk1pwtaap+PCZ3T5jWVoUpqOf8MY laOd2uo0r9FZ2gIWCGl6dHO0Mh2PzO+yiL7k/8X04Yz+MqJdVkzfHN3oOXRDPIGA9i7z9vqiDP00 RfM4/o3490PxKNm9bs3Ti5rx5jRFiwkREPOtKW1P6Sgzg2aEUTPyvL4oTwPBO+IJeNMQRRmiz9F0 9/p5YTO6qWbkt+tYzNhATJsLadadjMrTYpnP4SOnUYJODrvLaH5nPhdgvAgspns59IHTPhY0QRbI pX1LdHZN3HuOBlMa5NHDvTTtJ2n+BX3fD4ddPaRRHh2sl8zR6CpNkyQt1N77Yb1eg/4mTYvfStHm C77TrritmM4NSPigPJCCnKODTse7y3OWSy9uRmbgNJ0KiBcxT4InsGryQXtB8tkRcAKEuzKNl9EG o88a0uloAKFeNzyQTtPz5WkFOvplarMpbS+hg0K7Av1esLdZ2l9Cx8mXS8fTsvd6U9rLpQdr07gn nkCWTozoOI/mx2gpepSk4xkfBuI3lk8W0s2YpXEePdbXoYdaujcmJwvxtMxygkdZlXb0YjqelvVZ ls5d+Eyu4qRGmQU0n0xmFuOWrtsuo6fTMi3A1qZZMc3TdlU6sR4SfH+SWQmersVYAZtYZF7hzEC4 iqNn1q/N2cK7zCs5ON2LC19D7ukTQUeJSv5QGe1Pyp+HKEebvag6+fxgylBEUyCdjjLm1zw3e5Jp OFsdkk2Hh/KuqGC6ZDo8Yee0QVxeO7Ul27JzniSmQ5CCbkSPl+57f9lj10PaCOeLJh/U/LhXbro5 IKJRuO5khbSUE5qDgI5O2E3ieirldLob0X4cem+V85kLNypoO3Hi1c4sFm2w6SE93VEzTpzNNxjR OEFLGg1MTnuJpDDknUy3I5omaEkl240X48DsFIqkukpjGs3Oc/TK9PRllUlYEW3NaP6n8eGGe6zx WtFLnYag4Z9xMEPcYJuI2h/TYaeJaLRpj0Si8Yz4bBKM990Por1ZmgRrH2ZM45j2gmjbG9YPvm9m 6rSxF/yhm3ZJP+gxdkyTuDrZQdfcqJBYQY+xExekx/TG5S+4ioV5s2uCo9vMsAk3mTUE/Vn3Upf5 hLQhm3aj24zwJ5tUkmC3ev7sGjM9rk49tmH9CwBjRotOk0c7/CAiqovdMHLBAtSiy6/C9RM6o3F4 mxH+JI9uxEfbIp9Wob24puosNdaguJpHg/NSOhxXzARNwtuk0ewnswt3g7Om8XWOCZqCVhs8pppz D3YvT9jzx0wjjS7i3+jWHhjcgBHdn7gwQ9tJGgVFW6epw1jxkpRG86Tx4KTu3Nvb/eqR/vzBWZ3c 2UX8G+3bN/d2Xjdq5G7/VMscyKbocMV4nrbwEwvvHVv0hLiDTwDeO7VY071qugM4+dXV2Qi1Tkfw CcvQXpJ2C2jbPrBtsM/oqe8jCDD4sccO/av3fcQf9ZLgm/Yzq/fpQlqsanHaz9LY2retgHZJSLvs gFz6RNDIwZhw+sU8/Q+J66//LkH7SfrhcBc8AVP60Q6nf+nUArqDcf/Yqt1bTJtF9C6nm/U03Q/p q/sY31lOsyL69zADYDCl9xmnv3RZQBOM28cWcNekDwRtpemrUzZtxrJ0ToY0RTNaswxxeYagQ5LM kBcLM0R0cpqb100LgwObnhI3oA9EXiP+v6AdfHPG8/qgmBZLtbyLEzOvN7ZOGuAJb0a6y+lr3qKM 98aL3SDWP8T4B2e8Ny7Y6/eCzu/n0BSAFv9fo6eMVw4wAUBj3S5C3SD59jDutnkNYcUdndP8SXnx Aaq98vSgmP7H4FjPM+aKahnZXlivPwvjYBhr0BOsjHYa8wNYLr36iE7BwrHxP8PgGwomCxHdM+VP cTK0zInZqyltqqHNnoJJ8IxOHv6ueQwtuqQ9R3vxwdL6W3jcMkfrEo5lSLDnZvqq8XCQAZsuEgEx nTPnXlEl45DUSB2SJmmr/KX6+RsWMenNvw6MDzX6ZMNVPnEebEYP42VF3lk6my4i1rTZosW0Htmy lloIm6clLRB5ObTEZa0sLek1IiiHlvRan14OLXHhc46GchIkj8ZyEiSPlvImAINcmmkS4gHyaQkR sVg+7dQ23X67UUBL2ip6Id1QR9e3LiC2Wrqujta2MiA2VUKLYmUTJfS41mC1mrKAdHbUxXorM2T7 6GAgrimjHaYsry11tK0q1poymuiqAiKmkZ4ieiRmxWpoPm8dK8prTVlvDI/LldCOuhoyVkjz3vjT WjUJ3vL5tWjGujp6O2Ot8IBDq/K6oiu6oiv6N5geFryPiQRa/lbRFV3RFV3RFV3R3x86c/60IZHW 0zeaEule+kZjO+iM1dsOOtNu+jbSVGaXsW+L9mXS3m3Rnkzavy3a3hKa3hZtyqTTXVshbUile7dE 96TSxi3R+rbQpvxyfQu0Lb9c3wLtyS/XId2v7SZu2uRKwd0sLalnZ55xRVd0RVd0RVd0RVd0RVd0 RVd0RX+H6OHSt+PbgN5VR++ooq/ZWB1d/g3CVqaJQhpsJ000+gS8FG+yP6hLpvu79EGrppMd9s+S af3Da1r/pzYYO3rflkw3JrThMO2agC9k57U2ptqYwREVAZdJD2lIdwdMeym9hgQ0k0/zysd3nHd3 +TRgpMZpjad1Q3KsGes/ohrdYZ2afHqXx5r1gQI6yBDmiHd2lE4DQTMVNAnpDweK6JE62mIfvmRQ Ps27zIR1R5K7TNCMfd5lWONaenniyfcRp9vamEinWe0J7401QGrSm5FdOzz5vhBjo1S6ml9XdEVX dEVXdEVXdEVXdEVXdEVXdEXfFt1f88LAGUOLLhVcc6O5X0qhk9dv6ltDJ9ust5W0IZe2t5425dLm 7dC2XNrYetqTS/duh/bl0vrt0HRbaMpuh84ZZjag/duie1tCe7dFG1tC24XjwneZNhc80Ib0cO7j QuWVp6UPXdEVXdEVXdEVXdEVXdHbRI8Xrq3qm9B26cPeiq7oiq7oiv5+0yPxlwfF3278yeOS6OCC YCumGzLpAA0/AddNfMjjd5umv9X+czDqw8ENYPcc515XKv1njU4f7rxu0DeGT+7tSgzIRfspaloX ZyNEJujixJJKH+H28QXF2HeNV6euXPpGt87pEXZd40oZ3bmzhbQP6RbRswyR24yweYRFXmMs8lou /YMj3BnDHYx5b2zJpb88wiMHDjDmNURurKuxUTLt55zzlES7bP7Ta3+TaevBH+tD7ZddRz797YM/ 0obv/nt9CKTTE3cAXfSxhaD8gLgIueiF+MB7JbT5qWsgNTT+1E19BLZE2j5QRlunLmRqaE8d7Zx6 qpqRnCjJa+cd5Jy5KnqjRd5B5MyFCmpIsJFM7avJW+fz03T4LrRTYXreHyx6LgW0687JiSI+DY+x Bj1y5+REvKdf4TVonKA70b9onvbWoBNbR58L7JQmG9FTOXFVj7kk7crRUzk5FM9ouD49k5NNZuZ8 tSrdTzxhI4+21qX7yS4B8h7FX5NOyclrs2Y01deiU3JqQpWITW8depguEDifRmvQQy39fbJc9NLV NogKKE1n5dRde+k4rUbPyaku3Uu37kr0nJwuRL30sylN898Za/OlsGjA4m1An1IwemgtpQlg45xP tIBFNH9M+rbT+OJH9lJ6DPLkdInT05GiTQtf7OOldP9RnkwKH4f/hLZtu1eCzv98j1Qgs9dj0vaR BX5sLqNJ/htpmcU05N9z+iCPzpxLzKVhMW2Ge32IcuhU09rDPDpd4LLvuE91Tn9uLKXzZzwLvnP5 XmML/GJN2lpA0zBDWtp6tLmAZiDIa7AmDRfRRtAbAViLjlqRDEj76cDJzpkwPeI1ZE062k3yfLj3 9gdD4OUWxfXoqBXJKb46PEXQyy0C+lp01BsIQVdnrmF4eaWLrkf3Ypr9jNPIzmtkh61DxztEiHPn jB8F23mp6a5Fx/ci5Poqj7YKJwt2dHejiLantMlpOPc7/lIaFtGIJZsRzk1Pqb6QZgtokKINZBY0 8+r0tIZymmcIgmbR0yoIyE1rt4B2Z/TwT87cITDLLdVN6dd3img8oyffnLnO/NGiu5geoaKAGEtv oItpjItosJRmh+vRdPnTYP+2Hu2y5bk21NeicQl6DNaijTJ7ra1FA2U0KbMe1G+sQ3tl6E59Mf0y l8ZlaLK7mB7l0rDUAtn14sqXX2n0hX2os+DzSZbRhC2kC46jvTK0pY421dFw8WR7AzpvRJVE+0wZ HbfifiLChbQbmb1StDmlZ1n4cgFthQWtDA2n5Y/kLhytT1NdGX2pD27a4PGI7Y9nA0ly8a/nsO7l iaVNXPdjdo+97H88uWk2ytD91s7rnzYefMH2+4/y6WFr96tHf9non7oftd5gtf5HP3n9Zil6cHE2 svDe52wfns8eL9mMqOkOPnmM4YHbbU5o+7j7p09RqYB0vyYY49YZp2exTr7nbs/4uY/gvt371IU/ d6luwdYRLkPTd5CD2WARDV3CaQu8cOGLVWgXoQ4mdUF/UZDXKZrVM/S48KVzNrq6j8dBQIbNMnQn QxdvCF0RbAc0ndGDItpnTmkaoMu4Gdl57kQ9Q9PjkjRlaJYhBXQ6Q9plaZcNzh2MgwxBn+cv3PK8 RpDndXMCzyesVTYgmH3V+iEePxR0vwmyL5YUq1SiNyL4VqN/9ga84L1xLOjGctpgl2wPO7agxxTM DZS9sIbwgIAJuwchryGOoLvLaZA9tMqh84f9ZTRlymhXHY3V0YY6GixZk5vRbDWaEqaKJs9y6fCi AMhu9PVp50gZnXMqYkazmF4ydd+EXrQkUvpEVdyM9OmA6OeD7PwGrEDnHQoG9NsfDLXz5xmasBXo ThF9eIrR+WmGtlai9QL6jI/z5yRDo1XoOiukWXeOBivQFBTTTiNLE1aGzn+DqxR9PRcQqxStL1ga imhzjkay6PlmBMpowqTR2QyxpNHDdzI0kkZPzAwNMD3OPcOxGp1z0EiZMtrltK6GxupoOLppHVsq aKr3X+8dX6ugXXY+uji+Kk375WnMfnF0dWyUpt3yNOR5fXUMFdAiORTRLitPO2TQfTzUUEkar0AP mx/UHwzfNebpYd7JfLgCjc7/yto7RbDcJ2yLhZ7SGWJ87VqgNC0a5Zzvdam8Ni5dcXVDrxwtliL6 nC7VGztvChqXpMUwMOK0VZ62QTkaFP4kh4ZE0JZeil5wHWIh7ZWjrZXooBlPnXI0WolG5y7Pa1KO BivRw6ZrPXDOSn0o/aJLPnNriGvtk3K0tRo9XZ6lG4W6mPZL0WAd2i1Dr3Z1bUyPytDWWjQuQ6M1 6PzJwkqh3oxe/Asb0a46GqujoTJ60QXBG9KLQ70RjdXRUBm9JNSb0EtCvQmNV6UXLVqkSxNclS69 /bWujF766a1r03RXGU3U7bWjjh7XlNFDdXRfl0cPFb0pE1v40piKruiKruj/fzpS4HHyAEwKHU/G LtTRdIvoF45z19p/zHrtj+9qLnEIQgNJ9N8On9y1fv+BDs8+/p267/ebCO1Iorvo4tjS9vRXhxd/ gX0fnaOrM0k0NF4dWwAATh9bxIWcptLoq4C++pTT1GP3Oa1Lojt3AvqbzwR9PL6PLmuS6f/5e06z 45fnEmlIA/q//kXQ7xmclpXXMf3rfxX0QyiTjppxMhD0J0GGyAoIujgdTekuvI9/Ji2vh63fvctp z7y4azHUPx++I6s3Qoft7Qc05LQx+tqRVkOqsbGiK7qiK3oLaIWLFpltJGGdp2jFTB3NNHX0SB1N 1NFLI7IBPVJHE3X0sohsQo/U0UQdvSQiG9EjdfRcRIA0ei4iEumRsoBs+C5VJSIysv/36U0bXFMN dC91WXQQkY518/brk0bnpN7a/UqTRQcRaZ1+0xxZGOxbTXcAZdFBRPT3X7WxbQOLHfoISaNFRPTm RfvItjh9QCTS4jKSWqvVPhrufuAAqTSPCK2BgO6f1eXSI0Z1ymnMiD6QSxNOE/HWxLybW3JpHhH9 UGSIxZNPaoaIiLROr5rYwvDUbrpSaRL0RuyEvVEqzTReQ44wDWuIXHpUcCGABJqoo0WvUUWP1NFE HV0wH5FCj9TRRB2dHxE59Oj/2rtjFIRhKAzAbi5CbmC9gntpruQqFIo4OHoEj9KxYw/RIWMjDjo8 GrVQikUXeb9a+XOAj5K8vkfSPoKjBUeHqITRVQGjZQujwwRHP2kbU3tqi6MNim4gd8AOTnSMIj1Y v5o0adLfo13/b2iuTkt/aqE9IWOk3dJHja2kkHiqTS9W0W2XJBs/U6fnaTiVSbp2Tn1CbBzOLkvF BQTtmixG0j6D0RcDo8MeRwMjBELf41pOtT6dtG+jeLNTp22bQ0RswQJGmjTpt+gjju66IwB0148O oPOc9ANtD6T/gGZcfy6HADMfMF+zNpImTZr0j388eTlIkyZNmvRI6CsVEMQXiQN46wAAAABJRU5E rkJggg== ------=_NextPart_000_0000_01CA351D.C4D99D00--