Czy istnieje programowania (lub skrypty) język (lub jakiś specyficzny język domeny) o dwóch operatorów binarnych opl
i opr
od samego pierwszeństwa przy opl
czym lewy asocjacyjne i opr
bycia prawym asocjacyjne?
(Nie mogę znaleźć takiego przykładu, ale próbuję napisać parser na tyle ogólny, aby poradził sobie z tym dziwnym przypadkiem)
Jak parsowane byłyby wyrażenia postaci x opl
y opr
z lub x opr
y opl
z ? A bardziej ogólnie z jeszcze większą liczbą operandów?
language-design
parsing
Basile Starynkevitch
źródło
źródło
x <@ y @> z
z<@
czym lewy asocjacyjne i@>
bycia prawym asocjacyjne, GHC daje „pierwszeństwo parsowania błąd”: „Nie można mieszać«<@
»[infixl 0]«@>
»[infixr 0] w tym samym wyrażeniu Infix” (gdzie zdefiniowane operatorzy na poziomie 0 na przykład).if_then_else_
lub[1;2;3]
zostanie zdefiniowany w bibliotekach?).Odpowiedzi:
Oto trzy języki, które pozwalają zdefiniować własnych operatorów, którzy robią dwie i pół różne rzeczy! Haskell i Coq nie pozwalają na tego rodzaju shenanigany - ale inaczej - podczas gdy Agda pozwala na takie mieszanie skojarzeń.
Po pierwsze, w Haskell po prostu nie wolno ci tego robić. Możesz zdefiniować własnych operatorów i nadać im pierwszeństwo (od 0–9) i wybrane przez siebie skojarzenie. Jednak raport Haskella zabrania mieszania skojarzeń :
Tak więc w GHC , jeśli zdefiniujemy
infixl
operator lewostronny ( )<@
i prawostronny@>
na tym samym poziomie pierwszeństwa - powiedzmy 0 - wtedy ocenax <@ y @> z
daje błąd(W rzeczywistości można również zadeklarować, że operator jest nieoznaczony, ale nie jest skojarzony, na przykład
==
, więcx == y == z
jest to błąd składniowy!)Z drugiej strony istnieje zależna od języka pisarka / twierdzarka Agda (która, co prawda, jest znacznie mniej popularna). Agda ma jedne z najbardziej plastycznych składni w dowolnym języku, który znam, obsługując operatory mixfix : standardowa biblioteka zawiera funkcję
który po wywołaniu jest napisany
z argumentami wypełniającymi podkreślenia! Wspominam o tym, ponieważ oznacza to, że musi obsługiwać niezwykle elastyczną analizę. Naturalnie Agda ma również deklaracje stałość (choć jej poziom pierwszeństwa wynosić ponad dowolnych liczb naturalnych i są zwykle w 0-100), a Agda nie pozwalają mieszać operatorów o tym samym priorytecie, ale różnych fixities. Nie mogę jednak znaleźć informacji na ten temat w dokumentacji, więc musiałem eksperymentować.
Użyjmy ponownie naszego
<@
i@>
z góry. W dwóch prostych przypadkach mamyx <@ y @> z
parsowanie jakox <@ (y @> z)
; ix @> y <@ z
parsowanie jako(x @> y) <@ z
.Myślę, że to , co robi Agda, to pogrupowanie wiersza na fragmenty „lewostronnie asocjacyjne” i „prawostronne” i - chyba że myślę o czymś złym - fragment prawostronny ma „priorytet” w przejmowaniu sąsiednich argumentów. To nam daje
parsowanie jako
lub
Jednak pomimo moich eksperymentów pomyliłem się, kiedy napisałem to po raz pierwszy, co może być pouczające :-)
(A Agda, podobnie jak Haskell, ma niepowiązane operatory, które poprawnie podają błędy analizy, więc mieszane skojarzenia mogłyby również spowodować błąd analizy).
Wreszcie istnieje Coq -prover / zależnie typowany język , który ma jeszcze bardziej elastyczną składnię niż Agda, ponieważ jego rozszerzenia składniowe są w rzeczywistości implementowane poprzez podanie specyfikacji nowych konstrukcji składniowych, a następnie przepisanie ich na język podstawowy (niejasno podobny do makr , Przypuszczam). W Coq składnia listy
[1; 2; 3]
jest opcjonalnym importem ze standardowej biblioteki. Nowe składnie mogą nawet wiązać zmienne!Po raz kolejny w Coq możemy zdefiniować własnych operatorów infix i nadać im poziomy pierwszeństwa (głównie od 0 do 99) oraz powiązania. Jednak w Coq każdy poziom pierwszeństwa może mieć tylko jedno skojarzenie . Więc jeśli zdefiniujemy
<@
jako lewostronny, a następnie spróbujemy zdefiniować@>
jako prawostronny na tym samym poziomie - powiedzmy 50 - otrzymamyWiększość operatorów w Coq znajduje się na poziomach, które można podzielić przez 10; jeśli miałem problemy z asocjatywnością (te poziomy są globalne), generalnie po prostu podniosłem poziom o jeden w dowolnym kierunku (zwykle w górę).
źródło
graphviz
?)\ttfamily \Tree[.<@ [.<@ [.<@ a b ] [.@> c [.@> d [.@> e f ]]]] g ]
.Od czasu, gdy zostały spopularyzowane przez Douglasa Crockforda, parsery Pratt (lub parsery Top-Down Operator Precedence) zaczęły być coraz bardziej popularne. Te parsery działają na podstawie tabeli pierwszeństwa i asocjatywności operatora, a nie mają wbudowanych reguł w stałej gramatyce, więc są pomocne w językach, które pozwalają użytkownikom definiować własnych operatorów.
Mają funkcję parsowania, która działa najpierw analizując lewy termin wyrażenia, a następnie rekurencyjnie wiąże nowe operatory i prawe terminy, o ile odpowiednio się wiążą. Operatory lewostronnie wiążą prawe terminy, które mają pierwszeństwo aż do tego samego pierwszeństwa, a operatory prawostronne wiążą tylko ich poziom pierwszeństwa, ale go nie uwzględniają. Wierzę, że skutkuje to tym samym drzewem parsowania, co w przypadku Agdy, cytowanym powyżej.
źródło