Pyparsing - грамматика с рекурсией

Question

Я пытаюсь создать грамматику, которая будет анализировать следующие выражения:

1. func()

2. func(a)

3. func(a) + func(b)

4. func(func(a) + func()) + func(b)

Я реализовал это для (1) и (2),но как только я расширил rvalue << (identifier | function_call) на operation, он перестал работать из-за:

Exception raised:Expected W:(ABCD...), found ')'  (at char 5), (line:1, col:6)
Exception raised:maximum recursion depth exceeded

Может кто-нибудь из вас объяснить, почему?Насколько я понял в выражении rvalue << (identifier | function_call | operation) function_call должно совпадать до operation, и рекурсия не должна иметь место.

Код:

from pyparsing import Forward, Optional, Word, Literal, alphanums, delimitedList

rvalue = Forward()

operation = rvalue + Literal('+') + rvalue
identifier = Word(alphanums + '_')('identifier')
function_args = delimitedList(rvalue)('function_args')

function_name = identifier('function_name')
function_call = (
    (function_name + Literal("(") + Optional(function_args) + Literal(")"))
)('function_call')

rvalue << (identifier | function_call | operation)
function_call.setDebug()


def test_function_call_no_args():
    bdict = function_call.parseString("func()", parseAll=True).asDict()
    assert bdict['function_name'] == 'func'
    assert 'function_args' not in bdict


def test_function_call_one_arg():
    bdict = function_call.parseString("func(arg)", parseAll=True).asDict()
    assert bdict['function_name'] == 'func'
    assert 'function_args' in bdict


def test_function_call_many_args():
    bdict = function_call.parseString("func(arg1, arg2)", parseAll=True).asDict()
    assert bdict['function_name'] == 'func'
    assert 'function_args' in bdict

Answer 1

Насколько я понял в выражении rvalue << (identifier | function_call | operation) function_call должен быть сопоставлен до операции, и рекурсия не должна иметь место.

Рекурсия не выполняется, если один изпредыдущие альтернативы успешны.Но если оба сбоя, operation пробуется и вы получаете бесконечную рекурсию.

Например, в test_function_call_no_args вы пытаетесь проанализировать func(), используя правило function_call.Это будет анализировать func как имя функции и ( как начало списка аргументов.Затем он попытается выполнить синтаксический анализ Optional(function_args), который, в свою очередь, попытается выполнить синтаксический анализ delimitedList(rvalue).Теперь это попытается проанализировать rvalue, и поскольку ) не соответствует первым двум альтернативам, он попробует последний, что приведет к бесконечной рекурсии.

Когда правило рекурсивное, вывсегда должен потреблять входные данные до достижения рекурсии - не должно быть возможности достичь рекурсии без использования входных данных.Таким образом, рекурсия, стоящая последним в альтернативе, недостаточна - должно быть еще одно не необязательное правило (которое также не совпадает с пустой строкой), которое должно быть успешно запущено перед ним.

PS: rvalue так как это может фактически никогда не совпадать с вызовом функции, потому что вызовы функций начинаются с идентификатора, и вы сначала сопоставляете identifier.