Debian Codegraph @

doc/parser-rules.md

raw
1 # Parser Rules
2
3 Parsers consist of a set of parser rules either in a parser or a combined grammar. A Java application launches a parser by invoking the rule function, generated by ANTLR, associated with the desired start rule. The most basic rule is just a rule name followed by a single alternative terminated with a semicolon:
4
5 ```
6 /** Javadoc comment can precede rule */
7 retstat : 'return' expr ';' ;
8 ```
9
10 Rules can also have alternatives separated by the |
11
12 ```
13 operator:
14 stat: retstat
15 | 'break' ';'
16 | 'continue' ';'
17 ;
18 ```
19
20 Alternatives are either a list of rule elements or empty. For example, here’s a rule with an empty alternative that makes the entire rule optional:
21
22 ```
23 superClass
24 : 'extends' ID
25 | // empty means other alternative(s) are optional
26 ;
27 ```
28
29 ## Alternative Labels
30
31 As we saw in Section 7.4, Labeling Rule Alternatives for Precise Event Methods, we can get more precise parse-tree listener events by labeling the outermost alternatives of a rule using the # operator. All alternatives within a rule must be labeled, or none of them. Here are two rules with labeled alternatives.
32
33 ```
34 grammar T;
35 stat: 'return' e ';' # Return
36 | 'break' ';' # Break
37 ;
38 e : e '*' e # Mult
39 | e '+' e # Add
40 | INT # Int
41 ;
42 ```
43
44 Alternative labels do not have to be at the end of the line and there does not have to be a space after the # symbol.
45 ANTLR generates a rule context class definition for each label. For example, here is the listener that ANTLR generates:
46
47 ```java
48 public interface AListener extends ParseTreeListener {
49 void enterReturn(AParser.ReturnContext ctx);
50 void exitReturn(AParser.ReturnContext ctx);
51 void enterBreak(AParser.BreakContext ctx);
52 void exitBreak(AParser.BreakContext ctx);
53 void enterMult(AParser.MultContext ctx);
54 void exitMult(AParser.MultContext ctx);
55 void enterAdd(AParser.AddContext ctx);
56 void exitAdd(AParser.AddContext ctx);
57 void enterInt(AParser.IntContext ctx);
58 void exitInt(AParser.IntContext ctx);
59 }
60 ```
61
62 There are enter and exit methods associated with each labeled alternative. The parameters to those methods are specific to alternatives.
63
64 You can reuse the same label on multiple alternatives to indicate that the parse tree walker should trigger the same event for those alternatives. For example, here’s a variation on rule e from grammar A above:
65
66 ```
67 e : e '*' e # BinaryOp
68 | e '+' e # BinaryOp
69 | INT # Int
70 ;
71 ```
72
73 ANTLR would generate the following listener methods for e:
74
75 ```java
76 void enterBinaryOp(AParser.BinaryOpContext ctx);
77 void exitBinaryOp(AParser.BinaryOpContext ctx);
78 void enterInt(AParser.IntContext ctx);
79 void exitInt(AParser.IntContext ctx);
80 ```
81
82 ANTLR gives errors if an alternative name conflicts with a rule name. Here’s another rewrite of rule e where two
83 alternative labels conflict with rule names:
84
85 ```
86 e : e '*' e # e
87 | e '+' e # Stat
88 | INT # Int
89 ;
90 ```
91
92 The context objects generated from rule names and labels get capitalized and so label Stat conflicts with rule stat:
93
94 ```bash
95 $ antlr4 A.g4
96 error(124): A.g4:5:23: rule alt label e conflicts with rule e
97 error(124): A.g4:6:23: rule alt label Stat conflicts with rule stat
98 warning(125): A.g4:2:13: implicit definition of token INT in parser
99 ```
100
101 ## Rule Context Objects
102
103 ANTLR generates methods to access the rule context objects (parse tree nodes) associated with each rule reference. For rules with a single rule reference, ANTLR generates a method with no arguments. Consider the following rule.
104
105 ```
106 inc : e '++' ;
107 ```
108
109 ANTLR generates this context class:
110
111 ```java
112 public static class IncContext extends ParserRuleContext {
113 public EContext e() { ... } // return context object associated with e
114 ...
115 }
116 ```
117
118 ANTLR also provide support to access context objects when there is more than a single reference to a rule:
119
120 ```
121 field : e '.' e ;
122 ```
123
124 ANTLR generates a method with an index to access the ith element as well as a method to get context for all references to that rule:
125
126 ```java
127 public static class FieldContext extends ParserRuleContext {
128 public EContext e(int i) { ... } // get ith e context
129 public List<EContext> e() { ... } // return ALL e contexts
130 ...
131 }
132 ```
133
134 If we had another rule, s, that references field, an embedded action could access the list of e rule matches performed by field:
135
136 ```
137 s : field
138 {
139 List<EContext> x = $field.ctx.e();
140 ...
141 }
142 ;
143 ```
144
145 A listener or visitor could do the same thing. Given a pointer to a FieldContext object, f, f.e() would return List<EContext>.
146
147 ## Rule Element Labels
148
149 You can label rule elements using the = operator to add fields to the rule context objects:
150
151 ```
152 stat: 'return' value=e ';' # Return
153 | 'break' ';' # Break
154 ;
155 ```
156
157 Here value is the label for the return value of rule e, which is defined elsewhere.
158 Labels become fields in the appropriate parse tree node class. In this case, label value becomes a field in ReturnContext because of the Return alternative label:
159
160 ```java
161 public static class ReturnContext extends StatContext {
162 public EContext value;
163 ...
164 }
165 ```
166
167 It’s often handy to track a number of tokens, which you can do with the += “list label” operator. For example, the following rule creates a list of the Token objects matched for a simple array construct:
168
169 ```
170 array : '{' el+=INT (',' el+=INT)* '}' ;
171 ```
172
173 ANTLR generates a List field in the appropriate rule context class:
174
175 ```
176 public static class ArrayContext extends ParserRuleContext {
177 public List<Token> el = new ArrayList<Token>();
178 ...
179 }
180 ```
181
182 These list labels also work for rule references:
183
184 ```
185 elist : exprs+=e (',' exprs+=e)* ;
186 ```
187
188 ANTLR generates a field holding the list of context objects:
189
190 ```
191 public static class ElistContext extends ParserRuleContext {
192 public List<EContext> exprs = new ArrayList<EContext>();
193 ...
194 }
195 ```
196
197 ## Rule Elements
198
199 Rule elements specify what the parser should do at a given moment just like statements in a programming language. The elements can be rule, token, string literal like expression, ID, and ’return’. Here’s a complete list of the rule elements (we’ll look at actions and predicates in more detail later):
200
201 <table>
202 <tr>
203 <th>Syntax</th><th>Description</th>
204 </tr>
205 <tr>
206 <td>T</td><td>
207 Match token T at the current input position. Tokens always begin with a capital letter.</td>
208 </tr>
209 <tr>
210 <td>’literal’</td><td>
211 Match the string literal at the current input position. A string literal is simply a token with a fixed string.</td>
212 </tr>
213 <tr>
214 <td>r</td><td>
215 Match rule r at current input position, which amounts to invoking the rule just like a function call. Parser rule names always begin with a lowercase letter.</td>
216 </tr>
217 <tr>
218 <td>r [«args»]</td><td>
219 Match rule r at current input position, passing in a list of arguments just like a function call. The arguments inside the square brackets are in the syntax of the target language and are usually a comma-separated list of expressions.</td>
220 </tr>
221 <tr>
222 <td>{«action»}</td><td>
223 Execute an action immediately after the preceding alternative element and immediately before the following alternative element. The action conforms to the syntax of the target language. ANTLR copies the action code to the generated class verbatim, except for substituting attribute and token references such as $x and $x.y.</td>
224 </tr>
225 <tr>
226 <td>{«p»}?</td><td>
227 Evaluate semantic predicate «p». Do not continue parsing past a predicate if «p» evaluates to false at runtime. Predicates encountered during prediction, when ANTLR distinguishes between alternatives, enable or disable the alternative(s) surrounding the predicate(s).</td>
228 </tr>
229 <tr>
230 <td>.</td><td>
231 Match any single token except for the end of file token. The “dot” operator is called the wildcard.</td>
232 </tr>
233 </table>
234
235 When you want to match everything but a particular token or set of tokens, use the `~` “not” operator. This operator is rarely used in the parser but is available. `~INT` matches any token except the `INT` token. `~’,’` matches any token except the comma. `~(INT|ID)` matches any token except an INT or an ID.
236
237 Token, string literal, and semantic predicate rule elements can take options. See Rule Element Options.
238
239 ## Subrules
240
241 A rule can contain alternative blocks called subrules (as allowed in Extended BNF Notation: EBNF). A subrule is like a rule that lacks a name and is enclosed in parentheses. Subrules can have one or more alternatives inside the parentheses. Subrules cannot define attributes with locals and returns like rules can. There are four kinds of subrules (x, y, and z represent grammar fragments):
242
243 <table>
244 <tr>
245 <th>Syntax</th><th>Description</th>
246 </tr>
247 <tr>
248 <td><img src=images/xyz.png></td><td>(x|y|z).
249 Match any alternative within the subrule exactly once. Example:
250 <br>
251 <tt>
252 returnType : (type | 'void') ;
253 </tt>
254 </td>
255 </tr>
256 <tr>
257 <td><img src=images/xyz_opt.png></td><td>(x|y|z)?
258 Match nothing or any alternative within subrule. Example:
259 <br>
260 <tt>
261 classDeclaration
262 : 'class' ID (typeParameters)? ('extends' type)?
263 ('implements' typeList)?
264 classBody
265 ;
266 </tt>
267 <tr>
268 <td><img src=images/xyz_star.png></td><td>(x|y|z)*
269 Match an alternative within subrule zero or more times. Example:
270 <br>
271 <tt>
272 annotationName : ID ('.' ID)* ;
273 </tt>
274 </tr>
275 <tr>
276 <td><img src=images/xyz_plus.png></td><td>(x|y|z)+
277 Match an alternative within subrule one or more times. Example:
278 <br>
279 <tt>
280 annotations : (annotation)+ ;
281 </tt>
282 </td>
283 </tr>
284 </table>
285
286 You can suffix the `?`, `*`, and `+` subrule operators with the nongreedy operator, which is also a question mark: `??`, `*?`, and `+?`. See Section 15.6, Wildcard Operator and Nongreedy Subrules.
287
288 As a shorthand, you can omit the parentheses for subrules composed of a single alternative with a single rule element reference. For example, `annotation+` is the same as `(annotation)+` and `ID+` is the same as `(ID)+`. Labels also work with the shorthand. `ids+=INT+` make a list of `INT` token objects.
289
290 ## Catching Exceptions
291
292 When a syntax error occurs within a rule, ANTLR catches the exception, reports the error, attempts to recover (possibly by consuming more tokens), and then returns from the rule. Every rule is wrapped in a `try/catch/finally` statement:
293
294 ```
295 void r() throws RecognitionException {
296 try {
297 rule-body
298 }
299 catch (RecognitionException re) {
300 _errHandler.reportError(this, re);
301 _errHandler.recover(this, re);
302 }
303 finally {
304 exitRule();
305 }
306 }
307 ```
308
309 In Section 9.5, Altering ANTLR’s Error Handling Strategy, we saw how to use a strategy object to alter ANTLR’s error handling. Replacing the strategy changes the strategy for all rules, however. To alter the exception handling for a single rule, specify an exception after the rule definition:
310
311 ```
312 r : ...
313 ;
314 catch[RecognitionException e] { throw e; }
315 ```
316
317 That example shows how to avoid default error reporting and recovery. r rethrows the exception, which is useful when it makes more sense for a higher-level rule to report the error. Specifying any exception clause, prevents ANTLR from generating a clause to handle `RecognitionException`.
318
319 You can specify other exceptions as well:
320
321 ```
322 r : ...
323 ;
324 catch[FailedPredicateException fpe] { ... }
325 catch[RecognitionException e] { ... }
326 ```
327
328 The code snippets inside curly braces and the exception “argument” actions must be written in the target language; Java, in this case.
329 When you need to execute an action even if an exception occurs, put it into the `finally` clause:
330
331 ```
332 r : ...
333 ;
334 // catch blocks go first
335 finally { System.out.println("exit rule r"); }
336 ```
337
338 The finally clause executes right before the rule triggers `exitRule` before returning. If you want to execute an action after the rule finishes matching the alternatives but before it does its cleanup work, use an `after` action.
339
340 Here’s a complete list of exceptions:
341
342 <table>
343 <tr>
344 <th>Exception name</th><th>Description</th>
345 </tr>
346 <tr>
347 <td>RecognitionException</td><td>
348 The superclass of all exceptions thrown by an ANTLR-generated recognizer. It’s a subclass of RuntimeException to avoid the hassles of checked exceptions. This exception records where the recognizer (lexer or parser) was in the input, where it was in the ATN (internal graph data structure representing the grammar), the rule invocation stack, and what kind of problem occurred.</td>
349 </tr>
350 <tr>
351 <td>NoViableAltException</td><td>
352 Indicates that the parser could not decide which of two or more paths to take by looking at the remaining input. This exception tracks the starting token of the offending input and also knows where the parser was in the various paths when the error occurred.</td>
353 </tr>
354 <tr>
355 <td>LexerNoViableAltException</td><td>
356 The equivalent of NoViableAltException but for lexers only.</td>
357 </tr>
358 <tr>
359 <td>InputMismatchException</td><td>
360 The current input Token does not match what the parser expected.</td>
361 </tr>
362 <tr>
363 <td>FailedPredicateException</td><td>
364 A semantic predicate that evaluates to false during prediction renders the surrounding alternative nonviable. Prediction occurs when a rule is predicting which alternative to take. If all viable paths disappear, parser will throw NoViableAltException. This predicate gets thrown by the parser when a semantic predicate evaluates to false outside of prediction, during the normal parsing process of matching tokens and calling rules.</td>
365 </tr>
366 </table>
367
368 ## Rule Attribute Definitions
369
370 There are a number of action-related syntax elements associated with rules to be aware of. Rules can have arguments, return values, and local variables just like functions in a programming language. (Rules can have actions embedded among the rule elements, as we’ll see in Section 15.4, Actions and Attributes.) ANTLR collects all of the variables you define and stores them in the rule context object. These variables are usually called attributes. Here’s the general syntax showing all possible attribute definition locations:
371
372 ```
373 rulename[args] returns [retvals] locals [localvars] : ... ;
374 ```
375
376 The attributes defined within those [...] can be used like any other variable. Here is a sample rule that copies parameters to return values:
377
378 ```
379 // Return the argument plus the integer value of the INT token
380 add[int x] returns [int result] : '+=' INT {$result = $x + $INT.int;} ;
381 ```
382
383 The args, locals, and return `[...]` are generally in the target language but with some constraints. The `[...]` string is a comma-separated list of declarations either with prefix or postfix type notation or no-type notation. The elements can have initializer such as `[int x = 32, float y]` but don't go too crazy as we are parsing this generic text manually in [ScopeParser](https://github.com/antlr/antlr4/blob/master/tool/src/org/antlr/v4/parse/ScopeParser.java).
384
385 * Java, CSharp, C++ use `int x` notation but C++ must use a slightly altered notation for array references, `int[] x`, to fit in the *type* *id* syntax.
386 * Go and Swift give the type after the variable name, but Swift requires a `:` in between. Go `i int`, Swift `i:int`. For Go target, you must either use `int i` or `i:int`.
387 * Python and JavaScript don't specify static types so actions are just identifier lists such as `[i,j]`.
388
389 Technically any target could use either notation. For examples, see [TestScopeParsing](https://github.com/antlr/antlr4/blob/master/tool-testsuite/test/org/antlr/v4/test/tool/TestScopeParsing.java).
390
391 As with the grammar level, you can specify rule-level named actions. For rules, the valid names are `init` and `after`. As the names imply, parsers execute init actions immediately before trying to match the associated rule and execute after actions immediately after matching the rule. ANTLR after actions do not execute as part of the finally code block of the generated rule function. Use the ANTLR finally action to place code in the generated rule function finally code block.
392
393 The actions come after any argument, return value, or local attribute definition actions. The `row` rule preamble from Section 10.2, Accessing Token and Rule Attributes illustrates the syntax nicely:
394 actions/CSV.g4
395
396 ```
397 /** Derived from rule "row : field (',' field)* '\r'? '\n' ;" */
398 row[String[] columns]
399 returns [Map<String,String> values]
400 locals [int col=0]
401 @init {
402 $values = new HashMap<String,String>();
403 }
404 @after {
405 if ($values!=null && $values.size()>0) {
406 System.out.println("values = "+$values);
407 }
408 }
409 : ...
410 ;
411 ```
412
413 Rule row takes argument columns, returns values, and defines local variable col. The “actions” in square brackets are copied directly into the generated code:
414
415 ```java
416 public class CSVParser extends Parser {
417 ...
418 public static class RowContext extends ParserRuleContext {
419 public String [] columns;
420 public Map<String,String> values;
421 public int col=0;
422 ...
423 }
424 ...
425 }
426 ```
427
428 The generated rule functions also specify the rule arguments as function arguments, but they are quickly copied into the local RowContext object:
429
430 ```java
431 public class CSVParser extends Parser {
432 ...
433 public final RowContext row(String [] columns) throws RecognitionException {
434 RowContext _localctx = new RowContext(_ctx, 4, columns);
435 enterRule(_localctx, RULE_row);
436 ...
437 }
438 ...
439 }
440 ```
441
442 ANTLR tracks nested `[...]` within the action so that `String[]` columns is parsed properly. It also tracks angle brackets so that commas within generic type parameters do not signify the start of another attribute. `Map<String,String>` values is one attribute definition.
443
444 There can be multiple attributes in each action, even for return values. Use a comma to separate attributes within the same action:
445
446 ```
447 a[Map<String,String> x, int y] : ... ;
448 ```
449
450 ANTLR interprets that action to define two arguments, x and y:
451
452 ```java
453 public final AContext a(Map<String,String> x, int y)
454 throws RecognitionException
455 {
456 AContext _localctx = new AContext(_ctx, 0, x, y);
457 enterRule(_localctx, RULE_a);
458 ...
459 }
460 ```
461
462 ## Start Rules and EOF
463
464 A start rule is the rule engaged first by the parser; it’s the rule function called by the language application. For example, a language application that parsed to Java code might call `parser.compilationUnit()` for a `JavaParser` object called `parser`. Any rule in the grammar can act as a start rule.
465
466 Start rules don’t necessarily consume all of the input. They consume only as much input as needed to match an alternative of the rule. For example, consider the following rule that matches one, two, or three tokens, depending on the input.
467
468 ```
469 s : ID
470 | ID '+'
471 | ID '+' INT
472 ;
473 ```
474
475 Upon `a+3`, rule `s` matches the third alternative. Upon `a+b`, it matches the second alternative and ignores the final `b` token. Upon `a b`, it matches the first alternative, ignoring the `b` token. The parser does not consume the complete input in the latter two cases because rule `s` doesn’t explicitly say that end of file must occur after matching an alternative of the rule.
476
477 This default functionality is very useful for building things like IDEs. Imagine the IDE wanting to parse a method somewhere in the middle of a big Java file. Calling rule `methodDeclaration` should try to match just a method and ignore whatever comes next.
478
479 On the other hand, rules that describe entire input files should reference special predefined-token `EOF`. If they don’t, you might scratch your head for a while wondering why the start rule doesn’t report errors for any input no matter what you give it. Here’s a rule that’s part of a grammar for reading configuration files:
480
481 ```
482 config : element*; // can "match" even with invalid input.
483 ```
484
485 Invalid input would cause `config` to return immediately without matching any input and without reporting an error. Here’s the proper specification:
486
487 ```
488 file : element* EOF; // don't stop early. must match all input
489 ```