Debian Codegraph @

www/doc/lexertips.html

raw
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 : { &lt; ([" ", "\t", "\n"])+ &gt; }
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 : { &lt; ~[] &gt; }
67 </pre>
68
69 is better than doing
70
71 <pre> TOKEN : { &lt; (~[])+ &gt; }
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 &lt; ~[] &gt; 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 &lt; NONE : "\"none\"" | "\'none\'" &gt;
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 &lt; NONE1 : "\"none\"" &gt;
115 |
116 &lt; NONE2 : "\'none'\" &gt;
117 </pre>
118
119 and define a nonterminal called None() as :
120
121 <pre>
122 void None() : {} { &lt;NONE1&gt; | &lt;NONE2&gt; }
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>