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

"Ralph Boland" <rpboland@gmail.com>
2 Feb 2006 11:31:22 -0500

          From comp.compilers

Related articles
followpos for '?' and '+' operators meeta.gupta@yahoo.com (Meeta Gupta) (2006-01-31)
Re: followpos for '?' and '+' operators clint@0lsen.net (Clint Olsen) (2006-01-31)
Re: followpos for '?' and '+' operators jburgy@gmail.com (jburgy) (2006-01-31)
Re: followpos for '?' and '+' operators rpboland@gmail.com (Ralph Boland) (2006-02-02)
| List of all articles for this month |

From: "Ralph Boland" <rpboland@gmail.com>
Newsgroups: comp.compilers
Date: 2 Feb 2006 11:31:22 -0500
Organization: http://groups.google.com
References: 06-01-13006-01-148
Keywords: lex, DFA

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


Post a followup to this message

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