Como configurar uma gramática que pode lidar com ambiguidade

Estou tentando criar uma gramática para analisar algumas fórmulas semelhantes ao Excel que eu criei, onde um caractere especial no início de uma seqüência de caracteres significa uma fonte diferente. Por exemplo, $pode significar uma string, portanto " $This is text" seria tratada como uma entrada de string no programa e &pode significar uma função, &foo()podendo ser tratada como uma chamada para a função interna foo.

O problema que estou enfrentando é como construir a gramática corretamente. Por exemplo, esta é uma versão simplificada como um 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')

Assim, com esta gramática, coisas como: $This is a string, &foo(), &foo(#arg1), &foo($arg1,,#arg2)e &foo(!w1,w2,w3,,!w4,w5,w6)são analisados como esperado. Mas se eu quiser adicionar mais flexibilidade ao meu simpleterminal, preciso começar a mexer na SINGLESTRdefinição do token que não é conveniente.

O que eu tentei

A parte que eu não consigo superar é que, se eu quero ter uma string incluindo parênteses (que são literais de func), não posso lidar com eles na minha situação atual.

• Se eu adicionar os parênteses SINGLESTR, entendo Expected STARTSYMBOL, porque ele está se confundindo com a funcdefinição e pensa que um argumento de função deve ser passado, o que faz sentido.
• Se eu redefinir a gramática para reservar o símbolo "comercial" apenas para funções e adicionar parênteses SINGLESTR, posso analisar uma string com parênteses, mas todas as funções que estou tentando analisar fornecem Expected LPAR.

Minha intenção é que qualquer coisa que comece com a $seja analisada como um SINGLESTRtoken e então eu poderia analisar coisas como &foo($first arg (has) parentheses,,$second arg).

Minha solução, por enquanto, é que estou usando palavras de 'escape' como LEFTPAR e RIGHTPAR em minhas strings e escrevi funções auxiliares para transformá-las em parênteses quando processo a árvore. Então, $This is a LEFTPARtestRIGHTPARproduz a árvore correta e quando eu a processo, isso é traduzido para This is a (test).

Para formular uma pergunta geral: Posso definir minha gramática de forma que alguns caracteres especiais para a gramática sejam tratados como caracteres normais em algumas situações e como especiais em qualquer outro caso?

EDIT 1

Com base em um comentário jbndlr, revisei minha gramática para criar modos individuais com base no símbolo de início:

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

Isso cai (um pouco) no meu segundo caso de teste. Eu posso analisar todos os simpletipos de strings (tokens TEXT, MD ou DB que podem conter parênteses) e funções vazias; por exemplo, &foo()ou &foo(&bar())analise corretamente. No momento em que coloco um argumento em uma função (não importa qual tipo), recebo um UnexpectedEOF Error: Expected ampersand, RPAR or ARGSEP. Como prova de conceito, se eu remover os parênteses da definição de SINGLESTR na nova gramática acima, tudo funcionará como deveria, mas estou de volta à estaca zero.

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

Resultado:

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 seja o que você estava procurando.

Esses foram dias loucos. Eu tentei cotovia e falhei. Eu também tentei persimoniouse pyparsing. Todos esses analisadores diferentes tiveram o mesmo problema com o token 'argumento' consumindo o parêntese correto que fazia parte da função, eventualmente falhando porque os parênteses da função não foram fechados.

O truque foi descobrir como você define um parêntese correto que "não é especial". Veja a expressão regular MIDTEXTRPARno código acima. Eu o defini como um parêntese à direita que não é seguido pela separação de argumentos ou pelo final da string. Fiz isso usando a extensão de expressão regular, (?!...)que corresponde apenas se não for seguida, ...mas não consumir caracteres. Felizmente, ele ainda permite o final da sequência de caracteres dentro dessa extensão especial de expressão regular.

EDITAR:

O método mencionado acima só funciona se você não tiver um argumento que termina com a), porque a expressão regular MIDTEXTRPAR não entenderá isso) e pensará que esse é o fim da função, embora haja mais argumentos a serem processados. Além disso, pode haver ambiguidades como ... asdf) ,, ..., pode ser o fim de uma declaração de função dentro de um argumento ou um 'tipo texto') dentro de um argumento e a declaração da função continua.

Esse problema está relacionado ao fato de que o que você descreve na sua pergunta não é uma gramática livre de contexto ( https://en.wikipedia.org/wiki/Context-free_grammar ) para a qual existem analisadores como cotovia. Em vez disso, é uma gramática sensível ao contexto ( https://en.wikipedia.org/wiki/Context-sensitive_grammar ).

A razão para ser uma gramática sensível ao contexto é porque você precisa que o analisador 'lembre-se' de que está aninhado dentro de uma função e de quantos níveis de aninhamento existem e que essa memória está disponível na sintaxe da gramática de alguma forma.

EDIT2:

Observe também o analisador a seguir, sensível ao contexto e que parece resolver o problema, mas tem uma complexidade de tempo exponencial no número de funções aninhadas, pois tenta analisar todas as possíveis barreiras de funções até encontrar uma que funcione. Eu acredito que tem que ter uma complexidade exponencial, pois não é livre 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())

O problema é que os argumentos da função estão entre parênteses, onde um dos argumentos pode conter parênteses.
Uma das soluções possíveis é usar backspace \ before (ou) quando faz parte do String

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

Solução semelhante usada por C, para incluir aspas duplas (") como parte da constante de string, em que a constante de string é colocada entre aspas duplas.

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

Saída é

   start
     func
       f
       simple   !g\(

   start
     func
      f
      simple    #g