gmane.comp.parsers.sbp.user

Re: Lone negative conjuncts

Adam Megacz — 2011-01-27T23:22:10

Sean <root< at >rprogrammer.net> writes:

Hrm, doesn't

  X = ~~Y

work?



I think you would actually want to use "any string of any length" as the
positive conjunct:

  X = ~[]* &~ Y

Where ~[]* is SBP admittedly-strange idiom for "any string" (read it as
[] being the empty character class, ~[] being its complement, and ~[]*
being the repetition thereof zero or more times; nearly all my grammars
make this into a nonterminal called "Any" or something like that).

  - a

Scala bindings for SBP added, Haskell bindings deprecated

Adam Megacz — 2011-01-23T03:10:43

The Haskell bindings for SBP have fallen into a state of terminal
disrepair, and I regret that I haven't been able to find a decent
Haskell<->Java bridge.  So, for the moment, I'm abandoning the Haskell
bindings.

However, on the positive side, I've added (terribly inefficient) Scala
bindings to the latest checkin:

  http://git.megacz.com/?p=sbp.git;a=summary

walking parse trees in Scala is quite pleasant, for basically the same
reasons that it was pleasant in Haskell.  For an example usage, see the
source code for WiX:

  http://git.megacz.com/?p=wix.git;a=blob;f=src/Doc.scala

  - a

Lone negative conjuncts

Sean — 2011-01-23T03:19:54

Thanks for the clarification, I think I understand it now.
But just one more thing:
In the definition of boolean grammars I read, it said m (number of
positive conjuncts) + n (number of negative conjuncts) >= 1, but in
SBP it seems to be m >= 1, that is one cannot create a rule formed
solely out of disjunctions.

Would it be functionally equivalent to make a Sequence with no
elements as the base, and andnot() negative conjuncts to that?

Re: Rewriting in needs and hates

Adam Megacz — 2011-01-23T03:07:36

Sean <root< at >rprogrammer.net> writes:

No.  Any time you have a conjunct (positive or negative), the parse tree
produced by the second half is discarded.  For example:

  A = B &  C
    | D &~ E

parse trees for "C" and "E" will never be produced.

In the case of negative conjuncts ("E") we cannot save the parse trees

Re: Understanding the grammars

Adam Megacz — 2011-01-23T03:04:20

Hi, Sean.

Sean <root< at >rprogrammer.net> writes:

Sadly, SBP can't do that.  The toString() methods on the grammar classes
are just for convenience and debugging; they don't actually produce a
valid GrammarAST.

There are actually two steps here:

  1) from "mygrammar.g" to GrammarAST
  2) from GrammarAST to Grammar (i.e., Union, Sequence, etc)

both of these steps are "one way" -- you lose information, so there's no
way to reverse the process.


Hrm, I'm not quite sure why you'd want to do that.  Are you attempting
to modify the parser itself, or do you just want to use it?

If you just want to use the parser, you should write your grammars using
the metagrammar.  If the parser malfunctions, let me know (and I'll try
to fix any bugs), but for the most part you should be able to debug your
grammar by looking at the parse trees (or parse errors) -- the same as
with other parsers like bison.

On the other hand, if you want to learn about the Tomita GLR algorithm
(and Okhotin's extension to boolean GLR), I don't

Rewriting in needs and hates

Sean — 2011-01-13T08:39:56

Is the rewriting tag ever used in the sequences which specify
conjunctions and disjunctions (needs and hates)?

Understanding the grammars

Sean — 2011-01-12T07:11:23

Hi, I'm trying to learn about boolean grammars, and I think I
understand the explanation on http://users.utu.fi/aleokh/boolean/
My question is: how can I inspect Union, Sequence, and Atom object graphs?
I tried using toString(StringBuffer) but haven't yet succeeded in
producing output that can be run back through GrammarAST.
Briefly I tried using Eclipse to inspect the raw object fields, but I
can see that would require some reverse-engineering.
If there was some way to dump a grammar (given a Union object, say)
into the N and P sets, with rules in canonical form, that would be
interesting, but just being able to show the grammar in its most basic
form (ie, with syntactic shortcuts like *?+ resolved) would be very
nice (in fact, I think it would be almost be enough to learn the
metagrammar).
    --RP

mailing list moved to sbp< at >lists.berkeley.edu

Adam Megacz — 2010-10-24T23:03:57

Hi, this email is just a reminder that the mailing list has been moved
from the old host at hcoop.net to sbp< at >lists.berkeley.edu.  Everybody who
was subscribed to the old list has been subscribed to the new list (you
should have recieved an email).  Here's the link:

  https://calmail.berkeley.edu/manage/list/listinfo/sbp< at >lists.berkeley.edu

Re: Indentation (tree) parsing

Adam Megacz — 2010-05-02T20:58:45

Adam Megacz <megacz< at >cs.berkeley.edu> writes:

FWIW, there are at least two subtle issues here.

First, how to handle a "partial" indentation decrease.  For example:

...red
........blue
.....green

There really are only two choices.  Either allow this (and say that
blue and green are siblings with red their common parent), or declare
this to be an error and reject it.

The other issue is trickier.

...red
.....blue
........green
.....purple
.....white

Are purple and white siblings, or are they a single node that spans
two lines?  The knee-jerk reaction is to say that they are siblings,
but then you won't be able to parse this:

...module foo
.....import fred
........bob
.....if 1=2 then yes
.....else no

because the "if 1=2 then yes" and "else no" will end up as siblings in
the parse tree, where any sane grammar will expect "else no" to be a
child of "if 1=2".

The choices here are more difficult:

  1. Always assume they are siblings

  2. Always assume that the largest possible contiguous sequence of

Re: Indentation (tree) parsing

Adam Megacz — 2010-05-02T01:23:21

Yang Zhang <yanghatespam< at >gmail.com> writes:

Hi, sorry about the slow reply here; I'm usually quicker.

The technique used in the LDTA06 paper only applies when the arity of
each tree node can be determined by examining its head.  In the grammar
given in that paper, the tree has fixed arity (every non-leaf node is of
degree 2).

I've added a new regression test (see the end of regression.tc) that
shows how to do indentation-based parsing for binary trees.  It should
be straightforward to adapt it to any fixed arity, and it shouldn't be
hard to see how to do varying arity as long as you can determine the
arity from the head of the node.

I believe that variable arity parsing (where the arity is determined
from the indentation, like in Haskell) is possible, but I haven't had
time to work it out yet.

  - a

Indentation (tree) parsing

Yang Zhang — 2010-03-17T18:56:49

Hi, I'm interested in parsing this text:

xxx
|xxx
|xxx
||xxx
||xxx
|xxx
xxx

into this tree:

Branch {
  Branch {
    Leaf
    Branch {
      Leaf
      Leaf
    }
    Leaf
  }
  Leaf
}

I was borrowing the technique outlined in the LDTA06 paper, but I
can't seem to really hack it. Here's my current grammar:

s = Tree [\n ]!*
Tree = Tree::(Branch | Leaf)+
Leaf = Leaf::"|"**! "xxx" "\n" &~ BranchR "|"
BranchR = "|" BranchR "|" | [~|]++! "\n"
Branch = Branch::"|"**! "xxx" "\n" Tree &~ LeafR
LeafR = "|" LeafR "|" | "|" [~|]++! "\n"

It seems that Branch should be wrapped, but I don't know how to not
consume the subsequent nodes in the tree as part of the Branch itself
(i.e. not sure how to get the "lookahead" behavior). Any hints? Thanks
in advance.

Re: Getting started

Adam Megacz — 2010-03-03T00:02:40

Yang Zhang <yanghatespam< at >gmail.com> writes:

See the "\n" there at the end of "text"?  Your grammar probably doesn't
include any provisions for whitespace.  Try adding this line to math.g
instead:

  s = Expr [\n ]!*


Ok, fixed.


Ah, unfortunately GrammarAST.emitCode() does not work yet.  I've checked
in a comment mentioning this fact.


I wish I had time to... probably not until the end of the semester.
Keep pestering me!

  - a

Getting started

Yang Zhang — 2010-02-05T00:11:51

Hi, I've been reading the docs (incl. the Javadoc), but I still don't
have a very good sense of how to write and use some simple grammars.
I'm interested in specifying grammars using the metagrammar, but
mostly I've been working my way backwards around the Java source and
tweaking the files in tests/*.g without luck.

For instance, after adding "s=Expr" to math.g, running `java -jar
edu.berkeley.sbp.jar tests/math.g testme` (where `testme` just has
`1+1`) gives me:

unexpected end of file at 2:1
     text: 1+1\n
 expected:

        at edu.berkeley.sbp.ParseFailed.error(ParseFailed.java:232)
        at edu.berkeley.sbp.ParseFailed.error(ParseFailed.java:144)
        at edu.berkeley.sbp.GSS$Phase.shift(GSS.java:158)
        at edu.berkeley.sbp.GSS$Phase.<init>(GSS.java:105)
        at edu.berkeley.sbp.Parser.parse(Parser.java:49)
        at edu.berkeley.sbp.misc.CommandLine.main(CommandLine.java:23)

`demo.g` fails to parse using the metagrammar -- I had to add `blah::`
in front of certain things to get to the

Re: Build issues

Adam Megacz — 2010-01-21T18:11:26

Yang Zhang <yanghatespam< at >gmail.com> writes:

My apologies, it looks like I mis-merged some old code.  I have fixed
things, and "make test" should work now.  Could you let me know if it
works for you?

Let me know if you have any other questions,

  - a

Build issues

Yang Zhang — 2010-01-21T15:13:28

I tried both git and , but although the code builds, the main class is
commented out. Removing the comment markers introduces a bunch of
build errors, some of which weren't trivial fixes, such as missing
classes (Bindings) and methods. Attached are fixes for some of the
issues, after which I see the following build issues:

$ make
mkdir -p bin
javac  -cp javax.servlet.jar -d bin -sourcepath src
src/edu/berkeley/sbp/Grammar.java
src/edu/berkeley/sbp/meta/MetaGrammar.java
src/edu/berkeley/sbp/meta/GrammarAST.java
src/edu/berkeley/sbp/meta/Repeat.java
src/edu/berkeley/sbp/misc/StringWalker.java
src/edu/berkeley/sbp/misc/CommandLine.java
src/edu/berkeley/sbp/misc/ReflectiveWalker.java
src/edu/berkeley/sbp/misc/Cartesian.java
src/edu/berkeley/sbp/misc/Demo.java
src/edu/berkeley/sbp/misc/Java15.java
src/edu/berkeley/sbp/misc/TestAstGenerator.java
src/edu/berkeley/sbp/misc/IndentingReader.java
src/edu/berkeley/sbp/misc/RegressionTests.java
src/edu/berkeley/sbp/misc/Demo2.java
src/edu/berkeley/sbp/misc/TreeWalker.ja