Re: compiler with non-deterministic grammar

Sandeep Dutta (Sandeep.dutta@mpct.com) wrote:
: Try PRECCX - the infinite look-ahead compiler compiler .. for this
: compiler compiler the grammar needs to be specified in a Prologue like
: language (ie goal-proving) the parser generated by this compiler
: compiler will try to prove all possible paths (ideal for context
: sensitive grammar)




I don't think PRECC will help much. PRECC is a first-match
arbitrary-backtrack parser generator. As such it will accept with
probability one the first matching alternate it finds in a recursive
descent parse. It does not, therefore, investigate all parses. In
general, a grammar must be reordered for so that the desired match is
first. Often it is best to reorder the grammar so that the longest
match comes as the first alternate production. This is awkward and
non-general - I can display an unambiguous grammar for which PRECC
cannot work in that for any given grammar ordering there is a string
in the language that will not be correctly parsed. So (i) the
generality claims for PRECC are over-strong and (ii) it is not
probabilistic (although it might be made so in the same way as a
previous poster suggested that PCCTS might be deployed.


                                                Adrian


--
    Dr Adrian Johnstone, Dean of the Science Faculty, Dept of Computer Science,
        Royal Holloway, University of London, Egham, Surrey, TW20 0EX, England.
Email: adrian@dcs.rhbnc.ac.uk Tel: +44 (0)1784 443425 Fax: +44 (0)1784 443420
--

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