| 1 |
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> |
| 2 |
<html xmlns="http://www.w3.org/1999/xhtml"> |
| 3 |
<!-- |
| 4 |
|
| 5 |
Copyright (c) 2006, Sreenivasa Viswanadha <[email protected]> |
| 6 |
All rights reserved. |
| 7 |
|
| 8 |
Redistribution and use in source and binary forms, with or without |
| 9 |
modification, are permitted provided that the following conditions are met: |
| 10 |
|
| 11 |
* Redistributions of source code must retain the above copyright notice, |
| 12 |
this list of conditions and the following disclaimer. |
| 13 |
* Redistributions in binary form must reproduce the above copyright |
| 14 |
notice, this list of conditions and the following disclaimer in the |
| 15 |
documentation and/or other materials provided with the distribution. |
| 16 |
* Neither the name of the Sun Microsystems, Inc. nor the names of its |
| 17 |
contributors may be used to endorse or promote products derived from |
| 18 |
this software without specific prior written permission. |
| 19 |
|
| 20 |
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
| 21 |
AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
| 22 |
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
| 23 |
ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE |
| 24 |
LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
| 25 |
CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
| 26 |
SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
| 27 |
INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
| 28 |
CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
| 29 |
ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF |
| 30 |
THE POSSIBILITY OF SUCH DAMAGE. |
| 31 |
|
| 32 |
--> |
| 33 |
<head> |
| 34 |
<title>Tips for writing a good JavaCC lexical specification</title> |
| 35 |
</head> |
| 36 |
|
| 37 |
<body bgcolor="#FFFFFF" > |
| 38 |
<h1> Tips for writing a good JavaCC lexical specification</h1> |
| 39 |
|
| 40 |
<p> |
| 41 |
There are many ways to write the lexical specification for a grammar. But |
| 42 |
the performance of the generated token manager varies significantly depending |
| 43 |
on how you do this. Here are a few tips: |
| 44 |
</p> |
| 45 |
<ul> |
| 46 |
|
| 47 |
<li> Try to specify as many String literals as possible. These are recognized |
| 48 |
by a Deterministic Finite Automata (DFA), which is much faster than the Nondeterministic Finite Automata (NFA) needed to recognize other kinds |
| 49 |
of complex regular expressions. For example, to skip blanks/tabs/newlines, |
| 50 |
<pre> |
| 51 |
SKIP : { " " | "\t" | "\n" } |
| 52 |
</pre> |
| 53 |
is more efficient than doing |
| 54 |
<pre> |
| 55 |
SKIP : { < ([" ", "\t", "\n"])+ > } |
| 56 |
</pre> |
| 57 |
|
| 58 |
because in the first case you only have string literals, it will generate |
| 59 |
a DFA whereas for the second case it will generate an NFA. |
| 60 |
|
| 61 |
</li> |
| 62 |
<li> Try to use the pattern ~[] just by itself as much as possible. For example, |
| 63 |
doing a |
| 64 |
|
| 65 |
<pre> |
| 66 |
MORE : { < ~[] > } |
| 67 |
</pre> |
| 68 |
|
| 69 |
is better than doing |
| 70 |
|
| 71 |
<pre> TOKEN : { < (~[])+ > } |
| 72 |
</pre> |
| 73 |
|
| 74 |
of course, if your grammar dictates that one of these cannot be used, then |
| 75 |
you don't have a choice, but try to use < ~[] > as much as possible. |
| 76 |
</li> |
| 77 |
<li> Specify all the String literals in the order of increasing length, i.e., |
| 78 |
all shorter string literals before longer ones. This will help optimizing |
| 79 |
the bit vectors needed for string literals. |
| 80 |
</li> |
| 81 |
<li> Try to minimize the use of lexical states. When using these, try to move |
| 82 |
all your complex regular expressions into a single lexical state, leaving |
| 83 |
others to just recognize simple string literals. |
| 84 |
</li> |
| 85 |
<li> Try to use IGNORE_CASE judiciously. Best thing to do is to set this option |
| 86 |
at the grammar level. If that is not possible, then try to have it set for |
| 87 |
*all* regular expressions in a lexical state. There is heavy performance |
| 88 |
penalty for setting IGNORE_CASE for some regular expressions and not for others in the |
| 89 |
same lexical state. |
| 90 |
</li> |
| 91 |
<li> Try to SKIP as much possible, if you don't care about certain patterns. |
| 92 |
Here, you have to be a bit careful about EOF. seeing an EOF after SKIP |
| 93 |
is fine whereas, seeing an EOF after a MORE is a lexical error. |
| 94 |
</li> |
| 95 |
<li> Try to avoid specifying lexical actions with MORE specifications. Generally |
| 96 |
every MORE should end up in a TOKEN (or SPECIAL_TOKEN) finally so you can |
| 97 |
do the action there at the TOKEN level, if it is possible. |
| 98 |
</li> |
| 99 |
<li> Also try to avoid lexical actions and lexical state changes with SKIP |
| 100 |
specifications (especially for single character SKIP's like " ", "\t", |
| 101 |
"\n" etc.). For such cases, a simple loop is generated to eat up the |
| 102 |
SKIP'ed single characters. So obviously, if there is a lexical action |
| 103 |
or state change associated with this, it is not possible to it this way. |
| 104 |
</li> |
| 105 |
<li>Try to avoid having a choice of String literals for the same token, e.g. |
| 106 |
<pre> |
| 107 |
< NONE : "\"none\"" | "\'none\'" > |
| 108 |
</pre> |
| 109 |
|
| 110 |
Instead, have two different token kinds for this and use a nonterminal which |
| 111 |
is a choice between those choices. The above example can be written as : |
| 112 |
|
| 113 |
<pre> |
| 114 |
< NONE1 : "\"none\"" > |
| 115 |
| |
| 116 |
< NONE2 : "\'none'\" > |
| 117 |
</pre> |
| 118 |
|
| 119 |
and define a nonterminal called None() as : |
| 120 |
|
| 121 |
<pre> |
| 122 |
void None() : {} { <NONE1> | <NONE2> } |
| 123 |
</pre> |
| 124 |
|
| 125 |
This will make recognition much faster. Note however, that if the choice is |
| 126 |
between two complex regular expressions, it is OK to have the choice. |
| 127 |
</li> |
| 128 |
</ul> |
| 129 |
</body> |
| 130 |
</html> |