Infinite recursion caused by multiple occurrences of a parsing item YACC-PLY

Question

I'm dealing with a Yacc (the ply one) and I have no idea how to make more occurrences of a parsing item without making the program crashing due to infinite recursion. Let's say I have:

def p_Attribute(p):
    ''' Attribute : STRING
                  | NUMBER 
                  | Attribute
                  | empty '''
[do stuff] 

NOTE: The question is similar to: Python PLY zero or more occurrences of a parsing item but the solution proposed there is not working, I always have infinite recursion.

Answer 1

The problem here is actually in your grammar. Yacc-like parsers don't work with this kind of rule as it requires reducing an Attribute to reduce an Attribute, hence the infinite recursion. (Edit to add note: it would be OK if the right hand Attribute had some non-empty non-ambiguous token required, e.g., Attribute : STRING | NUMBER | '$' Attribute | empty is parseable and allows any number of $ signs in front of the other acceptable Attributes. But as it is, both alternatives, Attribute and empty, can be completely empty. That's a reduce/reduce conflict and it resolves badly here. I think the reduce/reduce conflict might resolve "as desired" if you put the empty rule first—but that's still the "wrong way" to do this, in general.)

Presumably you want one of three things (but I'm not sure which, so imagine the parser generator's confusion :-) ):

• zero or more Attributes in sequence (equivalent to regexp-like "x*")
• one or more Attributes in sequence (equivalent to regexp-like "x+")
• zero or one Attribute, but no more (equivalent to regexp-like "x?")

For all three of these you should, in general, start by defining a single non-terminal that recognizes exactly one valid attribute-like-thing, e.g.:

Exactly_One_Attribute : STRING | NUMBER

(which I'm going to just spell Attribute below).

Then you define a rule that accepts what you intend to allow for your sequence (or optional-attribute). For instance:

Zero_Or_More_Attributes : Zero_Or_More_Attributes Attribute | empty

(This uses "left recursion", which should be the most efficient. Use right recursion—see below—only if you really want to recognize items in the other order.)

To require at least one attribute:

One_Or_More_Attributes: One_Or_More_Attributes Attribute | Attribute

(also left-recursive in this example), or:

Attribute_opt : empty | Attribute

which allows either "nothing" (empty) or exactly one attribute.

---

The right-recursive version is simply:

Zero_Or_More_Attributes : Attribute Zero_Or_More_Attributes | empty

As a general rule, when using right recursion, the parser winds up having to "shift" (push onto its parse stack) more tokens. Eventually the parser comes across a token that fails to fit the rule (in this case, something not a STRING or NUMBER) and then it can begin reducing each shifted token using the right-recursive rule, working on the STRING-and-NUMBERs right to left. Using left recursion, it gets to do reductions earlier, working left to right. See http://www.gnu.org/software/bison/manual/html_node/Algorithm.html#Algorithm for more.