Re: LL(1) grammar for regex

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

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