Parsing a tree of groups with PLY Yacc

Question

The structure I'm trying to parse looks like so:

group "a" [
    group "b" [
      group "c" [
      ]
    ]
    group "d" [
    ]
]

and the grammar:

def p_group(p):
    '''group : GROUP string subgroups'''
    p[0] = DNAGroup(p[2])
    for sgroup in p[3]:
        print p[0].getName(), "subgroup ", sgroup.getName()
        p[0].add(sgroup)
        sgroup.setParent(p[0])

def p_subgroups(p):
    '''subgroups : "[" group
                    | subgroups group
                    | subgroups "]"
                    | "[" "]"'''
    if p[0] is None:
        p[0] = []
    if p[2] != ']':
        p[0] += [p[2]]

Each parent has a list of children groups, and each child has a reference to it's parent. I can't seem to get the grammar to go without shift/reduce conflicts and it's not parsing correctly.

Answer 1

The problem lies in the definition of subgroups: in the subgroup state, the token GROUP can result in either shifting or reducing (shift taking this as a new group to parse, reduce recognizing subgroups-handled-so-far and leaving GROUP to be rescanned to make a new group), and the token ']' can also result in shifting or reducing (similar reasoning).

I think your intent is such that you can rewrite this as:

subgroups : "[" sublist_opt "]"

with:

sublist_opt : group sublist_opt
            | empty

(I leave you to fill in the python code for this grammar fragment).