Re: Backtracking yacc

bromage@mullauna.cs.mu.OZ.AU (Andrew Bromage)
Thu, 17 Sep 1992 03:54:34 GMT

          From comp.compilers
Related articles
Backtracking yacc jarmo@ksvltd.FI (Jarmo Raiha) (1992-09-10)
Re: Backtracking yacc ipser@solomon.technet.sg (1992-09-11)
Re: Backtracking yacc sasghm@unx.sas.com (Gary Merrill) (1992-09-11)
Re: Backtracking yacc sasghm@unx.sas.com (Gary Merrill) (1992-09-14)
Re: Backtracking yacc ipser@solomon.technet.sg (1992-09-16)
Re: Backtracking yacc bromage@mullauna.cs.mu.OZ.AU (1992-09-17)
Re: Backtracking yacc Jasper.Kamperman@cwi.nl (1992-09-17)
Re: Backtracking yacc sasghm@unx.sas.com (1992-09-17)
Re: Backtracking yacc diamond@jit081.enet.dec.com (18-Sep-1992 1420) (1992-09-18)
Re: Backtracking yacc harwood@progress.com (Tom Harwood) (1992-09-18)
Re: Backtracking yacc ipser@solomon.technet.sg (1992-09-19)
Re: Backtracking yacc andrewd@cs.adelaide.edu.au (1992-09-21)
[6 later articles]
| List of all articles for this month |
Newsgroups: comp.compilers
From: bromage@mullauna.cs.mu.OZ.AU (Andrew Bromage)
Organization: Computer Science, University of Melbourne, Australia
Date: Thu, 17 Sep 1992 03:54:34 GMT
References: 92-09-059
Keywords: yacc, parse

In posting by jarmo@ksvltd.FI (Jarmo Raiha):
>[ ...Besides, isn't there a theorem that says that
>any LR(k) grammar can be rewritten as LR(1)? -John]


The way I understand it is that any LR(k) _language_ can be rewritten as
LR(1) and, in fact, if you introduce a nonterminal representing the end of
input (which can be shifted), can also be written as LR(0). The trouble is
that the grammar may not represent the true structure of the language.


Compare, for example, parsing mathematical expressions with an LL parser.
The language is LL, sure, but the correct precedences and the possibility
of left recursion cannot be resolved without using some other method.


Andrew Bromage
--

Post a followup to this message

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