sankar@Neon.Stanford.EDU (Sriram Sankar) (10/27/90)
I've been reading the messages on whether or not PASCAL is LL/LR. Some
background: LL(n+1) languages are a strict superset of LL(n) languages;
LR(n+1) languages are the same set as the LR(n) languages (n>0). A
standard transformation of all languages before generating tables is to
tag a $ to the end of all programs. This transformation makes the
language LR(0) (refer to the prefix property). i.e., intuitively, there's
not that much difference between LR(0) and LR(n), n>0 languages.
A language is LR iff it can be accepted by a deterministic PDA. (Note:
CFL iff it can be accepted by a NDPDA.) Inherently ambiguous languages
are not LR. To determine intuitively if a language is LR, try to mimic a
DPDA. It has an "infinite" stack but only a finite number of states and
cannot go backwards on the input. So if you can make a shift/reduce
decision by looking only at a finite and bounded amount of information on
the top of the stack and a finite and bounded number of input symbols,
then the language is LR. Since PASCAL has a rule that dangling else's
associate with the innermost 'if', it seems obvious to me that PASCAL (at
least wrt to the if statement) is LR. If the dangling else was associated
with the outermost 'if' you can still make the necessary S/R decisions, so
I do think (not looked at it carefully enough though) that this too is LR.
About LL-ness. I do this intuitively by trying to design a recursive
descent machine. It seems pretty easy for a recursive descent machine to
handle the dangling else in PASCAL, so I guess that PASCAL does have a
grammar that is LL. But this I'm not absolutely sure of (this whole
paragraph on LL-ness), so I'd like to hear your comments rather than
spending the time trying to figure it out. :-)
One of my interest areas is to build parsing tools that will accept
"user-friendly" grammars of CFLs. What people do nowadays is accept the
existing two engines (LL and LR) and bend over backwards to get their
grammars acceptable to one of them.
Sriram Sankar
Computer Systems Lab
Stanford University
sankar@cs.stanford.edu
--
Send compilers articles to compilers@esegue.segue.boston.ma.us
{ima | spdcc | world}!esegue. Meta-mail to compilers-request@esegue.piet@cs.ruu.nl (Piet van Oostrum) (10/29/90)
>>>>> In article <1990Oct26.213044.28243@Neon.Stanford.EDU>, sankar@Neon.Stanford.EDU (Sriram Sankar) (SS) writes:
SS> Since PASCAL has a rule that dangling else's associate with the
SS> innermost 'if', it seems obvious to me that PASCAL (at least wrt to the
SS> if statement) is LR. If the dangling else was associated with the
SS> outermost 'if' you can still make the necessary S/R decisions, so I do
SS> think (not looked at it carefully enough though) that this too is LR.
It is even very easy to rewrite the grammar to be LR(1). Someone did that a
few postings ago. See also the dragon book [1], p. 175
The dragon book also states that it is impossible to change the
if-then-else grammar to an equivalent one that is LL(1) (page 192). I have
not seen a proof of this, so I accept this by faith.
[1] Aho, Sethi and Ullman, Compilers, Principles, Techniques and Tools,
Addison-Wesley.
--
Piet* van Oostrum, Dept of Computer Science, Utrecht University,
Padualaan 14, P.O. Box 80.089, 3508 TB Utrecht, The Netherlands.
Telephone: +31 30 531806 Uucp: uunet!mcsun!ruuinf!piet
Telefax: +31 30 513791 Internet: piet@cs.ruu.nl (*`Pete')
--
Send compilers articles to compilers@esegue.segue.boston.ma.us
{ima | spdcc | world}!esegue. Meta-mail to compilers-request@esegue.