Разбор последовательности выражений с использованием yacc

Я пытаюсь разобрать последовательность выражений без разделителей, чтобы иметь возможность анализировать вызовы функций стиля ML/F #:

myfunc expr1 expr2 expr3

Однако последовательность выражений дает мне список конфликтов сдвига/уменьшения.

Я предполагаю, что конфликты вызваны рекурсивным характером моей грамматики, но я не знаю, как исправить эти конфликты.

Мои (упрощенные) правила приоритета и грамматика выглядят так:

/* Lowest precedence */
%left PLUS
%left TIMES
%left LPAR
/* Highest precedence */

Expr: 
 | CSTINT { CstI $1 }
 | LPAR Expr RPAR { $2 }
 | Expr TIMES Expr { Prim("*", $1, $3) }
 | Expr PLUS Expr { Prim("+", $1, $3) }
 | NAME ExprList { Call(Var $1, $2) }

ExprList:
 | { [] }
 | Expr ExprList { $1::$2 }

Когда я передаю это в fsyacc, я получаю список изменений/уменьшения и уменьшения/уменьшения конфликтов. Пример конфликта смены/сокращения

state 11: shift/reduce error on PLUS

Выход из fsyacc для состояния 11:

state 11:
 items:
 Expr -> Expr . 'TIMES' Expr
 Expr -> Expr . 'PLUS' Expr
 ExprList -> Expr . ExprList

 actions:
 action 'EOF' (noprec): reduce ExprList --> 
 action 'LPAR' (explicit left 10000): shift 6
 action 'RPAR' (noprec): reduce ExprList --> 
 action 'COMMA' (noprec): reduce ExprList --> 
 action 'PLUS' (explicit left 9998): shift 13
 action 'TIMES' (explicit left 9999): shift 12
 action 'NAME' (noprec): shift 14
 action 'CSTINT' (noprec): shift 5
 action 'error' (noprec): reduce ExprList --> 
 action '#' (noprec): reduce ExprList --> 
 action '$$' (noprec): reduce ExprList --> 

 immediate action: <none>
 gotos:
 goto Expr: 11
 goto ExprList: 16
</none>

Прошло некоторое время с тех пор, как я прошел курс по теории компиляторов, поэтому, хотя я знаю, что такое сдвиг/сокращение и сокращение/сокращение конфликтов, я не привык думать о них. В частности, я не вижу, как уменьшение на PLUS может привести к действительному анализу. В целом, любое понимание одного или нескольких из следующих вопросов будет высоко оценено:

  1. Почему моя грамматика кажется двусмысленной?
  2. Могу ли я исправить это с использованием правил приоритета и/или ассоциативности или, если нет,
  3. Нужно ли переписывать грамматику, и если да, то грубо, как мне это сделать?
  4. Як является подходящим инструментом для такой конструкции?
1 ответ

1. Почему моя грамматика кажется двусмысленной?

Ваша грамматика неоднозначна. Это не иллюзия.

Пусть f - функция.

f x + 7

Является ли это f(x) + 7 или f(x+7)?. Ваша грамматика производит оба.

Приложение IIRC, приложение приложения тесно связывается и связывается слева. Таким образом, указанное выражение должно анализироваться как f(x) + 7.

2. Могу ли я исправить это с использованием правил приоритета и/или ассоциативности, а если нет,

Вы можете disambiguate приложение функции с правилами приоритета и ассоциативности; вам просто нужно объявить для него приоритет с %prec. Однако, это заканчивается тем, что выглядело немного уродливым и...

3. Нужно ли переписывать грамматику, и если да, то грубо, как мне это сделать?

... Я не верю, что правильно представлять приложение-функцию как Name ExprList. Это намного чище, если вы карри аргументы по одному, по крайней мере, при создании АСТ, и он выглядит красивее, если вы делаете это в грамматике, а не с правилами приоритета, которые действительно не были предназначены для невидимых операторов. Смотри ниже.

4. Является ли подходящим инструментом для такой конструкции?

Конечно, почему бы и нет?

Вот два рабочих (насколько мне известно) грамматики yacc. Первый использует объявления приоритета для всего; второй отделяет функциональное приложение, которое, по моему мнению, более чистое:

// grammar1.y:

%left '+'
%left '*'
%left ATOM ';' '(' ')'

%%

program: /* empty */ { $$ = ""; }
 | program statement ';' { std::cout << $2 << std::endl; }
 | program ';'
 ;

statement: expr
 ;

expr: ATOM
 | '(' expr ')' { $$ = $2; }
 | expr expr %prec ATOM { $$ = '(' + $1 + ' ' + $2 + ')'; }
 | expr '+' expr { $$ = "(+ " + $1 + ' ' + $3 + ')'; }
 | expr '*' expr { $$ = "(* " + $1 + ' ' + $3 + ')'; }
 ;
// grammar2.y

%token ATOM

%left '+'
%left '*'

%%

program: /* empty */ { $$ = ""; }
 | program statement ';' { std::cout << $2 << std::endl; }
 | program ';'
 ;

statement: expr
 ;

term : ATOM
 | '(' expr ')' { $$ = $2; }
 ;

apply: term
 | apply term { $$ = '(' + $1 + ' ' + $2 + ')'; }
 ;

expr : apply
 | expr '+' expr { $$ = "(+ " + $1 + ' ' + $3 + ')'; }
 | expr '*' expr { $$ = "(* " + $1 + ' ' + $3 + ')'; }
 ;

licensed under cc by-sa 3.0 with attribution.