How do you construct a parse tree during LL(1) parsing?

Question

I was wondering if there is a way to construct a parse tree during LL(1) parsing. I've been trying for days, but have been unable to find a solution. This question is similar, but it doesn't provide enough implementation details, and it is for the AST, not the parse tree.

Details:

• I am using a stack

Answer 1

I would do it that way:

Examle Grammar:

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

results into:

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

perform ll parsing: "((n+n)+n)" -> ll -> [1,1,0,2,0,2,0,2] you will get a list of performed rules

now you can build a tree

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']], ')']