Re: followpos for '?' and '+' operators

jburgy wrote:
> Clint Olsen wrote:
> > On 2006-01-31, Meeta Gupta <meeta.gupta@yahoo.com> wrote:
> > > But How Can I Calculate The Followpos For '?' And '+' Operators? How
> > > Should I Handle These Operators When I Build The Syntax Tree For A
> > > Regular Expression.
> >
> > Since you already know the rules for the '*', '.' and '|' operators, you
> > can intuitively figure out how to do it for '+' and '?'. Hint: You can
> > rewrite the syntax tree for '?' and '+' using the operators you already
> > know. So, '+' is the same as '{re}*' and so on...
> >
> > -Clint
>
> Uh, have you considered searching through the archives?
>
> http://compilers.iecc.com/comparch/article/98-08-139


I hope this is not homework.


Check the rules on page 138 of the red dragon book.
First you need rules for firstPos, lastPos, and nullable.


The rules for A+ are like those for A* except A+ is nullable only if A
is. This can be shown by applying the rules to the equation AA*.


The rules for A? are like those for A*.
This can be shown by applying the rules to the equation A | epsilon.




Now for computing followPos.
The rule for A+ is like the rule for A*.
There is no rule for A?; none is needed since the situation is
completely handled the the other rules.
This can be shown by computing the applying the rules for followPos
to the expression A | epsilon. Note that, since there is no rule for
the '|' operator, there is no rule for the '?' operator either.


Hope this helps.


Ralph Boland

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