Re: Minding my Ps and Qs

Torben Mogensen <>
16 Feb 1999 23:20:01 -0500

          From comp.compilers

Related articles
Minding my Ps and Qs (Peter R. Wilson) (1999-02-15)
Re: Minding my Ps and Qs (Torben Mogensen) (1999-02-16)
Re: Minding my Ps and Qs (JPA) (1999-02-21)
| List of all articles for this month |

From: Torben Mogensen <>
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 (

Post a followup to this message

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