Cómo configurar una gramática que pueda manejar la ambigüedad

Estoy tratando de crear una gramática para analizar algunas fórmulas similares a Excel que he ideado, donde un carácter especial al comienzo de una cadena significa una fuente diferente. Por ejemplo, $puede significar una cadena, por lo que " $This is text" se trataría como una entrada de cadena en el programa y &puede significar una función, por lo que &foo()se puede tratar como una llamada a la función interna foo.

El problema al que me enfrento es cómo construir la gramática correctamente. Por ejemplo, esta es una versión simplificada como 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')

Así pues, con esta gramática, cosas como: $This is a string, &foo(), &foo(#arg1), &foo($arg1,,#arg2)y &foo(!w1,w2,w3,,!w4,w5,w6)están todos analizados como se esperaba. Pero si quisiera agregar más flexibilidad a mi simpleterminal, entonces necesito comenzar a jugar con la SINGLESTRdefinición del token que no es conveniente.

Que he probado

La parte que no puedo superar es que si quiero tener una cadena que incluya paréntesis (que son literales de func), entonces no puedo manejarlos en mi situación actual.

• Si agrego los paréntesis SINGLESTR, obtengo Expected STARTSYMBOL, porque se está mezclando con la funcdefinición y cree que se debe pasar un argumento de función, lo cual tiene sentido.
• Si redefino la gramática para reservar el símbolo de ampersand solo para las funciones y agrego los paréntesis SINGLESTR, entonces puedo analizar una cadena con paréntesis, pero cada función que estoy tratando de analizar da Expected LPAR.

Mi intención es que cualquier cosa que comience con a $se analice como una SINGLESTRficha y luego pueda analizar cosas como &foo($first arg (has) parentheses,,$second arg).

Mi solución, por ahora, es que estoy usando palabras de 'escape' como LEFTPAR y RIGHTPAR en mis cadenas y he escrito funciones de ayuda para cambiarlas entre paréntesis cuando proceso el árbol. Entonces, $This is a LEFTPARtestRIGHTPARproduce el árbol correcto y cuando lo proceso, esto se traduce a This is a (test).

Para formular una pregunta general: ¿Puedo definir mi gramática de tal manera que algunos caracteres que son especiales para la gramática sean tratados como caracteres normales en algunas situaciones y como especiales en cualquier otro caso?

EDITAR 1

Basado en un comentario de jbndlrRevisé mi gramática para crear modos individuales basados ​​en el símbolo de inicio:

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
'''

Esto cae (algo) en mi segundo caso de prueba. Puedo analizar todos los simpletipos de cadenas (tokens TEXT, MD o DB que pueden contener paréntesis) y funciones que están vacías; por ejemplo, &foo()o &foo(&bar())analizar correctamente. En el momento en que pongo un argumento dentro de una función (no importa qué tipo), obtengo un UnexpectedEOF Error: Expected ampersand, RPAR or ARGSEP. Como prueba de concepto, si elimino los paréntesis de la definición de SINGLESTR en la nueva gramática anterior, entonces todo funciona como debería, pero vuelvo al punto de partida.

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)")

Salida:

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

Espero que sea lo que estabas buscando.

Esos han sido locos unos días. Traté de alondra y fallé. También intentépersimonious y pyparsing. Todos estos analizadores diferentes tenían el mismo problema con el token 'argumento' que consumía el paréntesis correcto que era parte de la función, y finalmente fallaba porque los paréntesis de la función no estaban cerrados.

El truco consistía en descubrir cómo se define un paréntesis correcto que "no es especial". Vea la expresión regular para MIDTEXTRPARen el código anterior. Lo definí como un paréntesis correcto que no es seguido por la separación de argumentos o por el final de la cadena. Lo hice usando la extensión de expresión regular (?!...)que coincide solo si no es seguida ...pero no consume caracteres. Afortunadamente, incluso permite que el final de la cadena coincida dentro de esta extensión especial de expresión regular.

EDITAR:

El método mencionado anteriormente solo funciona si no tiene un argumento que termine con a), porque entonces la expresión regular MIDTEXTRPAR no captará eso) y pensará que ese es el final de la función a pesar de que hay más argumentos para procesar. Además, puede haber ambigüedades como ... asdf) ,, ..., puede ser el final de una declaración de función dentro de un argumento, o un 'texto') dentro de un argumento y la declaración de función continúa.

Este problema está relacionado con el hecho de que lo que describe en su pregunta no es una gramática libre de contexto ( https://en.wikipedia.org/wiki/Context-free_grammar ) para la que existen analizadores como la alondra. En cambio, es una gramática sensible al contexto ( https://en.wikipedia.org/wiki/Context-sensitive_grammar ).

La razón de que sea una gramática sensible al contexto es porque necesita que el analizador 'recuerde' que está anidado dentro de una función y cuántos niveles de anidamiento hay, y que esta memoria está disponible dentro de la sintaxis de la gramática de alguna manera.

EDIT2:

También eche un vistazo al siguiente analizador que es sensible al contexto y parece resolver el problema, pero tiene una complejidad de tiempo exponencial en el número de funciones anidadas, ya que trata de analizar todas las posibles barreras de función hasta que encuentre una que funcione. Creo que tiene que tener una complejidad exponencial ya que no está libre de contexto.

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

El problema es que los argumentos de función están encerrados entre paréntesis, donde uno de los argumentos puede contener paréntesis.
Una de las posibles soluciones es usar la tecla de retroceso \ before (o) cuando es parte de String

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

Solución similar utilizada por C, para incluir comillas dobles (") como parte de la constante de cadena donde la constante de cadena está entre comillas dobles.

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

La salida es

   start
     func
       f
       simple   !g\(

   start
     func
      f
      simple    #g