Re: LL(1) grammar for regex

Sylvain Schmitz <schmitz@i3s.unice.fr>
27 Mar 2006 01:18:30 -0500

          From comp.compilers

Related articles
LL(1) grammar for regex not@www-no.ucsd.edu (James Brown \[MVP\]) (2006-03-22)
Re: LL(1) grammar for regex schmitz@i3s.unice.fr (Sylvain Schmitz) (2006-03-27)
Re: LL(1) grammar for regex cfc@shell01.TheWorld.com (Chris F Clark) (2006-03-27)
| List of all articles for this month |

From: Sylvain Schmitz <schmitz@i3s.unice.fr>
Newsgroups: comp.compilers
Date: 27 Mar 2006 01:18:30 -0500
Organization: Compilers Central
References: 06-03-074
Keywords: lex
Posted-Date: 27 Mar 2006 01:18:30 EST

James Brown [MVP] wrote:
  > I briefly tried to describe concatenation as:
  >
  > concat ::= rep concat
  > | rep
  >
  > node *concat()
  > {
  > node *left = rep();
  >
  > if(ch) // note I don't test for '.'
  > {
  > node *right = concat();
  > return new node(CONCAT, 0, left, right);
  > }
  >
  > return left;
  > }


It seems like what you are missing is a means to stop the recursion.
The idea is that you should test whether `ch' is a valid first symbol in
the derivation of `concat', i.e. whether `ch' belongs to
`Firsts(concat)'. If not, you should not call `concat ()'.


Now for a solution: you can rewrite your grammar rule as


          concat ::= rep+


which translates as


          node *
          concat ()
          {
              node *ret = rep ();


              /* while `ch' is in the Firsts set of `rep' */
              while (isalnum (ch) || ch == '(')
                  {
                      ret = new node (CONCAT, 0, ret, rep ());
                  }


              return ret;
          }


--
Hope that helps,


      Sylvain



Post a followup to this message

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