En ocamlyacc, gramática de aplicación de funciones y precedencia

Question

Soy OCaml novato y estoy tratando de escribir una gramática simple similar a OCaml, y no puedo resolver esto. Mi gramática permite algo como esto:

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

Sin embargo, si quiero usar la función así definida, puedo escribir: (sub 7) 3 pero no puedo escribir sub 7 3, lo que realmente me molesta. Por alguna razón, se interpreta como si escribiera sub (7 3) (que trataría 7 como una función con el argumento 3). Las secciones relevantes son:

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

/* ... */ 

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

Gracias!

Answer 1

El compilador ocaml hace aplicación de función como sigue: (de ocaml/parsing/parser.mly)

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

donde simple_expr es un subconjunto de los posibles valores expr que pueden evaluar a una función sin necesidad de paréntesis. Esto excluye que todas las construcciones sin corchetes se utilicen en línea con una llamada a función. También aclara la asociatividad de las subexpresiones, ya que la segunda subexpresión es explícitamente una lista.

cuanto a por qué el intento de usar %left APPLY para obtener la asociatividad correcta no funciona, a partir de los comentarios en parser.mly de ocaml:

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. 

que diría esto significa que no se puede utilizar % prec para asociatividad sin operador. Intente crear la asociatividad que desee mediante la definición de más reglas y vea a dónde conduce.

Answer 2

En caso de que llegaron a esta pregunta y pensó que finalmente había llegado el momento en que encuentre exactamente lo que está buscando, entonces se sintieron decepcionados, aquí es una respuesta más explícita:

No se puede utilizar% prec por la razón que mencionó Thelema. Por lo tanto, debe definir la asociatividad para establecer un conjunto recursivo de reglas.

Aquí hay una simplificado parser.mly

%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 } 

El recursiva solución alternativa es realmente para controlar el caso que nos preocupa con respecto a esta cuestión, sin embargo, es fácil ver cómo se puede aplicar a la definición asociatividad para el resto de las expresiones también.

Lo esencial de este enfoque es intentar hacer coincidir el patrón en cuestión con los patrones definidos en el caso de inicio (exp), y dejar una llamada al caso inmediato siguiente (exp2) como un patrón general si su patrón no coincide con ninguno anterior; continuando con este enfoque hasta que el patrón finalmente coincida. Esto implica que el patrón de prioridad más alta existe en el caso más alejado: en este ejemplo, exp8.

En este ejemplo, el caso de Aplicar (Aplicación de función) está en exp7. Esto se debe a que Apply se define para tener la asociatividad más alta de cualquier patrón en este ejemplo. La razón por la que no tiene prioridad sobre los casos en exp8 se debe a Aplicar evaluación para nuevas llamadas a casos de expresión, no llamadas de valor. Si exp8 no existiera, tendríamos una mirada infinita en nuestras manos.

En el hipotético simple.ml, la aplicación de función se define como una expresión de la siguiente propiedad: Apply of expr * expr.Y dado que Apply es recursivo a la izquierda, estamos evaluando la expresión correcta (exp8) y la recursión a la izquierda (exp7).

Answer 3

También se puede usar cosas como éstas para evitar romper las expresiones abajo en muchos niveles:

%nonassoc LET FUN IF 

%left OR 

%left AND 

%left EQ NE LT LE 

%left PLUS MINUS 

%left MUL DIV