<body>
-<p>
-<b>
- <font color=red>IMPORTANT:</font>
- BE SURE TO READ THE FILE
- <tt><font size=big><a href=../../../../jargon.txt>doc/jargon.txt</a></big></tt> FIRST!<br> Also, see the legend at the bottom of this page.
-</b>
+<p style="border: 1px red solid; width: 50%; padding: 10px; background-color: white; margin-left: auto; margin-right: auto">
+
+ The public APIs in this package are <b>stable</b>; package-private
+ APIs and all other packages are subject to change in future
+ releases.<br><br>Be sure to read <a
+ href=../../../../jargon.txt>doc/jargon.txt</a> and the <a
+ href=#package_description>description</a> below.
+
</p>
<p>
<li> Exceptions.
</ul>
</p>
+
+<h2>Theory of Operation</h2>
+
+<p>
+
+The input that you parse is considered to be a stream of
+<tt>Tokens</tt>; this stream is represented by an
+<tt>Input<Token></tt>. In order to create this <tt>Input</tt>,
+you must first decide what kind of tokens you want to parse. Based on
+this decision, you should then implement subclasses of <tt>Input</tt>,
+<tt>Parser</tt>, and <tt>Atom</tt> for that token type. If you are
+parsing characters (which you usually are), these subclasses are
+provided in the <tt>edu.berkeley.sbp.chr.*</tt> package so you don't
+have to write them yourself.
+
+</p><p>
+
+You then create a grammar by instantiating objects belonging to your
+subclass of <tt>Atom</tt> and forming them into sequences using
+<tt>Sequence.create___()</tt> and <tt>new Union()</tt>.
+
+</p><p>
+
+Ultimately you will wind up with an instance of <tt>Union</tt>
+corresponding to the "start nonterminal" of your grammar. You can
+then provide this <tt>Union</tt> to the constructor of your
+<tt>Parser</tt> subclass and invoke the <tt>Parser.parse(Input)</tt>
+method on the <tt>Input</tt> to be parsed.
+
+</p><p>
+
+The result will be a <tt>Forest</tt>, which is an efficient
+representation of a set of one or more trees that may share subtrees.
+
+</p><p>
+
+If the parse was ambiguous, you can use
+<tt>Forest.expand(HashSet)</tt> to expand the Forest into all the
+possible trees (there is not yet a stable API for inspecting the
+<tt>Forest</tt> directly).
+
+</p><p>
+
+If the parse was <i>not</i> ambiguous, you can call
+<tt>Forest.expand1()</tt> to return the single possible parsing as a
+<tt>Tree</tt>. You would then typically use the methods of the
+<tt>Tree</tt> class to examine the parse tree.
+
+</p>
+<h2>Guide to the API</h2>
+
+<h2>Example</h2>
+
+<div class=example>
+<font color=cyan>package</font> <font color=#f0f>edu.berkeley.sbp.misc</font>;<br>
+<br>
+<font color=cyan>import</font> <font color=#f0f>edu.berkeley.sbp.*</font>;<br>
+<br>
+<font color=cyan>public</font> <font color=cyan>class</font> Demo2 {<br>
+<br>
+ <font color=cyan>private</font> <font color=cyan>static</font> <font color=orange>Atom</font> <font color=#00f>atom</font>(<font color=orange>char</font> <font color=yellow>c</font>) {<br>
+ <font color=cyan>return</font> <font color=cyan>new</font> edu.berkeley.sbp.chr.<font color=orange>CharAtom</font>(c); }<br>
+ <font color=cyan>private</font> <font color=cyan>static</font> <font color=orange>Atom</font> <font color=#00f>atom</font>(<font color=orange>char</font> <font color=yellow>c1</font>, <font color=orange>char</font> <font color=yellow>c2</font>) {<br>
+ <font color=cyan>return</font> <font color=cyan>new</font> edu.berkeley.sbp.chr.<font color=orange>CharAtom</font>(c1, c2); }<br>
+<br>
+ <font color=cyan>public</font> <font color=cyan>static</font> <font color=cyan>void</font> <font color=#00f>main</font>(<font color=orange>String[]</font> s) throws Exception {<br>
+<br>
+ <font color=orange>Union</font> <font color=yellow>expr</font> = <font color=cyan>new</font> <font color=orange>Union</font>(<font color=#0f0>"Expr"</font>);<br>
+<br>
+ <font color=orange>Element[]</font> <font color=yellow>add</font> <font color=yellow></font> = <font color=cyan>new</font> <font color=orange>Element</font>[] { expr, atom(<font color=#0f0>'+'</font>), expr };<br>
+ <font color=orange>Element[]</font> <font color=yellow>mult</font> <font color=yellow></font> = <font color=cyan>new</font> <font color=orange>Element</font>[] { expr, atom(<font color=#0f0>'*'</font>), expr };<br>
+ <font color=orange>Element[]</font> <font color=yellow>paren</font> = <font color=cyan>new</font> <font color=orange>Element</font>[] { atom(<font color=#0f0>'('</font>), expr, atom(<font color=#0f0>')'</font>) };<br>
+<br>
+ <font color=orange>Sequence</font> <font color=yellow>addSequence</font> = <font color=orange>Sequence</font>.create(<font color=#0f0>"add"</font>, add, <font color=#f0f>null</font>, <font color=#f0f>false</font>);<br>
+ <font color=orange>Sequence</font> <font color=yellow>multSequence</font> = <font color=orange>Sequence</font>.create(<font color=#0f0>"mult"</font>, mult, <font color=#f0f>null</font>, <font color=#f0f>false</font>);<br>
+<br>
+<font color=red>
+ // uncomment this line to disambiguate<br>
+ //multSequence = multSequence.andnot(Sequence.create("add", add, null, false));<br>
+</font>
+<br>
+ expr.add(<font color=orange>Sequence</font>.create(paren, 1));<br>
+ expr.add(addSequence);<br>
+ expr.add(multSequence);<br>
+ expr.add(<font color=orange>Sequence</font>.create(atom(<font color=#0f0>'0'</font>, <font color=#0f0>'9'</font>)));<br>
+<br>
+ <font color=orange>String</font> <font color=yellow>input</font> = <font color=#0f0>"8+(1+3)*7"</font>;<br>
+<br>
+ System.out.println(<font color=#0f0>"input: \""+input+"\""</font>);<br>
+<br>
+ <font color=orange>StringBuffer</font> <font color=yellow>sb</font> = <font color=cyan>new</font> <font color=orange>StringBuffer</font>();<br>
+ expr.toString(sb);<br>
+ System.out.println(<font color=#0f0>"grammar: \n"</font>+sb);<br>
+<br>
+ <font color=orange>Forest</font> <font color=yellow>f</font> = <font color=cyan>new</font> edu.berkeley.sbp.chr.<font color=orange>CharParser</font>(expr).parse(input);<br>
+ System.out.println(<font color=#0f0>"output: "</font>+f.expand1().toPrettyString());<br>
+ }<br>
+<br>
+}<br>
+</div>
+
+<p>
+Executing this code gives the following:
+</p>
+
+<div class=example>
+java -Xmx900m -cp edu.berkeley.sbp.jar edu.berkeley.sbp.misc.Demo2<br>
+input: "8+(1+3)*7"<br>
+grammar:<br>
+Expr = [(] Expr [)]<br>
+ | "add":: Expr [+] Expr<br>
+ | "mult":: Expr [*] Expr<br>
+ | [0-9]<br>
+<br>
+Exception in thread "main" unresolved ambiguity; shared subtrees are shown as "*"<br>
+ possibility: mult:{add:{* * *} * *}<br>
+ possibility: add:{* * mult:{* * *}}<br>
+</div>
+
+<p>
+If we uncomment the line in the example, the result is:
+</p>
+
+<div class=example>
+java -Xmx900m -cp edu.berkeley.sbp.jar edu.berkeley.sbp.misc.Demo2<br>
+input: "8+(1+3)*7"<br>
+grammar: <br>
+Expr = [(] Expr [)] <br>
+ | "add":: Expr [+] Expr <br>
+ | "mult":: Expr [*] Expr &~ "add":: Expr [+] Expr <br>
+ | [0-9] <br>
+<br>
+output: add:{8 + mult:{add:{1 + 3} * 7}}<br>
+</div>
+
</body>
projects / sbp.git / blobdiff