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

On Mar 29, 8:45 am, "Aloha Kakuikanu" <aloha.kakuik..._at_yahoo.com> wrote:
>
> There has to be a (relatively) labor intensive manual step of
> transforming the grammar into LA(1) or LALR form.
>
> Gradually parsers evolve to embrace more powerful (but slower) parsing
> methods. The popular bison parser, for example, has been extended to
> implement GLR method, which handles arbitrary context free grammar.
> Still, BNF remains to be language that most programmers don't speak.

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.

A good mental model of how parsers work is important, and existing tools don't do a very good job of supporting that. They also don't produce great error messages, either, making autodidacticism (sadly the foundation of our profession) quite difficult.

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.

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.

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.

Marshall

PS. Sorry for the off-topic rant. Received on Thu Mar 29 2007 - 19:28:10 CEST