Jak skonfigurować gramatykę, która może obsługiwać dwuznaczność

Próbuję utworzyć gramatykę, aby przeanalizować niektóre formuły podobne do Excela, które opracowałem, gdzie znak specjalny na początku łańcucha oznacza inne źródło. Na przykład $może oznaczać ciąg znaków, więc „ $This is text” byłby traktowany jako wejście łańcucha w programie i &może oznaczać funkcję, więc &foo()może być traktowany jako wywołanie funkcji wewnętrznej foo.

Problem, przed którym stoję, polega na tym, jak poprawnie zbudować gramatykę. Na przykład jest to uproszczona wersja jako 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')

Tak, z tym gramatyki, rzeczy takie jak: $This is a string, &foo(), &foo(#arg1), &foo($arg1,,#arg2)i &foo(!w1,w2,w3,,!w4,w5,w6)są przetwarzane zgodnie z oczekiwaniami. Ale jeśli chcę dodać więcej elastyczności mojemu simpleterminalowi, muszę zacząć bawić się SINGLESTRdefinicją tokena, co nie jest wygodne.

Co próbowałem

Część, której nie mogę przejść, to to, że jeśli chcę mieć ciąg zawierający nawiasy (które są literałami func), to nie mogę sobie z nimi poradzić w obecnej sytuacji.

• Jeśli dodam nawiasy SINGLESTR, to dostaję Expected STARTSYMBOL, ponieważ miesza się z funcdefinicją i uważa, że ​​należy przekazać argument funkcji, co ma sens.
• Jeśli redefiniuję gramatykę, aby zarezerwować znak ampersand tylko dla funkcji i dodać nawiasy SINGLESTR, to mogę przeanalizować ciąg z nawiasami, ale każda funkcja, którą próbuję przeanalizować, daje Expected LPAR.

Moim zamiarem jest, aby wszystko zaczynające się od a $było analizowane jako SINGLESTRtoken, a następnie mogłem analizować takie rzeczy jak &foo($first arg (has) parentheses,,$second arg).

Moje rozwiązanie na razie polega na tym, że używam słów „ucieczki”, takich jak LEFTPAR i RIGHTPAR, i napisałem funkcje pomocnicze, aby zmienić je w nawiasy podczas przetwarzania drzewa. Tak więc $This is a LEFTPARtestRIGHTPARtworzy prawidłowe drzewo, a kiedy je przetwarzam, to zostaje przetłumaczone na This is a (test).

Aby sformułować ogólne pytanie: Czy mogę zdefiniować gramatykę w taki sposób, aby niektóre znaki, które są szczególne dla gramatyki, były traktowane jako normalne znaki w niektórych sytuacjach i jako specjalne w każdym innym przypadku?

EDYCJA 1

W oparciu o komentarz jbndlrzrewidowałem gramatykę, aby utworzyć poszczególne tryby w oparciu o symbol początkowy:

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

Dotyczy to (nieco) mojego drugiego przypadku testowego. Potrafię parsować wszystkie simpletypy ciągów (tokeny TEXT, MD lub DB, które mogą zawierać nawiasy) i funkcje, które są puste; na przykład &foo()lub &foo(&bar())parsuj poprawnie. W momencie umieszczenia argumentu w funkcji (bez względu na typ), otrzymuję UnexpectedEOF Error: Expected ampersand, RPAR or ARGSEP. Jako dowód na to, że jeśli usunę nawiasy z definicji SINGLESTR w nowej gramatyce powyżej, wszystko działa tak, jak powinno, ale wracam do pierwszego.

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

Wynik:

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

Mam nadzieję, że tego właśnie szukałeś.

To były szalone dni. Próbowałem skowronka i nie udało mi się. Też próbowałem persimoniousi pyparsing. Wszystkie te różne parsery miały ten sam problem z tym, że token argumentu zajmował właściwy nawias, który był częścią funkcji, ostatecznie zawodząc, ponieważ nawiasy funkcji nie były zamknięte.

Sztuczka polegała na tym, aby dowiedzieć się, jak zdefiniować właściwy nawias, który nie jest „specjalny”. Zobacz wyrażenie regularne MIDTEXTRPARw powyższym kodzie. Zdefiniowałem go jako właściwy nawias, po którym nie następuje separacja argumentów ani koniec łańcucha. Zrobiłem to, używając rozszerzenia wyrażenia regularnego, (?!...)które pasuje tylko wtedy, gdy nie następuje po nim, ...ale nie zużywa znaków. Na szczęście pozwala nawet dopasować koniec łańcucha w tym specjalnym rozszerzeniu wyrażenia regularnego.

EDYTOWAĆ:

Wyżej wymieniona metoda działa tylko wtedy, gdy nie masz argumentu kończącego się na a), ponieważ wtedy wyrażenie regularne MIDTEXTRPAR tego nie złapie) i pomyśli, że to koniec funkcji, mimo że jest więcej argumentów do przetworzenia. Mogą również występować niejasności, takie jak ... asdf) ,, ..., może to być koniec deklaracji funkcji wewnątrz argumentu lub „tekstowy”) wewnątrz argumentu i deklaracja funkcji trwa.

Problem ten związany jest z faktem, że to, co opisujesz w swoim pytaniu, nie jest gramatyką bezkontekstową ( https://en.wikipedia.org/wiki/Context-free_grammar ), dla której istnieją parsery takie jak skowronek. Zamiast tego jest to gramatyka kontekstowa ( https://en.wikipedia.org/wiki/Context-sensitive_grammar ).

Powodem tego, że jest gramatyką zależną od kontekstu, jest to, że potrzebujesz parsera, aby „zapamiętać”, że jest zagnieżdżony w funkcji i ile jest poziomów zagnieżdżenia, i mieć tę pamięć w jakiś sposób dostępną w składni gramatyki.

EDYCJA 2:

Spójrz również na następujący parser, który jest kontekstowy i wydaje się rozwiązać problem, ale ma wykładniczą złożoność czasową w liczbie zagnieżdżonych funkcji, ponieważ próbuje przeanalizować wszystkie możliwe bariery funkcji, dopóki nie znajdzie takiej, która działa. Uważam, że musi mieć wykładniczą złożoność, ponieważ nie jest pozbawiona kontekstu.

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

Problem polega na tym, że argumenty funkcji są zawarte w nawiasach, gdzie jeden z argumentów może zawierać nawiasy.
Jednym z możliwych rozwiązań jest użycie backspace \ przed (lub), gdy jest on częścią String

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

Podobne rozwiązanie stosowane przez C, w celu uwzględnienia podwójnych cudzysłowów („) jako części stałej łańcuchowej, gdzie stała łańcuchowa jest ujęta w podwójne cudzysłowy.

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

Dane wyjściowe to

   start
     func
       f
       simple   !g\(

   start
     func
      f
      simple    #g