<body>
-<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!</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. There is also a
+ <a href=#faq>faq</a> a the end of this document.
+
+</p>
+
+<p>
+This package forms the stable core of the SBP API Classes fall into
+five categories:
+
+<ul> <li> <font color=green>Elements of the grammar</font> -- the
+ pieces from which a grammar is composed.
+
+ <li> <font color=purple>Input, Location, and Region</font> -- the
+ input to be parsed, as well as classes for describing
+ locations and regions of that input.
+
+ <li> Parser -- the engine that actually performs the parsing
+ process.
+
+ <li> <font color=blue>Trees and Forests</font> -- used to
+ represent the output of the parsing process.
+
+ <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>
+
+<a name=example></a>
+<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>
+
+<h2>FAQs</h2>
+
+<hr>
+<p>
+<b>I get the error <tt>java.lang.Error: multiple non-dropped elements
+ in sequence</tt>, what does this mean?</b>
+</p>
+
+<p>
+<font color=red><b>Note</b></font>: this question deals with the
+package <tt>edu.berkeley.sbp.<b>meta</b></tt>, which is not considered
+stable.
+</p>
+
+<p>
+When using the class <tt>edu.berkeley.sbp.meta.Grammar</tt>, you must
+supply an instance of <tt>Grammar.Bindings</tt>; this instance tells
+SBP how to create a parse tree for an expression using the parse trees
+of its subexpressions.
+</p>
+
+<p>
+SBP has no trouble determining what to do when parsing an expression
+that drops all of its subexpressions, or all but one -- for example:
+</p>
+
+<div class=example>
+A = B! C D! E!
+</div>
+
+<p>
+... in this example, only <tt>C</tt> is "non-dropped". In this case,
+the result of parsing <tt>A</tt> is simply the result of parsing
+<tt>C</tt>.
+</p>
+
+<p>
+However, if we were to leave more than one element un-dropped, SBP
+needs to know how to form a single tree out of the two non-dropped
+subtrees. There are two ways to do this. The simplest is to provide
+a tag -- a string which becomes the common parent of the two subtrees:
+</p>
+
+<div class=example>
+Expr = <b>Mult::</b> Expr "*" Expr
+</div>
+
+<p>
+If you are using <tt>AnnotationGrammarBindings</tt>, you can also deal
+with this situation by declaring a method/inner-class whose name
+matches the nonterminal (<tt>Expr</tt>) and has appropriate
+annotations. This is fairly advanced stuff, and the code it uses
+isn't quite as mature as the rest of the code.
+</p>
+
+
+<h2>Reporting Bugs</h2>
+
+<p>
+
+Bug reports are especially appreciated when you submit them as a test
+case (here's the
+<a href=../../../../../tests/testcase.g>grammar</a> and some
+<a href=../../../../../tests/regression.tc>examples</a>).
+
+This way we can add your bug report as part of the regression suite,
+and be sure we never release a new version in which the bug has crept
+back in!
+
+</p>
+
+<p>
+For now, please send bug reports to <a
+href=http://research.cs.berkeley.edu/project/sbp/list/>the mailing
+list</a>.
+</p>
+
</body>
projects / sbp.git / blobdiff