Re: Regular expression grammar?

Bruce Ediger <bediger@teal.csn.net> wrote:


> Dr Dobb's Journal, April 1999 carried an article by Brian Kernighan
> and Rob Pike titled "Regular Expressions". I read the article, and
> I was struck by the beginning sentences of the second-to-last paragraph:


> 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.
    The following is a grammar of your regular expressions:
%token SYMBOL OR STAR LPAREN RPAREN
%%
regexp : term
                                | regexp OR term
                                ;
term : factor
                                | term factor
                                ;
factor : primary
                                | factor STAR
                                ;
primary : SYMBOL
                                | LPAREN regexp RPAREN
                                ;
%%
this produces no shif or reduce conflicts and has normal predence of
STAR before concatenation before alternation.

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