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.
   9
  10 </p>
  11
  12 <p>
  13 This package forms the stable core of the SBP API  Classes fall into
  14 five categories:
  15
  16 <ul> <li> <font color=green>Elements of the grammar</font> -- the
  17           pieces from which a grammar is composed.
  18
  19      <li> <font color=purple>Input, Location, and Region</font> -- the
  20           input to be parsed, as well as classes for describing
  21           locations and regions of that input.
  22
  23      <li> Parser -- the engine that actually performs the parsing
  24           process.
  25
  26      <li> <font color=blue>Trees and Forests</font> -- used to
  27           represent the output of the parsing process.
  28
  29      <li> Exceptions.
  30 </ul>
  31 </p>
  32
  33 <h2>Theory of Operation</h2>
  34
  35 <p>
  36
  37 The input that you parse is considered to be a stream of
  38 <tt>Tokens</tt>; this stream is represented by an
  39 <tt>Input&lt;Token&gt;</tt>.  In order to create this <tt>Input</tt>,
  40 you must first decide what kind of tokens you want to parse.  Based on
  41 this decision, you should then implement subclasses of <tt>Input</tt>,
  42 <tt>Parser</tt>, and <tt>Atom</tt> for that token type.  If you are
  43 parsing characters (which you usually are), these subclasses are
  44 provided in the <tt>edu.berkeley.sbp.chr.*</tt> package so you don't
  45 have to write them yourself.
  46
  47 </p><p>
  48
  49 You then create a grammar by instantiating objects belonging to your
  50 subclass of <tt>Atom</tt> and forming them into sequences using
  51 <tt>Sequence.create___()</tt> and <tt>new Union()</tt>.
  52
  53 </p><p>
  54
  55 Ultimately you will wind up with an instance of <tt>Union</tt>
  56 corresponding to the "start nonterminal" of your grammar.  You can
  57 then provide this <tt>Union</tt> to the constructor of your
  58 <tt>Parser</tt> subclass and invoke the <tt>Parser.parse(Input)</tt>
  59 method on the <tt>Input</tt> to be parsed.
  60
  61 </p><p>
  62
  63 The result will be a <tt>Forest</tt>, which is an efficient
  64 representation of a set of one or more trees that may share subtrees.
  65
  66 </p><p>
  67
  68 If the parse was ambiguous, you can use
  69 <tt>Forest.expand(HashSet)</tt> to expand the Forest into all the
  70 possible trees (there is not yet a stable API for inspecting the
  71 <tt>Forest</tt> directly).
  72
  73 </p><p>
  74
  75 If the parse was <i>not</i> ambiguous, you can call
  76 <tt>Forest.expand1()</tt> to return the single possible parsing as a
  77 <tt>Tree</tt>.  You would then typically use the methods of the
  78 <tt>Tree</tt> class to examine the parse tree.
  79
  80 </p>
  81
  82 <a name=example>
  83 <h2>Guide to the API</h2>
  84
  85 <h2>Example</h2>
  86
  87 <div class=example>
  88 <font color=cyan>package</font>&nbsp;<font color=#f0f>edu.berkeley.sbp.misc</font>;<br>
  89 <br>
  90 <font color=cyan>import</font>&nbsp;<font color=#f0f>edu.berkeley.sbp.*</font>;<br>
  91 <br>
  92 <font color=cyan>public</font>&nbsp;<font color=cyan>class</font>&nbsp;Demo2&nbsp;{<br>
  93 <br>
  94 &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>
  95 &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>
  96 &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>
  97 &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>
  98 <br>
  99 &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>
 100 <br>
 101 &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>
 102 <br>
 103 &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>
 104 &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>
 105 &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>
 106 <br>
 107 &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>
 108 &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>
 109 <br>
 110 <font color=red>
 111 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;uncomment&nbsp;this&nbsp;line&nbsp;to&nbsp;disambiguate<br>
 112 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//multSequence&nbsp;=&nbsp;multSequence.andnot(Sequence.create("add",&nbsp;add,&nbsp;null,&nbsp;false));<br>
 113 </font>
 114 <br>
 115 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;expr.add(<font color=orange>Sequence</font>.create(paren,&nbsp;1));<br>
 116 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;expr.add(addSequence);<br>
 117 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;expr.add(multSequence);<br>
 118 &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>
 119 <br>
 120 &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>
 121 <br>
 122 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;System.out.println(<font color=#0f0>"input:&nbsp;&nbsp;\""+input+"\""</font>);<br>
 123 <br>
 124 &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>
 125 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;expr.toString(sb);<br>
 126 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;System.out.println(<font color=#0f0>"grammar:&nbsp;\n"</font>+sb);<br>
 127 <br>
 128 &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>
 129 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;System.out.println(<font color=#0f0>"output:&nbsp;"</font>+f.expand1().toPrettyString());<br>
 130 &nbsp;&nbsp;&nbsp;&nbsp;}<br>
 131 <br>
 132 }<br>
 133 </div>
 134
 135 <p>
 136 Executing this code gives the following:
 137 </p>
 138
 139 <div class=example>
 140 java&nbsp;-Xmx900m&nbsp;-cp&nbsp;edu.berkeley.sbp.jar&nbsp;edu.berkeley.sbp.misc.Demo2<br>
 141 input:&nbsp;&nbsp;"8+(1+3)*7"<br>
 142 grammar:<br>
 143 Expr&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=&nbsp;[(]&nbsp;Expr&nbsp;[)]<br>
 144 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;"add"::&nbsp;Expr&nbsp;[+]&nbsp;Expr<br>
 145 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;"mult"::&nbsp;Expr&nbsp;[*]&nbsp;Expr<br>
 146 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;[0-9]<br>
 147 <br>
 148 Exception&nbsp;in&nbsp;thread&nbsp;"main"&nbsp;unresolved&nbsp;ambiguity;&nbsp;shared&nbsp;subtrees&nbsp;are&nbsp;shown&nbsp;as&nbsp;"*"<br>
 149 &nbsp;&nbsp;possibility:&nbsp;mult:{add:{*&nbsp;*&nbsp;*}&nbsp;*&nbsp;*}<br>
 150 &nbsp;&nbsp;possibility:&nbsp;add:{*&nbsp;*&nbsp;mult:{*&nbsp;*&nbsp;*}}<br>
 151 </div>
 152
 153 <p>
 154 If we uncomment the line in the example, the result is:
 155 </p>
 156
 157 <div class=example>
 158 java&nbsp;-Xmx900m&nbsp;-cp&nbsp;edu.berkeley.sbp.jar&nbsp;edu.berkeley.sbp.misc.Demo2<br>
 159 input:&nbsp;&nbsp;"8+(1+3)*7"<br>
 160 grammar:&nbsp;<br>
 161 Expr&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=&nbsp;[(]&nbsp;Expr&nbsp;[)]&nbsp;<br>
 162 &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>
 163 &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>
 164 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;[0-9]&nbsp;<br>
 165 <br>
 166 output:&nbsp;add:{8&nbsp;+&nbsp;mult:{add:{1&nbsp;+&nbsp;3}&nbsp;*&nbsp;7}}<br>
 167 </div>
 168
 169 <h2>Reporting Bugs</h2>
 170
 171 <p>
 172
 173 Bug reports are especially appreciated when you submit them as a test
 174 case (here's the
 175 <a href=../../../../../tests/testcase.g>grammar</a> and some
 176 <a href=../../../../../tests/regression.tc>examples</a>).
 177
 178 This way we can add your bug report as part of the regression suite,
 179 and be sure we never release a new version in which the bug has crept
 180 back in!
 181
 182 </p>
 183
 184 <p>
 185 For now, please send bug reports to <a
 186 href=http://research.cs.berkeley.edu/project/sbp/list/>the mailing
 187 list</a>.
 188 </p>
 189
 190 </body>