深度優(yōu)先構(gòu)建文本結(jié)構(gòu)樹 - 馮俊輝

這是馮俊輝在做本科畢業(yè)設(shè)計的時候，一個驚為天人的發(fā)現(xiàn)次酌！

只要短短幾十行 python，就能構(gòu)建一個完美的文本結(jié)構(gòu)樹剂公！

待處理文本

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):
    # 大于當(dāng)前多層（與 index 代表的第0層相比）
    if next_layer - current_layer > 1:
        parse_ast_tree(index[len(index) - 1]['child'], current_layer + 1, next_layer, next_line)

    # 大于當(dāng)前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})

    # 等于當(dāng)前層
    if next_layer == current_layer:  # current_layer 的父節(jié)點 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])  # 層數(shù) 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': []}]}]}]