Re: compiler with non-deterministic grammar (A Johnstone)
17 May 1997 00:09:46 -0400

          From comp.compilers

Related articles
compiler with non-deterministic grammar (Wei-cheng Lai) (1997-05-03)
Re: compiler with non-deterministic grammar (Scott Stanchfield) (1997-05-08)
Re: compiler with non-deterministic grammar eserra@svmp01.Harris.COM (Efren Serra) (1997-05-13)
Re: compiler with non-deterministic grammar (Sandeep Dutta) (1997-05-15)
Re: compiler with non-deterministic grammar (1997-05-17)
| List of all articles for this month |

From: (A Johnstone)
Newsgroups: comp.compilers
Date: 17 May 1997 00:09:46 -0400
Organization: Royal Holloway, University of London
References: 97-05-014 97-05-186
Keywords: parse

Sandeep Dutta ( 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.


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

Post a followup to this message

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