Как настроить грамматику, которая может справляться с двусмысленностью

import lark
grammar = r'''start: instruction

?instruction: simple
            | func

MIDTEXTRPAR: /\)+(?!(\)|,,|$))/
SINGLESTR: (LETTER+|DIGIT+|"_"|" ") (LETTER+|DIGIT+|"_"|" "|"("|MIDTEXTRPAR)*
FUNCNAME: (LETTER+) (LETTER+|DIGIT+|"_")* // no parentheses allowed in the func name
DB: "!" SINGLESTR (WORDSEP SINGLESTR)*
TEXT: "$" SINGLESTR
MD: "#" SINGLESTR
simple: TEXT|DB|MD
ARGSEP: ",," // argument separator
WORDSEP: "," // word separator
CONDSEP: ";;" // condition separator
STAR: "*"
func: "&" FUNCNAME "(" [simple|func] (ARGSEP simple|func)* ")"

%import common.LETTER
%import common.WORD
%import common.DIGIT
%ignore ARGSEP
%ignore WORDSEP
'''

parser = lark.Lark(grammar, parser='earley')
parser.parse("&foo($first arg (has) parentheses,,$second arg)")

Выход:

Tree(start, [Tree(func, [Token(FUNCNAME, 'foo'), Tree(simple, [Token(TEXT, '$first arg (has) parentheses')]), Token(ARGSEP, ',,'), Tree(simple, [Token(TEXT, '$second arg')])])])

Надеюсь, это то, что вы искали.

Это были сумасшедшие несколько дней. Я пробовал жаворонок и потерпел неудачу. Я также пробовал persimonious и pyparsing. У всех этих различных синтаксических анализаторов была одна и та же проблема с токеном «аргумент», использующим правильную скобку, которая была частью функции, и в конечном итоге терпела неудачу, потому что скобки функции не были закрыты.

Хитрость заключалась в том, чтобы выяснить, как определить правую скобку, которая не является особенной. См. регулярное выражение для MIDTEXTRPAR в приведенном выше коде. Я определил его как правую скобку, за которой не следует разделение аргументов или конец строки. Я сделал это, используя расширение регулярного выражения (?!...), которое соответствует, только если за ним не следует ..., но не использует символы. К счастью, он даже позволяет сопоставлять конец строки внутри этого специального расширения регулярного выражения.

РЕДАКТИРОВАТЬ:

Вышеупомянутый метод работает только в том случае, если у вас нет аргумента, оканчивающегося на ), потому что тогда регулярное выражение MIDTEXTRPAR не поймает это ) и будет думать, что это конец функции, даже если есть больше аргументов для обработки. Кроме того, могут быть двусмысленности, такие как ...asdf),,..., это может быть конец объявления функции внутри аргумента или «текстовый») внутри аргумента, и объявление функции продолжается.

Эта проблема связана с тем, что то, что вы описываете в своем вопросе, не является контекстно-свободной грамматикой (https://en.wikipedia.org/wiki/Context-free_grammar), для которых существуют парсеры, такие как lark. Вместо этого это контекстно-зависимая грамматика (https://en.wikipedia.org/wiki/Context-sensitive_grammar).

Причина того, что это контекстно-зависимая грамматика, заключается в том, что вам нужно, чтобы синтаксический анализатор «помнил», что он вложен внутри функции, и сколько существует уровней вложенности, и каким-то образом эта память доступна внутри синтаксиса грамматики.

РЕДАКТИРОВАТЬ2:

Также взгляните на следующий синтаксический анализатор, который является контекстно-зависимым и, кажется, решает проблему, но имеет экспоненциальную временную сложность по количеству вложенных функций, поскольку он пытается проанализировать все возможные функциональные барьеры, пока не найдет тот, который работает. Я считаю, что он должен иметь экспоненциальную сложность, поскольку он не является контекстно-свободным.

_funcPrefix = '&'
_debug = False

class ParseException(Exception):
    pass

def GetRecursive(c):
    if isinstance(c,ParserBase):
        return c.GetRecursive()
    else:
        return c

class ParserBase:
    def __str__(self):
        return type(self).__name__ + ": [" + ','.join(str(x) for x in self.contents) +"]"
    def GetRecursive(self):
        return (type(self).__name__,[GetRecursive(c) for c in self.contents])

class Simple(ParserBase):
    def __init__(self,s):
        self.contents = [s]

class MD(Simple):
    pass

class DB(ParserBase):
    def __init__(self,s):
        self.contents = s.split(',')

class Func(ParserBase):
    def __init__(self,s):
        if s[-1] != ')':
            raise ParseException("Can't find right parenthesis: '%s'" % s)
        lparInd = s.find('(')
        if lparInd < 0:
            raise ParseException("Can't find left parenthesis: '%s'" % s)
        self.contents = [s[:lparInd]]
        argsStr = s[(lparInd+1):-1]
        args = list(argsStr.split(',,'))
        i = 0
        while i<len(args):
            a = args[i]
            if a[0] != _funcPrefix:
                self.contents.append(Parse(a))
                i += 1
            else:
                j = i+1
                while j<=len(args):
                    nestedFunc = ',,'.join(args[i:j])
                    if _debug:
                        print(nestedFunc)
                    try:
                        self.contents.append(Parse(nestedFunc))
                        break
                    except ParseException as PE:
                        if _debug:
                            print(PE)
                        j += 1
                if j>len(args):
                    raise ParseException("Can't parse nested function: '%s'" % (',,'.join(args[i:])))
                i = j

def Parse(arg):
    if arg[0] not in _starterSymbols:
        raise ParseException("Bad prefix: " + arg[0])
    return _starterSymbols[arg[0]](arg[1:])

_starterSymbols = {_funcPrefix:Func,'$':Simple,'!':DB,'#':MD}

P = Parse("&foo($first arg (has)) parentheses,,&f($asdf,,&nested2($23423))),,&second(!arg,wer))")
print(P)

import pprint
pprint.pprint(P.GetRecursive())

Проблема заключается в том, что аргументы функции заключены в круглые скобки, где один из аргументов может содержать круглые скобки.
Одним из возможных решений является использование возврата \ перед ( или ), когда он является частью строки.

  SINGLESTR: (LETTER+|DIGIT+|"_"|" ") (LETTER+|DIGIT+|"_"|" "|"\("|"\)")*

Аналогичное решение, используемое C, для включения двойных кавычек ("") как части строковой константы, где строковая константа заключена в двойные кавычки.

  example_string1='&f(!g\()'
  example_string2='&f(#g)'
  print(parser.parse(example_string1).pretty())
  print(parser.parse(example_string2).pretty())

Выход

   start
     func
       f
       simple   !g\(

   start
     func
      f
      simple    #g