Re: Regular expression grammar?

"J.H.Jongejan" <jjan@cs.rug.nl>
20 Sep 1999 11:59:33 -0400

          From comp.compilers

Related articles
Regular expression grammar? bediger@teal.csn.net (Bruce Ediger) (1999-09-16)
Re: Regular expression grammar? jjan@cs.rug.nl (J.H.Jongejan) (1999-09-20)
Re: Regular expression grammar? terryg@uswest.net (1999-09-20)
Re: Regular expression grammar? lex@cc.gatech.edu (1999-09-20)
Re: Regular expression grammar? cbarron3@ix.netcom.com (1999-09-20)
Re: Regular expression grammar? zalman@netcom18.netcom.com (Zalman Stern) (1999-09-24)
Re: Regular expression grammar? zalman@netcom18.netcom.com (Zalman Stern) (1999-09-24)
Re: Regular expression grammar? zalman@netcom18.netcom.com (Zalman Stern) (1999-09-24)
[1 later articles]
| List of all articles for this month |

From: "J.H.Jongejan" <jjan@cs.rug.nl>
Newsgroups: comp.compilers
Date: 20 Sep 1999 11:59:33 -0400
Organization: Groningen University (NL)
References: 99-09-051
Keywords: lex

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


Post a followup to this message

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