Search code examples
flex-lexerlex

flex recursion definitions cause flex scanner push-back overflow

I am very new to flex and I don't know how to handle a recursion definitions. When i try to do this:

C   A|BA|A{C}|BA{C}

It show me that

flex scanner push-back overflow

I have no idea why this is happening. I think it should work to match all [BABAA][AAABAABA] etc. The end point BA and A without {C} is already defined. What is the correct way to rewrite the definitions in order to solve this error. I am so confused now. Thank you.

Solution

  • Flex definitions are macros, nothing more. Unlike the C preprocessor, Flex doesn't detect or suppress recursive expansion, and there are no conditionals, so a self-referencing macro will inevitably overflow the input buffer. (Flex expands macros by pushing the replacement string back into the input buffer. Unlike lex, it surrounds the replacement text with parentheses in order to provide a modicum of hygiene.)

    Basically, flex patterns are really regular expressions (in the mathematical sense) and can only match regular languages. That is normally enough for recognising tokens, which is the expected use case. Anything more complicated should be handled with a parser.

    In this case, where the recursion is at the end of the pattern, you could just use a repetition operator, such as (B?A)+.