2 <head><title>The Scannerless Boolean Parser (SBP)</title>
8 font-family: helvetica, verdana, arial, sans-serif;
13 border-top-width: 2pt;
14 border-top-style: solid;
18 font-family: helvetica, verdana, arial, sans-serif;
25 font-family: helvetica, verdana, arial, sans-serif;
31 font-family: helvetica, verdana, arial, sans-serif;
36 LI { margin-top: 5px; }
41 <center><table><tr><td width=600>
44 <font style='font-size:24pt; font-family:helvetica, verdana, arial, sans-serif'>
45 <b>SBP: the Scannerless Boolean Parser</b></font>
50 16-Aug: A new snapshot is <a href=../../edu.berkeley.sbp.tgz>here</a>.
56 <table width=500 style='background: #daa; padding: 10px'><tr><td>
57 <p style='padding: 5px; color:white; background: red; width:100%'><b>Update:</b> [29-July-2006]</font></p>
60 <a href=../../images/error.png>
61 <img align=right src=../../images/error.png width=200>
63 Error handling has been massively improved. Here's an example parsing
64 from a substantial portion of the <a href=../tests/java15.g>Java 1.5
65 grammar</a>. The <a href=../tests/java15.test>input</a> is missing a
66 closing angle-bracket on a generic type definition. Click on the
67 image to view <a href=../../images/error.png>full size</a>. Type
68 <tt>make java15</tt> after a checkout to try it yourself.
76 <table width=400><tr><td>
77 <font color=gray><b>Update:</b> [22-July-2006]<br><br>
79 The <a href=api/edu/berkeley/sbp/package-summary.html>API has been finalized</a> and includes a <a href=api/edu/berkeley/sbp/package-summary.html#package_description>decent example/mini-tutorial</a>.
86 <table width=400><tr><td>
88 <font color=gray><b>Update:</b></font> [17-July-2006]<br><br>
90 There is now a <a href=http://research.cs.berkeley.edu/project/sbp/list/>mailing list</a>.
98 <table width=400><tr><td>
99 <font color=gray><b>Update:</b> [05-July-2006]</font><br><br>
101 The reflective grammar-to-java bindings are complete, so SBP is now
102 vastly easier to use. You can find example code <a
103 href=../src/edu/berkeley/sbp/misc/Demo.java>here</a>
104 and the companion grammar <a
105 href=../tests/demo.g>here</a>.
112 The Scannerless Boolean Parser (SBP) is a scannerless parser for <a
113 href=http://www.cs.queensu.ca/home/okhotin/boolean/>boolean
114 grammars</a> (a superset of context-free grammars). It is written in
115 Java and emits Java source code.
117 <h1>What is interesting about it?</h1>
119 SBP deliberately sacrifices performance in favor of ease of extensibility.
122 Since it is an implementation of the (modified) <a
123 href=http://www.program-transformation.org/Sdf/GeneralizedLR>Lang-Tomita
124 GLR algorithm</a>, SBP supports all context-free languages.
128 href=http://en.wikipedia.org/wiki/Lexerless_parsing>scannerless</a>
129 (does not require a lexer). This allows it to easily handle languages
130 which have non-regular lexical structure or lack a clear lexer-parser
131 distinction, such as TeX, XML, RFC1738 (URLs), ASN.1, SMTP headers,
135 In addition to the juxtaposition and union operators provided in
136 context-free languages, SBP supports grammars which use the
137 intersection operator (<a
138 href=http://www.cs.queensu.ca/home/okhotin/conjunctive/>conjunctive
139 grammars</a>) and the complement operator (<a
140 href=http://www.cs.queensu.ca/home/okhotin/boolean/>boolean
143 <h1>What features does it have?</h1>
145 Features fully implemented are in <font color=green>green</font>;
146 those partially implemented are in <font color=orange>orange</font>;
147 those unimplemented (but planned) are in <font color=red>red</font>.
149 <ul> <li> <b>An implementation of the Lang-Tomita GLR parsing algorithm</b>
151 <li> Including <font color=green>Johnstone & Scott's RNGLR algorithm</font> for epsilon-productions</a>
153 <li> <a href=http://citeseer.ist.psu.edu/vandenbrand02disambiguation.html><font color=green>Visser's</font> extensions</a>
154 for <font color=green>scannerless parsing</font>
155 <ul> <li> <font color=green>Follow</font>, <font color=green>Avoid, Prefer</font>, <font color=green>Reject</font> constraints
156 <li> <font color=green>Character ranges</font>
157 <li> Automatic insertion of <font color=green>whitespace/comments</font>
160 <li> <font color=green>Any topological space</font> can be
161 used as an alphabet (need not be discrete)
162 <ul> <li> <font color=green>Unicode</font>
163 <li> <font color=orange>Trees</font>
166 <li> <font color=green>Associativity constraints</font> on <font color=green><i>n</i>-ary operators</font>
170 <li> <b>Ability to parse a wide variety of grammars in
171 </b> O(n<sup>3</sup>) time:
174 <li> <font color=green>all context-free grammars</font>
176 <li> <font color=green>epsilon productions</font>, <font
177 color=green>included in the parse forest</font>
179 <li> <font color=green>circularities</font>, <font
180 color=red>included in the parse forest</font>.
182 <li> Regular expression operators (
183 <tt><font color=green>*</font></tt>,
184 <tt><font color=green>?</font></tt>,
185 <tt><font color=green>+</font></tt>
188 <li> <font color=green>conjunctive grammars</font>
189 (<font color=green>intersection</font> operator)
191 <li> <font color=orange>boolean grammars</font> (<font
192 color=green>intersection</font>, <font
193 color=green>intersect-with-complement</font>, and
194 <font color=orange>generalized-complement</font>)
198 <li> <b>Facilitates experimenting with grammars</b>
201 <li> <font color=green>Interpreted mode</font>, in which the
202 parse table is interpreted directly, eliminating the
203 need for a compiler and making it easier for grammars
204 to operate on grammars.
206 <li> <font color=green>Simple
207 <a href=api/edu/berkeley/sbp/package-summary.html>API</a></font>
208 makes it easy to generate, analyze, and modify grammars
212 <li> Components of a grammar (nonterminals,
213 productions, etc) <font
214 color=green>represented as objects</font>
215 <li> composite elements implement <font color=green><tt>Iterable<T></tt></font>
218 <li> <font color=red>Compiled mode</font>, in which Java
219 source code is emitted; compiling this code yields a
220 parser. The resulting parser is <i>much</i> faster.
226 <h1>What is it deliberately missing?</h1>
228 <ul> <li> Semantic actions; the only option is to return a parse forest.
230 <li> This keeps the grammar specification language-neutral.
231 <li> A grammar can, however, indicate that certain parts of the parse tree should be dropped.
235 <h1>What features would be nice to have?</h1>
238 <li> <strike>Drop Farshi's algorithm and use <a
239 href=http://doi.ieeecomputersociety.org/10.1109/HICSS.2002.994495>GRMLR</a></strike>.
240 <font color=green>Done!</font>
242 <li> An implementation of the <a
243 href=http://www.cs.berkeley.edu/~smcpeak/elkhound/sources/elkhound/algorithm.html>McPeak-Necula
244 optimization</a> for bounded-depth determinism.
246 <li> Lazy parse trees, to decrease the space requirements from
247 o(n) to o(1) [but still O(n)].
249 <li> Consider implementing <a
250 href=http://www.cs.uvic.ca/~nigelh/Publications/cc99-paper.pdf>
251 Aycock-Horspool</a> unrolling. Improves performance with
252 only highly localized increase in algorithmic complexity.
253 Subsumes many other optimizations.
257 <h1>What are the long term goals?</h1>
259 As we come to a more mature understanding of the pragmatic aspects of
260 boolean grammars, a long-term goal is to migrate support for these
261 features to existing high-performance GLR implementations (<a
262 href=http://www.cs.berkeley.edu/~smcpeak/elkhound/>Elkhound</a>, <a
263 href=http://www.delorie.com/gnu/docs/bison/bison_90.html>bison-glr</a>).
265 <h1>Where can I read more about it?</h1>
267 <ul> <li> The <a href=../README>README</a> file is the best place to start
268 <li> After that, be sure to read <a href=jargon.txt>jargon.txt</a>
270 href=api/edu/berkeley/sbp/package-summary.html>javadoc</a>
271 is the best description of the API
272 <li> There's a <a href=../tests/meta.g>tentative metagrammar</a>,
274 <li> You can also get <a href=osq.lunch.talk.pdf>slides</a>
275 from my talk at the OSQ Lunch on 02-Nov-2005, though some of
276 the stuff (specifically what SBP can and cannot do) is
278 <li> A <a href=preprint.pdf>preprint</a> of one of my conference
282 <h1>Where can I get it?</h1>
284 The color coding above accurately reflects the state of the
285 implementation (<font color=green>11-Dec-2005</font>). However, in its current state it is a
286 bit messy, and may require a bit of fiddling to get it to do what you
287 want. This situation should improve in the next few weeks as I am
288 done adding features (for now) and am currently focusing on
289 reliability, cleanliness, and performance.
292 SBP is available under the BSD license.
295 You can download a snapshot (<font color=green>11-Dec-2005</font>) <a
296 href=../../edu.berkeley.sbp.tgz>here</a>. The parser-generator
297 requires Java 1.5 or later; the Java code it emits <font
298 color=orange>should run on any Java 1.1+ JVM</font>. After unpacking
299 the archive, simply type <tt>make</tt> to compile SBP and run the
304 </td></tr></table></center>