由于可选块的有序声明，导致语法不明确

Question

我需要帮助为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;

其思想是任何X_block都可以是空的。我理解移位-减少冲突，因为当启动和接收标识符(IDEN)时，它不知道是在const_block ::= <empty>中减少并将IDEN作为dec_variable的一部分，还是移位并将IDEN令牌作为const_block的一部分。如果我删除const_block或type_block中的空/epsilon生成，冲突就会消失，尽管语法会不正确，因为它将是一个无限的常量列表，并且它会在保留字"中给出语法错误；类型"；。

所以我可能会产生歧义，因为常数和变量都可以从一开始就以"0"开头；id："；并且任一块都可以首先出现。我如何重写规则以解决歧义及其引起的转移/减少冲突？

我试着做一些类似的事情：

declaration_block ::= const_block types_block var_block | const_block types_block | const_block var_block | types_block var_block | types_block | var_decl | ;

但我也有同样的问题。

另一种尝试是创建new_rules来识别它是常量还是变量。。。但是contant_block中的空规则的范围并没有消失。

dec_const ::= start_const ASSIGN valor_constantes SEMICOLON;
start_const ::= IDEN TWOPOINT CONSTANT;

// dec_var ::=  start_variables SEMICOLON;
// start_var ::=  lista_iden TWOPOINT tipos_validos;

如果我把问题简化为更简单的问题，不考虑类型，只允许一个常量或变量的声明，那么这些块可能是空的这一事实就会产生问题：

dec_var ::=  iden_list TWOPOINT valid_types SEMICOLON | ;
iden_list ::= IDEN | IDEN COMMA lista_iden;

我希望以某种方式改写规则，以解决这一冲突，并在未来处理类似的问题。

非常感谢

Answer 1

首先，您的语法并不含糊。但它确实有一个shift-reduce冲突(事实上，其中有两个)，这表明它不能仅用一个前瞻性令牌进行确定性解析。

碰巧的是，如果您有一个解析器生成器，可以通过增加前瞻性来解决问题(或多或少)。然而，这样的解析器生成器非常罕见，CUP不是其中之一。有一些解析器生成器可以通过回溯(可能带有记忆，如ANTLR4)或通过使用允许并行探索多个备选方案的算法(例如GLR)来允许任意前瞻。但我不知道有什么解析器生成器可以生成一个使用两个前瞻性令牌的确定性转换表(在这种情况下，这就足够了)。

因此，解决方案是在语法中添加一些明显的冗余，以排除需要多个先行标记的情况。

基本问题是以下一组可能的输入：

...; a : constant 3 ; ...
...; a : Integer ; ...

这里没有任何歧义。第一个只能是一个常量声明；第二个只能是变量声明。但请注意，直到我们看到关键字constant(如第一种情况)或可能是类型的标识符(如第二种情况)，我们才会发现这个事实。

这意味着我们需要避免强制解析器做出任何涉及a和:的决定，直到下一个令牌可用。特别地，我们不能强迫它决定a是仅仅是IDEN，还是iden_list中的第一个(或唯一一个)元素。

解析需要iden_list

...; a , b : Integer ; ...

但这不是问题，因为CCD_ 14是我们有列表的明确标志。因此，该分辨率必须包括对CCD_ 15进行加扰而不将CCD_ 16缩减为CCD_ 17。这需要(显然)冗余生产：

var_block::=
| dec_var var_block
dec_var     : iden_list ':' type ';'
| IDEN ':' type ';'
iden_list   : IDEN ',' IDEN
| iden_list ',' IDEN

(注意：我把valid_types改成了type，因为valid是多余的——只解析有效的语法——而且我认为你永远不应该对单数对象使用复数名称；这会让读者感到困惑。)

然而，这还不够，因为我们还需要避免强制解析器在变量声明之前决定是否需要减少const_block。为此，我们需要类似于您已经尝试删除空块定义，而是提供八个不同的declaration_block生成，八个可能的空子句中的每一个都有一个。只要您将块定义更改为左递归而不是右递归，这将很好地工作。正确的递归定义迫使解析器在const_block的末尾执行缩减，这意味着它只需要知道const_block的末尾在哪里，只有一个先行标记。

总的来说，如果你要使用像CUP这样的自下而上的解析器，你应该养成使用左递归的习惯，除非你有充分的理由不这样做(比如定义右关联运算符)。有一些例外，但总的来说，左递归会产生更少的惊喜，此外，它不会在长输入时烧穿解析器堆栈。

做出所有这些改变，我们最终会得到这样的结果，其中：

• 块定义被更改为具有非空基本情况的左递归定义
• ident_list被迫具有至少两个元素；冗余的"；为一个标识符的情况增加了生产
• 开始生产被分为八种可能的组合，以允许三个子条款中的每一个都是空的
• 进行了一些小的名称更改

declaration_block ::= 
|                           var_block
|               types_block
|               types_block var_block
|   const_block 
|   const_block             var_block
|   const_block types_block
|   const_block types_block var_block
;
// Constant declaration
const_block ::= dec_const
|   const_block dec_const ;
dec_const   ::= IDEN TWOPOINT CONSTANT ASSIGN const_value SEMICOLON;
//Types declaration
types_block ::= dec_type
|   types_block dec_type ;
dec_type    ::= TYPE IDEN IS RECORD
reg_list
END RECORD SEMICOLON;
reg_list    ::= dec_reg 
|   reg_list dec_reg;
dec_reg     ::= IDEN TWOPOINT type SEMICOLON;
//Variable declaration
var_block   ::= dec_var
|   var_block dec_var;
dec_var     :   iden_list ':' type ';'
|   IDEN ':' type ';' ;
iden_list   :   IDEN ',' IDEN
|   iden_list ',' IDEN;

// common use
const_value ::= INT | boolean;
boolean     ::= TRUE | FALSE;
type        ::= primitive_type | IDEN;
primitive_type ::= INTEGER | BOOLEAN;