grammar.py

def follow_chunk(c):
    while c is not None:
        yield c
        c=c.next

def print_chunk_tree(base,tc=''):
    for c in follow_chunk(base):
        def display_chunk(chunk,tc):
            print(tc,end='')
            print(chunk)
            if isinstance(chunk,GroupChunk):
                for sub_chunk in follow_chunk(chunk.sub_chunk):
                    print_chunk_tree(sub_chunk,tc+'-'*2)
            if chunk.alt is not None:
                print(tc,end='')
                print("Alternate:")
                print_chunk_tree(chunk.alt,tc+'^'*4)
        display_chunk(c,tc)

def extract_open_close(s,o,c):
    oc,cc,i,s=1,0,1,s[s.find(o):]
    while oc != cc:
        if s[i]=='\\':i+=1
        elif s[i]==o and o!=c:oc+=1
        elif s[i]==c:cc+=1
        i+=1
    return (s[i:] if len(s)>i else ""),s[1:i-1]

class ChunkParseError(Exception):pass

class Chunk:
    prefix = "chunk"
    def __init__(self,dat):
        self.dat=dat.strip()
        self.next=None
        self.alt=None
        self.name="???"
    def parse(self,text):
        d,s=self(text)
        return self.name,d,(self.next.parse(s) if self.next else s)
    def __call__(self,s):
        try:
            return self.apply(s)
        except ChunkParseError as e:
            if self.alt is not None:
                return self.alt(s)
            else:
                raise e
    def apply(self,text):return None,text
    def __str__(self):return self.prefix+":"+self.dat

class ExternalChunk(Chunk):
    external_mappings={}
    prefix="identifier"
    def __init__(self,grammar,v):
        super().__init__(v)
        self.grammar=grammar
    def apply(self,s):
        ct=self.grammar.rules.get(self.dat,None)
        if ct is None:raise ChunkParseError()
        return ct.apply(s)

class LiteralChunk(Chunk):
    prefix='literal'
    def apply(self,s):
        s=s.strip()
        if s[:len(self.dat)]==self.dat:
            return s[:len(self.dat)],s[len(self.dat):]
        raise ChunkParseError()

class GroupChunk(Chunk):
    prefix='group'
    def __init__(self,v,sub_chunk):
        super().__init__(v)
        self.sub_chunk = sub_chunk
    def apply(self,s):
        if self.sub_chunk is None:
            raise ChunkParseError()
        return self.sub_chunk.parse(s)

class OptionalChunk(GroupChunk):
    prefix='optional'

class RepeatedChunk(OptionalChunk):
    prefix='repeated'

class Grammar:
    r'''
        number: "\d+" | number_calculation;
        @bool: "true" | "false" | bool_calculation | compare_calculation;
        string: "\"([^\"\\\\]*(?:\\.[^\"\\\\]*)*)\"" | string_calculation;
        number_calculation: number, ("\\+"|"\\-"|"\\/"|"\\*"), number;
        bool_calculation: bool, ("\\|"|"&"), bool;
        compare_calculation: number, ("([<>]\\=?)"|"([\\!\\=])="), number;
    '''
    default_rules = {}
    def __init__(self,gramstr=None,**rules):
        self.rules=dict(self.default_rules.items())
        self.rules.update(rules)
        if isinstance(gramstr,Chunk):self.head=gramstr
        else:
            rrules,self.head=self.parse_grammar(gramstr or self.__doc__)
            self.rules.update(rrules)

    def parse_grammar(self,s):
        def process_rule(rule):
            name=rule[:rule.find(":")].strip()
            rule=rule[rule.find(":")+1:].strip()
            return rule,name
        rules=[process_rule(r.strip()) for r in s.split(";") if len(r.strip())>0]
        def extract_rhs(s):
            f,l=None,None
            def append_to_chain(chunk,ff,ll):
                if ff is None:return chunk,chunk
                else:
                    ll.next=chunk
                    return ff,chunk
            while len(s)>0:
                if s[0]=='"':
                    end=1
                    while end<len(s) and s[end]!='"':
                        if s[end]=="\\":
                            s=s[:end]+s[end+1:]
                        end+=1
                    c,s=s[1:end],s[end+1:]
                    f,l=append_to_chain(LiteralChunk(c),f,l)
                elif s[0]=='[':
                    s,c = extract_open_close(s,'[',']')
                    sc,a=extract_rhs(c)
                    f,l=append_to_chain(OptionalChunk(c,sc),f,l)
                elif s[0]=='(':
                    s,c = extract_open_close(s,'(',')')
                    sc,a=extract_rhs(c)
                    f,l=append_to_chain(GroupChunk(c,sc),f,l)
                elif s[0]=='{':
                    s,c = extract_open_close(s,'{','}')
                    sc,a=extract_rhs(c)
                    f,l=append_to_chain(RepeatedChunk(c,sc),f,l)
                elif s[0]==',' and f is not None:
                    c,s=extract_rhs(s[1:])
                    f,l=append_to_chain(c,f,l)
                elif s[0]=='|' and f is not None:
                    c,s=extract_rhs(s[1:])
                    f.alt=c
                elif len(s)>len(s.strip()):
                    s=s.strip()
                else:
                    i=0
                    while i<len(s) and (s[i].isalpha() or s[i]=='_') :i+=1
                    name,s=s[:i+1],s[i+1:]
                    f,l=append_to_chain(ExternalChunk(self,name),f,l)
            return f,s.strip()
        rules = {r[1]:extract_rhs(r[0])[0] for r in rules}
        h,c=Chunk("Default Head"),0
        for name, chunk in list(rules.items()):
            oname=name
            while name[0]=='@': name = name[1:]
            chunk.name=name
            if oname!=name:
                if h.next is None:h.next=chunk
                else:
                    c+=1
                    s,b=h,Chunk("Alternate Head "+str(c))
                    b.sub=chunk
                    while s.alt is not None:s=s.alt
                    s.alt=b
                del rules[oname]
                rules[name]=chunk
        return rules,h

g=Grammar()
print_chunk_tree(g.head,' ')

d=g.head.parse("false")
print(d)