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

9

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.

Dima1982
fuente
Tienes caracteres que identifican lo que viene después de ellos (tu STARTSYMBOL) y agregas separadores y paréntesis cuando es necesario que sean claros; No veo ninguna ambigüedad aquí. Aún tendría que dividir su STARTSYMBOLlista en elementos individuales para poder distinguirlos.
jbndlr
Voy a publicar una respuesta muy pronto, he estado trabajando en ello durante varios días.
iliar
Le di una respuesta. Aunque solo faltan 2 horas para que caduque la recompensa, aún puede otorgarla manualmente en el siguiente período de gracia de 24 horas. Si mi respuesta no es buena, dígamelo pronto y lo arreglaré.
iliar

Respuestas:

3
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())
iliar
fuente
1
¡Gracias, esto funciona según lo previsto! Otorga la recompensa ya que no necesitas escapar de los paréntesis de ninguna manera. Usted hizo un esfuerzo adicional y se nota! Todavía existe el caso límite de un argumento de 'texto' que termina con un paréntesis, pero tendré que vivir con ese. También explicaste las ambigüedades de una manera clara y solo tendré que probarlo un poco más, pero creo que para mis propósitos esto funcionará muy bien. Gracias por proporcionar también más información sobre la gramática sensible al contexto. ¡Realmente lo aprecio!
Dima1982
@ Dima1982 Muchas gracias!
iliar
@ Dima1982 Eche un vistazo a la edición, hice un analizador que quizás pueda resolver su problema a costa de una complejidad de tiempo exponencial. Además, lo pensé y si su problema tiene un valor práctico, escapar de los paréntesis podría ser la solución más simple. O convertir la función entre paréntesis en otra cosa, como delimitar el final de una lista de argumentos de funciones con, &por ejemplo.
iliar
1

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
Venkatesh Nandigama
fuente
Creo que es más o menos lo mismo que la propia solución de OP de reemplazar "(" y ")" con LEFTPAR y RIGHTPAR.
iliar