Debian Codegraph @

examples/JavaGrammars/OPTIMIZING

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 file describes in a step by step manner how you can modify the
30 lookaheads in your grammar to optimize for space in the generated
31 parser. This is only necessary until JavaCC is improved to do this
32 optimization automatically (at which time, we will delete this file).
33
34 1. How much space optimization can one expect?
35
36 The optimizations that we show here gets rid of all methods in the
37 generated parser which start with "jj_2" and "jj_3" respectively. So
38 take a look at your generated parser and figure out how much space is
39 occupied by these methods. When we performed this optimization on the
40 Java grammar, we were able to decrease the size of the generated
41 parser by more than 50%.
42
43 2. Why are "jj_2" and "jj_3" methods generated?
44
45 These methods are generated to handle all lookaheads except the
46 following:
47
48 a. A syntactic lookahead of 1 (the most common situation).
49 b. For any amount of syntactic lookahead - when the target expansion can
50 match the empty string.
51 c. When the syntactic lookahead is 0. Typically there is only semantic
52 lookahead this situation.
53
54 The "jj_2" and "jj_3" methods are also generated for lookaheads in the
55 (a) and (b) categories above when hoisting of semantic predicates is
56 required.
57
58 3. Summary of how we achieve the optimization:
59
60 Essentially, we go through the entire grammar looking for choice
61 points that are not one of (a), (b), or (c) above. We then replace
62 the lookaheads at these points with one of kind (c) above.
63
64 When we do this, JavaCC generates a parser where all the new semantic
65 lookaheads causes hoisting which affect other related choice points
66 and cause the "jj_2" and "jj_3" methods to be generated there.
67
68 So the final step is to locate these related choice points and insert
69 explicit lookahead specifications here to prevent hoisting from taking
70 place.
71
72 4. When is a grammar amenable to such optimization?
73
74 If the majority of the choice points in your grammar use lookaheads
75 that fall into the categories (a), (b), or (c) above then go for it.
76 Otherwise, you'll be spending too much work and essentially rewriting
77 the entire parser. It took a few hours to optimize the Java grammar.
78 But I would not recommend doing it for C++ (for C++, just wait for
79 JavaCC to be upgraded to do it automatically).
80
81 5. Step by step instructions:
82
83 Suppose your grammar file is called Grammar.jj. You are going to go
84 through two steps - in the first step, you create Grammar1.jj, and
85 in the second step you create the final grammar file - Grammar2.jj.
86 Lets also assume that the parsers generated from these grammar files
87 are Grammar.java, Grammar1.java, and Grammar2.java respectively.
88
89 STEP 1:
90
91 For every lookahead in your grammar that does not fit into categories
92 (a), (b), or (c) above, replace it with an equivalent semantic
93 lookahead. When you're done with all such replacements, the resulting
94 file is Grammar1.jj.
95
96 Example:
97
98 In the Java1.1.jj grammar, we have the following production for Name:
99
100 void Name() :
101 {}
102 {
103 <IDENTIFIER>
104 ( LOOKAHEAD(2)
105 "." <IDENTIFIER>
106 )*
107 }
108
109 It uses a lookahead of 2 - obviously this means that the choice
110 selection succeeds only if the next two characters are a "." and
111 an <IDENTIFIER>. The following modification replaces the syntactic
112 lookahead with a semantic lookahead:
113
114 void Name() :
115 {}
116 {
117 <IDENTIFIER>
118 ( LOOKAHEAD( { getToken(1).kind == DOT && getToken(2).kind == IDENTIFIER } )
119 "." <IDENTIFIER>
120 )*
121 }
122
123 STEP 2:
124
125 Run JavaCC on both Grammar.jj and Grammar1.jj to obtain Grammar.java
126 and Grammar1.java. Remember, the goal is to get rid of "jj_2" and
127 "jj_3" methods from the grammar. Changes are you will see a bunch of
128 "jj_2" and "jj_3" methods in Grammar1.java. We need to focus only
129 on the "jj_2" methods. When these methods are removed, the "jj_3"
130 methods automatically go away too. In the Java grammar, we found 23
131 "jj_2" methods to get rid of in this step.
132
133 Search for calls to "jj_2" methods in Grammar1.java. Locate the
134 corresponding portions in Grammar1.jj (the choice points in the grammar
135 corresponding to these calls). These calls are there to perform
136 hoisting (which you don't want - you don't need to understand hoisting
137 to perform this step).
138
139 Now look for corresponding locations in Grammar.java. You will see
140 references to a token mask array instead of a "jj_2" call at these
141 locations. Take a look at the value of the token mask array. Use
142 these values to create a new lookahead for this choice point to get
143 rid of the "jj_2" call.
144
145 The resulting grammar (Grammar2.jj) is the grammar you want.
146
147 Obviously, we need an example:
148
149 The Java parser generated after performing step 1 has the following
150 method with a call to a "jj_2" method ("jj_2_3"):
151
152 static final public void UnmodifiedInterfaceDeclaration() throws ParseException {
153 jj_consume_token(INTERFACE);
154 jj_consume_token(IDENTIFIER);
155 if (jj_mask_29[getToken(1).kind]) {
156 jj_consume_token(EXTENDS);
157 NameList();
158 } else {
159 jj_expLA1[29] = jj_gen;
160 ;
161 }
162 jj_consume_token(LBRACE);
163 label_8:
164 while (true) {
165 if (jj_2_3(1)) {
166 ;
167 } else {
168 break label_8;
169 }
170 InterfaceMemberDeclaration();
171 }
172 jj_consume_token(RBRACE);
173 }
174
175 The corresponding location in the Java grammar is:
176
177 void UnmodifiedInterfaceDeclaration() :
178 {}
179 {
180 "interface" <IDENTIFIER> [ "extends" NameList() ]
181 "{"
182 ( // <-- the choice point
183 InterfaceMemberDeclaration()
184 )*
185 "}"
186 }
187
188 The choice point corresponding to the call to "jj_2_3" above is
189 marked by the arrow.
190
191 Now lets take a look at the parser generated from the original Java
192 grammar. The above method is shown below:
193
194 static final public void UnmodifiedInterfaceDeclaration() throws ParseException {
195 jj_consume_token(INTERFACE);
196 jj_consume_token(IDENTIFIER);
197 if (jj_mask_40[getToken(1).kind]) {
198 jj_consume_token(EXTENDS);
199 NameList();
200 } else {
201 jj_expLA1[40] = jj_gen;
202 ;
203 }
204 jj_consume_token(LBRACE);
205 label_9:
206 while (true) {
207 if (jj_mask_41[getToken(1).kind]) {
208 ;
209 } else {
210 jj_expLA1[41] = jj_gen;
211 break label_9;
212 }
213 InterfaceMemberDeclaration();
214 }
215 jj_consume_token(RBRACE);
216 }
217
218 Instead of the call to "jj_2_3", there is a reference to the token
219 mask array "jj_mask_41". Now take a look at the initialization of
220 "jj_mask_41" that occurs a few lines further on:
221
222 static boolean[] jj_mask_41 = new boolean[120];
223 static {
224 jj_mask_41[ABSTRACT] =
225 jj_mask_41[BOOLEAN] =
226 jj_mask_41[BYTE] =
227 jj_mask_41[CHAR] =
228 jj_mask_41[CLASS] =
229 jj_mask_41[DOUBLE] =
230 jj_mask_41[FINAL] =
231 jj_mask_41[FLOAT] =
232 jj_mask_41[INT] =
233 jj_mask_41[INTERFACE] =
234 jj_mask_41[LONG] =
235 jj_mask_41[NATIVE] =
236 jj_mask_41[PRIVATE] =
237 jj_mask_41[PROTECTED] =
238 jj_mask_41[PUBLIC] =
239 jj_mask_41[SHORT] =
240 jj_mask_41[STATIC] =
241 jj_mask_41[SYNCHRONIZED] =
242 jj_mask_41[TRANSIENT] =
243 jj_mask_41[VOID] =
244 jj_mask_41[VOLATILE] =
245 jj_mask_41[IDENTIFIER] = true;
246 }
247
248 This defines the tokens that must be matched at the choice point
249 in order for that choice point to succeed. Use this to explicitly
250 insert a lookahead specification into the grammar to prevent the
251 hoisting of semantic predicates. Hence the resulting production
252 in the final grammar is:
253
254 void UnmodifiedInterfaceDeclaration() :
255 {}
256 {
257 "interface" <IDENTIFIER> [ "extends" NameList() ]
258 "{"
259 (
260 LOOKAHEAD(1, <ABSTRACT> | <BOOLEAN> | <BYTE> | <CHAR> | <CLASS> | <DOUBLE> |
261 <FINAL> | <FLOAT> | <INT> | <INTERFACE> | <LONG> | <NATIVE> |
262 <PRIVATE> | <PROTECTED> | <PUBLIC> | <SHORT> | <STATIC> |
263 <SYNCHRONIZED> | <TRANSIENT> | <VOID> | <VOLATILE> | <IDENTIFIER>)
264 InterfaceMemberDeclaration()
265 )*
266 "}"
267 }