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
[email protected]
https://cfengine.org/mailman/listinfo/help-cfengine
