Re: detecting ambiguous grammars

Joachim Durchholz <joachim.durchholz@gmx.de> wrote:
>2) "undecidable" means: you can write an algorithm that checks whether a
>given grammar is ambiguous. However, this algorithm may take an
>arbitrarily long time to terminate, and for some grammars it will never
>reach a conclusion and continue to run forever.


Of course, this doesn't prevent you from building algorithms which will
(almost certainly) cope well with all *real* grammars. Many problems
which compilers solve every day are, *in their full generality*, highly
intractable or provably undecidable. Most real grammars are relatively
simple, especially if they are written by human beings rather than
generated by programs.
--
When failure is not an option, success | Henry Spencer henry@spsystems.net
can get expensive. -- Peter Stibrany | (aka henry@zoo.toronto.edu)

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