Python Enhancement Proposals

Python »
PEP Index »
PEP 269

PEP 269 – Pgen Module for Python

Author:: Jonathan Riehl <jriehl at spaceship.com>
Status:

Abstract

Much like theparser module exposes the Python parser, this PEPproposes that the parser generator used to create the Pythonparser,pgen, be exposed as a module in Python.

Through the course of Pythonic history, there have been numerousdiscussions about the creation of a Python compiler[1]. Thesehave resulted in several implementations of Python parsers, mostnotably theparser module currently provided in the Pythonstandard library[2] and Jeremy Hylton’scompiler module[3].However, while multiple language changes have been proposed[4][5], experimentation with the Python syntax has lacked thebenefit of a Python binding to the actual parser generator used tobuild Python.

By providing a Python wrapper analogous to Fred Drake Jr.’s parserwrapper, but targeted at thepgen library, the followingassertions are made:

Reference implementations of syntax changes will be easier todevelop. Currently, a reference implementation of a syntaxchange would require the developer to use thepgen tool fromthe command line. The resulting parser data structure wouldthen either have to be reworked to interface with a customCPython implementation, or wrapped as a C extension module.
Reference implementations of syntax changes will be easier todistribute. Since the parser generator will be available inPython, it should follow that the resulting parser willaccessible from Python. Therefore, reference implementationsshould be available as pure Python code, versus using customversions of the existing CPython distribution, or as compilableextension modules.
Reference implementations of syntax changes will be easier todiscuss with a larger audience. This somewhat falls out of thesecond assertion, since the community of Python users is mostlikely larger than the community of CPython developers.
Development of small languages in Python will be furtherenhanced, since the additional module will be a fullyfunctional LL(1) parser generator.

Specification

The proposed module will be calledpgen. Thepgen module willcontain the following functions:

`parseGrammarFile(fileName)->AST`

TheparseGrammarFile() function will read the file pointed toby fileName and create an AST object. The AST nodes willcontain the nonterminal, numeric values of the parsergenerator meta-grammar. The output AST will be an instance ofthe AST extension class as provided by theparser module.Syntax errors in the input file will cause the SyntaxErrorexception to be raised.

`parseGrammarString(text)->AST`

TheparseGrammarString() function will follow the semantics oftheparseGrammarFile(), but accept the grammar text as astring for input, as opposed to the file name.

`buildParser(grammarAst)->DFA`

ThebuildParser() function will accept an AST object for inputand return a DFA (deterministic finite automaton) datastructure. The DFA data structure will be a C extensionclass, much like the AST structure is provided in theparsermodule. If the input AST does not conform to the nonterminalcodes defined for thepgen meta-grammar,buildParser() willthrow aValueError exception.

`parseFile(fileName,dfa,start)->AST`

TheparseFile() function will essentially be a wrapper for thePyParser_ParseFile() C API function. The wrapper code willaccept the DFA C extension class, and the file name. An ASTinstance that conforms to the lexical values in thetokenmodule and the nonterminal values contained in the DFA will beoutput.

`parseString(text,dfa,start)->AST`

TheparseString() function will operate in a similar fashionto theparseFile() function, but accept the parse text as anargument. Much likeparseFile() will wrap thePyParser_ParseFile() C API function,parseString() will wrapthePyParser_ParseString() function.

`symbolToStringMap(dfa)->dict`

ThesymbolToStringMap() function will accept a DFA instanceand return a dictionary object that maps from the DFA’snumeric values for its nonterminals to the string names of thenonterminals as found in the original grammar specificationfor the DFA.

`stringToSymbolMap(dfa)->dict`

ThestringToSymbolMap() function output a dictionary mappingthe nonterminal names of the input DFA to their correspondingnumeric values.

Extra credit will be awarded if the map generation functions andparsing functions are also methods of the DFA extension class.

Implementation Plan

A cunning plan has been devised to accomplish this enhancement:

Rename thepgen functions to conform to the CPython namingstandards. This action may involve adding some header files totheInclude subdirectory.
Move thepgen C modules in the Makefile.pre.in from uniquepgenelements to the Python C library.
Make any needed changes to theparser module so the ASTextension class understands that there are AST types it may notunderstand. Cursory examination of the AST extension classshows that it keeps track of whether the tree is a suite or anexpression.

Code an additional C module in theModules directory. The Cextension module will implement the DFA extension class and thefunctions outlined in the previous section.
Add the new module to the build process. Black magic, indeed.