| 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 |
} |