Re: regular expression operators in CF grammars

> While this is potentially a true statement, if you think about it, it
> discourages all improvement, since any improvement runs the risk of
> being incorrect until it is "proven".


Correctness proofs for good algorithms are usually not that difficult.


> Note, even a "classical" algorithm has some risk that ones own
> implementation has made an error (perhaps typographical) in the
> implementation.


So, if it is hard enough to correctly implement a correct algorithm then...


> That being said, there are some fairly straight-forward algorithms for
> implementing EBNF translations directly as part of the parser
> generation. I would be very surprised in the EBNF translations in
> some of the more popular LL parser generators (e.g. ANTLR, JavaCC,
> RDP) were not robust.


Would you be surprised to learn that 4 of 22 grammars were
misclassified in the Ph.D. thesis on which one of these tools was
based?


> Lest one think that the conflict avoidance problem is a minor point,
> let me just say that I have seen numerous grammars where using regular
> expressions were an important key to making the grammar parseable.


This would be a compelling argument for EBNF if we could be sure that the
method produces correct results.


http://parsers.org/slk

Return to the comp.compilers page.
Search the comp.compilers archives again.