Re: Regular expression grammar?

Bruce Ediger wrote:
<snipped part>
> Kelly defines regular languages like this (page 38):
>
> (a) The empty set is a regular language
> (b) The set containing the zero-length string is a regular language
> (c) The set containing every single character in the alphabet is regular
> (d) For two regular languages A and B, A | B, AB, A* are regular
> (e) No other languages are regular
>
> His notation for regular expressions follows directly, and seems
> pretty standard to me.
>
> My "yacc" grammar for regular expressions:
>
> --------
> %token SYMBOL OR STAR LPAREN RPAREN
> %%
> regexp
> : SYMBOL /* any letter of the alphabet (c) */
> | regexp OR regexp /* alternation (d) */
> | regexp regexp /* concatenation (d) */
> | regexp STAR /* Kleene Closure (d) */
> | RPAREN regexp LPAREN /* grouping */
> ;
> %%
> --------
> This gives a bunch of shift/reduce conflicts. I can't seem to get around
> them by putting in operator precedences, or the analogy of algebraic
> terms and factors.


I can give you an LL(1) grammar:


    E : T E'
    E': OR T E'
    E':
    T : F T'
    T': F T'
    T':
    F : P F'
    F': STAR
    P : SYMBOL
    P : EPSILON
    P : LPAR E RPAR


--
Jan Jongejan 8-{) --me with moustache
Dept. Comp.Sci.,
Univ. of Groningen,
Netherlands.
email: jjan@cs.rug.nl

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