diff -r 128b45caba5b compiler.rst --- a/compiler.rst Sun Jun 26 09:01:18 2016 +0300 +++ b/compiler.rst Fri Jul 08 19:08:51 2016 +0100 @@ -74,6 +74,26 @@ 'else' statement. ``REQ(CHILD(node, 2), COLON)`` can be used to access what should be the first ``:`` and require it be an actual ``:`` token. +As an optimization, certain kinds of nodes (listed in the big switch +statement in ``PyNode_Compress``), when they only have a single child, +are replaced with the child node. This allows "compressing" long +branchless stretches in the parse tree, significantly lowering the +peak memory consumption by the parser: back in 2002, Andrew MacIntyre +reported that up to 89% of nodes in a parse tree have a single child; +the "node compression" allows most of these nodes to be eliminated. + +The implication for parse tree consumers is that a node's children +may not have exactly the types as defined in Grammar/Grammar; any +child node could have been replaced with a more specific subclass. +For example, a ``testlist`` node can now have an ``atom`` node as a +direct child, instead of a:: + + test -> or_test -> and_test -> not_test -> comparison -> + expr -> xor_expr -> and_expr -> shift_expr -> + arith_expr -> term -> factor -> power -> atom_expr -> atom + +degenerate subtree of single-child nodes. + Abstract Syntax Trees (AST) ---------------------------