Path: utzoo!attcan!uunet!decwrl!sun-barr!olivea!mintaka!spdcc!esegue!compilers-sender
From: sankar@Neon.Stanford.EDU (Sriram Sankar)
Newsgroups: comp.compilers
Subject: Re. Is PASCAL LL/LR
Keywords: Pascal, parse, LL(1)
Message-ID: <1990Oct26.213044.28243@Neon.Stanford.EDU>
Date: 26 Oct 90 21:30:44 GMT
Sender: compilers-sender@esegue.segue.boston.ma.us
Reply-To: sankar@Neon.Stanford.EDU (Sriram Sankar)
Organization: Computer Science Department, Stanford University
Lines: 40
Approved: compilers@esegue.segue.boston.ma.us

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.