parser for asdl 1 definition files reads in an asdl description and parses it into an ast that describes it the ebnf we re parsing here figure 1 of the paper 1 extended to support modules and attributes after a product words starting with capital letters are terminals literal tokens are in double quotes others are nonterminals id is either tokenid or constructorid module module id definitions definitions typeid type type product sum product fields attributes fields fields field field field typeid id sum constructor constructor attributes fields constructor constructorid fields 1 the zephyr abstract syntax description language by wang et al see http asdl sourceforge net the following classes define nodes into which the asdl description is parsed note this is a metaast asdl files such as python asdl describe the ast structure used by a programming language but asdl files themselves need to be parsed this module parses asdl files and uses a simple ast to represent them see the ebnf at the top of the file to understand the logical connection between the various node types a generic visitor for the metaast that describes asdl this can be used by emitters note that this visitor does not provide a generic visit method so a subclass needs to define visit methods from visitmodule to as deep as the interesting node we also define a check visitor that makes sure the parsed asdl is wellformed generic tree visitor for asts def initself self cache def visitself obj args klass obj class meth self cache getklass if meth is none methname visit klass name meth getattrself methname none self cacheklass meth if meth try methobj args except exception as e printerror visiting r s obj e raise class checkvisitorbase def initself supercheck self init self cons self errors 0 self types def visitmoduleself mod for dfn in mod dfns self visitdfn def visittypeself type self visittype value strtype name def visitsumself sum name for t in sum types self visitt name def visitconstructorself cons name key strcons name conflict self cons getkey if conflict is none self conskey name else print redefinition of constructor formatkey print defined in and formatconflict name self errors 1 for f in cons fields self visitf key def visitfieldself field name key strfield type l self types setdefaultkey l appendname def visitproductself prod name for f in prod fields self visitf name def checkmod v check v visitmod for t in v types if t not in mod types and not t in builtintypes v errors 1 uses joinv typest print undefined type used in formatt uses return not v errors the asdl parser itself comes next the only interesting external interface here is the toplevel parse function def parsefilename types for describing tokens in an asdl specification tokenkind is provides a scope for enumerated token kinds constructorid typeid equals comma question pipe asterisk lparen rparen lbrace rbrace range11 operatortable equals comma question pipe lparen rparen asterisk lbrace rbrace token namedtuple token kind value lineno class asdlsyntaxerrorexception def initself msg linenonone self msg msg self lineno lineno or unknown def strself return syntax error on line 0 lineno 0 msg formatself def tokenizeasdlbuf some kind of identifier comment operators parser for asdl files create then call the parse method on a buffer containing asdl this is a simple recursive descent parser that uses tokenizeasdl for the lexing parse the asdl in the buffer and return an ast with a module root if we see a it s a product otherwise it s a sum look for constructorid more constructors return the value of the current token and read the next one into self curtoken the match primitive of rd parsers verifies that the current token is of the given kind kind can be a tuple in which the kind must match one of its members returns the value of the current token reads in the next token parser for asdl 1 definition files reads in an asdl description and parses it into an ast that describes it the ebnf we re parsing here figure 1 of the paper 1 extended to support modules and attributes after a product words starting with capital letters are terminals literal tokens are in double quotes others are non terminals id is either tokenid or constructorid module module id definitions definitions typeid type type product sum product fields attributes fields fields field field field typeid id sum constructor constructor attributes fields constructor constructorid fields 1 the zephyr abstract syntax description language by wang et al see http asdl sourceforge net the following classes define nodes into which the asdl description is parsed note this is a meta ast asdl files such as python asdl describe the ast structure used by a programming language but asdl files themselves need to be parsed this module parses asdl files and uses a simple ast to represent them see the ebnf at the top of the file to understand the logical connection between the various node types a generic visitor for the meta ast that describes asdl this can be used by emitters note that this visitor does not provide a generic visit method so a subclass needs to define visit methods from visitmodule to as deep as the interesting node we also define a check visitor that makes sure the parsed asdl is well formed generic tree visitor for asts a visitor that checks a parsed asdl tree for correctness errors are printed and accumulated check the parsed asdl tree for correctness return true if success for failure the errors are printed out and false is returned the asdl parser itself comes next the only interesting external interface here is the top level parse function parse asdl from the given file and return a module node describing it types for describing tokens in an asdl specification tokenkind is provides a scope for enumerated token kinds tokenize the given buffer yield token objects some kind of identifier comment operators parser for asdl files create then call the parse method on a buffer containing asdl this is a simple recursive descent parser that uses tokenize_asdl for the lexing parse the asdl in the buffer and return an ast with a module root if we see a it s a product otherwise it s a sum look for constructorid more constructors return the value of the current token and read the next one into self cur_token the match primitive of rd parsers verifies that the current token is of the given kind kind can be a tuple in which the kind must match one of its members returns the value of the current token reads in the next token
from collections import namedtuple
import re

__all__ = [
    'builtin_types', 'parse', 'AST', 'Module', 'Type', 'Constructor',
    'Field', 'Sum', 'Product', 'VisitorBase', 'Check', 'check']








builtin_types = {'identifier', 'string', 'int', 'constant'}

class AST:
    def __repr__(self):
        raise NotImplementedError

class Module(AST):
    def __init__(self, name, dfns):
        self.name = name
        self.dfns = dfns
        self.types = {type.name: type.value for type in dfns}

    def __repr__(self):
        return 'Module({0.name}, {0.dfns})'.format(self)

class Type(AST):
    def __init__(self, name, value):
        self.name = name
        self.value = value

    def __repr__(self):
        return 'Type({0.name}, {0.value})'.format(self)

class Constructor(AST):
    def __init__(self, name, fields=None):
        self.name = name
        self.fields = fields or []

    def __repr__(self):
        return 'Constructor({0.name}, {0.fields})'.format(self)

class Field(AST):
    def __init__(self, type, name=None, seq=False, opt=False):
        self.type = type
        self.name = name
        self.seq = seq
        self.opt = opt

    def __str__(self):
        if self.seq:
            extra = "*"
        elif self.opt:
            extra = "?"
        else:
            extra = ""

        return "{}{} {}".format(self.type, extra, self.name)

    def __repr__(self):
        if self.seq:
            extra = ", seq=True"
        elif self.opt:
            extra = ", opt=True"
        else:
            extra = ""
        if self.name is None:
            return 'Field({0.type}{1})'.format(self, extra)
        else:
            return 'Field({0.type}, {0.name}{1})'.format(self, extra)

class Sum(AST):
    def __init__(self, types, attributes=None):
        self.types = types
        self.attributes = attributes or []

    def __repr__(self):
        if self.attributes:
            return 'Sum({0.types}, {0.attributes})'.format(self)
        else:
            return 'Sum({0.types})'.format(self)

class Product(AST):
    def __init__(self, fields, attributes=None):
        self.fields = fields
        self.attributes = attributes or []

    def __repr__(self):
        if self.attributes:
            return 'Product({0.fields}, {0.attributes})'.format(self)
        else:
            return 'Product({0.fields})'.format(self)







class VisitorBase(object):
    
    def __init__(self):
        self.cache = {}

    def visit(self, obj, *args):
        klass = obj.__class__
        meth = self.cache.get(klass)
        if meth is None:
            methname = "visit" + klass.__name__
            meth = getattr(self, methname, None)
            self.cache[klass] = meth
        if meth:
            try:
                meth(obj, *args)
            except Exception as e:
                print("Error visiting %r: %s" % (obj, e))
                raise

class Check(VisitorBase):
    
    def __init__(self):
        super(Check, self).__init__()
        self.cons = {}
        self.errors = 0
        self.types = {}

    def visitModule(self, mod):
        for dfn in mod.dfns:
            self.visit(dfn)

    def visitType(self, type):
        self.visit(type.value, str(type.name))

    def visitSum(self, sum, name):
        for t in sum.types:
            self.visit(t, name)

    def visitConstructor(self, cons, name):
        key = str(cons.name)
        conflict = self.cons.get(key)
        if conflict is None:
            self.cons[key] = name
        else:
            print('Redefinition of constructor {}'.format(key))
            print('Defined in {} and {}'.format(conflict, name))
            self.errors += 1
        for f in cons.fields:
            self.visit(f, key)

    def visitField(self, field, name):
        key = str(field.type)
        l = self.types.setdefault(key, [])
        l.append(name)

    def visitProduct(self, prod, name):
        for f in prod.fields:
            self.visit(f, name)

def check(mod):
    
    v = Check()
    v.visit(mod)

    for t in v.types:
        if t not in mod.types and not t in builtin_types:
            v.errors += 1
            uses = ", ".join(v.types[t])
            print('Undefined type {}, used in {}'.format(t, uses))
    return not v.errors




def parse(filename):
    
    with open(filename, encoding="utf-8") as f:
        parser = ASDLParser()
        return parser.parse(f.read())


class TokenKind:
    
    (ConstructorId, TypeId, Equals, Comma, Question, Pipe, Asterisk,
     LParen, RParen, LBrace, RBrace) = range(11)

    operator_table = {
        '=': Equals, ',': Comma,    '?': Question, '|': Pipe,    '(': LParen,
        ')': RParen, '*': Asterisk, '{': LBrace,   '}': RBrace}

Token = namedtuple('Token', 'kind value lineno')

class ASDLSyntaxError(Exception):
    def __init__(self, msg, lineno=None):
        self.msg = msg
        self.lineno = lineno or '<unknown>'

    def __str__(self):
        return 'Syntax error on line {0.lineno}: {0.msg}'.format(self)

def tokenize_asdl(buf):
    
    for lineno, line in enumerate(buf.splitlines(), 1):
        for m in re.finditer(r'\s*(\w+|--.*|.)', line.strip()):
            c = m.group(1)
            if c[0].isalpha():
                
                if c[0].isupper():
                    yield Token(TokenKind.ConstructorId, c, lineno)
                else:
                    yield Token(TokenKind.TypeId, c, lineno)
            elif c[:2] == '--':
                
                break
            else:
                
                try:
                    op_kind = TokenKind.operator_table[c]
                except KeyError:
                    raise ASDLSyntaxError('Invalid operator %s' % c, lineno)
                yield Token(op_kind, c, lineno)

class ASDLParser:
    
    def __init__(self):
        self._tokenizer = None
        self.cur_token = None

    def parse(self, buf):
        
        self._tokenizer = tokenize_asdl(buf)
        self._advance()
        return self._parse_module()

    def _parse_module(self):
        if self._at_keyword('module'):
            self._advance()
        else:
            raise ASDLSyntaxError(
                'Expected "module" (found {})'.format(self.cur_token.value),
                self.cur_token.lineno)
        name = self._match(self._id_kinds)
        self._match(TokenKind.LBrace)
        defs = self._parse_definitions()
        self._match(TokenKind.RBrace)
        return Module(name, defs)

    def _parse_definitions(self):
        defs = []
        while self.cur_token.kind == TokenKind.TypeId:
            typename = self._advance()
            self._match(TokenKind.Equals)
            type = self._parse_type()
            defs.append(Type(typename, type))
        return defs

    def _parse_type(self):
        if self.cur_token.kind == TokenKind.LParen:
            
            return self._parse_product()
        else:
            
            sumlist = [Constructor(self._match(TokenKind.ConstructorId),
                                   self._parse_optional_fields())]
            while self.cur_token.kind  == TokenKind.Pipe:
                
                self._advance()
                sumlist.append(Constructor(
                                self._match(TokenKind.ConstructorId),
                                self._parse_optional_fields()))
            return Sum(sumlist, self._parse_optional_attributes())

    def _parse_product(self):
        return Product(self._parse_fields(), self._parse_optional_attributes())

    def _parse_fields(self):
        fields = []
        self._match(TokenKind.LParen)
        while self.cur_token.kind == TokenKind.TypeId:
            typename = self._advance()
            is_seq, is_opt = self._parse_optional_field_quantifier()
            id = (self._advance() if self.cur_token.kind in self._id_kinds
                                  else None)
            fields.append(Field(typename, id, seq=is_seq, opt=is_opt))
            if self.cur_token.kind == TokenKind.RParen:
                break
            elif self.cur_token.kind == TokenKind.Comma:
                self._advance()
        self._match(TokenKind.RParen)
        return fields

    def _parse_optional_fields(self):
        if self.cur_token.kind == TokenKind.LParen:
            return self._parse_fields()
        else:
            return None

    def _parse_optional_attributes(self):
        if self._at_keyword('attributes'):
            self._advance()
            return self._parse_fields()
        else:
            return None

    def _parse_optional_field_quantifier(self):
        is_seq, is_opt = False, False
        if self.cur_token.kind == TokenKind.Asterisk:
            is_seq = True
            self._advance()
        elif self.cur_token.kind == TokenKind.Question:
            is_opt = True
            self._advance()
        return is_seq, is_opt

    def _advance(self):
        
        cur_val = None if self.cur_token is None else self.cur_token.value
        try:
            self.cur_token = next(self._tokenizer)
        except StopIteration:
            self.cur_token = None
        return cur_val

    _id_kinds = (TokenKind.ConstructorId, TokenKind.TypeId)

    def _match(self, kind):
        
        if (isinstance(kind, tuple) and self.cur_token.kind in kind or
            self.cur_token.kind == kind
            ):
            value = self.cur_token.value
            self._advance()
            return value
        else:
            raise ASDLSyntaxError(
                'Unmatched {} (found {})'.format(kind, self.cur_token.kind),
                self.cur_token.lineno)

    def _at_keyword(self, keyword):
        return (self.cur_token.kind == TokenKind.TypeId and
                self.cur_token.value == keyword)