Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!lll-winken!uunet!world!esegue!compilers-sender
From: lindsay@comp.vuw.ac.nz (Lindsay Groves)
Newsgroups: comp.compilers
Subject: Re: Can Pascal be parsed by LR(1) parsing algorithm?
Keywords: pascal, parse
Message-ID: <1990Oct16.015524.25858@comp.vuw.ac.nz>
Date: 16 Oct 90 01:55:24 GMT
References: <9010091533.AA02386@apple.com> <9010101445.AA06181@dynamo.ecn.purdue.edu>
Sender: compilers-sender@esegue.segue.boston.ma.us
Reply-To: lindsay@comp.vuw.ac.nz (Lindsay Groves)
Organization: Computer Science Dept, Victoria University, Wellington, NEW ZEALAND
Lines: 35
Approved: compilers@esegue.segue.boston.ma.us

In article <9010101445.AA06181@dynamo.ecn.purdue.edu>,
hankd@dynamo.ecn.purdue.edu (Hank Dietz) writes:
|> Pascal is generally defined using a set of syntax diagrams which, by
|> definition, means the language can be recognized using LL(1).

You must be using a strange definition a syntax diagrams if they can
only describe languages that have LL(1) grammars.

As I understand them, syntax diagrams can generate ALL context free
languages, not just those that are also LL(1); i.e. I can turn any
context free grammar into a set of syntax diagrams and vice versa.

For example, the following syntax diagram describes the language
consisting of all non-empty palindromes of even length over the alphabet
{a, b}.  This language is inherently ambiguous (ie cannot be recognised
by a deterministic PDA), so it is definitely not LL(1) (nor LL(k),
LR(k), ...):


        +-------------------------------+
        |                               ^
        v                               |
  S  ----------> a ---> a --------------+----->|
           |                         ^
           |---> b ---> b ---------->|
           |                         |
           |---> a ---> S ---> a --->|
           |                         |
           +---> b ---> S ---> b --->+


Lindsay
-- 
Send compilers articles to compilers@esegue.segue.boston.ma.us
{ima | spdcc | world}!esegue.  Meta-mail to compilers-request@esegue.