Ну для начала, ты неправильно ставишь цель. После синтаксического разбора у тебя будет не список, а древовидная структура данных, а итоговый код будет результатом обхода этой структуры в глубину.
Так что читай про восходящий алгоритм. Идея у него простая. У тебя должен быть набор правил твоей грамматики, например:
ЦИКЛ_WHILE = 'while' '(' ВЫРАЖЕНИЕ ')' ОПЕРАТОР
Заглавными я записал нетерминальные символы - что-то, что раскрывается далее в последовательность токенов.
Остальное - терминальные символы, т.е. токены.
Итак, у тебя есть цепочка символов - терминальных или нетерминальных. Нетерминальные хранят в себе кусочек дерева программы, терминальные хранят в себе один токен.
1. Перебираешь правила, ищешь правило, соответствующее текущей позиции в цепочке. Для начала цепочки это будет правило "программа в целом".
2. Строишь узел дерева, соответствующий найденному правилу.
3. Помещаешь в этот узел терминальные символы, входящие в правило. В примере выше это будут 'while' и '('. Сдвигаешь позицию в цепочке.
4. Если в правиле дальше идёт нетерминальный символ, рекурсивно обрабатываешь цепочку по правилу для этого символа, начиная с текущей позиции. Когда обработка закончится, у тебя позиция в цепочке сместится на конец последовательности символов для этого нетерминала, и можно будет продолжить для следующего символа в правиле.
5. Когда правило закончилось - возвращаешь полученное мини-дерево, чтобы вышележащий код его встроил в свой узел дерева.
6. Если есть альтернативы, сохраняешь текущую позицию в цепочке и пробуешь альтернативы по очереди. Если альтернатива не сработала (правило тут не подходит), то возвращаешься к сохранённой позиции и пробуешь уже с другой альтернативой.
7. Если в какой-то момент ни одно правило не подошло, или если мы получили неожиданный терминал, есть синтаксическая ошибка в коде.
Это сравнительно легко реализуется через косвенную рекурсию. Т.е. у тебя в парсере будет много методов nfrjuj вида (псевдокод!):
def parse_while_node(tokens: List[Token], pos: int) -> TreeNode, int:
"""Принимает список токенов и позицию в нём, возвращает мини-дерево и новую позицию в списке."""
node = WhileNode() # узел дерева разбора, соответствующий циклу while
assert tokens[pos].type == 'while' # проверяем фиксированный токен, выкидываешь исключение если это не он
pos += 1
assert tokens[pos].type == '('
pos += 1
# обращаемся к другому правилу для разбора нетерминального символа ВЫРАЖЕНИЕ
# сохраняем мини-дерево для выражения условия и обновляем позицию
node.condition, pos = parse_expression_node(tokens, pos)
assert tokens[pos].type == ')'
pos += 1
# аналогично парсим нетерминал ОПЕРАТОР
node.body, pos = parse_operator_node(tokens, pos)
# возвращаем вызвавшему нас коду наше минидерево с узлом while на вершине,
# а также позицию где мы остановились
return node, pos
А для реализации правила вида
ОПЕРАТОР = ПРИСВАИВАНИЕ | ВЕТВЛЕНИЕ | ЦИКЛ_WHILE
можно будет сделать так:
def parse_operator_node(tokens: List[Token], pos: int) -> TreeNode, int:
variants = [parse_assignment_node, parse_if_node, parse_while_node]
for variant in variants:
try: # пробуем вариант из ветвления
node, pos = variant(tokens, pos)
except:
pass # вариант не подошёл - пробуем другой
else: # вариант подошёл
return node, pos
else: # ни один вариант не подошёл
raise Exception()
