Re: What is the logic of storing XML in a Database?

From: Aloha Kakuikanu <>
Date: 29 Mar 2007 10:44:49 -0700
Message-ID: <>

On Mar 29, 10:28 am, "Marshall" <> wrote:
> I think the current situation with regards to BNF not being a
> widely held technical skill has a lot to do with the historical
> situation regarding transformation into LALR etc. That is
> not only "labor intensive, manual" but also cognitively difficult.
> Consider trying to explain to someone the difference between
> shift-reduce conflicts and reduce-reduce conflicts, for example.

This is again declarative versus procedural. BNF is declarative description of the language, while automata is procedural. Automaton processes one symbol of the at a time, and I never has been able keep my mind focused on the intricacies of state management and backtracking. BNF describes what rules a whole set of strings obeys to.

> Lately we hear a lot about Earley parsing and other techniques.
> Also, the trend lately is for scannerless parsers, or at least
> parsers generators where the scanning and the parsing are
> described by a unified format.

CYK is conceptually simpler method. Maybe the reason why I like it so much is because in the essence CYK is calculating transitive closure.

> For myself, I have high hopes for the wider adoption of parser
> generators through the vehicle of backtracking parsers. They
> have poor worst-case performance, but typical performance
> is fine. In fact my understanding is that if you give an ll(1) grammar
> to a backtracking parser generator it will generate a parser
> as good as what you would get out of a parser generator
> that *only* accepted ll(1). The advantage of the backtracking
> parser is that it will accept a much wider range of grammars,
> making it more accessible to everyman.

It is not only the parser engine implementation. The BNF language should be improved as well. Two operations is good to advance the theory, but practice need a rich set of killer operations.

> Another gripe I have is a common limitation with the handling
> of different recursivity of rules. A top-down parser cannot
> handle a left-recursive rule, a bottom-up parser can't handle
> a right recursive rule. Left recursive rules rules naturally model
> right associative operators; right recursive rules naturally
> model left associative operators. Almost every language of
> interest will have both left associative and right associative
> operators. Yes, there are transformations you can do that
> will turn one into the other, but those are, again, manual
> and labor intensive, not to mention cognitively complex.

I'm past the state where I evaluated off the shelf parsers. CYK algorithm is so simple, that even mediocre programmer can code it. Likewise, Earley. They are a bit slower, but history always proves that programmer time is more valuable than the machine. Received on Thu Mar 29 2007 - 19:44:49 CEST

Original text of this message