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 simple
terminalowi, muszę zacząć bawić się SINGLESTR
definicją 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ę zfunc
definicją 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ć, dajeExpected LPAR
.
Moim zamiarem jest, aby wszystko zaczynające się od a $
było analizowane jako SINGLESTR
token, 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 LEFTPARtestRIGHTPAR
tworzy 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 jbndlr
zrewidował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 simple
typy 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.
źródło
STARTSYMBOL
) i dodajesz separatory i nawiasy tam, gdzie jest to wymagane; Nie widzę tu żadnych dwuznaczności. Nadal będziesz musiał podzielić swojąSTARTSYMBOL
listę na poszczególne elementy, aby można je było rozróżnić.Odpowiedzi:
Wynik:
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
persimonious
ipyparsing
. 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
MIDTEXTRPAR
w 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.
źródło
&
na przykład.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
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.
Dane wyjściowe to
źródło