2 Feb 2006 11:31:22 -0500

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) |

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.