Debugging LALR is difficult

[Daniel Cohen]

In package src/grammars.bnfgrammar, on the "MAIN" branch, you can find the Java source file, BNFbnfgo.java. It has 1500 lines of code. It implements the complete BNF grammar to parse BNF (but it still lacks a code emitter).
I have read in books that debugging a LALR grammar is difficult. Well it's brutal!
Although it's kinda fun, planning a debugger, as a priority project in the near future.

With BNF for Java's syntax analyzer, I can introduce bugs in the analyzer code itself, or in the parser algorithms, or (likely) in the way I interpret the BNF syntax in the first place.

Java debug doesn't help. JUnit adds confidence to the algorithms. But it's up to my ingenuity.

[Daniel Cohen]

To help me debug the parser, I've been using a series of simple grammars. For example:

grammar: letter = 'a';
source #1: a      (which should succeed)
source #2: z      (which should fail )

grammar: letter = 'a'|'b'|'c';
(same source text, same result)

grammar: word={letter};
source #1: abc    (which should succeed)
source #2: abz    (which should fail)

[Daniel Cohen]

When a BNF grammar parses its source, it works by scanning the input terminals, trying to find a match to its syntax rules.

For example, in "Hello World",
- greeting word = "Hello" | "Hi";
Then, if the source text is "Hi", the "Hello" term must fail before the "Hi" term succeeds.

In other words, "fail" does not mean "fail", until all rules fail. That is what makes LALR debug so difficult.

So I have added some working features to help the BNF grammar developer:
- "Source" can report the text row and column where it is scanning, as well as the ultimate scan for the run.
- Any "ParseTree" node can report its entire context (in depth) within the parse tree.
- All framwork objects have a "toXML()" or "toBNF()" similar to Java's "toString()".

As of May 2005, "BNF for Java" pre-alpha is still too difficult to use, but the features that we have implemented work. I believe that you, the BNF grammar developer, will find the "alpha" release to be usable and useful.

-- Dan Cohen in Calgary