No products in the cart.

Learn Python – Interactive Python

Parse Trees

Python’s parser is an LL(1) parser mostly based off of the implementation laid out in the Dragon Book [Aho86].

The grammar file for Python can be found in Grammar/Grammar with the numeric value of grammar rules stored in Include/graminit.h. The list of types of tokens (literal tokens, such as :, numbers, etc.) can be found in Grammar/Tokens with the numeric value stored in Include/token.h. The parse tree is made up of node *structs (as defined in Include/node.h).

Querying data from the node structs can be done with the following macros (which are all defined in Include/node.h):

CHILD(node *, int)
Returns the nth child of the node using zero-offset indexing
RCHILD(node *, int)
Returns the nth child of the node from the right side; use negative numbers!
NCH(node *)
Number of children the node has
STR(node *)
String representation of the node; e.g., will return : for a COLON token
TYPE(node *)
The type of node as specified in Include/graminit.h
REQ(node *, TYPE)
Assert that the node is the type that is expected
LINENO(node *)
Retrieve the line number of the source code that led to the creation of the parse rule; defined in Python/ast.c

For example, consider the rule for ‘while’:

while_stmt ::=  "while" expression ":" suite : ["else" ":" suite]

The node representing this will have TYPE(node) == while_stmt and the number of children can be 4 or 7 depending on whether there is an ‘else’ statement. REQ(CHILD(node, 2), COLON) can be used to access what should be the first : and require it be an actual : token.

Leave a Comment



Connect with: