doc/sbp.html

   1 <html>
   2 <head><title>The Scannerless Boolean Parser (SBP)</title>
   3 <style>
   4
   5     H1 {
   6         margin-left: -20px;
   7         margin-top: 30px;
   8         font-family: helvetica, verdana, arial, sans-serif;
   9         font-size: 14pt;
  10         font-weight: bold;
  11         text-align: left;
  12         width : 100%;
  13         border-top-width: 2pt;
  14         border-top-style: solid;
  15     }
  16
  17     H2 {
  18         font-family: helvetica, verdana, arial, sans-serif;
  19         font-size: 12pt;
  20         font-weight: bold;
  21     }
  22
  23     H3 {
  24         margin-left: -10px;
  25         font-family: helvetica, verdana, arial, sans-serif;
  26         font-size: 12pt;
  27         font-weight: bold;
  28     }
  29
  30     TH, TD, P, LI {
  31         font-family: helvetica, verdana, arial, sans-serif;
  32         font-size: 13px;
  33         text-decoration:none;
  34     }
  35
  36     LI { margin-top: 5px; }
  37
  38 </style>
  39 </head>
  40 <body>
  41 <center><table><tr><td width=600>
  42
  43 <center>
  44 <font style='font-size:24pt; font-family:helvetica, verdana, arial, sans-serif'>
  45 <b>SBP: the Scannerless Boolean Parser</b></font>
  46 </center>
  47
  48 <p>
  49 <center>
  50 16-Aug: A new snapshot is <a href=../../edu.berkeley.sbp.tgz>here</a>.
  51 </center>
  52 </p>
  53
  54 <br><br>
  55 <center>
  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>
  58
  59 <p align=right>
  60 <a href=../../images/error.png>
  61 <img align=right src=../../images/error.png width=200>
  62 </a>
  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.
  69 </p>
  70
  71 </td></tr></table>
  72 </center>
  73
  74 <br><br>
  75 <center>
  76 <table width=400><tr><td>
  77 <font color=gray><b>Update:</b> [22-July-2006]<br><br>
  78
  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>.
  80 </font>
  81 </td></tr></table>
  82 </center>
  83
  84 <br><br>
  85 <center>
  86 <table width=400><tr><td>
  87
  88 <font color=gray><b>Update:</b></font> [17-July-2006]<br><br>
  89
  90 There is now a <a href=http://research.cs.berkeley.edu/project/sbp/list/>mailing list</a>.
  91
  92
  93 </td></tr></table>
  94 </center>
  95
  96 <br><br>
  97 <center>
  98 <table width=400><tr><td>
  99 <font color=gray><b>Update:</b> [05-July-2006]</font><br><br>
 100 <font color=gray>
 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>.
 106 </font>
 107 </td></tr></table>
 108 </center>
 109
 110 <h1>What is it?</h1>
 111
 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.
 116
 117 <h1>What is interesting about it?</h1>
 118
 119 SBP deliberately sacrifices performance in favor of ease of extensibility.
 120 <p>
 121
 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.
 125 <p>
 126
 127 It is <a
 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,
 132 and Wiki markup.
 133 <p>
 134
 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
 141 grammars</a>).
 142
 143 <h1>What features does it have?</h1>
 144
 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>.
 148
 149 <ul> <li> <b>An implementation of the Lang-Tomita GLR parsing algorithm</b>
 150      <ul>
 151           <li> Including <font color=green>Johnstone &amp; Scott's RNGLR algorithm</font> for epsilon-productions</a>
 152
 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>
 158                </ul>
 159
 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>
 164           </ul>
 165
 166           <li> <font color=green>Associativity constraints</font> on <font color=green><i>n</i>-ary operators</font>
 167
 168      </ul>
 169
 170      <li> <b>Ability to parse a wide variety of grammars in
 171           </b> O(n<sup>3</sup>) time:
 172
 173      <ul>
 174           <li> <font color=green>all context-free grammars</font>
 175
 176           <li> <font color=green>epsilon productions</font>, <font
 177                color=green>included in the parse forest</font>
 178
 179           <li> <font color=green>circularities</font>, <font
 180          color=red>included in the parse forest</font>.
 181
 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>
 186                )
 187
 188           <li> <font color=green>conjunctive grammars</font>
 189                (<font color=green>intersection</font> operator)
 190
 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>)
 195      </ul>
 196
 197
 198      <li> <b>Facilitates experimenting with grammars</b>
 199
 200      <ul>
 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.
 205
 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
 209                programmatically.
 210
 211           <ul>
 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&lt;T&gt;</tt></font>
 216           </ul>
 217
 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.
 221      </ul>
 222
 223
 224 </ul>
 225
 226 <h1>What is it deliberately missing?</h1>
 227
 228 <ul> <li> Semantic actions; the only option is to return a parse forest.
 229      <ul>
 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.
 232      </ul>
 233 </ul>
 234
 235 <h1>What features would be nice to have?</h1>
 236
 237 <ul>
 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>
 241
 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.
 245
 246     <li> Lazy parse trees, to decrease the space requirements from
 247          o(n) to o(1) [but still O(n)].
 248
 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.
 254
 255 </ul>
 256
 257 <h1>What are the long term goals?</h1>
 258
 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>).
 264
 265 <h1>Where can I read more about it?</h1>
 266
 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>
 269      <li> The <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>,
 273           written in itself.
 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
 277           outdated.
 278      <li> A <a href=preprint.pdf>preprint</a> of one of my conference
 279           submissions.
 280 </ul>
 281
 282 <h1>Where can I get it?</h1>
 283
 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.
 290 <p>
 291
 292 SBP is available under the BSD license.
 293 <p>
 294
 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
 300 regression tests.
 301
 302
 303
 304 </td></tr></table></center>
 305 </body>
 306 </html>