Nesting delimited lists in pyparsing without causing infinite recursion?

operator-precedence, pyparsing, python

Solution

I believe your second approach with `operatorPrecedence` is the better way to go. However, you have a couple problems. One is that your keywords "and" and "or" are also Words by your definition. You should probably set it up like this:

and_tok = pyp.Keyword("and")
or_tok = pyp.Keyword("or")
Word = ~(and_tok | or_tok) + pyp.Word(pyp.alphas)("Word")

This will prevent "and" and "or" from being matched as Words.

Another problem is that you aren't setting up operatorPrecedence right. The first argument to it is supposed to be the "atom" expression --- the base element that can occur between operators. operatorPrecedence automatically sets up the necessary nesting. By passing in Phrase as the atom you're creating an additional level of nesting that will cause it to run amok. Instead, your first argument to operatorPrecedence should be Word (or `pyp.OneOrMore(Word)` if you want to allow multi-word operands).

In addition, operatorPrecedence will automatically handle the case of a single atom, so you don't need to have the `^ Word` business in there. This means you can dispense with `Phrase` and just have your `Expression` directly be the operatorPrecedence thing.

Putting that all together you get this:

Expression = (
    pyp.operatorPrecedence(pyp.OneOrMore(Word), [
        (and_tok, 2, pyp.opAssoc.LEFT),
        (or_tok, 2, pyp.opAssoc.LEFT)
    ])
)

The result is like this:

>>> test("Hello and Bob")

<ITEM>
  <ITEM>
    <Word>Hello</Word>
    <AND>and</AND>
    <Word>Bob</Word>
  </ITEM>
</ITEM>

>>> test("TestA and TestB and TestC or TestD")

<ITEM>
  <ITEM>
    <ITEM>
      <Word>TestA</Word>
      <AND>and</AND>
      <Word>TestB</Word>
      <AND>and</AND>
      <Word>TestC</Word>
    </ITEM>
    <OR>or</OR>
    <Word>TestD</Word>
  </ITEM>
</ITEM>

This isn't exactly the form you wanted, because the operands are inside the nested lists rather than wrapping them, but you should be able to reconfigure the structure using a `parseAction` (operatorrPrecedence lets you pass one in for each operand).

(Also, your original desired data for `test("TestA and TestB and TestC or TestD")` is inconsistent with your description. If you want "and" and "or" to have the same precedence, then this will bracket as `(TestA and TestB and TestC) or TestD`, as it does in the above example. If you want `(TestC or TestD)` to bracket together, you'd need to give "or" a higher precedence.)

Problem

I have the following toy grammar in Pyparsing: ``` import pyparsing as pp or_tok = "or" and_tok = "and" lparen = pp.Suppress("(") rparen = pp.Suppress(")") Word = pp.Word(pp.alphas)("Word") Phrase = pp.Forward() And_Phrase = pp.Group(pp.delimitedList(Phrase, and_tok))("And_Phrase") Or_Phrase = pp.Group(pp.delimitedList(Phrase, or_tok))("Or_Phrase") Phrase << (pp.Optional(lparen) + (And_Phrase ^ Or_Phrase) + pp.Optional(rparen)) ^ Word Expression = pp.OneOrMore(Word ^ Phrase)("Expression") def test(text): output = Expression.parseString(text) print output.asXML() ``` However, running this program will infinitely recurse, which isn't what I wanted. Rather, I wanted my grammar to be able to handle nested phrases so that the above program would resolve to something equivalent to the below: ``` >>> test("TestA and TestB and TestC or TestD") <Expression> <And_Phrase> <Word>TestA</Word> <Word>TestB</Word> <Or_Phrase> <Word>TestC</Word> <Word>TestD</Word> </Or_Phrase> </And_Phrase> </Expression> ``` I attempted to modify the definitions for `And_Phrase` and `Or_Phrase` so that they would match only lists that have two or more elements, but couldn't figure out how to do so. I also tried using `pyparsing.operatorPrecedence`, but I don't think I did it right: ``` import pyparsing as pp or_tok = "or" and_tok = "and" lparen = pp.Suppress("(") rparen = pp.Suppress(")") Word = pp.Word(pp.alphas)("Word") Phrase = pp.Forward() Phrase << Word ^ \ pp.operatorPrecedence(Phrase, [ (and_tok, 2, pp.opAssoc.LEFT), (or_tok, 2, pp.opAssoc.LEFT) ]) Expression = pp.OneOrMore(Word ^ Phrase)("Expression") def test(text): output = Expression.parseString(text) print output.asXML() ``` ...because it didn't yield a list at all: ``` >>> test("Hello world and bob") <Expression> <Word>Hello</Word> <Word>world</Word> <Word>and</Word> <Word>bob</Word> </Expression> ``` How can I modify my rule definitions so that they will handle nested lists?

Original source