Как вы строите дерево синтаксического анализа во время синтаксического анализа LL (1)?

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

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

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

stack abstract-syntax-tree compiler-construction ll parse-tree
person xilpex    schedule 01.05.2020    source источник
comment
Дерево синтаксического анализа - это один из случаев AST (в котором ничего не абстрагируется :-)), и оба решения, предложенные в связанном ответе, фактически создают деревья синтаксического анализа. Вы пробовали один из них? (Я не думаю, что вы можете сказать, что ответ с фактически работающим кодом не содержит достаточно деталей реализации. Он может быть написан не на том языке, который вам нужен, но в этом случае вам нужно указать, какие языки приемлемы :-) и предоставьте достаточно рабочего кода, чтобы избежать неизбежного, что мы не пишем код для ваших язвительных комментариев.   -  person rici    schedule 01.05.2020
comment
(Конечно, эти язвительные комментарии неверны. Многие люди предоставляют здесь код на золотой тарелке, хотя, вероятно, им не следует этого делать, так как это только поощряет плохие вопросы. Но обычно этого не происходит, если код действительно легко понять. записывать.)   -  person rici    schedule 01.05.2020
comment
@rici -- Да, я попробовал первый. Проблема в том, что у него недостаточно деталей реализации, например, когда выходить из текущего AST.   -  person xilpex    schedule 01.05.2020
comment
Вы покидаете текущий узел AST, когда он завершен. Скелет — это правая часть продукции, и каждый раз, когда встречается узел AST, вы заполняете один символ. Так что вы знаете, когда вы дойдете до конца.   -  person rici    schedule 02.05.2020
comment
Алгоритм, предложенный в этом ответе; это начинается примерно в середине ответа.   -  person rici    schedule 02.05.2020
comment
@rici -- Спасибо! У меня такое ощущение, что из-за этого восходящие синтаксические анализаторы будут намного быстрее, потому что вы знаете дочерние узлы, поэтому вам не нужно включать дополнительный шаг. Это верно?   -  person xilpex    schedule 02.05.2020
comment
Да, я не большой поклонник сверху вниз. Хотя имеет место быть.   -  person rici    schedule 02.05.2020
comment
Позвольте мне сформулировать это по-другому. В синтаксическом анализаторе с рекурсивным спуском грамматика реализуется в потоке управления синтаксического анализатора. Это простая и мощная идея, но у нее есть ограничения: LL(1) — жесткое ограничение; поток управления может быть специальным; вам нужно беспокоиться о переполнении стека и т. д. Но это простое и быстрое решение многих распространенных проблем синтаксического анализа. Однако. Если вы хотите построить AST из парсера, управляемого таблицами, нет никаких причин принимать эти ограничения. Используйте зрелый доступный генератор синтаксических анализаторов и сконцентрируйтесь на интересных вещах, которые появляются после синтаксического анализа.   -  person rici    schedule 02.05.2020

Ответы (1)


arrow_upward
0
arrow_downward

Я бы сделал так:

Пример грамматики:

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']], ')']
person Hexception    schedule 09.05.2020