16 Feb 1999 23:20:01 -0500

Related articles |
---|

Minding my Ps and Qs peter.r.wilson@boeing.com (Peter R. Wilson) (1999-02-15) |

Re: Minding my Ps and Qs torbenm@diku.dk (Torben Mogensen) (1999-02-16) |

Re: Minding my Ps and Qs paul.janssens@skynet.be (JPA) (1999-02-21) |

From: | Torben Mogensen <torbenm@diku.dk> |

Newsgroups: | comp.compilers |

Date: | 16 Feb 1999 23:20:01 -0500 |

Organization: | Compilers Central |

References: | 99-02-067 |

Keywords: | parse, LL(1) |

In comp.compilers you write:

*>I got stuck on a term in the grammar that was of the form:*

*>1 t = { P | Q } P .*

*>That is, sentences consisting of any number of P and/or Q, followed by*

*>P. This is LL(oo) as written.*

An LL(1) version of this can be obtained by left factoring. We first

eliminate the {} and |:

t -> P t

t -> Q t

t -> P

We then left factor and get

t -> P t'

t -> Q

t' -> t

t' ->

We can get this back in EBNF as

t -> P [t] | Q t

which is in LL(1) as required (assuming P and Q have disjoint FIRST

sets etc.)

Torben Mogensen (torbenm@diku.dk)

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.