Bison 语法中的悬挂 Else

Question

以下语法受到悬空 else 问题的困扰，尽管我在阅读 http://marvin.cs.uidaho.edu/~heckendo/CS445/danglingElse.html 我想知道你是否能发现我的内容做错了...

%{
%}

%token PROGRAM CONST TYPE ARRAY LIST SET OF RECORD VAR FUNCTION PROCEDURE
%token INTEGER REAL BOOLEAN CHAR FORWARD LENGTH NEW T_BEGIN END IF THEN ELSE
%token WHILE DO CASE OTHERWISE FOR TO DOWNTO WITH READ WRITE
%token LISTFUNC SEMI 
%token CCONST BCONST STRING RCONST ICONST ID
%token RBRACK RPAREN COMMA  ASSIGN DOTDOT COLON
%token LBRACK INOP RELOP EQU ADDOP OROP MULDIVANDOP NOTOP DOT LPAREN

%nonassoc LBRACK 
%nonassoc INOP RELOP EQU 
%left ADDOP OROP
%left MULDIVANDOP
%nonassoc NOTOP
%left DOT LPAREN 

%%

program : header declarations subprograms comp_statement DOT 
;

header : PROGRAM ID SEMI
;

declarations : constdefs typedefs vardefs 
;

constdefs : CONST constant_defs SEMI
|
;
constant_defs : constant_defs SEMI ID EQU expression 
| ID EQU expression 
;

expression : expression RELOP expression 
| expression EQU expression  
| expression INOP expression  
| expression OROP expression  
| expression ADDOP expression  
| expression MULDIVANDOP expression  
| ADDOP expression 
| NOTOP expression
| variable 
| ID LPAREN expressions RPAREN 
| LENGTH LPAREN expression RPAREN
| NEW LPAREN expression RPAREN 
| constant 
| LPAREN expression RPAREN
| setlistexpression 
;

variable : ID 
| variable DOT ID 
| variable LBRACK expressions RBRACK 
| LISTFUNC LPAREN expression RPAREN 
;

expressions : expressions COMMA expression 
| expression
;

constant : ICONST 
| RCONST
| BCONST 
| CCONST 
;

setlistexpression : LBRACK expressions RBRACK
| LBRACK RBRACK
;

typedefs : TYPE type_defs SEMI 
| 
;

type_defs : type_defs SEMI ID EQU type_def 
| ID EQU type_def 
;

type_def : ARRAY LBRACK dims RBRACK OF typename 
| LIST OF typename 
| SET OF typename 
| RECORD fields END 
| limit DOTDOT limit 
;

dims : dims COMMA limits 
| limits 
;

limits : limit DOTDOT limit
| ID
;

limit : sign ICONST 
| CCONST 
| BCONST 
| ADDOP ID 
|
ID
;

sign : ADDOP
| 
;

typename : standard_type
| ID 
;

standard_type : INTEGER 
| REAL
| BOOLEAN
| CHAR 
;

fields : fields SEMI field 
| field 
;

field : identifiers COLON typename 
;

identifiers : identifiers COMMA ID 
| ID 
;

vardefs : VAR variable_defs SEMI 
| 
;

variable_defs : variable_defs SEMI identifiers COLON typename
| identifiers COLON typename
;

subprograms : subprograms subprogram SEMI 
| 
;

subprogram : sub_header  SEMI FORWARD
| sub_header SEMI declarations subprograms comp_statement
;

sub_header : FUNCTION ID formal_parameters COLON standard_type 
| FUNCTION ID formal_parameters COLON LIST 
| PROCEDURE ID formal_parameters 
| FUNCTION ID  
;

formal_parameters : LPAREN parameter_list RPAREN
| 
;

parameter_list : parameter_list SEMI pass identifiers COLON typename 
| pass identifiers COLON typename 
;

pass : VAR 
| 
;

comp_statement : T_BEGIN statements END 
;


assignment : variable ASSIGN expression 
| variable ASSIGN STRING 
;

case_statement : CASE expression OF cases case_tail END 
;

cases : cases SEMI single_case 
| single_case 
;

single_case : label_list COLON statement 
| 
;

label_list : label_list COMMA label 
| label 
;

label : sign constant 
| sign ID 
;


case_tail : SEMI OTHERWISE COLON statement 
| 
;

while_statement : WHILE expression DO statement 
;

for_statement : FOR ID ASSIGN iter_space DO statement 
;

iter_space : expression TO expression
| expression DOWNTO expression 
;

with_statement : WITH variable DO statement 
;

subprogram_call : ID
| ID LPAREN expressions RPAREN 
;

io_statement : READ LPAREN read_list RPAREN 
| WRITE LPAREN write_list RPAREN
;

read_list : read_list COMMA read_item 
| read_item 
;

read_item : variable 
;

write_list : write_list COMMA write_item 
| write_item 
;

write_item : expression 
| STRING
;
statements : statements SEMI statement 
| statement 
;

statement : matched
| unmatched
;

matched: assignment 
| matched_if_statement
| case_statement 
| while_statement 
| for_statement 
| with_statement 
| subprogram_call 
| io_statement 
| comp_statement
|
;


matched_if_statement: IF expression THEN matched ELSE matched
;

unmatched: IF expression THEN statement
| IF expression THEN matched ELSE unmatched
;

%%

我已将 if 语句代码放在脚本的底部。

感谢您抽出时间。

Answer 1

问题在于，匹配可以通过多种方式扩展为以语句结尾的内容（因此是不匹配）。特别是，While_statement、for_statement 和 with_statement 都以没有任何终止符的statement 结尾。因此该语句可能是一个不匹配 (if)，因此如果它出现在THEN之后，就会触发歧义。例如：

IF expression THEN WHILE expression DO IF expression THEN statement ELSE statement

是不明确的，因为 ELSE 可以绑定到任一 IF。要修复它，您需要拆分
所有可能以匹配 和不匹配 版本的语句结尾的语句。所以你最终会得到

statement : matched
| unmatched
;

matched: assignment 
| matched_if_statement
| case_statement 
| matched_while_statement 
| matched_for_statement 
| matched_with_statement 
| subprogram_call  
| io_statement 
| comp_statement
|
;

unmatched: unmatched_if_statement 
| unmatched_while_statement 
| unmatched_for_statement 
| unmatched_with_statement 
;

matched_while_statement : WHILE expression DO matched
;

unmatched_while_statement : WHILE expression DO unmatched
;

etc。

unmatched规则全部扩展为一些复杂的语句，该语句以不匹配的if结尾，没有相应的else，而else不能出现在THEN和ELSE之间。