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