cpython/Parser/asdl.py at main · All-Blockchains/cpython · GitHub

History

399 lines (341 loc) · 13.5 KB

Raw

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

376

377

378

379

380

381

382

383

384

385

386

387

388

389

390

391

392

393

394

395

396

397

398

399

#-------------------------------------------------------------------------------

# 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/

#-------------------------------------------------------------------------------

from collections import namedtuple

import enum

import re

__all__ = [

'builtin_types', 'parse', 'AST', 'Module', 'Type', 'Constructor',

'Field', 'Sum', 'Product', 'VisitorBase', 'Check', 'check']

# 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.

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 Quantifier(enum.Enum):

OPTIONAL = enum.auto()

SEQUENCE = enum.auto()

class Field(AST):

def __init__(self, type, name=None, quantifiers=None):

self.type = type

self.name = name

self.seq = False

self.opt = False

self.quantifiers = quantifiers or []

if len(self.quantifiers) > 0:

self.seq = self.quantifiers[-1] is Quantifier.SEQUENCE

self.opt = self.quantifiers[-1] is Quantifier.OPTIONAL

def __str__(self):

extra = ""

for mod in self.quantifiers:

if mod is Quantifier.SEQUENCE:

extra += "*"

elif mod is Quantifier.OPTIONAL:

extra += "?"

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

def __repr__(self):

if self.quantifiers:

texts = []

for mod in self.quantifiers:

if mod is Quantifier.SEQUENCE:

texts.append("SEQUENCE")

elif mod is Quantifier.OPTIONAL:

texts.append("OPTIONAL")

extra = ", quantifiers=[{}]".format(", ".join(texts))

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)

# 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.

class VisitorBase(object):

"""Generic tree visitor for ASTs."""

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):

"""A visitor that checks a parsed ASDL tree for correctness.

Errors are printed and accumulated.

"""

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):

"""Check the parsed ASDL tree for correctness.

Return True if success. For failure, the errors are printed out and False

is returned.

"""

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

# The ASDL parser itself comes next. The only interesting external interface

# here is the top-level parse function.

def parse(filename):

"""Parse ASDL from the given file and return a Module node describing it."""

with open(filename, encoding="utf-8") as f:

parser = ASDLParser()

return parser.parse(f.read())

# Types for describing tokens in an ASDL specification.

class TokenKind:

"""TokenKind is provides a scope for enumerated token kinds."""

(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):

"""Tokenize the given buffer. Yield Token objects."""

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():

# Some kind of identifier

if c[0].isupper():

yield Token(TokenKind.ConstructorId, c, lineno)

else:

yield Token(TokenKind.TypeId, c, lineno)

elif c[:2] == '--':

# Comment

break

else:

# Operators

try:

op_kind = TokenKind.operator_table[c]

except KeyError:

raise ASDLSyntaxError('Invalid operator %s' % c, lineno)

yield Token(op_kind, c, lineno)

class ASDLParser:

"""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.

"""

def __init__(self):

self._tokenizer = None

self.cur_token = None

def parse(self, buf):

"""Parse the ASDL in the buffer and return an AST with a Module root.

"""

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:

# If we see a (, it's a product

return self._parse_product()

else:

# Otherwise it's a sum. Look for ConstructorId

sumlist = [Constructor(self._match(TokenKind.ConstructorId),

self._parse_optional_fields())]

while self.cur_token.kind == TokenKind.Pipe:

# More constructors

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()

quantifiers = self._parse_optional_field_quantifier()

id = (self._advance() if self.cur_token.kind in self._id_kinds

else None)

fields.append(Field(typename, id, quantifiers=quantifiers))

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):

quantifiers = []

while self.cur_token.kind in (TokenKind.Asterisk, TokenKind.Question):

if self.cur_token.kind == TokenKind.Asterisk:

quantifiers.append(Quantifier.SEQUENCE)

elif self.cur_token.kind == TokenKind.Question:

quantifiers.append(Quantifier.OPTIONAL)

self._advance()

return quantifiers

def _advance(self):

""" Return the value of the current token and read the next one into

self.cur_token.

"""

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):

"""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

"""

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)

cpython/Parser/asdl.py at main · All-Blockchains/cpython · GitHub

Uh oh!

Expand file tree

Breadcrumbs

asdl.py

Latest commit

History

Breadcrumbs

asdl.py

File metadata and controls