Python绘制语法分析树

发表于 分类于 Waline：
本文字数： 3.7k 阅读时长 ≈ 3 分钟
使用python的graphviz库跟据语法分析器分析LL(1)文法得到的最左推导结果构建语法分析树

安装graphviz库

  1. 安装对应软件包

    graphviz官网

    我选的是stable_windows_10_cmake_Release_x64_graphviz-install-2.47.1-win64.exe

  2. 安装python库

    1
    pip install graphviz

解析语法分析器输出

在LL(1)无回溯的递归下降语法分析器里实现了语法分析器。要获取语法分析的输出，只需要将构建脚本中的：

1
parser.exe code.txt

改为：

1
parser.exe code.txt > output.txt

这样就将输出的结果重定向到了output.txt。

得到的output.txt中每一行的格式类似于：

1
parent -> child1 child2 child3 ...

按照空格分隔，第一个是父节点名，第二个是->，之后是一系列子节点名。

按照最左推导的定义，如果child1是非终结符，则child1有子节点，并且一定就在下一行，比如：

1
2
parent -> child1 child2 child3 ...
child1 -> child11 child12 ...

否则依次考虑child2、child3...

所以这是一个深度优先遍历语法分析树的过程，只要用一个栈就可以将这棵树建立起来。

graphviz绘图

graphviz中Digraph和Graph分别对应有向图和无向图，这里使用的是无向图。

其基本用法是：

1
2
3
4
5
dot = Graph()  # 新建无向图
dot.node('node_name0', 'node_label0')  # 添加节点，其中node_name是用来唯一标识节点的，node_label则用来显示
dot.node('node_name1', 'node_label1')
dot.edge('node_name0', 'node_name1')  # 添加边: 从node_name0到node_name1
dot.render('output_name', format='svg', view=True)  # 指定输出名、格式，并查看结果

完整代码&测试运行

test.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#!/usr/bin/env python
# -*-coding:utf-8 -*-

import sys
from graphviz import Graph

dot = Graph()
nodes_cnt = 0  # 用来标识节点

lines = []
words_stk = []  # (node0, name)


def new_node(label: str) -> str:  # 新建节点并返回其标识
    global nodes_cnt
    new_node_name = 'node' + str(nodes_cnt)
    dot.node(new_node_name, label)
    nodes_cnt += 1
    return new_node_name


def draw():  # 构建语法分析树
    # 树根
    words_stk.append(('Program', new_node('Program')))
    for line in lines:
        words = line.split()
        if len(words) > 2:
            parent = words[0]
            while len(words_stk) > 0 and words_stk[len(words_stk) - 1][0] != parent:  # 之前的(如果有)一定都是叶子
                words_stk.pop()
            if len(words_stk) > 0 and words_stk[len(words_stk)-1][0] == parent:  # 继续进入最左子树(此节点已经创建过)
                parent_name = words_stk.pop()[1]
            else:
                parent_name = new_node(parent)  # parent一定是已经作为子节点创建过了，一定不会进入此分支，否则说明语法分析出错
                print('Error at node: ' + parent_name + ' ' + parent)
            tmp = []
            # 从左到右创建子节点, words[0]为parent, words[1]为'->'
            for child in words[2:]:  # 添加子节点
                child_name = new_node(child)
                tmp.append((child, child_name))
                dot.edge(parent_name, child_name)
            # 从右到左入栈
            while len(tmp) > 0:
                words_stk.append(tmp.pop())
    dot.render('test', format='svg', view=True)


def has_error() -> bool:  # 词法分析器输出错误或未知
    has_err = False
    for line in lines:
        if 'Error' in line or 'Unknown' in line:
            has_err = True
            print(line)
    return has_err


if __name__ == '__main__':
    if len(sys.argv) > 1:
        for file in sys.argv[1:]:  # 对命令行参数里指定的每个文件进行处理
            print('Processing file: '+file)
            lines = open(file, 'r').readlines()
            if not has_error():  # 有错误就不进行处理
                draw()
    else:
        print('No input file!')


output.txt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
Program	-> Block
Block	-> { Decls Stmts }
Decls	-> Decl Decls
Decl	-> Type id ;
Type	-> int
Decls	-> epsilon
Stmts	-> Stmt Stmts
Stmt	-> id = Expr ;
Expr	-> Term Expr1
Term	-> Factor Term1
Factor	-> num
Term1	-> epsilon
Expr1	-> epsilon
Stmts	-> Stmt Stmts
Stmt	-> while ( Bool ) Stmt
Bool	-> Expr Bool1
Expr	-> Term Expr1
Term	-> Factor Term1
Factor	-> id
Term1	-> epsilon
Expr1	-> epsilon
Bool1	-> <= Expr
Expr	-> Term Expr1
Term	-> Factor Term1
Factor	-> num
Term1	-> epsilon
Expr1	-> epsilon
Stmt	-> Block
Block	-> { Decls Stmts }
Decls	-> epsilon
Stmts	-> Stmt Stmts
Stmt	-> id = Expr ;
Expr	-> Term Expr1
Term	-> Factor Term1
Factor	-> id
Term1	-> epsilon
Expr1	-> + Term Expr1
Term	-> Factor Term1
Factor	-> id
Term1	-> epsilon
Expr1	-> epsilon
Stmts	-> Stmt Stmts
Stmt	-> id = Expr ;
Expr	-> Term Expr1
Term	-> Factor Term1
Factor	-> id
Term1	-> epsilon
Expr1	-> + Term Expr1
Term	-> Factor Term1
Factor	-> num
Term1	-> epsilon
Expr1	-> epsilon
Stmts	-> epsilon
Stmts	-> epsilon

在构建脚本中添加或手动运行:

1
python test.py output.txt

输出：

相关文章