Parser/asdl.py

   1 """An implementation of the Zephyr Abstract Syntax Definition Language.
   2
   3 See http://asdl.sourceforge.net/ and
   4 http://www.cs.princeton.edu/~danwang/Papers/dsl97/dsl97-abstract.html.
   5
   6 Only supports top level module decl, not view.  I'm guessing that view
   7 is intended to support the browser and I'm not interested in the
   8 browser.
   9 """
  10
  11 #__metaclass__ = type
  12
  13 import os
  14 import traceback
  15
  16 import spark
  17
  18 class Token:
  19     # spark seems to dispatch in the parser based on a token's
  20     # type attribute
  21     def __init__(self, type, lineno):
  22         self.type = type
  23         self.lineno = lineno
  24
  25     def __str__(self):
  26         return self.type
  27
  28     def __repr__(self):
  29         return str(self)
  30
  31 class Id(Token):
  32     def __init__(self, value, lineno):
  33         self.type = 'Id'
  34         self.value = value
  35         self.lineno = lineno
  36
  37     def __str__(self):
  38         return self.value
  39
  40 class ASDLSyntaxError:
  41
  42     def __init__(self, lineno, token=None, msg=None):
  43         self.lineno = lineno
  44         self.token = token
  45         self.msg = msg
  46
  47     def __str__(self):
  48         if self.msg is None:
  49             return "Error at '%s', line %d" % (self.token, self.lineno)
  50         else:
  51             return "%s, line %d" % (self.msg, self.lineno)
  52
  53 class ASDLScanner(spark.GenericScanner, object):
  54
  55     def tokenize(self, input):
  56         self.rv = []
  57         self.lineno = 1
  58         super(ASDLScanner, self).tokenize(input)
  59         return self.rv
  60
  61     def t_id(self, s):
  62         r"[\w\.]+"
  63         # XXX doesn't distinguish upper vs. lower, which is
  64         # significant for ASDL.
  65         self.rv.append(Id(s, self.lineno))
  66
  67     def t_xxx(self, s): # not sure what this production means
  68         r"<="
  69         self.rv.append(Token(s, self.lineno))
  70
  71     def t_punctuation(self, s):
  72         r"[\{\}\*\=\|\(\)\,\?\:]"
  73         self.rv.append(Token(s, self.lineno))
  74
  75     def t_comment(self, s):
  76         r"\-\-[^\n]*"
  77         pass
  78
  79     def t_newline(self, s):
  80         r"\n"
  81         self.lineno += 1
  82
  83     def t_whitespace(self, s):
  84         r"[ \t]+"
  85         pass
  86
  87     def t_default(self, s):
  88         r" . +"
  89         raise ValueError, "unmatched input: %s" % `s`
  90
  91 class ASDLParser(spark.GenericParser, object):
  92     def __init__(self):
  93         super(ASDLParser, self).__init__("module")
  94
  95     def typestring(self, tok):
  96         return tok.type
  97
  98     def error(self, tok):
  99         raise ASDLSyntaxError(tok.lineno, tok)
 100
 101     def p_module_0(self, (module, name, _0, _1)):
 102         " module ::= Id Id { } "
 103         if module.value != "module":
 104             raise ASDLSyntaxError(module.lineno,
 105                                   msg="expected 'module', found %s" % module)
 106         return Module(name, None)
 107
 108     def p_module(self, (module, name, _0, definitions, _1)):
 109         " module ::= Id Id { definitions } "
 110         if module.value != "module":
 111             raise ASDLSyntaxError(module.lineno,
 112                                   msg="expected 'module', found %s" % module)
 113         return Module(name, definitions)
 114
 115     def p_definition_0(self, (definition,)):
 116         " definitions ::= definition "
 117         return definition
 118
 119     def p_definition_1(self, (definitions, definition)):
 120         " definitions ::= definition definitions "
 121         return definitions + definition
 122
 123     def p_definition(self, (id, _, type)):
 124         " definition ::= Id = type "
 125         return [Type(id, type)]
 126
 127     def p_type_0(self, (product,)):
 128         " type ::= product "
 129         return product
 130
 131     def p_type_1(self, (sum,)):
 132         " type ::= sum "
 133         return Sum(sum)
 134
 135     def p_type_2(self, (sum, id, _0, attributes, _1)):
 136         " type ::= sum Id ( fields ) "
 137         if id.value != "attributes":
 138             raise ASDLSyntaxError(id.lineno,
 139                                   msg="expected attributes, found %s" % id)
 140         return Sum(sum, attributes)
 141
 142     def p_product(self, (_0, fields, _1)):
 143         " product ::= ( fields ) "
 144         # XXX can't I just construct things in the right order?
 145         fields.reverse()
 146         return Product(fields)
 147
 148     def p_sum_0(self, (constructor,)):
 149         " sum ::= constructor """
 150         return [constructor]
 151
 152     def p_sum_1(self, (constructor, _, sum)):
 153         " sum ::= constructor | sum "
 154         return [constructor] + sum
 155
 156     def p_sum_2(self, (constructor, _, sum)):
 157         " sum ::= constructor | sum "
 158         return [constructor] + sum
 159
 160     def p_constructor_0(self, (id,)):
 161         " constructor ::= Id "
 162         return Constructor(id)
 163
 164     def p_constructor_1(self, (id, _0, fields, _1)):
 165         " constructor ::= Id ( fields ) "
 166         # XXX can't I just construct things in the right order?
 167         fields.reverse()
 168         return Constructor(id, fields)
 169
 170     def p_fields_0(self, (field,)):
 171         " fields ::= field "
 172         return [field]
 173
 174     def p_fields_1(self, (field, _, fields)):
 175         " fields ::= field , fields "
 176         return fields + [field]
 177
 178     def p_field_0(self, (type,)):
 179         " field ::= Id "
 180         return Field(type)
 181
 182     def p_field_1(self, (type, name)):
 183         " field ::= Id Id "
 184         return Field(type, name)
 185
 186     def p_field_2(self, (type, _, name)):
 187         " field ::= Id * Id "
 188         return Field(type, name, seq=1)
 189
 190     def p_field_3(self, (type, _, name)):
 191         " field ::= Id ? Id "
 192         return Field(type, name, opt=1)
 193
 194     def p_field_4(self, (type, _)):
 195         " field ::= Id * "
 196         return Field(type, seq=1)
 197
 198     def p_field_5(self, (type, _)):
 199         " field ::= Id ? "
 200         return Field(type, opt=1)
 201
 202 builtin_types = ("identifier", "string", "int", "bool", "object")
 203
 204 # below is a collection of classes to capture the AST of an AST :-)
 205 # not sure if any of the methods are useful yet, but I'm adding them
 206 # piecemeal as they seem helpful
 207
 208 class AST:
 209     pass # a marker class
 210
 211 class Module(AST):
 212     def __init__(self, name, dfns):
 213         self.name = name
 214         self.dfns = dfns
 215         self.types = {} # maps type name to value (from dfns)
 216         for type in dfns:
 217             self.types[type.name.value] = type.value
 218
 219     def __repr__(self):
 220         return "Module(%s, %s)" % (self.name, self.dfns)
 221
 222 class Type(AST):
 223     def __init__(self, name, value):
 224         self.name = name
 225         self.value = value
 226
 227     def __repr__(self):
 228         return "Type(%s, %s)" % (self.name, self.value)
 229
 230 class Constructor(AST):
 231     def __init__(self, name, fields=None):
 232         self.name = name
 233         self.fields = fields or []
 234
 235     def __repr__(self):
 236         return "Constructor(%s, %s)" % (self.name, self.fields)
 237
 238 class Field(AST):
 239     def __init__(self, type, name=None, seq=0, opt=0):
 240         self.type = type
 241         self.name = name
 242         self.seq = seq
 243         self.opt = opt
 244
 245     def __repr__(self):
 246         if self.seq:
 247             extra = ", seq=1"
 248         elif self.opt:
 249             extra = ", opt=1"
 250         else:
 251             extra = ""
 252         if self.name is None:
 253             return "Field(%s%s)" % (self.type, extra)
 254         else:
 255             return "Field(%s, %s%s)" % (self.type, self.name, extra)
 256
 257 class Sum(AST):
 258     def __init__(self, types, attributes=None):
 259         self.types = types
 260         self.attributes = attributes or []
 261
 262     def __repr__(self):
 263         if self.attributes is None:
 264             return "Sum(%s)" % self.types
 265         else:
 266             return "Sum(%s, %s)" % (self.types, self.attributes)
 267
 268 class Product(AST):
 269     def __init__(self, fields):
 270         self.fields = fields
 271
 272     def __repr__(self):
 273         return "Product(%s)" % self.fields
 274
 275 class VisitorBase(object):
 276
 277     def __init__(self, skip=0):
 278         self.cache = {}
 279         self.skip = skip
 280
 281     def visit(self, object, *args):
 282         meth = self._dispatch(object)
 283         if meth is None:
 284             return
 285         try:
 286             meth(object, *args)
 287         except Exception, err:
 288             print "Error visiting", repr(object)
 289             print err
 290             traceback.print_exc()
 291             # XXX hack
 292             if hasattr(self, 'file'):
 293                 self.file.flush()
 294             os._exit(1)
 295
 296     def _dispatch(self, object):
 297         assert isinstance(object, AST), repr(object)
 298         klass = object.__class__
 299         meth = self.cache.get(klass)
 300         if meth is None:
 301             methname = "visit" + klass.__name__
 302             if self.skip:
 303                 meth = getattr(self, methname, None)
 304             else:
 305                 meth = getattr(self, methname)
 306             self.cache[klass] = meth
 307         return meth
 308
 309 class Check(VisitorBase):
 310
 311     def __init__(self):
 312         super(Check, self).__init__(skip=1)
 313         self.cons = {}
 314         self.errors = 0
 315         self.types = {}
 316
 317     def visitModule(self, mod):
 318         for dfn in mod.dfns:
 319             self.visit(dfn)
 320
 321     def visitType(self, type):
 322         self.visit(type.value, str(type.name))
 323
 324     def visitSum(self, sum, name):
 325         for t in sum.types:
 326             self.visit(t, name)
 327
 328     def visitConstructor(self, cons, name):
 329         key = str(cons.name)
 330         conflict = self.cons.get(key)
 331         if conflict is None:
 332             self.cons[key] = name
 333         else:
 334             print "Redefinition of constructor %s" % key
 335             print "Defined in %s and %s" % (conflict, name)
 336             self.errors += 1
 337         for f in cons.fields:
 338             self.visit(f, key)
 339
 340     def visitField(self, field, name):
 341         key = str(field.type)
 342         l = self.types.setdefault(key, [])
 343         l.append(name)
 344
 345     def visitProduct(self, prod, name):
 346         for f in prod.fields:
 347             self.visit(f, name)
 348
 349 def check(mod):
 350     v = Check()
 351     v.visit(mod)
 352
 353     for t in v.types:
 354         if not mod.types.has_key(t) and not t in builtin_types:
 355             v.errors += 1
 356             uses = ", ".join(v.types[t])
 357             print "Undefined type %s, used in %s" % (t, uses)
 358
 359     return not v.errors
 360
 361 def parse(file):
 362     scanner = ASDLScanner()
 363     parser = ASDLParser()
 364
 365     buf = open(file).read()
 366     tokens = scanner.tokenize(buf)
 367     try:
 368         return parser.parse(tokens)
 369     except ASDLSyntaxError, err:
 370         print err
 371         lines = buf.split("\n")
 372         print lines[err.lineno - 1] # lines starts at 0, files at 1
 373
 374 if __name__ == "__main__":
 375     import glob
 376     import sys
 377
 378     if len(sys.argv) > 1:
 379         files = sys.argv[1:]
 380     else:
 381         testdir = "tests"
 382         files = glob.glob(testdir + "/*.asdl")
 383
 384     for file in files:
 385         print file
 386         mod = parse(file)
 387         print "module", mod.name
 388         print len(mod.dfns), "definitions"
 389         if not check(mod):
 390             print "Check failed"
 391         else:
 392             for dfn in mod.dfns:
 393                 print dfn.type