Need help on making the recursive parser using pyparsing

Question

I am trying the python pyparsing for parsing. I got stuck up while making the recursive parser.

Let me explain the problem

I want to make the Cartesian product of the elements. The syntax is

cross({elements },{element})

I put in more specific way

cross({a},{c1}) or cross({a,b},{c1}) or cross({a,b,c,d},{c1}) or

So the general form is first group will have n elements (a,b,c,d). The second group will have one element that so the final output will be Cartesian Product.

The syntax is to be made recursive because it can go to n level like

cross(cross({a,b},{c1}),{c2})

This means cross a,b with c1. Lets say outcome us y. We again cross y it with c2

This can be till n level cross(cross(cross(cross......

What i want is to have object to be initialized using setparseAction

So i will have 2 class

class object1(object):
     This will be used by a,b,c,d 

class object2(object):
       This will hold cross elements

I need help on this i am not able to make the recursive parser.

Answer 1

You should look at definitions of other languages to see how this is usually handled.

For example, look at how multiplication is defined.

It isn't

{expression} * {expression}

Because the recursion is hard to deal with, and there's no implied left-to-right ordering. What you see more often are things like

{term} + {factor}
{factor} * {unary-expression}

Which puts priorities and a left-to-right ordering around the operators.

Look at something like http://www.cs.man.ac.uk/~pjj/bnf/c_syntax.bnf for examples of how things like this are commonly structured.

Answer 2

I agree with @S.Lott you should reconsider your grammar.

Recursive definitions can be introduced using Forward():

from pyparsing import (Literal, Word, OneOrMore, Forward, nums, alphas)

def BNF():
    """
    element      :: id
    elements     :: '{' element [ ',' element ]+ '}' 
                  | 'cross' '(' elements ',' '{' element '}' ')'
    """
    lcb, rcb, lb, rb, comma = [Literal(c).suppress() for c in '{}(),']
    element  = Word(alphas, alphas+nums+"_") # id
    elements = Forward()
    elements << ((lcb + element + OneOrMore(comma + element) + rcb) 
                 | (Literal('cross') + lb + elements + comma
                    + lcb + element + rcb + rb))
    return elements

print BNF().parseString("cross(cross({a,b},{c1}),{c2})")

Output:

['cross', 'cross', 'a', 'b', 'c1', 'c2']

Answer 3

I don't know if this is any help, but here is how you would do what you want in lepl. Since the grammar appears to be correct I assume that it would be easy to translate to pyparsing.

from lepl import *

def compile_parser():

    class Cross(Node): pass

    word = Token('[a-z0-9]+')
    par, en, bra, ket = [~Token('\\'+c) for c in '(){}']
    comma = ~Token(',')

    cross  = Delayed()
    vector = bra & word[1:,comma] & ket                 > list
    arg    = vector | cross
    cross += ~word('cross') & par & arg[2,comma] & en   > Cross

    parser = cross.string_parser()
    return lambda expr: parser(expr)[0]


if __name__ == '__main__':

    parser = compile_parser()
    print parser('cross({a},{c1})')
    print parser('cross({a,b},{c1})')
    print parser('cross({a,b,c,d},{c1})')
    print parser('cross(cross({a,b},{c1}),{c2})')

The output is:

Cross
 +- [u'a']
 `- [u'c1']

Cross
 +- [u'a', u'b']
 `- [u'c1']

Cross
 +- [u'a', u'b', u'c', u'd']
 `- [u'c1']

Cross
 +- Cross
 |   +- [u'a', u'b']
 |   `- [u'c1']
 `- [u'c2']