src/edu/berkeley/sbp/package.html

   1 <body>
   2 <p style="border: 1px red solid; width: 50%; padding: 10px; background-color: white; margin-left: auto; margin-right: auto">
   3
   4    The public APIs in this package are <b>stable</b>; package-private
   5    APIs and all other packages are subject to change in future
   6    releases.<br><br>Be sure to read <a
   7    href=../../../../jargon.txt>doc/jargon.txt</a> and the <a
   8    href=#package_description>description</a> below; there is also a
   9    <a href=#faq>faq</a> a the end of this document.
  10
  11 </p>
  12
  13 <p>
  14 This package forms the stable core of the SBP API  Classes fall into
  15 five categories:
  16
  17 <ul> <li> <font color=green>Elements of the grammar</font> -- the
  18           pieces from which a grammar is composed.
  19
  20      <li> <font color=purple>Input, Location, and Region</font> -- the
  21           input to be parsed, as well as classes for describing
  22           locations and regions of that input.
  23
  24      <li> Parser -- the engine that actually performs the parsing
  25           process.
  26
  27      <li> <font color=blue>Trees and Forests</font> -- used to
  28           represent the output of the parsing process.
  29
  30      <li> Exceptions.
  31 </ul>
  32 </p>
  33
  34 <h2>Theory of Operation</h2>
  35
  36 <p>
  37
  38 The input that you parse is considered to be a stream of
  39 <tt>Tokens</tt>; this stream is represented by an
  40 <tt>Input&lt;Token&gt;</tt>.  In order to create this <tt>Input</tt>,
  41 you must first decide what kind of tokens you want to parse.  Based on
  42 this decision, you should then implement subclasses of <tt>Input</tt>,
  43 <tt>Parser</tt>, and <tt>Atom</tt> for that token type.  If you are
  44 parsing characters (which you usually are), these subclasses are
  45 provided in the <tt>edu.berkeley.sbp.chr.*</tt> package so you don't
  46 have to write them yourself.
  47
  48 </p><p>
  49
  50 You then create a grammar by instantiating objects belonging to your
  51 subclass of <tt>Atom</tt> and forming them into sequences using
  52 <tt>Sequence.create___()</tt> and <tt>new Union()</tt>.
  53
  54 </p><p>
  55
  56 Ultimately you will wind up with an instance of <tt>Union</tt>
  57 corresponding to the "start nonterminal" of your grammar.  You can
  58 then provide this <tt>Union</tt> to the constructor of your
  59 <tt>Parser</tt> subclass and invoke the <tt>Parser.parse(Input)</tt>
  60 method on the <tt>Input</tt> to be parsed.
  61
  62 </p><p>
  63
  64 The result will be a <tt>Forest</tt>, which is an efficient
  65 representation of a set of one or more trees that may share subtrees.
  66
  67 </p><p>
  68
  69 If the parse was ambiguous, you can use
  70 <tt>Forest.expand(HashSet)</tt> to expand the Forest into all the
  71 possible trees (there is not yet a stable API for inspecting the
  72 <tt>Forest</tt> directly).
  73
  74 </p><p>
  75
  76 If the parse was <i>not</i> ambiguous, you can call
  77 <tt>Forest.expand1()</tt> to return the single possible parsing as a
  78 <tt>Tree</tt>.  You would then typically use the methods of the
  79 <tt>Tree</tt> class to examine the parse tree.
  80
  81 </p>
  82
  83 <a name=example></a>
  84 <h2>Guide to the API</h2>
  85
  86 <h2>Example</h2>
  87
  88 <div class=example>
  89 <font color=cyan>package</font>&nbsp;<font color=#f0f>edu.berkeley.sbp.misc</font>;<br>
  90 <br>
  91 <font color=cyan>import</font>&nbsp;<font color=#f0f>edu.berkeley.sbp.*</font>;<br>
  92 <br>
  93 <font color=cyan>public</font>&nbsp;<font color=cyan>class</font>&nbsp;Demo2&nbsp;{<br>
  94 <br>
  95 &nbsp;&nbsp;&nbsp;&nbsp;<font color=cyan>private</font>&nbsp;<font color=cyan>static</font>&nbsp;<font color=orange>Atom</font>&nbsp;<font color=#00f>atom</font>(<font color=orange>char</font>&nbsp;<font color=yellow>c</font>)&nbsp;{<br>
  96 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color=cyan>return</font>&nbsp;<font color=cyan>new</font>&nbsp;edu.berkeley.sbp.chr.<font color=orange>CharAtom</font>(c);&nbsp;}<br>
  97 &nbsp;&nbsp;&nbsp;&nbsp;<font color=cyan>private</font>&nbsp;<font color=cyan>static</font>&nbsp;<font color=orange>Atom</font>&nbsp;<font color=#00f>atom</font>(<font color=orange>char</font>&nbsp;<font color=yellow>c1</font>,&nbsp;<font color=orange>char</font>&nbsp;<font color=yellow>c2</font>)&nbsp;{<br>
  98 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color=cyan>return</font>&nbsp;<font color=cyan>new</font>&nbsp;edu.berkeley.sbp.chr.<font color=orange>CharAtom</font>(c1,&nbsp;c2);&nbsp;}<br>
  99 <br>
 100 &nbsp;&nbsp;&nbsp;&nbsp;<font color=cyan>public</font>&nbsp;<font color=cyan>static</font>&nbsp;<font color=cyan>void</font>&nbsp;<font color=#00f>main</font>(<font color=orange>String[]</font>&nbsp;s)&nbsp;throws&nbsp;Exception&nbsp;{<br>
 101 <br>
 102 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color=orange>Union</font>&nbsp;<font color=yellow>expr</font>&nbsp;=&nbsp;<font color=cyan>new</font>&nbsp;<font color=orange>Union</font>(<font color=#0f0>"Expr"</font>);<br>
 103 <br>
 104 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color=orange>Element[]</font>&nbsp;<font color=yellow>add</font>&nbsp;&nbsp;<font color=yellow></font>&nbsp;=&nbsp;<font color=cyan>new</font>&nbsp;<font color=orange>Element</font>[]&nbsp;{&nbsp;expr,&nbsp;atom(<font color=#0f0>'+'</font>),&nbsp;expr&nbsp;};<br>
 105 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color=orange>Element[]</font>&nbsp;<font color=yellow>mult</font>&nbsp;<font color=yellow></font>&nbsp;=&nbsp;<font color=cyan>new</font>&nbsp;<font color=orange>Element</font>[]&nbsp;{&nbsp;expr,&nbsp;atom(<font color=#0f0>'*'</font>),&nbsp;expr&nbsp;};<br>
 106 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color=orange>Element[]</font>&nbsp;<font color=yellow>paren</font>&nbsp;=&nbsp;<font color=cyan>new</font>&nbsp;<font color=orange>Element</font>[]&nbsp;{&nbsp;atom(<font color=#0f0>'('</font>),&nbsp;expr,&nbsp;atom(<font color=#0f0>')'</font>)&nbsp;};<br>
 107 <br>
 108 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color=orange>Sequence</font>&nbsp;<font color=yellow>addSequence</font>&nbsp;=&nbsp;<font color=orange>Sequence</font>.create(<font color=#0f0>"add"</font>,&nbsp;add,&nbsp;<font color=#f0f>null</font>,&nbsp;<font color=#f0f>false</font>);<br>
 109 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color=orange>Sequence</font>&nbsp;<font color=yellow>multSequence</font>&nbsp;=&nbsp;<font color=orange>Sequence</font>.create(<font color=#0f0>"mult"</font>,&nbsp;mult,&nbsp;<font color=#f0f>null</font>,&nbsp;<font color=#f0f>false</font>);<br>
 110 <br>
 111 <font color=red>
 112 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;uncomment&nbsp;this&nbsp;line&nbsp;to&nbsp;disambiguate<br>
 113 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//multSequence&nbsp;=&nbsp;multSequence.andnot(Sequence.create("add",&nbsp;add,&nbsp;null,&nbsp;false));<br>
 114 </font>
 115 <br>
 116 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;expr.add(<font color=orange>Sequence</font>.create(paren,&nbsp;1));<br>
 117 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;expr.add(addSequence);<br>
 118 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;expr.add(multSequence);<br>
 119 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;expr.add(<font color=orange>Sequence</font>.create(atom(<font color=#0f0>'0'</font>,&nbsp;<font color=#0f0>'9'</font>)));<br>
 120 <br>
 121 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color=orange>String</font>&nbsp;<font color=yellow>input</font>&nbsp;=&nbsp;<font color=#0f0>"8+(1+3)*7"</font>;<br>
 122 <br>
 123 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;System.out.println(<font color=#0f0>"input:&nbsp;&nbsp;\""+input+"\""</font>);<br>
 124 <br>
 125 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color=orange>StringBuffer</font>&nbsp;<font color=yellow>sb</font>&nbsp;=&nbsp;<font color=cyan>new</font>&nbsp;<font color=orange>StringBuffer</font>();<br>
 126 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;expr.toString(sb);<br>
 127 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;System.out.println(<font color=#0f0>"grammar:&nbsp;\n"</font>+sb);<br>
 128 <br>
 129 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color=orange>Forest</font>&nbsp;<font color=yellow>f</font>&nbsp;=&nbsp;<font color=cyan>new</font>&nbsp;edu.berkeley.sbp.chr.<font color=orange>CharParser</font>(expr).parse(input);<br>
 130 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;System.out.println(<font color=#0f0>"output:&nbsp;"</font>+f.expand1().toPrettyString());<br>
 131 &nbsp;&nbsp;&nbsp;&nbsp;}<br>
 132 <br>
 133 }<br>
 134 </div>
 135
 136 <p>
 137 Executing this code gives the following:
 138 </p>
 139
 140 <div class=example>
 141 java&nbsp;-Xmx900m&nbsp;-cp&nbsp;edu.berkeley.sbp.jar&nbsp;edu.berkeley.sbp.misc.Demo2<br>
 142 input:&nbsp;&nbsp;"8+(1+3)*7"<br>
 143 grammar:<br>
 144 Expr&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=&nbsp;[(]&nbsp;Expr&nbsp;[)]<br>
 145 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;"add"::&nbsp;Expr&nbsp;[+]&nbsp;Expr<br>
 146 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;"mult"::&nbsp;Expr&nbsp;[*]&nbsp;Expr<br>
 147 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;[0-9]<br>
 148 <br>
 149 Exception&nbsp;in&nbsp;thread&nbsp;"main"&nbsp;unresolved&nbsp;ambiguity;&nbsp;shared&nbsp;subtrees&nbsp;are&nbsp;shown&nbsp;as&nbsp;"*"<br>
 150 &nbsp;&nbsp;possibility:&nbsp;mult:{add:{*&nbsp;*&nbsp;*}&nbsp;*&nbsp;*}<br>
 151 &nbsp;&nbsp;possibility:&nbsp;add:{*&nbsp;*&nbsp;mult:{*&nbsp;*&nbsp;*}}<br>
 152 </div>
 153
 154 <p>
 155 If we uncomment the line in the example, the result is:
 156 </p>
 157
 158 <div class=example>
 159 java&nbsp;-Xmx900m&nbsp;-cp&nbsp;edu.berkeley.sbp.jar&nbsp;edu.berkeley.sbp.misc.Demo2<br>
 160 input:&nbsp;&nbsp;"8+(1+3)*7"<br>
 161 grammar:&nbsp;<br>
 162 Expr&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=&nbsp;[(]&nbsp;Expr&nbsp;[)]&nbsp;<br>
 163 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;"add"::&nbsp;Expr&nbsp;[+]&nbsp;Expr&nbsp;<br>
 164 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;"mult"::&nbsp;Expr&nbsp;[*]&nbsp;Expr&nbsp;&~&nbsp;"add"::&nbsp;Expr&nbsp;[+]&nbsp;Expr&nbsp;<br>
 165 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;[0-9]&nbsp;<br>
 166 <br>
 167 output:&nbsp;add:{8&nbsp;+&nbsp;mult:{add:{1&nbsp;+&nbsp;3}&nbsp;*&nbsp;7}}<br>
 168 </div>
 169
 170 <a name=faq></a>
 171 <h2>FAQs</h2>
 172
 173 <hr>
 174 <p>
 175 <b>I get the error <tt>java.lang.Error: multiple non-dropped elements
 176    in sequence</tt>, what does this mean?</b>
 177 </p>
 178
 179 <p>
 180 <font color=red><b>Note</b></font>: this question deals with the
 181 package <tt>edu.berkeley.sbp.<b>meta</b></tt>, which is not considered
 182 stable.
 183 </p>
 184
 185 <p>
 186 When using the class <tt>edu.berkeley.sbp.meta.Grammar</tt>, you must
 187 supply an instance of <tt>Grammar.Bindings</tt>; this instance tells
 188 SBP how to create a parse tree for an expression using the parse trees
 189 of its subexpressions.
 190 </p>
 191
 192 <p>
 193 SBP has no trouble determining what to do when parsing an expression
 194 that drops all of its subexpressions, or all but one -- for example:
 195 </p>
 196
 197 <div class=example>
 198 A = B! C D! E!
 199 </div>
 200
 201 <p>
 202 ... in this example, only <tt>C</tt> is "non-dropped".  In this case,
 203 the result of parsing <tt>A</tt> is simply the result of parsing
 204 <tt>C</tt>.
 205 </p>
 206
 207 <p>
 208 However, if we were to leave more than one element un-dropped, SBP
 209 needs to know how to form a single tree out of the two non-dropped
 210 subtrees.  There are two ways to do this.  The simplest is to provide
 211 a tag -- a string which becomes the common parent of the two subtrees:
 212 </p>
 213
 214 <div class=example>
 215 Expr = <b>Mult::</b>  Expr "*" Expr
 216 </div>
 217
 218 <p>
 219 If you are using <tt>AnnotationGrammarBindings</tt>, you can also deal
 220 with this situation by declaring a method/inner-class whose name
 221 matches the nonterminal (<tt>Expr</tt>) and has appropriate
 222 annotations.  This is fairly advanced stuff, and the code it uses
 223 isn't quite as mature as the rest of the code.
 224 </p>
 225
 226
 227 <h2>Reporting Bugs</h2>
 228
 229 <p>
 230
 231 Bug reports are especially appreciated when you submit them as a test
 232 case (here's the
 233 <a href=../../../../../tests/testcase.g>grammar</a> and some
 234 <a href=../../../../../tests/regression.tc>examples</a>).
 235
 236 This way we can add your bug report as part of the regression suite,
 237 and be sure we never release a new version in which the bug has crept
 238 back in!
 239
 240 </p>
 241
 242 <p>
 243 For now, please send bug reports to <a
 244 href=http://research.cs.berkeley.edu/project/sbp/list/>the mailing
 245 list</a>.
 246 </p>
 247
 248 </body>