Auf ocamlyacc, Funktion Anwendung Grammatik und Vorrang

Question

Ich bin OCaml Neuling und ich versuche, eine einfache OCaml-ähnliche Grammatik zu schreiben, und ich kann das nicht herausfinden. Meine Grammatik erlaubt so etwas wie diese:

let sub = fun x -> fun y -> x - y;; 

Allerdings, wenn ich die Funktion so definiert verwendet werden soll, kann ich schreiben: (sub 7) 3 aber ich kann sub 7 3 nicht schreiben, was wirklich nervt mich. Aus irgendeinem Grund wird es so interpretiert, als ob ich sub (7 3) geschrieben hätte (was 7 als eine Funktion mit dem Argument 3 behandeln würde). Die relevanten Abschnitte sind:

/* other operators, then at the very end: */ 
%left APPLY 

/* ... */ 

expr: 
    /* ... */ 
    | expr expr %prec APPLY  { Apply($1, $2) } 

Danke!

Answer 1

Der ocaml Compiler tut Funktion Anwendung wie folgt: (von ocaml/parsing/parser.mly)

expr: 
... 
    | simple_expr simple_labeled_expr_list 
     { mkexp(Pexp_apply($1, List.rev $2)) } 

wo simple_expr eine Teilmenge der möglichen ausdr Werte ist, die, ohne Klammern auf eine Funktion auswerten kann. Dies schließt aus, dass alle Nicht-selbst-geklammerten Konstrukte inline mit einem Funktionsaufruf verwendet werden. Es verdeutlicht auch die Assoziativität der Teilausdrücke, da der zweite Teilausdruck explizit eine Liste ist.

Wie, warum Ihr Versuch %left APPLY zu verwenden, um die richtige Assoziativität funktioniert nicht zu bekommen, aus den Kommentaren in ocaml der parser.mly:

We will only use associativities with operators of the kind x * x -> x 
for example, in the rules of the form expr: expr BINOP expr 
in all other cases, we define two precedences if needed to resolve 
conflicts. 

Ich würde sagen, das bedeutet, dass Sie nicht verwenden können % prec für Assoziativität ohne Operator. Versuchen Sie, die gewünschte Assoziativität zu erstellen, indem Sie mehr Regeln definieren und sehen, wo das führt.

Answer 2

Falls Sie auf diese Frage kam und dachte, dass Sie endlich diesen Moment erreicht hatte, wenn Sie genau das finden, was Sie suchen, dann enttäuscht waren, ist hier eine deutlichere Antwort:

Sie können nicht verwenden% prec aus dem Grund Thelema erwähnt. Daher müssen Sie die Assoziativität beim Erstellen eines rekursiven Regelsatzes definieren.

Hier ist ein parser.mly

vereinfachte-around Arbeit

%token <int> Num 
    %token <string> Id 
    %token TRUE FALSE 
    %token LET REC EQ IN FUN ARROW IF THEN ELSE 
    %token PLUS MINUS MUL DIV LT LE NE AND OR 
    %token EOF   

    %start exp 
    %type <Simple.expr> exp 

    %% 

/* Associativity increases from exp to exp8 
* Each precedence level trickles down to higher level expressions if the pattern is not matched 
*/ 

/* Parses the LET, LET REC, FUN, and IF expressions */ 
exp: 
     LET Id EQ exp IN exp  { Let($2,$4,$6) } 
    | LET REC Id EQ exp IN exp { Letrec($3,$5,$7) } 
    | FUN Id ARROW exp   { Fun($2,$4) } 
    | IF exp THEN exp ELSE exp { If($2,$4,$6) } 
    | exp2      { $1 } 

/* Parses OR expressions */ 
exp2: 
     exp2 OR exp3    { Bin($1,Or,$3) } 
    | exp3      { $1 } 

/* Parses AND expressions */ 
exp3: 
     exp3 AND exp4    { Bin($1,And,$3) } 
    | exp4      { $1 } 

/* Parses EQ, NE, LT, and LE expressions */ 
exp4: 
     exp4 EQ exp5    { Bin($1,Eq,$3) } 
    | exp4 NE exp5    { Bin($1,Ne,$3) } 
    | exp4 LT exp5    { Bin($1,Lt,$3) } 
    | exp4 LE exp5    { Bin($1,Le,$3) } 
    | exp5      { $1 } 

/* Parses PLUS and MINUS expressions */ 
exp5: 
     exp5 PLUS exp6   { Bin($1,Plus,$3) } 
    | exp5 MINUS exp6   { Bin($1,Minus,$3) } 
    | exp6      { $1 } 

/* Parses MUL and DIV expressions */ 
exp6: 
     exp6 MUL exp7    { Bin($1,Mul,$3)} 
    | exp6 DIV exp7    { Bin($1,Div,$3)} 
    | exp7      { $1 } 

/* Parses Function Application expressions */ 
exp7: 
     exp7 exp8     { Apply($1,$2) } 
    | exp8      { $1 } 

/* Parses numbers (Num), strings (Id), booleans (True | False), and expressions in parentheses */ 
exp8: 
     Num      { Const($1) } 
    | Id      { Var($1) } 
    | TRUE      { True } 
    | FALSE      { False } 
    | LPAREN exp RPAREN   { $2 } 

Die rekursive ist wirklich der Fall für den Fang, die wir in Bezug auf diese Frage betroffen sind, ist es jedoch leicht zu sehen, wie es zu definieren, angewendet werden kann, Assoziativität für den Rest der Ausdrücke.

Der Kern dieses Ansatzes besteht darin, das fragliche Muster mit den im Anfangsfall (exp) definierten Mustern in Übereinstimmung zu bringen und einen Aufruf an den nächstfolgenden Fall (exp2) als Catch-All-Muster zu belassen Ihr Muster passt zu keinem davor; Fortsetzung mit diesem Ansatz, bis das Muster schließlich übereinstimmt. Dies bedeutet, dass das Muster mit der höchsten Priorität im weitesten Fall existiert - in diesem Beispiel exp8.

In diesem Beispiel ist der Fall für Apply (Funktionsanwendung) in exp7. Dies liegt daran, dass Apply in diesem Beispiel die höchste Assoziativität eines Musters aufweist. Der Grund dafür, dass es keine Priorität gegenüber den Fällen in exp8 hat, liegt darin, dass die Auswertung auf weitere Aufrufe von Ausdrucksfällen und nicht auf Aufrufe von Werten angewendet wird. Wenn exp8 nicht existieren würde, hätten wir einen unendlichen Blick auf unsere Hände.

In der hypothetischen simple.ml ist die Funktion Application als Ausdruck der folgenden Eigenschaft definiert: Apply of expr * expr.Und da Apply links-rekursiv ist, bewerten wir den rechten Ausdruck (exp8) und rekursiv auf der linken Seite (exp7).

Answer 3

Man kann auch Dinge wie diese verwenden, um zu vermeiden, die Ausdrücke brechen in so vielen Ebenen:

%nonassoc LET FUN IF 

%left OR 

%left AND 

%left EQ NE LT LE 

%left PLUS MINUS 

%left MUL DIV