Following up on this finally On 06/08/12 20:41, no-re...@cfengine.com wrote: > Forum: CFEngine Help > Subject: Re: CFEngine Help: memory exhausted error > Author: passerby > Link to topic: https://cfengine.com/forum/read.php?3,26355,26914#msg-26914 > > You've been using right recursion in your bison rules. > This uses up bison's stack of tokens if you're parsing long lists. > Solution: rewrite the offending rule(s) using left recursion. Then your list > can be as long as you like. > > I've been bitten by this in a project of mine; using right recursion bison > ran out of stack; using left recursion bison parsed a few million tokens in > the blink of an eye. > > From the manual: > > > 3.4 Recursive Rules > =================== > > A rule is called "recursive" when its RESULT nonterminal appears also > on its right hand side. Nearly all Bison grammars need to use > recursion, because that is the only way to define a sequence of any > number of a particular thing. Consider this recursive definition of a > comma-separated sequence of one or more expressions: > > expseq1: exp > | expseq1 ',' exp > ; > > Since the recursive use of `expseq1' is the leftmost symbol in the > right hand side, we call this "left recursion". By contrast, here the > same construct is defined using "right recursion": > > expseq1: exp > | exp ',' expseq1 > ; > > Any kind of sequence can be defined using either left recursion or right > recursion, but you should always use left recursion, because it can > parse a sequence of any number of elements with bounded stack space. > Right recursion uses up space on the Bison stack in proportion to the > number of elements in the sequence, because all the elements must be > shifted onto the stack before the rule can be applied even once. > The Bison Parser Algorithm Algorithm, for further explanation of this. > > "Indirect" or "mutual" recursion occurs when the result of the rule > does not appear directly on its right hand side, but does appear in > rules for other nonterminals which do appear on its right hand side. > > For example: > > expr: primary > | primary '+' primary > ; > > primary: constant > | '(' expr ')' > ; > > defines two mutually-recursive nonterminals, since each refers to the > other. > > _______________________________________________ > Help-cfengine mailing list > Help-cfengine@cfengine.org > https://cfengine.org/mailman/listinfo/help-cfengine
-- CTO and Founder CFEngine http://www.cfengine.com http://www.markburgess.org Twitter: @markburgess_osl, @CFEngine_news _______________________________________________ Help-cfengine mailing list Help-cfengine@cfengine.org https://cfengine.org/mailman/listinfo/help-cfengine
