język z dwoma operatorami binarnymi o tym samym priorytecie, lewostronny i prawostronny

11

Czy istnieje programowania (lub skrypty) język (lub jakiś specyficzny język domeny) o dwóch operatorów binarnych opli oprod samego pierwszeństwa przy oplczym lewy asocjacyjne i oprbycia 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?

Basile Starynkevitch
źródło
4
Jeśli to boli, nie rób tego.
CodesInChaos
1
W Haskell możesz zdefiniować własnych operatorów infix z ich własnymi pierwszeństwami, w tym przypadku pojawia się błąd; jeśli masz x <@ y @> zz <@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).
Antal Spector-Zabusky
@ AntalSpector-Zabusky: To byłaby świetna odpowiedź!
Basile Starynkevitch
@ AntalSpector-Zabusky: To samo w Swift. Wydaje mi się, że możesz zdefiniować operatory, ale w wyrażeniu musisz użyć wszystkich lewych asocjacyjnych lub wszystkich prawych asocjacyjnych operatorów z takim samym pierwszeństwem. Możesz więc użyć x leftop y leftop z lub x rightop y rightop z, ale nie x x leftop y rightop z.
gnasher729
@BasileStarynkevitch: Jak sobie życzysz! Ponieważ wspomniałeś o „elastycznych parserach”, dołączyłem kilka bardziej niejasnych języków, które mają bardzo elastyczne parsery (kiedykolwiek chciałeś if_then_else_lub [1;2;3]zostanie zdefiniowany w bibliotekach?).
Antal Spector-Zabusky

Odpowiedzi:

10

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ń :

Kolejne niepodzielne operatory o tym samym priorytecie muszą być albo lewe, albo prawe asocjacyjne, aby uniknąć błędu składniowego. [Raport Haskell 2010, rozdz. 3]

Tak więc w GHC , jeśli zdefiniujemy infixloperator lewostronny ( ) <@i prawostronny @>na tym samym poziomie pierwszeństwa - powiedzmy 0 - wtedy ocena x <@ y @> zdaje błąd

Błąd analizy pierwszeństwa
    nie może łączyć „ <@infixl 0] i @>„[ infixr 0] w tym samym wyrażeniu infix

(W rzeczywistości można również zadeklarować, że operator jest nieoznaczony, ale nie jest skojarzony, na przykład ==, więc x == y == zjest 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ę

if_then_else_ : ∀ {a} {A : Set a} → Bool → A → A → A

który po wywołaniu jest napisany

if b then t else f

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 mamy

  • x <@ y @> zparsowanie jako x <@ (y @> z); i
  • x @> y <@ zparsowanie 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

a <@ b <@ c @> d @> e @> f <@ g

parsowanie jako

(((a <@ b) <@ (c @> (d @> (e @> f)))) <@ g

lub

Przetwarzaj drzewo <kod> ((((a <@ b) <@ (c @> (d </code> @> (e @> f)))) <@ g

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

Błąd: Poziom 50 jest już zadeklarowany jako lewostronny, podczas gdy oczekuje się, że będzie prawostronny

Wię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ę).

Antal Spector-Zabusky
źródło
2
(O rany, co za dziwny wybór języków. Czy możesz powiedzieć, że studiuję teorię programowania języków? :-P)
Antal Spector-Zabusky
Wielkie dzięki za szczegółową odpowiedź. BTW, jak narysowałeś obrazek (jakim narzędziem graphviz?)
Basile Starynkevitch
BTW, dlaczego „poprawność” zamiast „pierwszeństwo”?
Basile Starynkevitch
@BasileStarynkevitch: To zależy od tego, co masz na myśli. Jeśli masz na myśli sekcję Coq, to ​​był tylko błąd :-) (I to już naprawione!)
Antal Spector-Zabusky
1
@BasileStarynkevitch: Poza tym przegapiłem twoje pytanie dotyczące zdjęcia! Narysowałem to za pomocą qtree pakietu LaTeX i wyrenderowałem w LaTeXit , rendererze fragmentów LaTeX dla komputerów Mac. Odpowiedni kod źródłowy to \ttfamily \Tree[.<@ [.<@ [.<@ a b ] [.@> c [.@> d [.@> e f ]]]] g ].
Antal Spector-Zabusky
2

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.

Jules
źródło