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

In article <9094@fy.sei.cmu.edu> firth@sei.cmu.edu I wrote:


[ The Pascal form 'if c then else s' ]


>But that is not legal Pascal. The relevant syntax (Wirth, section 9.2.2.1)
>reads
> <if-statement> ::= IF <expression> THEN <statement> |
> IF <expression> THEN <statement> ELSE <statement>
>
>and there is no production from <statement> that yields <empty>.


I was wrong. The above is indeed what Wirth's original paper says,
and what I used when implementing Pascal. But in the later book by
Jensen and Wirth, an extra production is added


<simple-statement> ::= ... | <empty-statement>


by means of which one can indeed produce <empty> from <statement>.
Since this book is by the original designer and of later date, we
should take it as superseding the older paper. Many thanks to
Bob Corbett for setting me straight on this point.


So, given that we do have empty statements, how nasty are they?
There is a simple mechanical test: list all the tokens that can
start a statement, then all the tokens that can follow a statement,
and if the sets overlap we are screwed, since any token in the
intersection might EITHER start a statement OR start a different
nonterminal after an empty statement.


The tokens that can start a statement are


GOTO BEGIN IF CASE WHILE REPEAT FOR WITH


and in addition, note that a label or case label can start with




The tokens that can follow a statement are


semicolon
END ELSE UNTIL


The intersection is null, so we can always identify an empty statement
by a one-token lookahead.


On another topic: while scrabbling through the listings I came across
a genuine and forgotten nasty. Consider this fragment


CASE fruit OF
apple: pear


This can continue as, for instance


apple: pear: x := 1;


or as


apple: pear := 1;


In other words, you cannot tell whether 'pear' starts another case
label or the statement labelled. That may discombobulate a parser
generator, especially since one or more comments may appear between
the identifier and the next token.


Again, hope that helps, and my apologies for regurgitating obsolete
information.
[Norm Diamond <diamond@tkov50.enet.dec.com>, Charles E Eaker
<eaker@sungod.crd.ge.com>, and Jon Mauney <mauney@csc.ncsu.edu> also noted
that Pascal does indeed allow null statements. -John]
--

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