На ocamlyacc, функция приложения грамматика и приоритет - PullRequest
Новая
       42

На ocamlyacc, функция приложения грамматика и приоритет

8 голосов
/ 17 мая 2010

Я новичок в OCaml и пытаюсь написать простую грамматику, похожую на OCaml, и не могу понять это. Моя грамматика позволяет что-то вроде этого: 

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

Однако, если я хочу использовать функцию, определенную таким образом, я могу написать: (sub 7) 3, но я не могу написать sub 7 3, что действительно вызывает у меня проблемы. По какой-то причине это интерпретируется так, как будто я написал sub (7 3) (что трактует 7 как функцию с аргументом 3). Соответствующие разделы: 

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

/* ... */

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

Спасибо!

Ответы [ 3 ]

9 голосов
/ 12 февраля 2011

Если вы подошли к этому вопросу и подумали, что, наконец, достигли того момента, когда вы нашли именно то, что искали, то были разочарованы, вот более четкий ответ:

Вы не можете использовать% prec по причине, указанной Телемой. Таким образом, вы должны определить ассоциативность при создании рекурсивного набора правил.

Вот упрощенный 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 }

Рекурсивный обходной путь действительно предназначен для выявления случая, в котором мы заинтересованы в отношении этого вопроса, однако легко увидеть, как его можно применять для определения ассоциативности и для остальных выражений.

Суть этого подхода состоит в том, чтобы попытаться сопоставить рассматриваемый шаблон с образцами, определенными в начальном случае (exp), и вы оставляете вызов непосредственно последующему случаю (exp2) в качестве универсального шаблона, если ваш шаблон не соответствует ни одному до этого; продолжая с этим подходом, пока образец наконец не совпадает. Это подразумевает, что шаблон с наивысшим приоритетом существует в самом дальнем падении - в этом примере, exp8.

В этом примере дело для Apply (приложения функции) в exp7. Это связано с тем, что в этом примере Apply определен, чтобы иметь наивысшую ассоциативность среди всех шаблонов. Причина, по которой он не имеет приоритета над случаями в exp8, связана с оценкой Применить для дальнейших вызовов к случаям выражения, а не к вызовам значений. Если бы exp8 не существовало, у нас был бы бесконечный взгляд на наши руки.

В гипотетическом файле simple.ml приложение функции определяется как выражение следующего свойства: Apply of expr * expr. А поскольку Apply является рекурсивным слева, мы оцениваем правильное выражение (exp8) и рекурсивно слева (exp7).

5 голосов
/ 24 мая 2010

Компилятор ocaml работает следующим образом: (с ocaml/parsing/parser.mly) 

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

, где simple_expr - это подмножество возможных значений expr, которые могут вычисляться для функции без использования скобок. Это исключает использование всех конструкций, не заключенных в квадратные скобки, внутри строки при вызове функции. Это также проясняет ассоциативность подвыражений, поскольку второе подвыражение явно является списком.

Относительно того, почему ваша попытка использовать %left APPLY для получения правильной ассоциативности не работает из комментариев в ocaml's 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.

Я бы сказал, что это означает, что вы не можете использовать% prec для ассоциативности без оператора. Попробуйте создать желаемую ассоциативность, определив дополнительные правила, и посмотрите, к чему это приведет.

0 голосов
/ 01 ноября 2011

Можно также использовать такие вещи, чтобы избежать разбиения выражений на множество уровней: 

%nonassoc LET FUN IF

%left OR

%left AND

%left EQ NE LT LE

%left PLUS MINUS

%left MUL DIV
...