Home > Archive > Compilers > February 2006 > followpos for '?' and '+' operators
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
followpos for '?' and '+' operators
|
|
| Meeta Gupta 2006-01-31, 7:07 pm |
| Hi,
I'm Writing A Program(In C) To Convert Regular
Expressions To DFA's(Directly Without Going Through
Intermediate NFA's) And I'M Following The Procedure
Given In The Dragon Book(Compilers:Principles,
Techniques And Tools). I've Been Able To Handle Cases
For |,.,* Oprators 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.
Meeta Gupta
Student
| |
| Clint Olsen 2006-01-31, 7:07 pm |
| 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
| |
| jburgy 2006-02-01, 3:58 am |
| Clint Olsen wrote:
> On 2006-01-31, Meeta Gupta <meeta.gupta@yahoo.com> wrote:
>
> 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
| |
| Ralph Boland 2006-02-02, 7:07 pm |
| jburgy wrote:
> Clint Olsen wrote:
>
> 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
|
|
|
|
|