Fri, 26 Oct 90 21:30:44 GMT

Related articles |
---|

Re. Is PASCAL LL/LR sankar@Neon.Stanford.EDU (1990-10-26) |

Re: Re. Is PASCAL LL/LR piet@cs.ruu.nl (1990-10-29) |

Newsgroups: | comp.compilers |

From: | sankar@Neon.Stanford.EDU (Sriram Sankar) |

Keywords: | Pascal, parse, LL(1) |

Organization: | Computer Science Department, Stanford University |

Date: | Fri, 26 Oct 90 21:30:44 GMT |

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.