1 Feb 1998 21:41:13 -0500

Related articles |
---|

LL(2) always factorable to LL(1)? aduncan@cs.ucsb.edu (Andrew M. Duncan) (1998-01-17) |

Re: LL(2) always factorable to LL(1)? clark@quarry.zk3.dec.com (Chris Clark USG) (1998-01-20) |

Re: LL(2) always factorable to LL(1)? bill@amber.ssd.csd.harris.com (1998-01-21) |

Re: LL(2) always factorable to LL(1)? mickunas@cs.uiuc.edu (1998-01-23) |

Re: LL(2) always factorable to LL(1)? cfc@world.std.com (Chris F Clark) (1998-01-23) |

Re: LL(2) always factorable to LL(1)? parrt@magelang.com (Terence Parr) (1998-01-23) |

Re: LL(2) always factorable to LL(1)? thetick@magelang.com (Scott Stanchfield) (1998-01-24) |

Re: LL(2) always factorable to LL(1)? parrt@magelang.com (Terence Parr) (1998-02-01) |

From: | Terence Parr <parrt@magelang.com> |

Newsgroups: | comp.compilers,comp.compilers.tools.pccts |

Date: | 1 Feb 1998 21:41:13 -0500 |

Organization: | MageLang Insitute |

References: | 98-01-071 98-01-080 98-01-086 98-01-100 |

Keywords: | parse, LL(1) |

Scott Stanchfield hath spake:

Has anyone proven that the set of languages that can be represented by

a predicated LL(k) grammar is a proper subset of those that can be

represented in LR(k)?

Actually predicated-LL(k) is a superset of LR(k).

There are two augmentations of LL(k) to produce predicated LL(k)

grammars as I define them (from well-known techniques):

o arbitrary lookahead (backtracking): syntactic predicate.

o altering the parse according to semantic information: semantic predicate.

Both of these have been used for ages by folks building hand-built and

some automatic language tools.

Arbitrary lookahead for LR is stronger than LR(k) for any finite k if

you want a finite grammar. ;) LR(k+1) is stronger than LR(k) IF you

cannot rewrite the grammar, hence, lookahead can only help. OTOH, If

I remember correctly, the size of the LR(1) equivalent of an LR(k)

grammar has a k term in the size function, leading one to conclude

that the LR(1) grammar would be infinitely large for infinite k. Or,

perhaps more simply, LR(k)==LL(k) for grammars with actions in the

worst case and we know large lookhahead helps LL.

Showing semantics help is more obvious as it adds a whole new

dimension (that of context-sensitivity) to your parser. CFL are a

subset of the context- sensitive languages. People have overcome this

limitation by transforming context-sensitive constructs to

context-free grammars by having the lexer return context-sensitive

token streams, leaving the parser CF. Unfortunately, this trick gets

screwed up with k>1 lookahead, which we know leads to stronger parsers

(particularly with arbitrary lookahead). It is best to leave

semantics in the parser where they belong. I.e., it is best to use

type : {isType(LT(1))}? ID ;

rather than

type : TYPENAME ; //lexer calls isType() to distinguish ID,TYPENAME

Anyway, predicated-LL(k) parsers are much stronger than pure

LR(k) parsers.

Regards,

Terence

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.