Зацикливание шага разбора в PLY Python 3

Question

В настоящее время я использую Python 3 для анализа языка программирования, который я делаю. Мне интересно, как я могу сделать цикл правила синтаксического анализа.

Это может быть неясно, поэтому вот пример.

У меня есть код:

def c_parse():
    def p_program(p):
        "program : actions"
        p[0] = ("PROGRAM", p[1])

    def p_actions(p):
        """actions : action
                   | actions action"""
        if len(p) == 3:
            p[0] = ("ACTIONS", p[1], p[2])
        elif len(p) == 2:
            p[0] = ("ACTION", p[1])

    def p_action(p):
        """action : function_call ';'
                  | variable_dec ';'
                  | if_statement ';'"""
        p[0] = ("ACTION_STATEMENT", p[1])

    ...

Учитывая вход:

x = "HELLO WORLD";
print(x);
print(x);

Это выводит это AST:

('PROGRAM', ('ACTIONS', ('ACTIONS', ('ACTION', ('ACTION_STATEMENT', 
('VARIABLE_DEC', ... ))), 
('ACTION_STATEMENT', ('FUNCTION_CALL', ... ))), ('ACTION_STATEMENT', 
('FUNCTION_CALL', ... ))))

Обратите внимание, что ACTIONS и ACTION_STATEMENT очень грязные. Это происходит из-за рекурсивного правила, определенного в функции p_actions(). Есть ли способ, где я мог бы просто получить хороший и чистый АСТ, как это:

(PROGRAM, (ACTION, (VARIABLE_DEC, ... )), (ACTION, (FUNCTION_CALL, ... )),
(ACTION, (FUNCTION_CALL, ...)))

Другими словами, могу ли я сделать так, чтобы функция p_actions() могла анализировать бесконечное количество узлов ACTION без использования рекурсии? Это возможно?

Кстати, я на macOS, если это имеет значение.

Answer 1

Если вы используете контекстно-свободную грамматику, вы не можете анализировать ввод неограниченной длины без использования рекурсии, потому что рекурсия - это способ выражения неограниченного повторения в контекстно-свободной грамматике. Это влияет на формальное синтаксическое дерево, но нет абсолютно никаких причин, по которым ваше абстрактное синтаксическое дерево (AST) должно сохранять каждую деталь синтаксического анализа.

AST называется абстрактным именно потому, что он абстрагирует некоторые детали грамматики, которые не очень полезны для семантического анализа. Вы можете создать AST любым удобным вам способом; Там нет произвольных правил. (Существует эвристика: AST должен сохранять именно те функции дерева разбора, которые вам полезны, и не более.)

Особенно часто удаляют единичные производства из AST. (Единичное производство - это производство, правая часть которого состоит только из одного нетерминала, такого как actions: action) когда они не добавляют никакой полезной информации. Иногда производство с одним нетерминалом с правой стороны будет удалено из AST, даже если это строго не единичное правило. Это будет зависеть от того, имеет ли производство семантическое значение. Например, expression: '(' expression ')' скорее всего, будет опущено, хотя expression: '-' expression не является.

С точки зрения Ply, пропуск продукции состоит из простого прохождения значения с правой стороны. Например, вы можете иметь:

def unit_rule(p):
  """actions : action
     program : actions
  """
  p[0] = p[1]   # Pass through the non-terminal's value

def parens(p):
  """expr : LPAREN expr RPAREN"""
  p[0] = p[2]   # Pass through the non-terminal's value

Вы также не ограничены просто созданием синтаксических узлов, которые точно копируют грамматическую структуру. Если вы хотите, чтобы список был представлен в AST в виде списка, это просто прекрасно. Питона append операция может быть довольно полезной для этого.

Итак, один из возможных способов получить АСТ, который вам нужен, был бы:

start = 'program'

def p_actions(p):
    """actions : actions action"""
    p[1].append(p[2])
    p[0] = p[1]       

def p_actions1(p):
    """actions : action"""
    p[0] = ["ACTIONS", p[1]]

def p_unit(p):
    """program : actions"
       action  : function_call ';'
               | variable_dec ';'
               | if_statement ';'
    """
    p[0] = p[1]

Некоторые заметки о приведенном выше коде:

1. Я не видел смысла ACTION узлы, поэтому я просто пропустил сами утверждения в последнем правиле. поскольку actions состоит только из ACTIONs, отмечая каждый элемент в списке как ACTION кажется излишним. Но вы можете положить в ACTION если хотите.)

2. В приведенном выше коде ACTIONS узел - это список, а не кортеж; p_actions Функция намеренно не создает новый список каждый раз, когда добавляется новый элемент. Обычно это нормально и экономит кучу создания кортежей и сборку мусора. Предполагается, что передаваемое значение больше нигде не используется, что, безусловно, имеет место, но не всегда может быть правдой. Однако, если вы действительно хотите кортежи, это не проблема:

   def p_actions(p):
       """actions : actions action"""
       p[0] = p[1] + (p[2],)
   

3. Обратите внимание, что нет необходимости помещать все произведения для нетерминала в одну и ту же функцию анализа. Производства могут быть сгруппированы в функции, если их действия одинаковы. В целом, если вы обнаружите, что пытаетесь выяснить, какое производство вызвало срабатывание функции действия (if len(p) == 3(например)), тогда вы можете подумать о разделении произведений между двумя различными функциями, каждая из которых имеет безусловное действие.