试图解决 Mini-C 文法的悬挂问题

Question

我有这个语法：

translation_unit 
    ::= external_declaration
    | translation_unit external_declaration

external_declaration 
    ::= function_definition
    | declaration

function_definition 
    ::= type_specifier declarator compound_statement
    | STATIC type_specifier declarator compound_statement

declaration 
    ::= type_specifier declarator ';'
    | EXTERN type_specifier declarator ';'

declaration_list_opt 
    ::= declaration_list
    | empty
    
declaration_list
    ::= declaration_list declaration
    | declaration

type_specifier 
    ::= INT
    | CHAR

declarator 
    ::= direct_declarator
    | ASTERISK declarator

direct_declarator 
    ::= ID
    | direct_declarator '(' parameter_type_list ')'
    | direct_declarator '(' ')'

parameter_type_list 
    ::= parameter_list ',' ELLIPSIS
    | parameter_list

parameter_list 
    ::= parameter_list ',' parameter_declaration
    | parameter_declaration

parameter_declaration 
    ::= type_specifier declarator

compound_statement 
    ::= '{' declaration_list_opt statement_list '}'
    | '{' declaration_list_opt '}'

expression_statement 
    ::= expression ';'

expression 
    ::= equality_expression

expression 
    ::= equality_expression '=' expression
    | equality_expression '+=' expression
    | equality_expression '-=' expression
    | equality_expression '*=' expression
    | equality_expression '/=' expression
    | equality_expression '%=' expression

equality_expression 
    ::= relational_expression

equality_expression 
    ::= equality_expression '==' relational_expression
    | equality_expression '!=' relational_expression

relational_expression 
    ::= additive_expression

relational_expression 
    ::= relational_expression '<'  additive_expression
    | relational_expression '>'  additive_expression
    | relational_expression '<=' additive_expression
    | relational_expression '>=' additive_expression

postfix_expression 
    ::= primary_expression
    | postfix_expression '(' argument_expression_list ')'
    | postfix_expression '(' ')'
    | postfix_expression '[' expression ']'


argument_expression_list 
    ::= argument_expression_list ',' expression
    | expression

unary_expression 
    ::= postfix_expression
    | '-' unary_expression
    | '+' unary_expression
    | '!' unary_expression
    | '*' unary_expression
    | '&' unary_expression

mult_expression 
    ::= unary_expression

mult_expression 
    ::= mult_expression '*' unary_expression
    | mult_expression '/' unary_expression
    | mult_expression '%' unary_expression

additive_expression 
    ::= mult_expression
    | additive_expression '+' mult_expression
    | additive_expression '-' mult_expression

primary_expression 
    ::= ID
    | INUMBER
    | FNUMBER
    | CHARACTER
    | string_literal
    | '(' expression ')'
    
string_literal 
    ::= string_literal STRING
    | STRING

statement 
    ::= compound_statement
    | expression_statement
    | selection_statement
    | iteration_statement
    | jump_statement

jump_statement 
    ::= RETURN ';'
    | RETURN expression ';'
    | BREAK ';'
    | CONTINUE ';'

iteration_statement 
    ::= WHILE '(' expression ')' statement
    | FOR '(' expression_statement expression_statement expression ')' statement

selection_statement 
    ::= IF '(' expression ')' statement
    | IF '(' expression ')' statement ELSE statement
    
statement_list 
    ::= statement_list statement
    | statement

当我使用 Sly 实现解析器时，它说 selection_statement 有一个减少冲突的转变。

我正在尝试不使用优先级来解决它。

我尝试使用这样的东西：

@_("matched",
   "unmatched")
   def selection_statement(self, p):
      pass
    
@_("IF '(' expression ')' matched ELSE matched")
   def matched(self, p):
      pass

@_("IF '(' expression ')' matched",
   "IF '(' expression ')' unmatched",
   "IF '(' expression ')' matched ELSE unmatched")
   def unmatched(self, p):
      pass

但是它对匹配有无限递归。

我尝试在 matched 上添加其他语句来解决递归问题，但它只会产生更多冲突。

我应该用什么来消除递归？

Answer 1

我找到了答案。我只需要修改我的语法看起来像这样：

statement 
    ::= matched
    | unmatched

matched 
    ::= if_matched
    | iteration_statement_matched
    | compound_statement
    | expression_statement
    | jump_statement

unmatched
    ::= if_unmatched
    | iteration_statement_unmatched

if_matched 
    ::= IF '(' expression ')' matched ELSE matched

if_unmatched 
    ::= IF '(' expression ')' statement
    | IF '(' expression ')' matched ELSE unmatched

iteration_statement_matched 
    ::= WHILE '(' expression ')' matched

iteration_statement_matched 
    ::= FOR '(' expression_statement expression_statement expression ')' matched

iteration_statement_unmatched 
    ::= WHILE '(' expression ')' unmatched

iteration_statement_unmatched 
    ::= FOR '(' expression_statement expression_statement expression ')' unmatched

我用这篇文章作为参考：Shift/reduce conflict in java cup - dangling else issue