Debian Codegraph @

www/doc/simpleREADME.html

raw
1 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
2 <html xmlns="http://www.w3.org/1999/xhtml">
3 <!--
4
5 Copyright (c) 2006, Sun Microsystems, Inc.
6 All rights reserved.
7
8 Redistribution and use in source and binary forms, with or without
9 modification, are permitted provided that the following conditions are met:
10
11 * Redistributions of source code must retain the above copyright notice,
12 this list of conditions and the following disclaimer.
13 * Redistributions in binary form must reproduce the above copyright
14 notice, this list of conditions and the following disclaimer in the
15 documentation and/or other materials provided with the distribution.
16 * Neither the name of the Sun Microsystems, Inc. nor the names of its
17 contributors may be used to endorse or promote products derived from
18 this software without specific prior written permission.
19
20 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
21 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
24 LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
25 CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
26 SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
27 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
28 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
29 ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
30 THE POSSIBILITY OF SUCH DAMAGE.
31
32 -->
33 <head>
34 <title>JavaCC README for SimpleExamples</title>
35 <!-- Changed by: Michael Van De Vanter, 14-Jan-2003 -->
36 </head>
37 <body bgcolor="#FFFFFF" >
38
39 <h1>JavaCC [tm]: README for SimpleExamples</h1>
40
41 <p>
42 This directory contains five examples to get you started using JavaCC.
43 Each example is contained in a single grammar file and are listed
44 below:
45 </p>
46 <pre>
47 Simple1.jj
48 Simple2.jj
49 Simple3.jj
50 Simple4.jj
51 NL_Xlator.jj
52 IdList.jj
53 </pre>
54 <p>
55 Once you have tried out and understood each of these examples, you
56 should take a look at more complex examples in other sub-directories
57 under the examples directory. But even with just these examples, you
58 should be able to get started on reasonable complex grammars.
59 </p>
60
61 <h2>Summary Instructions</h2>
62
63 <p>
64 If you are a parser and lexical analyzer expert and can understand the
65 examples by just reading them, the following instructions show you how
66 to get started with JavaCC. The instructions below are with respect
67 to Simple1.jj, but you can build any parser using the same set of
68 commands.
69 </p>
70 <ol>
71 <li>
72 Run javacc on the grammar input file to generate a bunch of Java
73 files that implement the parser and lexical analyzer (or token
74 manager):
75 <pre>
76 javacc Simple1.jj
77 </pre>
78 </li>
79 <li> Now compile the resulting Java programs:
80 <pre>
81 javac *.java
82 </pre>
83 </li>
84 <li> The parser is now ready to use. To run the parser, type:
85 <pre>
86 java Simple1
87 </pre>
88 </li>
89 </ol>
90 <p>
91 The Simple1 parser and others in this directory are designed to take
92 input from standard input. Simple1 recognizes matching braces
93 followed by zero or more line terminators and then an end of file.
94 </p>
95 <p>
96 Examples of legal strings in this grammar are:
97 <pre>
98 "{}", "{{{{{}}}}}", etc.
99 </pre>
100 Examples of illegal strings are:
101 <pre>
102 "{{{{", "{}{}", "{}}", "{{}{}}", "{ }", "{x}", etc.
103 </pre>
104 <p>
105 Try typing various different inputs to Simple1. Remember &lt;control-d&gt;
106 may be used to indicate the end of file (this is on the UNIX platform).
107 Here are some sample runs:
108 </p>
109 <pre>
110 % java Simple1
111 {{}}&lt;return&gt;
112 &lt;control-d&gt;
113 %
114
115 % java Simple1
116 {x&lt;return&gt;
117 Lexical error at line 1, column 2. Encountered: "x"
118 TokenMgrError: Lexical error at line 1, column 2. Encountered: "x" (120), after : ""
119 at Simple1TokenManager.getNextToken(Simple1TokenManager.java:146)
120 at Simple1.getToken(Simple1.java:140)
121 at Simple1.MatchedBraces(Simple1.java:51)
122 at Simple1.Input(Simple1.java:10)
123 at Simple1.main(Simple1.java:6)
124 %
125
126 % java Simple1
127 {}}&lt;return&gt;
128 ParseException: Encountered "}" at line 1, column 3.
129 Was expecting one of:
130 &lt;EOF&gt;
131 "\n" ...
132 "\r" ...
133
134 at Simple1.generateParseException(Simple1.java:184)
135 at Simple1.jj_consume_token(Simple1.java:126)
136 at Simple1.Input(Simple1.java:32)
137 at Simple1.main(Simple1.java:6)
138 %
139 </pre>
140
141 <h2>DETAILED DESCRIPTION OF Simple1.jj</h2>
142
143 <p>
144 This is a simple JavaCC grammar that recognizes a set of left braces
145 followed by the same number of right braces and finally followed by
146 zero or more line terminators and finally an end of file. Examples of
147 legal strings in this grammar are:
148 </p>
149 <pre>
150 "{}", "{{{{{}}}}}", etc.
151 </pre>
152 Examples of illegal strings are:
153 <pre>
154 "{{{{", "{}{}", "{}}", "{{}{}}", etc.
155 </pre>
156 <p>
157 This grammar file starts with settings for all the options offered by
158 JavaCC. In this case the option settings are their default values.
159 Hence these option settings were really not necessary. One could as
160 well have completely omitted the options section, or omitted one or
161 more of the individual option settings. The details of the individual
162 options is described in the JavaCC documentation in the web pages.
163 </p>
164 <p>
165 Following this is a Java compilation unit enclosed between
166 "PARSER_BEGIN(name)" and "PARSER_END(name)". This compilation unit
167 can be of arbitrary complexity. The only constraint on this
168 compilation unit is that it must define a class called "name" - the
169 same as the arguments to PARSER_BEGIN and PARSER_END. This is the
170 name that is used as the prefix for the Java files generated by the
171 parser generator. The parser code that is generated is inserted
172 immediately before the closing brace of the class called "name".
173 </p>
174 <p>
175 In the above example, the class in which the parser is generated
176 contains a main program. This main program creates an instance of the
177 parser object (an object of type Simple1) by using a constructor that
178 takes one argument of type java.io.InputStream ("System.in" in this
179 case).
180 </p>
181 <p>
182 The main program then makes a call to the non-terminal in the grammar
183 that it would like to parse - "Input" in this case. All non-terminals
184 have equal status in a JavaCC generated parser, and hence one may
185 parse with respect to any grammar non-terminal.
186 </p>
187 <p>
188 Following this is a list of productions. In this example, there are
189 two productions that define the non-terminals "Input" and
190 "MatchedBraces" respectively. In JavaCC grammars, non-terminals are
191 written and implemented (by JavaCC) as Java methods. When the
192 non-terminal is used on the left-hand side of a production, it is
193 considered to be declared and its syntax follows the Java syntax. On
194 the right-hand side, its use is similar to a method call in Java.
195 </p>
196 <p>
197 Each production defines its left-hand side non-terminal followed by a
198 colon. This is followed by a bunch of declarations and statements
199 within braces (in both cases in the above example, there are no
200 declarations and hence this appears as "{}") which are generated as
201 common declarations and statements into the generated method. This is
202 then followed by a set of expansions also enclosed within braces.
203 </p>
204 <p>
205 Lexical tokens (regular expressions) in a JavaCC input grammar are
206 either simple strings ("{", "}", "\n", and "\r" in the above example),
207 or a more complex regular expression. In our example above, there is
208 one such regular expression "&lt;EOF&gt;" which is matched by the end of
209 file. All complex regular expressions are enclosed within angular
210 brackets.
211 </p>
212 <p>
213 The first production above says that the non-terminal "Input" expands
214 to the non-terminal "MethodBraces" followed by zero or more line
215 terminators ("\n" or "\r") and then the end of file.
216 </p>
217 <p>
218 The second production above says that the non-terminal "MatchedBraces"
219 expands to the token "{" followed by an optional nested expansion of
220 "MatchedBraces" followed by the token "}". Square brackets [...]
221 in a JavaCC input file indicate that the ... is optional.
222 </p>
223 <p>
224 [...] may also be written as (...)?. These two forms are equivalent.
225 Other structures that may appear in expansions are:
226 </p>
227 <pre>
228 e1 | e2 | e3 | ... : A choice of e1, e2, e3, etc.
229 ( e )+ : One or more occurrences of e
230 ( e )* : Zero or more occurrences of e
231 </pre>
232 <p>
233 Note that these may be nested within each other, so we can have
234 something like:
235 </p>
236 <pre>
237 (( e1 | e2 )* [ e3 ] ) | e4
238 </pre>
239 <p>
240 To build this parser, simply run JavaCC on this file and compile the
241 resulting Java files:
242 <pre>
243 javacc Simple1.jj
244 javac *.java
245 </pre>
246 <p>
247 Now you should be able to run the generated parser. Make sure that
248 the current directory is in your CLASSPATH and type:
249 </p>
250 <pre>
251 java Simple1
252 </pre>
253 <p>
254 Now type a sequence of matching braces followed by a return and an end
255 of file (CTRL-D on UNIX machines). If this is a problem on your
256 machine, you can create a file and pipe it as input to the generated
257 parser in this manner (piping also does not work on all machines - if
258 this is a problem, just replace "System.in" in the grammar file with
259 'new FileInputStream("testfile")' and place your input inside this
260 file):
261 </p>
262 <pre>
263 java Simple1 &lt; myfile
264 </pre>
265 <p>
266 Also try entering illegal sequences such as mismatched braces, spaces,
267 and carriage returns between braces as well as other characters and
268 take a look at the error messages produced by the parser.
269 </p>
270
271 <h3>DETAILED DESCRIPTION OF Simple2.jj</h3>
272
273 <p>
274 Simple2.jj is a minor modification to Simple1.jj to allow white space
275 characters to be interspersed among the braces. So then input such
276 as:
277 </p>
278 <pre>
279 "{{ }\n}\n\n"
280 </pre>
281 <p>
282 will now be legal.
283 </p>
284 <p>
285 Take a look at Simple2.jj. The first thing you will note is that we
286 have omitted the options section. This does not change anything since
287 the options in Simple1.jj were all assigned their default values.
288 </p>
289 <p>
290 The other difference between this file and Simple1.jj is that this
291 file contains a lexical specification - the region that starts with
292 "SKIP". Within this region are 4 regular expressions - space, tab,
293 newline, and return. This says that matches of these regular
294 expressions are to be ignored (and not considered for parsing). Hence
295 whenever any of these 4 characters are encountered, they are just
296 thrown away.
297 </p>
298 <p>
299 In addition to SKIP, JavaCC has three other lexical specification
300 regions. These are:
301 </p>
302 <pre>
303 . TOKEN: This is used to specify lexical tokens (see next example)
304 . SPECIAL_TOKEN: This is used to specify lexical tokens that are to be
305 ignored during parsing. In this sense, SPECIAL_TOKEN is
306 the same as SKIP. However, these tokens can be recovered
307 within parser actions to be handled appropriately.
308 . MORE: This specifies a partial token. A complete token is
309 made up of a sequence of MORE's followed by a TOKEN
310 or SPECIAL_TOKEN.
311 </pre>
312 <p>
313 Please take a look at some of the more complex grammars such as the
314 Java grammars for examples of usage of these lexical specification
315 regions.
316 </p>
317 <p>
318 You may build Simple2 and invoke the generated parser with input from
319 the keyboard as standard input.
320 </p>
321 <p>
322 You can also try generating the parser with the various debug options
323 turned on and see what the output looks like. To do this type:
324 </p>
325 <pre>
326 javacc -debug_parser Simple2.jj
327 javac Simple2*.java
328 java Simple2
329 </pre>
330 <p>
331 Then type:
332 </p>
333 <pre>
334 javacc -debug_token_manager Simple2.jj
335 javac Simple2*.java
336 java Simple2
337 </pre>
338 <p>
339 Note that token manager debugging produces a lot of diagnostic
340 information and it is typically used to look at debug traces a single
341 token at a time.
342 </p>
343
344 <h3>DETAILED DESCRIPTION OF Simple3.jj</h3>
345
346 <p>
347 Simple3.jj is the third and final version of our matching brace
348 detector. This example illustrates the use of the TOKEN region for
349 specifying lexical tokens. In this case, "{" and "}" are defined as
350 tokens and given names LBRACE and RBRACE respectively. These labels
351 can then be used within angular brackets (as in the example) to refer
352 to this token. Typically such token specifications are used for
353 complex tokens such as identifiers and literals. Tokens that are
354 simple strings are left as is (in the previous examples).
355 </p>
356 <p>
357 This example also illustrates the use of actions in the grammar
358 productions. The actions inserted in this example count the number of
359 matching braces. Note the use of the declaration region to declare
360 variables "count" and "nested_count". Also note how the non-terminal
361 "MatchedBraces" returns its value as a function return value.
362 </p>
363
364 <h3>DETAILED DESCRIPTION OF NL_Xlator.jj</h3>
365
366 <p>
367 This example goes into the details of writing regular expressions in
368 JavaCC grammar files. It also illustrates a slightly more complex set
369 of actions that translate the expressions described by the grammar
370 into English.
371 </p>
372 <p>
373 The new concept in the above example is the use of more complex
374 regular expressions. The regular expression:
375 </p>
376 <pre>
377 &lt; ID: ["a"-"z","A"-"Z","_"] ( ["a"-"z","A"-"Z","_","0"-"9"] )* &gt;
378 </pre>
379 <p>
380 creates a new regular expression whose name is ID. This can be
381 referred anywhere else in the grammar simply as &lt;ID&gt;. What follows in
382 square brackets are a set of allowable characters - in this case it is
383 any of the lower or upper case letters or the underscore. This is
384 followed by 0 or more occurrences of any of the lower or upper case
385 letters, digits, or the underscore.
386 </p>
387 <p>
388 Other constructs that may appear in regular expressions are:
389 </p>
390 <pre>
391 ( ... )+ : One or more occurrences of ...
392 ( ... )? : An optional occurrence of ... (Note that in the case
393 of lexical tokens, (...)? and [...] are not equivalent)
394 ( r1 | r2 | ... ) : Any one of r1, r2, ...
395 </pre>
396 <p>
397 A construct of the form [...] is a pattern that is matched by the
398 characters specified in ... . These characters can be individual
399 characters or character ranges. A "~" before this construct is a
400 pattern that matches any character not specified in ... . Therefore:
401 </p>
402 <pre>
403 ["a"-"z"] matches all lower case letters
404 ~[] matches any character
405 ~["\n","\r"] matches any character except the new line characters
406 </pre>
407 <p>
408 When a regular expression is used in an expansion, it takes a value of
409 type "Token". This is generated into the generated parser directory
410 as "Token.java". In the above example, we have defined a variable of
411 type "Token" and assigned the value of the regular expression to it.
412 </p>
413
414 <h3>DETAILED DESCRIPTION OF IdList.jj</h3>
415
416 <p>
417 This example illustrates an important attribute of the SKIP
418 specification. The main point to note is that the regular expressions
419 in the SKIP specification are only ignored *between tokens* and not
420 *within tokens*. This grammar accepts any sequence of identifiers
421 with white space in between.
422 </p>
423 <p>
424 A legal input for this grammar is:
425 </p>
426 <pre>
427 "abc xyz123 A B C \t\n aaa"
428 </pre>
429 <p>
430 This is because any number of the SKIP regular expressions are allowed
431 in between consecutive &lt;Id&gt;'s. However, the following is not a legal
432 input:
433 </p>
434 <pre>
435 "xyz 123"
436 </pre>
437 <p>
438 This is because the space character after "xyz" is in the SKIP
439 category and therefore causes one token to end and another to begin.
440 This requires "123" to be a separate token and hence does not match
441 the grammar.
442 </p>
443 <p>
444 If spaces were OK within &lt;Id&gt;'s, then all one has to do is to replace
445 the definition of Id to:
446 </p>
447 <pre>
448 TOKEN :
449 {
450 &lt; Id: ["a"-"z","A"-"Z"] ( (" ")* ["a"-"z","A"-"Z","0"-"9"] )* &gt;
451 }
452 </pre>
453 <p>
454 Note that having a space character within a TOKEN specification does
455 not mean that the space character cannot be used in the SKIP
456 specification. All this means is that any space character that
457 appears in the context where it can be placed within an identifier
458 will participate in the match for &lt;Id&gt;, whereas all other space
459 characters will be ignored. The details of the matching algorithm are
460 described in the JavaCC documentation.
461 </p>
462 <p>
463 As a corollary, one must define as tokens anything within which
464 characters such as white space characters must not be present. In the
465 above example, if &lt;Id&gt; was defined as a grammar production rather than
466 a lexical token as shown below this paragraph, then "xyz 123" would
467 have been recognized as a legitimate &lt;Id&gt; (wrongly).
468 </p>
469 <pre>
470 void Id() :
471 {}
472 {
473 &lt;["a"-"z","A"-"Z"]&gt; ( &lt;["a"-"z","A"-"Z","0"-"9"]&gt; )*
474 }
475 </pre>
476 <p>
477 Note that in the above definition of non-terminal Id, it is made up of
478 a sequence of single character tokens (note the location of &lt;...&gt;s),
479 and hence white space is allowed between these characters.
480 </p>
481 </body>
482 </html>