Зацикливание шага разбора в PLY Python 3 - PullRequest
Новая
       26

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

0 голосов
/ 31 декабря 2018

В настоящее время я использую 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 ().Есть ли способ, где я мог бы просто получить хороший и чистый AST, как это: 

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

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

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

1 Ответ

0 голосов
/ 31 декабря 2018

Если вы используете контекстно-свободную грамматику, вы не можете анализировать ввод неограниченной длины без использования рекурсии, потому что рекурсия - это способ выражения неограниченного повторения в контекстно-свободной грамматике.Это влияет на формальное синтаксическое дерево, но нет абсолютно никакой причины, по которой вашему абстрактному синтаксическому дереву (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 в виде списка, это просто прекрасно.Операция Python append может быть очень полезна для этого.

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

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 состоит только из ACTION с, маркировка каждого элемента в списке как ACTION представляется избыточной.Но вы можете вставить ACTION, если хотите.)

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

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

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

...