Debian Codegraph @

examples/SimpleExamples/README

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