Debian Codegraph @

doc/wildcard.md

raw
1 # Wildcard Operator and Nongreedy Subrules
2
3 EBNF subrules like `(...)?`, `(...)*` and `(...)+` are greedy—They consume as much input as possible, but sometimes that’s not what’s needed. Constructs like `.*` consume until the end of the input in the lexer and sometimes in the parser. We want that loop to be nongreedy so we need to use different syntax: `.*?` borrowed from regular expression notation. We can make any subrule that has a `?`, `*`, or `+` suffix nongreedy by adding another `?` suffix. Such nongreedy subrules are allowed in both the parser and the lexer, but they are used much more frequently in the lexer.
4
5 ## Nongreedy Lexer Subrules
6
7 Here’s the very common C-style comment lexer rule that consumes any characters until it sees the trailing `*/`:
8
9 ```
10 COMMENT : '/*' .*? '*/' -> skip ; // .*? matches anything until the first */
11 ```
12
13 Here’s another example that matches strings that allow \" as an escaped quote character:
14
15 ```
16 grammar Nongreedy;
17 s : STRING+ ;
18 STRING : '"' ( '\\"' | . )*? '"' ; // match "foo", "\"", "x\"\"y", ...
19 WS : [ \r\t\n]+ -> skip ;
20 ```
21
22 ```bash
23 $ antlr4 Nongreedy.g4
24 $ javac Nongreedy*.java
25 $ grun Nongreedy s -tokens
26 => "quote:\""
27 => EOF
28 <= [@0,0:9='"quote:\""',<1>,1:0]
29 [@1,11:10='<EOF>',<-1>,2:0]
30 ```
31
32 Nongreedy subrules should be used sparingly because they complicate the recognition problem and sometimes make it tricky to decipher how the lexer will match text. Here is how the lexer chooses token rules:
33
34 <ol>
35 <li>The primary goal is to match the lexer rule that recognizes the most input characters.
36
37 ```
38 INT : [0-9]+ ;
39 DOT : '.' ; // match period
40 FLOAT : [0-9]+ '.' ; // match FLOAT upon '34.' not INT then DOT
41 ```
42 </li>
43 <li>
44 If more than one lexer rule matches the same input sequence, the priority goes to the rule occurring first in the grammar file.
45
46 ```
47 DOC : '/**' .*? '*/' ; // both rules match /** foo */, resolve to DOC
48 CMT : '/*' .*? '*/' ;
49 ```
50 </li>
51 <li>
52 Nongreedy subrules match the fewest number of characters that still allows the surrounding lexical rule to match.
53
54 ```
55 /** Match anything except \n inside of double angle brackets */
56 STRING : '<<' ~'\n'*? '>>' ; // Input '<<foo>>>>' matches STRING then END
57 END : '>>' ;
58 ```
59 </li>
60 <li>
61 <p>After crossing through a nongreedy subrule within a lexical rule, all decision-making from then on is "first match wins."
62 </p>
63 <p>
64 For example, literal `ab` in rule right-hand side (grammar fragment) `.*? (’a’|’ab’)` is dead code and can never be matched. If the input is ab, the first alternative, ’a’, matches the first character and therefore succeeds. (’a’|’ab’) by itself on the right-hand side of a rule properly matches the second alternative for input ab. This quirk arises from a nongreedy design decision that’s too complicated to go into here.</p>
65 <li>
66 </ol>
67
68 To illustrate the different ways to use loops within lexer rules, consider the following grammar, which has three different action-like tokens (using different delimiters so that they all fit within one example grammar).
69
70 ```
71 ACTION1 : '{' ( STRING | . )*? '}' ; // Allows {"foo}
72 ACTION2 : '[' ( STRING | ~'"' )*? ']' ; // Doesn't allow ["foo]; nongreedy *?
73 ACTION3 : '<' ( STRING | ~[">] )* '>' ; // Doesn't allow <"foo>; greedy *
74 STRING : '"' ( '\\"' | . )*? '"' ;
75 ```
76
77 Rule `ACTION1` allows unterminated strings, such as `"foo`, because input `"foo` matches to the wildcard part of the loop. It doesn’t have to go into rule `STRING` to match a quote. To fix that, rule `ACTION2` uses `~’"’` to match any character but the quote. Expression `~’"’` is still ambiguous with the `’]’` that ends the rule, but the fact that the subrule is nongreedy means that the lexer will exit the loop upon a right square bracket. To avoid a nongreedy subrule, make the alternatives explicit. Expression `~[">]` matches anything but the quote and right angle bracket. Here’s a sample run:
78
79 ```bash
80 $ antlr4 Actions.g4
81 $ javac Actions*.java
82 $ grun Actions tokens -tokens
83 => {"foo}
84 => EOF
85 <= [@0,0:5='{"foo}',<1>,1:0]
86 [@1,7:6='<EOF>',<-1>,2:0]
87 => $ grun Actions tokens -tokens
88 => ["foo]
89 => EOF
90 <= line 1:0 token recognition error at: '["foo]
91 '
92 [@0,7:6='<EOF>',<-1>,2:0]
93 => $ grun Actions tokens -tokens
94 => <"foo>
95 => EOF
96 <= line 1:0 token recognition error at: '<"foo>
97 '
98 [@0,7:6='<EOF>',<-1>,2:0]
99 ```
100
101 ## Nongreedy Parser Subrules
102
103 Nongreedy subrules and wildcard are also useful within parsers to do *fuzzy parsing* where the goal is to extract information from an input file without having to specify the full grammar. In contrast to nongreedy lexer decision-making, parsers always make globally correct decisions. A parser never makes a decision that will ultimately cause valid input to fail later on during the parse. Here is the central idea: Nongreedy parser subrules match the shortest sequence of tokens that preserves a successful parse for a valid input sentence.
104
105 For example, here are the key rules that demonstrate how to pull integer constants out of an arbitrary Java file:
106
107 ```
108 grammar FuzzyJava;
109
110 /** Match anything in between constant rule matches */
111 file : .*? (constant .*?)+ ;
112
113 /** Faster alternate version (Gets an ANTLR tool warning about
114 * a subrule like .* in parser that you can ignore.)
115 */
116 altfile : (constant | .)* ; // match a constant or any token, 0-or-more times
117
118 /** Match things like "public static final SIZE" followed by anything */
119 constant
120 : 'public' 'static' 'final' 'int' Identifier
121 {System.out.println("constant: "+$Identifier.text);}
122 ;
123
124 Identifier : [a-zA-Z_$] [a-zA-Z_$0-9]* ; // simplified
125 ```
126
127 The grammar contains a greatly simplified set of lexer rules from a real Java lexer; the whole file about 60 lines. The recognizer still needs to handle string and character constants as well as comments so it doesn’t get out of sync, trying to match a constant inside of the string for example. The only unusual lexer rule performs “match any character not matched by another lexer rule” functionality:
128
129 ```
130 OTHER : . -> skip ;
131 ```
132
133 This catchall lexer rule and the `.*?` subrule in the parser are the critical ingredients for fuzzy parsing.
134
135 Here’s a sample file that we can run into the fuzzy parser:
136
137 ```java
138 import java.util.*;
139 public class C {
140 public static final int A = 1;
141 public static final int B = 1;
142 public void foo() { }
143 public static final int C = 1;
144 }
145 ```
146
147 And here’s the build and test sequence:
148
149 ```bash
150 $ antlr4 FuzzyJava.g4
151 $ javac FuzzyJava*.java
152 $ grun FuzzyJava file C.java
153 constant: A
154 constant: B
155 constant: C
156 ```
157
158 Notice that it totally ignores everything except for the `public static final int` declarations. This all happens with only two parser rules.
159
160 Now let's try matching some simple class defs w/o having to build parser rules for the junk inside. Here want to catch just `A` and `B`:
161
162 ```
163 class A {
164 String name = "parrt";
165 }
166
167 class B {
168 int x;
169 int getDubX() {
170 return 2*x;
171 }
172 }
173 ```
174
175 This grammar does it.
176
177 ```
178 grammar Island;
179 file : clazz* ;
180 clazz : 'class' ID '{' ignore '}' ;
181 ignore : (method|.)*? ;
182 method : type ID '()' block ;
183 type : 'int' | 'void' ;
184 block : '{' (block | .)*? '}' ;
185 ID : [a-zA-Z] [a-zA-Z0-9]* ;
186 WS : [ \r\t\n]+ -> skip ;
187 ANY : . ;
188 ```
189
190 You get:
191
192 <img src=images/nonnested-fuzzy.png width=450>
193
194 Now let's try some nested classes
195
196 ```
197 class A {
198 String name = "parrt";
199 class Nested {
200 any filthy shite we want in here { }}}}}}
201 }
202 }
203
204 class B {
205 int x;
206 int getDubX() {
207 return 2*x;
208 }
209 }
210
211 ```
212
213 ```
214 grammar Island;
215 file : clazz* ;
216 clazz : 'class' ID '{' ignore '}' ;
217 ignore : (method|clazz|.)*? ; // <- only change is to add clazz alt here
218 method : type ID '()' block ;
219 type : 'int' | 'void' ;
220 block : '{' (block | .)*? '}' ;
221 ID : [a-zA-Z] [a-zA-Z0-9]* ;
222 WS : [ \r\t\n]+ -> skip ;
223 ANY : . ;
224 ```
225
226 You get:
227
228 <img src=images/nested-fuzzy.png width=600>