3

I'm reading Compilers: Principles, Techniques, and Tools and don't understand this:

In addition, if it is necessary to retract the forward pointer one position (i.e., the lexeme does not include the symbol that got us to the accepting state), then we shall additionally place a * near that accepting state. In our example, it is never necessary to retract forward by more than one position, but if it were, we could attach any number of *'s to the accepting state.

That all makes sense, but I don't understand the significance of the asterisk. The book was just using it in regular expressions (Kleene star/closure), is it being used to represent something else, or still Kleene star?

Pubby
  • 51,882
  • 13
  • 139
  • 180

2 Answers2

3

No, it's not the Kleene star, the text explains it, it says essentially to put back the last token because that character is not part of the accepted characters. If you consider for example just a <, then you read two characters in the RE, but you don't actually want to read the 2nd one, so you put it back so that any subsequent read will find it first.

Generally in a complete FSM (finite state machine), you would not have this situation as it would deal with the complete lexical syntax, but since they are showing just a part of a syntax they need to use this device. In this example, the "other" arc would go to another states (as more arcs).

Francis Upton IV
  • 19,322
  • 3
  • 53
  • 57
0

for the retraction part -> consider x<y, here y is the "other" we are talking about. after reading "x<y", we need to put y back to the buffer since it maybe of any requirement for next lexeme processing. This "putting back to the buffer" is referred as retracting

Somal Chakraborty
  • 31
  • 5