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

Я пытаюсь создать грамматику для анализа некоторых формул, подобных Excel, которые я разработал, где специальный символ в начале строки обозначает другой источник. Например, $может означать строку, поэтому " $This is text" будет рассматриваться как строковый ввод в программе и &может означать функцию, поэтому &foo()может рассматриваться как вызов внутренней функции foo.

Проблема, с которой я сталкиваюсь, заключается в том, как правильно построить грамматику. Например, это упрощенная версия как MWE:

grammar = r'''start: instruction

?instruction: simple
            | func

STARTSYMBOL: "!"|"#"|"$"|"&"|"~"
SINGLESTR: (LETTER+|DIGIT+|"_"|" ")*
simple: STARTSYMBOL [SINGLESTR] (WORDSEP SINGLESTR)*
ARGSEP: ",," // argument separator
WORDSEP: "," // word separator
CONDSEP: ";;" // condition separator
STAR: "*"
func: STARTSYMBOL SINGLESTR "(" [simple|func] (ARGSEP simple|func)* ")"

%import common.LETTER
%import common.WORD
%import common.DIGIT
%ignore ARGSEP
%ignore WORDSEP
'''
parser = lark.Lark(grammar, parser='earley')

Таким образом, с этой грамматикой, такие вещи , как: $This is a string, &foo(), &foo(#arg1), &foo($arg1,,#arg2)и &foo(!w1,w2,w3,,!w4,w5,w6)все разобраны , как и ожидалось. Но если я хочу добавить больше гибкости своему simpleтерминалу, то мне нужно начать возиться с SINGLESTRопределением токена, что не удобно.

Что я пробовал

Часть, которую я не могу обойти, состоит в том, что если я хочу иметь строку, включающую скобки (которые являются литералами func), то я не могу обработать их в моей текущей ситуации.

• Если я добавлю круглые скобки SINGLESTR, то получу Expected STARTSYMBOL, потому что он смешивается с funcопределением и думает, что должен быть передан аргумент функции, что имеет смысл.
• Если я переопределю грамматику, чтобы зарезервировать символ амперсанда только для функций и добавить круглые скобки SINGLESTR, то я смогу разобрать строку с круглыми скобками, но каждая функция, которую я пытаюсь проанализировать, дает Expected LPAR.

Мое намерение состоит в том, что все, что начинается с a $, будет проанализировано как SINGLESTRтокен, и тогда я смогу разобрать такие вещи, как &foo($first arg (has) parentheses,,$second arg).

Мое решение, на данный момент, заключается в том, что я использую в своих строках слова escape, такие как LEFTPAR и RIGHTPAR, и я написал вспомогательные функции, чтобы преобразовать их в скобки при обработке дерева. Таким образом, $This is a LEFTPARtestRIGHTPARсоздается правильное дерево, и когда я его обрабатываю, это переводится в This is a (test).

Чтобы сформулировать общий вопрос: могу ли я определить мою грамматику таким образом, чтобы некоторые символы, которые являются особыми для грамматики, рассматривались как обычные символы в некоторых ситуациях и как особые в любом другом случае?

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

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

grammar = r'''start: instruction

?instruction: simple
            | func

SINGLESTR: (LETTER+|DIGIT+|"_"|" ") (LETTER+|DIGIT+|"_"|" "|"("|")")*
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
'''

Это подпадает (несколько) под мой второй контрольный пример. Я могу анализировать все simpleтипы строк (токены TEXT, MD или DB, которые могут содержать скобки) и функции, которые пусты; например, &foo()или &foo(&bar())правильно разобрать. В тот момент, когда я помещаю аргумент в функцию (независимо от типа), я получаю UnexpectedEOF Error: Expected ampersand, RPAR or ARGSEP. В качестве доказательства концепции, если я уберу скобки из определения SINGLESTR в новой грамматике выше, то все будет работать как надо, но я вернусь к исходной точке.

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в коде выше. Я определил его как правую скобку, за которой не следует разделение аргумента или конец строки. Я сделал это с помощью расширения регулярного выражения, (?!...)которое соответствует только в том случае, если за ним не следуют, ...но не используются символы. К счастью, он даже позволяет сопоставить конец строки внутри этого специального расширения регулярного выражения.

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

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

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

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

EDIT2:

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

_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())

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

  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