Re: regular expression operators in CF grammars

SLK Parsers wrote:
>
> Correctness proofs for good algorithms are usually not that difficult.


Actually my definition of "good style" includes (among other things)
ease of proof. It's no use if an algorithm works but nobody
understands why, and if the reasons are understood, it's
straightforward to write that understanding down in form of a proof.
For the practicioners and trench inhabitants among us: writing down
proofs doesn't require advanced mathematical knowledge. The type
annotations in programs are just a (stylized) proof that the values
assigned to the variables will be of the type given. Note 2: Some
algorithms are indeed so complex that it's difficult or impossible to
produce a simple, straightforward proof. But especially in such
circumstances it's even more important to annotate what's happening.


I'd like to see a practical programming language that embodies these
ideas...


>>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?


I find this rather surprising. Are you sure that the grammars didn't
use special extensions that took them beyond their normal class?
(E.g. ANTLRs lookahead mechanism, which essentially allows one to
annotate an LL grammar with (hopefully equivalent) LR stuff to guide
the production selection.)


Regards,
Joachim

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