-<html>
-<head><title>The Scannerless Boolean Parser (SBP)</title>
-<style>
-
- H1 {
- margin-left: -20px;
- margin-top: 30px;
- font-family: helvetica, verdana, arial, sans-serif;
- font-size: 14pt;
- font-weight: bold;
- text-align: left;
- width : 100%;
- border-top-width: 2pt;
- border-top-style: solid;
- }
-
- H2 {
- font-family: helvetica, verdana, arial, sans-serif;
- font-size: 12pt;
- font-weight: bold;
- }
-
- H3 {
- margin-left: -10px;
- font-family: helvetica, verdana, arial, sans-serif;
- font-size: 12pt;
- font-weight: bold;
- }
-
- TH, TD, P, LI {
- font-family: helvetica, verdana, arial, sans-serif;
- font-size: 13px;
- text-decoration:none;
- }
-
- LI { margin-top: 5px; }
-
-</style>
-</head>
-<body>
-<center><table><tr><td width=600>
-
-<center>
-<font style='font-size:24pt; font-family:helvetica, verdana, arial, sans-serif'>
-<b>SBP: the Scannerless Boolean Parser</b></font>
-</center>
-
-<p>
-<center>
-16-Aug: A new snapshot is <a href=../../edu.berkeley.sbp.tgz>here</a>.
-</center>
-</p>
-
-<br><br>
-<center>
-<table width=500 style='background: #daa; padding: 10px'><tr><td>
-<p style='padding: 5px; color:white; background: red; width:100%'><b>Update:</b> [29-July-2006]</font></p>
-
-<p align=right>
-<a href=../../images/error.png>
-<img align=right src=../../images/error.png width=200>
-</a>
-Error handling has been massively improved. Here's an example parsing
-from a substantial portion of the <a href=../tests/java15.g>Java 1.5
-grammar</a>. The <a href=../tests/java15.test>input</a> is missing a
-closing angle-bracket on a generic type definition. Click on the
-image to view <a href=../../images/error.png>full size</a>. Type
-<tt>make java15</tt> after a checkout to try it yourself.
-</p>
-
-</td></tr></table>
-</center>
-
-<br><br>
-<center>
-<table width=400><tr><td>
-<font color=gray><b>Update:</b> [22-July-2006]<br><br>
-
-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>.
-</font>
-</td></tr></table>
-</center>
-
-<br><br>
-<center>
-<table width=400><tr><td>
-
-<font color=gray><b>Update:</b></font> [17-July-2006]<br><br>
-
-There is now a <a href=http://research.cs.berkeley.edu/project/sbp/list/>mailing list</a>.
-
-
-</td></tr></table>
-</center>
-
-<br><br>
-<center>
-<table width=400><tr><td>
-<font color=gray><b>Update:</b> [05-July-2006]</font><br><br>
-<font color=gray>
-The reflective grammar-to-java bindings are complete, so SBP is now
-vastly easier to use. You can find example code <a
-href=../src/edu/berkeley/sbp/misc/Demo.java>here</a>
-and the companion grammar <a
-href=../tests/demo.g>here</a>.
-</font>
-</td></tr></table>
-</center>
-
-<h1>What is it?</h1>
-
-The Scannerless Boolean Parser (SBP) is a scannerless parser for <a
-href=http://www.cs.queensu.ca/home/okhotin/boolean/>boolean
-grammars</a> (a superset of context-free grammars). It is written in
-Java and emits Java source code.
-
-<h1>What is interesting about it?</h1>
-
-SBP deliberately sacrifices performance in favor of ease of extensibility.
-<p>
-
-Since it is an implementation of the (modified) <a
-href=http://www.program-transformation.org/Sdf/GeneralizedLR>Lang-Tomita
-GLR algorithm</a>, SBP supports all context-free languages.
-<p>
-
-It is <a
-href=http://en.wikipedia.org/wiki/Lexerless_parsing>scannerless</a>
-(does not require a lexer). This allows it to easily handle languages
-which have non-regular lexical structure or lack a clear lexer-parser
-distinction, such as TeX, XML, RFC1738 (URLs), ASN.1, SMTP headers,
-and Wiki markup.
-<p>
-
-In addition to the juxtaposition and union operators provided in
-context-free languages, SBP supports grammars which use the
-intersection operator (<a
-href=http://www.cs.queensu.ca/home/okhotin/conjunctive/>conjunctive
-grammars</a>) and the complement operator (<a
-href=http://www.cs.queensu.ca/home/okhotin/boolean/>boolean
-grammars</a>).
-
-<h1>What features does it have?</h1>
-
-Features fully implemented are in <font color=green>green</font>;
-those partially implemented are in <font color=orange>orange</font>;
-those unimplemented (but planned) are in <font color=red>red</font>.
-
-<ul> <li> <b>An implementation of the Lang-Tomita GLR parsing algorithm</b>
- <ul>
- <li> Including <font color=green>Johnstone & Scott's RNGLR algorithm</font> for epsilon-productions</a>
-
- <li> <a href=http://citeseer.ist.psu.edu/vandenbrand02disambiguation.html><font color=green>Visser's</font> extensions</a>
- for <font color=green>scannerless parsing</font>
- <ul> <li> <font color=green>Follow</font>, <font color=green>Avoid, Prefer</font>, <font color=green>Reject</font> constraints
- <li> <font color=green>Character ranges</font>
- <li> Automatic insertion of <font color=green>whitespace/comments</font>
- </ul>
-
- <li> <font color=green>Any topological space</font> can be
- used as an alphabet (need not be discrete)
- <ul> <li> <font color=green>Unicode</font>
- <li> <font color=orange>Trees</font>
- </ul>
-
- <li> <font color=green>Associativity constraints</font> on <font color=green><i>n</i>-ary operators</font>
-
- </ul>
-
- <li> <b>Ability to parse a wide variety of grammars in
- </b> O(n<sup>3</sup>) time:
-
- <ul>
- <li> <font color=green>all context-free grammars</font>
-
- <li> <font color=green>epsilon productions</font>, <font
- color=green>included in the parse forest</font>
-
- <li> <font color=green>circularities</font>, <font
- color=red>included in the parse forest</font>.
-
- <li> Regular expression operators (
- <tt><font color=green>*</font></tt>,
- <tt><font color=green>?</font></tt>,
- <tt><font color=green>+</font></tt>
- )
-
- <li> <font color=green>conjunctive grammars</font>
- (<font color=green>intersection</font> operator)
-
- <li> <font color=orange>boolean grammars</font> (<font
- color=green>intersection</font>, <font
- color=green>intersect-with-complement</font>, and
- <font color=orange>generalized-complement</font>)
- </ul>
-
-
- <li> <b>Facilitates experimenting with grammars</b>
-
- <ul>
- <li> <font color=green>Interpreted mode</font>, in which the
- parse table is interpreted directly, eliminating the
- need for a compiler and making it easier for grammars
- to operate on grammars.
-
- <li> <font color=green>Simple
- <a href=api/edu/berkeley/sbp/package-summary.html>API</a></font>
- makes it easy to generate, analyze, and modify grammars
- programmatically.
-
- <ul>
- <li> Components of a grammar (nonterminals,
- productions, etc) <font
- color=green>represented as objects</font>
- <li> composite elements implement <font color=green><tt>Iterable<T></tt></font>
- </ul>
-
- <li> <font color=red>Compiled mode</font>, in which Java
- source code is emitted; compiling this code yields a
- parser. The resulting parser is <i>much</i> faster.
- </ul>
-
-
-</ul>
-
-<h1>What is it deliberately missing?</h1>
-
-<ul> <li> Semantic actions; the only option is to return a parse forest.
- <ul>
- <li> This keeps the grammar specification language-neutral.
- <li> A grammar can, however, indicate that certain parts of the parse tree should be dropped.
- </ul>
-</ul>
-
-<h1>What features would be nice to have?</h1>
-
-<ul>
- <li> <strike>Drop Farshi's algorithm and use <a
- href=http://doi.ieeecomputersociety.org/10.1109/HICSS.2002.994495>GRMLR</a></strike>.
- <font color=green>Done!</font>
-
- <li> An implementation of the <a
- href=http://www.cs.berkeley.edu/~smcpeak/elkhound/sources/elkhound/algorithm.html>McPeak-Necula
- optimization</a> for bounded-depth determinism.
-
- <li> Lazy parse trees, to decrease the space requirements from
- o(n) to o(1) [but still O(n)].
-
- <li> Consider implementing <a
- href=http://www.cs.uvic.ca/~nigelh/Publications/cc99-paper.pdf>
- Aycock-Horspool</a> unrolling. Improves performance with
- only highly localized increase in algorithmic complexity.
- Subsumes many other optimizations.
-
-</ul>
-
-<h1>What are the long term goals?</h1>
-
-As we come to a more mature understanding of the pragmatic aspects of
-boolean grammars, a long-term goal is to migrate support for these
-features to existing high-performance GLR implementations (<a
-href=http://www.cs.berkeley.edu/~smcpeak/elkhound/>Elkhound</a>, <a
-href=http://www.delorie.com/gnu/docs/bison/bison_90.html>bison-glr</a>).
-
-<h1>Where can I read more about it?</h1>
-
-<ul> <li> The <a href=../README>README</a> file is the best place to start
- <li> After that, be sure to read <a href=jargon.txt>jargon.txt</a>
- <li> The <a
- href=api/edu/berkeley/sbp/package-summary.html>javadoc</a>
- is the best description of the API
- <li> There's a <a href=../tests/meta.g>tentative metagrammar</a>,
- written in itself.
- <li> You can also get <a href=osq.lunch.talk.pdf>slides</a>
- from my talk at the OSQ Lunch on 02-Nov-2005, though some of
- the stuff (specifically what SBP can and cannot do) is
- outdated.
- <li> A <a href=preprint.pdf>preprint</a> of one of my conference
- submissions.
-</ul>
-
-<h1>Where can I get it?</h1>
-
-The color coding above accurately reflects the state of the
-implementation (<font color=green>11-Dec-2005</font>). However, in its current state it is a
-bit messy, and may require a bit of fiddling to get it to do what you
-want. This situation should improve in the next few weeks as I am
-done adding features (for now) and am currently focusing on
-reliability, cleanliness, and performance.
-<p>
-
-SBP is available under the BSD license.
-<p>
-
-You can download a snapshot (<font color=green>11-Dec-2005</font>) <a
-href=../../edu.berkeley.sbp.tgz>here</a>. The parser-generator
-requires Java 1.5 or later; the Java code it emits <font
-color=orange>should run on any Java 1.1+ JVM</font>. After unpacking
-the archive, simply type <tt>make</tt> to compile SBP and run the
-regression tests.
-
-
-
-</td></tr></table></center>
-</body>
-</html>
projects / sbp.git / commitdiff