Comment configurer une grammaire capable de gérer l'ambiguïté

J'essaie de créer une grammaire pour analyser certaines formules de type Excel que j'ai conçues, où un caractère spécial au début d'une chaîne signifie une source différente. Par exemple, $peut signifier une chaîne, donc " $This is text" serait traité comme une entrée de chaîne dans le programme et &peut signifier une fonction, donc &foo()peut être traité comme un appel à la fonction interne foo.

Le problème auquel je suis confronté est de savoir comment construire correctement la grammaire. Par exemple, il s'agit d'une version simplifiée en tant que 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')

Ainsi, avec cette grammaire, des choses comme: $This is a string, &foo(), &foo(#arg1), &foo($arg1,,#arg2)et &foo(!w1,w2,w3,,!w4,w5,w6)sont tous analysés comme prévu. Mais si je souhaite ajouter plus de flexibilité à mon simpleterminal, je dois commencer à bidouiller avec la SINGLESTRdéfinition de jeton, ce qui n'est pas pratique.

Qu'est-ce que j'ai essayé

La partie que je ne peux pas dépasser est que si je veux avoir une chaîne comprenant des parenthèses (qui sont des littéraux de func), je ne peux pas les gérer dans ma situation actuelle.

• Si j'ajoute les parenthèses SINGLESTR, alors j'obtiens Expected STARTSYMBOL, car cela se confond avec la funcdéfinition et il pense qu'un argument de fonction devrait être passé, ce qui est logique.
• Si je redéfinis la grammaire pour réserver le symbole esperluette aux fonctions uniquement et que j'ajoute les parenthèses SINGLESTR, je peux analyser une chaîne avec des parenthèses, mais chaque fonction que j'essaie d'analyser donne Expected LPAR.

Mon intention est que tout ce qui commence par un $soit analysé comme un SINGLESTRjeton et que je puisse ensuite analyser des choses comme &foo($first arg (has) parentheses,,$second arg).

Ma solution, pour l'instant, est que j'utilise des mots «d'échappement» comme LEFTPAR et RIGHTPAR dans mes chaînes et j'ai écrit des fonctions d'aide pour les changer entre parenthèses lorsque je traite l'arbre. Donc, $This is a LEFTPARtestRIGHTPARproduit le bon arbre et quand je le traite, cela se traduit par This is a (test).

Pour formuler une question générale: Puis-je définir ma grammaire de telle manière que certains caractères qui sont spéciaux à la grammaire sont traités comme des caractères normaux dans certaines situations et comme spéciaux dans tous les autres cas?

EDIT 1

Sur la base d'un commentaire de jbndlrj'ai révisé ma grammaire pour créer des modes individuels basés sur le symbole de départ:

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

Cela relève (quelque peu) de mon deuxième cas de test. Je peux analyser tous les simpletypes de chaînes (jetons TEXT, MD ou DB qui peuvent contenir des parenthèses) et les fonctions qui sont vides; par exemple, &foo()ou &foo(&bar())analyser correctement. Au moment où je mets un argument dans une fonction (quel que soit le type), j'obtiens un UnexpectedEOF Error: Expected ampersand, RPAR or ARGSEP. Comme preuve de concept, si je retire les parenthèses de la définition de SINGLESTR dans la nouvelle grammaire ci-dessus, alors tout fonctionne comme il se doit, mais je reviens à la case départ.

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

Production:

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

J'espère que c'est ce que vous cherchiez.

Ça a été fou quelques jours. J'ai essayé l'alouette et j'ai échoué. J'ai aussi essayé persimoniouset pyparsing. Tous ces différents analyseurs ont tous eu le même problème avec le jeton «argument» consommant la bonne parenthèse qui faisait partie de la fonction, échouant finalement parce que les parenthèses de la fonction n'étaient pas fermées.

L'astuce était de comprendre comment définir une bonne parenthèse qui n'est "pas spéciale". Voir l'expression régulière pour MIDTEXTRPARdans le code ci-dessus. Je l'ai défini comme une parenthèse droite qui n'est pas suivie d'une séparation d'arguments ou d'une fin de chaîne. J'ai fait cela en utilisant l'extension d'expression régulière (?!...)qui ne correspond que si elle n'est pas suivie ...mais ne consomme pas de caractères. Heureusement, il permet même de faire correspondre la fin de la chaîne à l'intérieur de cette extension d'expression régulière spéciale.

ÉDITER:

La méthode mentionnée ci-dessus ne fonctionne que si vous n'avez pas d'argument se terminant par a), car alors l'expression régulière MIDTEXTRPAR ne captera pas cela) et pensera que c'est la fin de la fonction même s'il y a plus d'arguments à traiter. En outre, il peut y avoir des ambiguïtés telles que ... asdf) ,, ..., il peut s'agir de la fin d'une déclaration de fonction à l'intérieur d'un argument, ou d'un "texte-like") à l'intérieur d'un argument et la déclaration de fonction continue.

Ce problème est lié au fait que ce que vous décrivez dans votre question n'est pas une grammaire sans contexte ( https://en.wikipedia.org/wiki/Context-free_grammar ) pour laquelle des analyseurs tels que lark existent. Il s'agit plutôt d'une grammaire contextuelle ( https://en.wikipedia.org/wiki/Context-sensitive_grammar ).

La raison pour laquelle il s'agit d'une grammaire contextuelle est parce que vous avez besoin que l'analyseur se souvienne qu'elle est imbriquée dans une fonction, et combien de niveaux d'imbrication il y a, et que cette mémoire soit disponible dans la syntaxe de la grammaire d'une manière ou d'une autre.

EDIT2:

Jetez également un œil à l'analyseur suivant qui est contextuel et semble résoudre le problème, mais a une complexité temporelle exponentielle dans le nombre de fonctions imbriquées, car il essaie d'analyser toutes les barrières de fonction possibles jusqu'à ce qu'il en trouve une qui fonctionne. Je crois qu'il doit avoir une complexité exponentielle, car il n'est pas sans contexte.

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

Le problème est que les arguments de la fonction sont placés entre parenthèses où l'un des arguments peut contenir des parenthèses.
Une des solutions possibles est d'utiliser backspace \ before (ou) quand il fait partie de String

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

Solution similaire utilisée par C, pour inclure des guillemets doubles (") en tant que partie de constante de chaîne où la constante de chaîne est placée entre guillemets doubles.

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

La sortie est

   start
     func
       f
       simple   !g\(

   start
     func
      f
      simple    #g