深度优先构建文本结构树 - 冯俊辉

这是冯俊辉在做本科毕业设计的时候，一个惊为天人的发现！

只要短短几十行 python，就能构建一个完美的文本结构树！

待处理文本

TranslationUnitDecl 0x7fd01b821ed0 <<invalid sloc>> <invalid sloc>
|-TypedefDecl 0x7fd01b822460 <<invalid sloc>> <invalid sloc> implicit referenced __int128_t '__int128'
| `-BuiltinType 0x7fd01b822140 '__int128'
|-TypedefDecl 0x7fd01b8224d0 <<invalid sloc>> <invalid sloc> implicit referenced __uint128_t 'unsigned __int128'
| `-BuiltinType 0x7fd01b822160 'unsigned __int128'
|-TypedefDecl 0x7fd01b822818 <<invalid sloc>> <invalid sloc> implicit __NSConstantString 'struct __NSConstantString_tag'
| `-RecordType 0x7fd01b8225c0 'struct __NSConstantString_tag'
|   `-CXXRecord 0x7fd01b822528 '__NSConstantString_tag'
|-TypedefDecl 0x7fd01b8228b0 <<invalid sloc>> <invalid sloc> implicit __builtin_ms_va_list 'char *'
| `-PointerType 0x7fd01b822870 'char *'
|   `-BuiltinType 0x7fd01b821f60 'char'
|-TypedefDecl 0x7fd01b854800 <<invalid sloc>> <invalid sloc> implicit referenced __builtin_va_list 'struct __va_list_tag [1]'
| `-ConstantArrayType 0x7fd01b822b90 'struct __va_list_tag [1]' 1
|   `-RecordType 0x7fd01b8229a0 'struct __va_list_tag'
|     `-CXXRecord 0x7fd01b822908 '__va_list_tag'
|-TypedefDecl 0x7fd01b854868 </Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/__config:321:1, col:20> col:20 referenced char16_t 'char16_t'
| `-BuiltinType 0x7fd01b8221a0 'char16_t'
|-TypedefDecl 0x7fd01b8548d0 <line:322:1, col:20> col:20 referenced char32_t 'char32_t'
| `-BuiltinType 0x7fd01b8221c0 'char32_t'

源代码

# coding=utf-8
from pprint import pprint


# get layer
def get_ast_layer(line):
    return int((len(line) + 1) / 2)


# parse text of line
def parse_ast_line(line):
    return {str: line}


# establish tree
def parse_ast_tree(index, current_layer, next_layer, next_line):
    # 大于当前多层（与 index 代表的第0层相比）
    if next_layer - current_layer > 1:
        parse_ast_tree(index[len(index) - 1]['child'], current_layer + 1, next_layer, next_line)

    # 大于当前1层，index 的最后一个孩子（因为是顺序遍历）添加 child
    self = parse_ast_line(next_line)
    child = []
    if next_layer - current_layer == 1:
        index[len(index) - 1]['child'].append({'aself': self, 'child': child})

    # 等于当前层
    if next_layer == current_layer:  # current_layer 的父节点 index 添加一个
        index.append({'aself': self, 'child': child})


# load ast tree
def parse_ast_file(file_path):
    # init
    index = []

    # deal with line
    with open(file_path, 'r') as file:
        # deal with line
        self = parse_ast_line(file.readline())  # 首行
        child = []
        index.append({
            'aself': self,  # 首行
            'child': child  # []
        })
        for line in file:
            line_list = line.split('-', 1)
            layer = get_ast_layer(line_list[0])  # 层数 1
            parse_ast_tree(index, current_layer=0, next_layer=layer, next_line=line_list[1])
    return index


path = './test.ast'
tree = parse_ast_file(path)
pprint(tree)

输出

[{'aself': {<type 'str'>: 'TranslationUnitDecl 0x7fd01b821ed0 <<invalid sloc>> <invalid sloc>\n'},
  'child': [{'aself': {<type 'str'>: "TypedefDecl 0x7fd01b822460 <<invalid sloc>> <invalid sloc> implicit referenced __int128_t '__int128'\n"},
             'child': [{'aself': {<type 'str'>: "BuiltinType 0x7fd01b822140 '__int128'\n"},
                        'child': []}]},
            {'aself': {<type 'str'>: "TypedefDecl 0x7fd01b8224d0 <<invalid sloc>> <invalid sloc> implicit referenced __uint128_t 'unsigned __int128'\n"},
             'child': [{'aself': {<type 'str'>: "BuiltinType 0x7fd01b822160 'unsigned __int128'\n"},
                        'child': []}]},
            {'aself': {<type 'str'>: "TypedefDecl 0x7fd01b822818 <<invalid sloc>> <invalid sloc> implicit __NSConstantString 'struct __NSConstantString_tag'\n"},
             'child': [{'aself': {<type 'str'>: "RecordType 0x7fd01b8225c0 'struct __NSConstantString_tag'\n"},
                        'child': [{'aself': {<type 'str'>: "CXXRecord 0x7fd01b822528 '__NSConstantString_tag'\n"},
                                   'child': []}]}]},
            {'aself': {<type 'str'>: "TypedefDecl 0x7fd01b8228b0 <<invalid sloc>> <invalid sloc> implicit __builtin_ms_va_list 'char *'\n"},
             'child': [{'aself': {<type 'str'>: "PointerType 0x7fd01b822870 'char *'\n"},
                        'child': [{'aself': {<type 'str'>: "BuiltinType 0x7fd01b821f60 'char'\n"},
                                   'child': []}]}]},
            {'aself': {<type 'str'>: "TypedefDecl 0x7fd01b854800 <<invalid sloc>> <invalid sloc> implicit referenced __builtin_va_list 'struct __va_list_tag [1]'\n"},
             'child': [{'aself': {<type 'str'>: "ConstantArrayType 0x7fd01b822b90 'struct __va_list_tag [1]' 1\n"},
                        'child': [{'aself': {<type 'str'>: "RecordType 0x7fd01b8229a0 'struct __va_list_tag'\n"},
                                   'child': [{'aself': {<type 'str'>: "CXXRecord 0x7fd01b822908 '__va_list_tag'\n"},
                                              'child': []}]}]}]},
            {'aself': {<type 'str'>: "TypedefDecl 0x7fd01b854868 </Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/__config:321:1, col:20> col:20 referenced char16_t 'char16_t'\n"},
             'child': [{'aself': {<type 'str'>: "BuiltinType 0x7fd01b8221a0 'char16_t'\n"},
                        'child': []}]},
            {'aself': {<type 'str'>: "TypedefDecl 0x7fd01b8548d0 <line:322:1, col:20> col:20 referenced char32_t 'char32_t'\n"},
             'child': [{'aself': {<type 'str'>: "BuiltinType 0x7fd01b8221c0 'char32_t'"},
                        'child': []}]}]}]