CUPS语法可选块顺序声明引发移位归约冲突的解决求助

需求与示例代码 #

需要定义CUPS语法的声明块，要求包含0或多个常量声明、0或多个类型记录声明、0或多个变量声明，三者必须按「常量→类型→变量」的固定顺序出现，但任意块可省略。待解析示例代码如下：

x: constant := True;
y: constant := 32

type Tpersona is record
    dni: Integer;
    edad : Integer;
    casado : Boolean;
end record;
    type Tfecha is record
    dia: Integer;
    mes : Integer;
    anyo : Integer;
end record;
    type Tcita is record
    usuario:Tpersona;
    fecha:Tfecha;
end record;

a: Integer;
x,y: Boolean;
x,y: Boolean;
x,y: Boolean;

当前语法的冲突问题 #

原语法将声明拆分为三个独立的可选块，每个块支持空产生式，导致移位归约冲突：

declaration_block ::= const_block types_block var_block;

// Constant declaration
const_block ::= dec_const const_block | ;
dec_const ::= IDEN TWOPOINT CONSTANT ASSIGN const_values SEMICOLON;

//Types declaration
types_block ::= dec_type types_block | ;
dec_type ::= TYPE IDEN IS RECORD
                reg_list
             END RECORD SEMICOLON;
reg_list ::= dec_reg reg_list | dec_reg;
dec_reg ::= IDEN TWOPOINT valid_types SEMICOLON;


//Variable declaration
var_block ::= dec_var var_block | ;
dec_variable ::=  iden_list TWOPOINT valid_types SEMICOLON;
iden_list ::= IDEN | IDEN COMMA iden_list;

// common use
const_values ::= INT | booleans;
booleans ::= TRUE | FALSE;
valid_types ::= primitive_types | IDEN;
primitive_types ::= INTEGER | BOOLEAN;

冲突原因：解析器收到IDEN token时，无法判断是移进作为常量声明的开头，还是先归约空的const_block/types_block，再作为变量声明的一部分——常量与变量声明的前两个token均为IDEN+TWOPOINT，导致决策歧义。

改写后的语法规则 #

调整规则结构，利用前瞻token明确区分不同声明类型，同时保留固定顺序要求：

declaration_block ::= const_decls type_decls var_decls ;

// 常量声明块：仅当后续存在IDEN : CONSTANT时解析
const_decls ::= const_decl const_decls | ;
const_decl ::= IDEN TWOPOINT CONSTANT ASSIGN const_values SEMICOLON ;

// 类型声明块：仅当后续存在TYPE时解析
type_decls ::= type_decl type_decls | ;
type_decl ::= TYPE IDEN IS RECORD reg_list END RECORD SEMICOLON ;
reg_list ::= dec_reg reg_list | dec_reg ;
dec_reg ::= IDEN TWOPOINT valid_types SEMICOLON ;

// 变量声明块：处理剩余IDEN开头的声明
var_decls ::= var_decl var_decls | ;
var_decl ::= iden_list TWOPOINT valid_types SEMICOLON ;
iden_list ::= IDEN | IDEN COMMA iden_list ;

// 公共规则
const_values ::= INT | booleans ;
booleans ::= TRUE | FALSE ;
valid_types ::= primitive_types | IDEN ;
primitive_types ::= INTEGER | BOOLEAN ;

规则说明 #

CUPS的LALR(1)解析器会通过前瞻token自动决策：

1. 遇到IDEN后，若后续是TWOPOINT CONSTANT，则移进解析常量声明；
2. 若后续是TWOPOINT+类型（INTEGER/BOOLEAN/自定义类型ID），则先归约空的const_decls和type_decls，再解析变量声明；
3. 类型声明以TYPE开头，与其他声明无起始冲突，可直接识别。

同类问题解决思路 #

1. 利用前瞻token区分路径：当不同产生式有共同前缀时，通过后续1~N个token明确归约/移位动作，比如本例中用CONSTANT标记常量声明；
2. 强化块的起始唯一性：让不同类型的声明使用唯一起始标记（如类型声明用TYPE），避免空块前置导致的歧义；
3. 调整产生式结构：将独立可选块整合为有序序列，让解析器能清晰判断当前处于哪个声明阶段；
4. 依赖LALR前瞻能力：LALR(1)支持单token前瞻，复杂场景可通过微调规则扩大前瞻区分度，消除冲突。

内容的提问来源于stack exchange，提问作者Eml0c