Sprache mit zwei binären Operatoren gleicher Priorität, linksassoziativ und rechtsassoziativ

11

Gibt es Programmierung (oder Scripting) Sprache (oder eine domänenspezifische Sprache) mit zwei binären Operatoren oplund oprder gleichen Priorität mit oplLinksassoziativität werden und oprrechtsassoziativ sein?

(Ich kann ein solches Beispiel nicht finden, aber ich versuche, einen Parser allgemein genug zu codieren, um diesen seltsamen Fall zu behandeln.)

Wie würden Ausdrücke der Form x opl y opr z oder x opr y opl z analysiert? Und allgemeiner mit noch mehr Operanden?

Basile Starynkevitch
quelle
4
Wenn es weh tut, tu das nicht.
CodesInChaos
1
In Haskell können Sie Ihre eigenen Infix-Operatoren mit ihren eigenen Prioritäten definieren. In diesem Fall wird eine Fehlermeldung angezeigt. wenn Sie x <@ y @> zmit <@gelassen werden assoziativ und @>sein rechtsassoziativ, GHC gibt Ihnen einen „Präzedenz - Parsing - Fehler“: „kann nicht mischen‚ <@‘[infixl 0] und‚ @>‘[infixr 0] in dem gleichen Infix Ausdruck“ (wo ich definierte diese Operatoren auf Ebene 0 für das Beispiel).
Antal Spector-Zabusky
@ AntalSpector-Zabusky: Das wäre eine tolle Antwort!
Basile Starynkevitch
@ AntalSpector-Zabusky: Gleiches gilt für Swift. Ich denke, Sie können die Operatoren tatsächlich definieren, aber in einem Ausdruck müssen Sie alle linken assoziativen oder alle rechten assoziativen Operatoren mit derselben Priorität verwenden. Sie können also x leftop y leftop z oder x rightop y rightop z verwenden, aber nicht x leftop y rightop z.
Gnasher729
@ BasileStarynkevitch: Wie du willst! Da Sie "flexible Parser" erwähnt haben, habe ich einige weitere obskure Sprachen hinzugefügt, die sehr flexible Parser enthalten (jemals in Bibliotheken definiert if_then_else_oder [1;2;3]definiert werden sollen?).
Antal Spector-Zabusky

Antworten:

10

Hier sind drei Sprachen, mit denen Sie Ihre eigenen Operatoren definieren können, die zweieinhalb verschiedene Dinge tun ! Haskell und Coq verbieten beide diese Art von Spielereien - aber unterschiedlich -, während Agda diese Art der Vermischung von Assoziativitäten zulässt.


Erstens dürfen Sie dies in Haskell einfach nicht tun. Sie können Ihre eigenen Operatoren definieren und ihnen den Vorrang (von 0 bis 9) und die Assoziativität Ihrer Wahl geben. Der Haskell-Bericht verbietet Ihnen jedoch, Assoziativitäten zu mischen :

Aufeinanderfolgende nicht parästhesierte Operatoren mit derselben Priorität müssen entweder links oder rechts assoziativ sein, um einen Syntaxfehler zu vermeiden. [Haskell 2010 Report, Kap. 3]

Wenn wir also in GHC einen linksassoziativen ( infixl) Operator <@und einen rechtsassoziativen Operator @>auf derselben Prioritätsstufe definieren - sagen wir 0 -, x <@ y @> zergibt die Auswertung den Fehler

Vorrang-Analysefehler
    können ' <@' [ infixl 0] und ' @>' [ infixr 0] nicht im selben Infix-Ausdruck mischen

(Tatsächlich können Sie einen Operator auch als Infix deklarieren, aber nicht assoziativ ==, so dass dies x == y == zein Syntaxfehler ist!)


Auf der anderen Seite gibt es den abhängig typisierten Sprach- / Theorembeweiser Agda (der zugegebenermaßen wesentlich weniger Mainstream ist). Agda hat einige der formbarsten Syntax aller mir bekannten Sprachen und unterstützt Mixfix- Operatoren: Die Standardbibliothek enthält die Funktion

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

was, wenn es aufgerufen wird, geschrieben wird

if b then t else f

mit den Argumenten, die die Unterstriche ausfüllen! Ich erwähne dies, weil dies bedeutet, dass es unglaublich flexibles Parsen unterstützen muss. Natürlich Agda hat auch fixity Erklärungen (obwohl seine Prioritätsebenen über beliebige natürliche Zahlen reichen, und sind in der Regel in 0-100), und Agda macht Sie erlauben Operatoren gleicher Priorität zu mischen , aber unterschiedliche fixities. Ich kann jedoch keine Informationen dazu in der Dokumentation finden, also musste ich experimentieren.

Lassen Sie uns unsere <@und @>von oben wiederverwenden . In den beiden einfachen Fällen haben wir

  • x <@ y @> zParsen als x <@ (y @> z); und
  • x @> y <@ zAnalyse als (x @> y) <@ z.

Ich denke, was Agda tut, ist, die Zeile in "linksassoziative" und "rechtsassoziative" Blöcke zu gruppieren, und - wenn ich nicht über falsche Dinge nachdenke - erhält der rechtsassoziative Block "Priorität" beim Ergreifen der benachbarten Argumente. Das gibt uns also

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

Analyse als

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

oder

Analysieren Sie den Baum von <code> (((a <@ b) <@ (c @> (d </ code> @> (e @> f))) <@ g

Trotz meiner Experimente habe ich beim ersten Schreiben falsch geraten, was lehrreich sein könnte :-)

(Und Agda hat wie Haskell nicht assoziative Operatoren, die Analysefehler korrekt angeben, sodass gemischte Assoziativitäten auch zu einem Analysefehler führen können.)


Schließlich gibt es noch die Satzbeweis- / abhängig typisierte Sprache Coq , die eine noch flexiblere Syntax als Agda aufweist, da ihre Syntaxerweiterungen tatsächlich implementiert werden, indem Spezifikationen für die neuen syntaktischen Konstrukte angegeben und diese dann in die Kernsprache umgeschrieben werden (vage makroähnlich) , Schätze ich). In Coq ist die Listensyntax [1; 2; 3]ein optionaler Import aus der Standardbibliothek. Neue Syntaxen können sogar Variablen binden!

Wiederum können wir in Coq unsere eigenen Infix-Operatoren definieren und ihnen Vorrangstufen (meistens von 0 bis 99) und Assoziativitäten zuweisen. In Coq kann jedoch jede Prioritätsstufe nur eine Assoziativität haben . Wenn wir also <@als linksassoziativ definieren und dann versuchen, @>auf derselben Ebene - sagen wir 50 - als rechtsassoziativ zu definieren , erhalten wir

Fehler: Level 50 ist bereits als linksassoziativ deklariert, während jetzt erwartet wird, dass es rechtsassoziativ ist

Die meisten Operatoren in Coq befinden sich auf Ebenen, die durch 10 teilbar sind. Wenn ich Assoziativitätsprobleme hatte (diese Assoziativitäten sind global), habe ich die Ebene im Allgemeinen nur um eins in beide Richtungen erhöht (normalerweise nach oben).

Antal Spector-Zabusky
quelle
2
(Gee, was für eine seltsame Auswahl an Sprachen. Kannst du mir sagen, dass ich Programmiersprachentheorie studiere ?:-P)
Antal Spector-Zabusky
Vielen Dank für Ihre ausführliche Antwort. Übrigens, wie haben Sie das Bild graphviz
gezeichnet
Übrigens, warum "Fixität" statt "Vorrang"?
Basile Starynkevitch
@ BasileStarynkevitch: Das hängt davon ab, wo du meinst. Wenn Sie in der Coq-Sektion meinen, war das nur ein Fehler :-) (Und einer, der jetzt behoben ist!)
Antal Spector-Zabusky
1
@BasileStarynkevitch: Außerdem habe ich deine Frage zum Bild verpasst! Ich habe das mit dem LaTeX-Paket qtree gezeichnet und es in LaTeXit , einem LaTeX-Snippet-Renderer für Macs , gerendert . Der relevante Quellcode war \ttfamily \Tree[.<@ [.<@ [.<@ a b ] [.@> c [.@> d [.@> e f ]]]] g ].
Antal Spector-Zabusky
2

Seit sie von Douglas Crockford populär gemacht wurden, sind Pratt Parsers (oder Top-Down Operator Precedence Parser) immer häufiger geworden. Diese Parser arbeiten anhand einer Tabelle mit Operatorrang und Assoziativität, anstatt die Regeln in eine feste Grammatik zu integrieren. Sie sind daher hilfreich für Sprachen, mit denen Benutzer ihre eigenen Operatoren definieren können.

Sie haben eine Analysefunktion, die funktioniert, indem zuerst der am weitesten links stehende Term eines Ausdrucks analysiert und dann rekursiv neue Operatoren und Begriffe für die rechte Hand gebunden werden, solange sie ordnungsgemäß binden. Linksassoziative Operatoren binden Begriffe der rechten Hand, die Vorrang bis einschließlich derselben Priorität haben, während rechtsassoziative Operatoren nur bis zu ihrer Vorrangstufe binden, diese jedoch nicht einschließen. Ich glaube, dies führt zu demselben Analysebaum wie für Agda, der oben zitiert wurde.

Jules
quelle