Re: Can Pascal be parsed by LR(1) parsing algorithm?

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
--

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