野牛语法中的悬空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

问题是，matched可以扩展到以statement结束的东西(因此是unmatched)的方法有很多。特别是While_statement、for_statement和with_statement都以没有终止符的statement结束。因此，statement可能是unmatched(如果)，因此，如果它出现在THEN之后，它就会触发歧义。例如:

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

是二义性的，因为ELSE可以绑定到IF。要解决这个问题，你需要分裂将所有可能以语句结尾的语句转换为matched和unmatched版本。最后你会得到

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
;

等

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