Как построить дерево разбора во время анализа LL (1)?

Question

Мне было интересно, есть ли способ построить дерево разбора во время синтаксического анализа LL (1). Я пытался в течение нескольких дней, но не смог найти решение. Этот вопрос похож, но он не предоставляет достаточно подробностей реализации, и он предназначен для AST, а не для дерева разбора.

Подробности:

• Я использую стек

Answer 1

Я бы сделал это следующим образом:

Грамматика экзамена:

statement -> number
statement -> '(' statement '+' statement ')'
number-> 'n'

приводит к:

RULES = [
    ["number"],
    ['(', "statement", '+', "statement", ')'],
    ['n'],
]

выполнит анализ: "((n+n)+n)" -> ll -> [1,1,0,2,0,2,0,2] вы получите список выполненных правил

теперь вы можете построить дерево

def tree(input, ll_output):
    rule = ll_output.pop(0)
    tokens = []
    for item in RULES[rule]:
        if len(item) > 1: tokens.append(tree(input, ll_output))
        else: tokens.append(input.pop(0))
    return tokens

input = ['(','(','n','+','n',')','+','n',')'] # "((n+n)+n)"
ll_output = [1,1,0,2,0,2,0,2]
tree(input, ll_output)
# -> ['(', ['(', [['n']], '+', [['n']], ')'], '+', [['n']], ')']