Bison сдвиг/свёртка

Question

Я пытаюсь описать этот синтаксис на Bison входного файла: https://courses.engr.illinois.edu/cs421/sp2011/mps/mp2/minijavasyntax.pdf

это мой вход:

%start Program 
%token KW_CLASS KW_EXTENDS KW_PUBLIC KW_STATIC KW_BOOLEAN KW_STRING KW_FLOAT KW_INT EOF 
%token KW_IF KW_WHILE KW_BREAK KW_CONTINUE KW_SWITCH KW_CASE KW_DEFAULT KW_RETURN 
%token KW_NEW KW_THIS KW_NULL KW_TRUE KW_FALSE KW_PRINTLN 
%token IDENT INT_LITERAL FLOAT_LITERAL STRING_LITERAL 

%nonassoc "THEN" 
%nonassoc KW_ELSE 

%right "STATEMENTS" 

%right OP_ASSIGN 
%left OP_OR 
%left OP_AND 
%nonassoc CMP_EQ CMP_NEQ 
%nonassoc CMP_GT CMP_LT CMP_GTE CMP_LTE 
%left OP_ADD OP_MINUS 
%left OP_MULT OP_DIV OP_MOD 
%right OP_NOT OP_UNARY "NEW" 
%left "FUNCALL" "SUBSCRIPT" '.' 
%nonassoc '(' 
%nonassoc ')' 
%% 
Program:  ClassDeclp EOF 
      ; 

ClassDeclp:  ClassDecl 
      | ClassDeclp ClassDecl 
      ; 
ClassDecl:  KW_CLASS IDENT ExtendsFrom 
      '{' VarDecls MethodDecls '}' 
      ; 
ExtendsFrom:  /*empty*/ 
       | KW_EXTENDS IDENT 
      ; 

VarDecls:  /*empty*/ 
      | VarDecls VarDecl 
      ; 
VarDecl:  Type IDENT ';' 
      | KW_STATIC Type IDENT ';' /*Co the sua thanh AcessModifier Type IDENT*/ 
      ; 

MethodDecls:  /*empty*/ 
      | MethodDecls MethodDecl 
      ; 
MethodDecl:  KW_PUBLIC Type IDENT 
      '('MethodParams')' 
      '{'VarDecls Statements KW_RETURN Expression ';' '}' 
      ; 

MethodParams:  /*empty*/ 
      | MethodParams ',' MethodParam 
      ;  
MethodParam:  Type IDENT; 

Type :   Type '['']' 
       | KW_BOOLEAN 
      | KW_STRING 
      | KW_FLOAT 
      | KW_INT 
      | IDENT 
      ; 
Statements:  Statements Statement %prec "STATEMENTS" 
      | /*empty*/ %prec "STATEMENT" 
      ; 
Statementp:  Statements Statement %prec "STATEMENTS" 
      ; 
Statement:  '{'Statements'}' 
      | KW_IF '(' Expression ')' Statement %prec "THEN" 
      | KW_IF '(' Expression ')' Statement KW_ELSE Statement 
      | KW_WHILE '(' Expression ')'Statement 
      | KW_PRINTLN '(' Expression ')' ';' 
      | IDENT OP_ASSIGN Expression ';' 
      | KW_BREAK ';' 
      | KW_CONTINUE ';' 
      | IDENT %prec "SUBSCRIPT" '['Expression']' '=' Expression ';' 
      | KW_SWITCH '(' Expression ')' '{' 
       Cases 
       KW_DEFAULT ':' Statementp '}' 
      ; 

Cases:   Cases Case 
      | /*empty*/ 
      ; 
Case:   KW_CASE INT_LITERAL ':' Statementp 
      ; 


Expression:  Expression OP_OR Expression 
      | Expression OP_AND Expression 
      | Expression CMP_EQ Expression 
      | Expression CMP_NEQ Expression 
      | Expression CMP_GT Expression 
      | Expression CMP_GTE Expression 
      | Expression CMP_LT Expression 
      | Expression CMP_LTE Expression 
      | Expression OP_ADD Expression 
      | Expression OP_MINUS Expression 
      | Expression OP_MULT Expression 
      | Expression OP_DIV Expression 
      | Expression OP_MOD Expression 
      | '-' Expression %prec OP_UNARY 
      | OP_NOT Expression 
      | Expression %prec "SUBSCRIPT" '['Expression']' 
      | Expression '.'"length" 
      | Expression '.' IDENT %prec "FUNCALL" '(' ParamList ')' 
      | INT_LITERAL 
      | FLOAT_LITERAL 
      | STRING_LITERAL 
      | KW_NULL 
      | KW_TRUE 
      | KW_FALSE 
      | IDENT 
      | KW_THIS 
      | KW_NEW Type '[' Expression ']' %prec "NEW" 
      | KW_NEW IDENT '('')'  %prec "NEW" 
      | '(' Expression ')' 
      ; 


ParamList:  /*empty*/ 
      | ParamList ',' Expression 
      | Expression 
      ; 
%% 
main(int argc, char** argv[]) 
{ 
    extern FILE *yyin; 
    ++argv; --argc; 
    yyin = fopen(argv[0], "r"); 
    yydebug = 1; 
    errors = 0; 
    yyparse(); 
} 

yyerror(char *s) 
{ 
    printf("%s\n", s); 
} 

/* Co 3 conflict RR can xu ly khi bien thuoc kieu bool 
    giua BoolExpr va Expresstion */ 

я получил два 16 конфликтов при компиляции. Один из конфликтов, я побежал Bison с --report = опережающего просмотра:

OP_NOT Expression . [OP_OR, OP_AND, CMP_EQ, CMP_NEQ, CMP_GT, CMP_LT, CMP_GTE, CMP_LTE, OP_ADD, OP_MINUS, OP_MULT, OP_DIV, OP_MOD, ')', ';', ',', '[', ']']

Что я ожидал, это «[» не в OP_NOT опережения знак, потому что нижний индекс приоритет должен выше оператора!. Другие конфликты подобны этому. Как я могу это решить. Tks

Answer 1

Это не так, как работает приоритет.

EDIT: Если вы обнаружили следующее описание запутанным или вы не хотите, чтобы пробираться через столько английского текста, вы могли бы взять мой обычный совет: Не используйте приоритет. Вы почти всегда можете написать недвусмысленную грамматику, не требующую объявления приоритета. И если вы это сделаете, вам не нужно понимать приоритет. (Хотя, если честно, это не так уж сложно, если вы понимаете, как LR разбора дела.) /EDIT

Внеочередные всегда сравнивает возможное снижение (т.е. производство которого rightt сторона соответствует верхней части тока стек синтаксического анализатора) и символ вида.

В точке:

Expression : Expression · '[' Expression ']' 

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

Тем не менее, в одном из состояний, в которых происходит эта точка, существует другая продукция:

Expression : OP_NOT Expression · 

Этот может быть уменьшена, так как точка находится в конце.

Поскольку обе эти точки находятся в одном состоянии, они должны быть действительными. Это означает, что мы смотрим на:

OP_NOT Expression · '[' Expression ']' 

И мы пытаемся выяснить, что делать. Мы могли бы уменьшить OP_NOT Expression до Expression, в какой момент мы имеем:

Expression · '[' Expression ']' 

Или мы могли бы сдвиг «[», оставив нас с

OP_NOT Expression '[' · Expression ']' 

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

Expression : OP_NOT Expression 

и символ который может быть сдвинут: '['.

Однако тщательный просмотр объявлений о приоритетах показывает, что приоритет не присвоен '['. Так Yacc/бизон не может проверить его против производства (приоритет которого определяется последним терминалом в правой, OP_NOT, так как нет %prec декларации.

Если вы хотите, чтобы оператор постфикса индекс ([ выражение ' ] ') ​​имеют более высокий приоритет, чем оператор префиксом OP_NOT, вы должны объявить приоритет для [, которая выше, чем OP_NOT.

Кстати, я не вижу смысла несогласованности здесь. вы могли бы использовали ! для OP_NOT (и - для OP_MINUS и т. д.), что было бы легче читать и меньше Работа.

Вы, кажется, думают, что %prec декларация в

Expression %prec "SUBSCRIPT" '['Expression']' 

актуальна. Это не. Он применим только в том случае, если парсер может уменьшить Expression '[' Expression ']'. Но это также бессмысленно, потому что вам не нужно создавать поддельный терминал для хранения приоритета этой продукции; его приоритет определяется последним терминалом в правой части, ']', поэтому вы можете просто объявить приоритет для этого терминала.

Поддельный маркер в декларации Expression : OP_MINUS Expression %prec OP_UNARY необходим, потому что '-' имеет два различных старшинства, или более точно, потому что OP_MINUS Expression имеет различный приоритет от Expresson OP_MINUS Expression. Однако на самом деле вам не нужно было изобретать поддельный токен; вы можете использовать любой токен с правильным приоритетом, например OP_NOT или OP_NEW.

В случае, если этого недостаточно, я попытался объяснить это несколькими различными ответами SO. Here's one и here's another one и here's another one. Кроме того, here's one by Chris Dodd и вот документация в the bison manual. Если вам повезет, вы можете найти описание на своем родном языке, используя любую интернет-поисковую систему, которая наилучшим образом подходит для вас или если вы будете разговаривать с вашим профессором.

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