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

Question

Я пытаюсь проанализировать последовательность выражений без разделителей, чтобы иметь возможность анализировать вызовы функций в стиле 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

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

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

Answer 1

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

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

Предположим, что функция f.

f  x + 7

В том, что f(x) + 7 или же f(x+7)?. Ваша грамматика производит оба.

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

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

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

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

... Я не верю, что правильно представлять функцию как Name ExprList, Будет намного чище, если вы будете каррировать аргументы по одному, по крайней мере, при построении AST, и это будет выглядеть лучше, если вы сделаете это в грамматике, а не с правилами приоритета, которые действительно не были предназначены для невидимых операторов. Увидеть ниже.

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

Конечно, почему нет?

Вот две рабочие (насколько я знаю) 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 + ')'; }
     ;