• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1#!/usr/bin/env python3.8
2
3""" Convert a grammar into a dot-file suitable for use with GraphViz
4
5    For example:
6        Generate the GraphViz file:
7        # scripts/grammar_grapher.py data/python.gram > python.gv
8
9        Then generate the graph...
10
11        # twopi python.gv -Tpng > python_twopi.png
12
13        or
14
15        # dot python.gv -Tpng > python_dot.png
16
17        NOTE: The _dot_ and _twopi_ tools seem to produce the most useful results.
18              The _circo_ tool is the worst of the bunch. Don't even bother.
19"""
20
21import argparse
22import sys
23
24from typing import Any, List
25
26sys.path.insert(0, ".")
27
28from pegen.build import build_parser
29from pegen.grammar import (
30    Alt,
31    Cut,
32    Grammar,
33    Group,
34    Leaf,
35    Lookahead,
36    Rule,
37    NameLeaf,
38    NamedItem,
39    Opt,
40    Repeat,
41    Rhs,
42)
43
44argparser = argparse.ArgumentParser(prog="graph_grammar", description="Graph a grammar tree",)
45argparser.add_argument(
46    "-s",
47    "--start",
48    choices=["exec", "eval", "single"],
49    default="exec",
50    help="Choose the grammar's start rule (exec, eval or single)",
51)
52argparser.add_argument("grammar_file", help="The grammar file to graph")
53
54
55def references_for_item(item: Any) -> List[Any]:
56    if isinstance(item, Alt):
57        return [_ref for _item in item.items for _ref in references_for_item(_item)]
58    elif isinstance(item, Cut):
59        return []
60    elif isinstance(item, Group):
61        return references_for_item(item.rhs)
62    elif isinstance(item, Lookahead):
63        return references_for_item(item.node)
64    elif isinstance(item, NamedItem):
65        return references_for_item(item.item)
66
67    # NOTE NameLeaf must be before Leaf
68    elif isinstance(item, NameLeaf):
69        if item.value == "ENDMARKER":
70            return []
71        return [item.value]
72    elif isinstance(item, Leaf):
73        return []
74
75    elif isinstance(item, Opt):
76        return references_for_item(item.node)
77    elif isinstance(item, Repeat):
78        return references_for_item(item.node)
79    elif isinstance(item, Rhs):
80        return [_ref for alt in item.alts for _ref in references_for_item(alt)]
81    elif isinstance(item, Rule):
82        return references_for_item(item.rhs)
83    else:
84        raise RuntimeError(f"Unknown item: {type(item)}")
85
86
87def main() -> None:
88    args = argparser.parse_args()
89
90    try:
91        grammar, parser, tokenizer = build_parser(args.grammar_file)
92    except Exception as err:
93        print("ERROR: Failed to parse grammar file", file=sys.stderr)
94        sys.exit(1)
95
96    references = {}
97    for name, rule in grammar.rules.items():
98        references[name] = set(references_for_item(rule))
99
100    # Flatten the start node if has only a single reference
101    root_node = {"exec": "file", "eval": "eval", "single": "interactive"}[args.start]
102
103    print("digraph g1 {")
104    print('\toverlap="scale";')  # Force twopi to scale the graph to avoid overlaps
105    print(f'\troot="{root_node}";')
106    print(f"\t{root_node} [color=green, shape=circle];")
107    for name, refs in references.items():
108        for ref in refs:
109            print(f"\t{name} -> {ref};")
110    print("}")
111
112
113if __name__ == "__main__":
114    main()
115