Verilog的variable_lvalue怎么能写给Bison呢？

Question

我正在研究 Verilog 解析器，使用 Bison 根据语言的正式规则制作解析器。

这个BNF形式化的语法规范来自IEEE Standard 1364-2001《IEEE标准Verilog硬件描述语言参考手册(LRM)》。

variable_lvalue ::=
    hierarchical_variable_identifier
  | hierarchical_variable_identifier <b>[</b> expression <b>]</b> { <b>[</b> expression <b>]</b> }
  | hierarchical_variable_identifier <b>[</b> expression <b>]</b> { <b>[</b> expression <b>]</b> } <b>[</b> range_expression <b>]</b>
  | hierarchical_variable_identifier <b>[</b> range_expression <b>]</b>
  | variable_concatenation

为了清楚起见，省略了层次标识符，将单个表达式的简化分解为 range_expression 到它自己的规则中，并使用左递归（range_expression 可能在也可能不在表达式的末尾列表）这就是我所拥有的。

nonempty_expression_in_brackets_list
    : OPENBRACKETS range_expression CLOSEBRACKETS { }
    | OPENBRACKETS expression CLOSEBRACKETS { }
    | OPENBRACKETS expression CLOSEBRACKETS nonempty_expression_in_brackets_list { }
    ;

range_expression是这样定义的

range_expression ::= 
    expression
  | msb_constant_expression: lsb_constant_expression
  | base_expression +: width_constant_expression
  | base_expression -: width_constant_expression

省略将单个表达式简化为 range_expression 的规则，这就是我所拥有的。

range_expression
  : constant_expression COLON constant_expression { }
  | expression PLUS COLON constant_expression     { }
  | expression MINUS COLON constant_expression    { }
  ;

即使在只使用一个表达式的最简单情况下，函数也存在问题。具体来说，解析器无法决定是将括号后的标识符缩减为 constant_function_argument 还是 function_argument（我希望 constant_function_call 或 function_call 在规则，但不是两者）。例如，解析后的文本中的类似内容会出现问题。

IDENTIFIER [ IDENTIFIER ( IDENTIFIER ) ]

第三个标识符是否缩减为function_argument，期待稍后缩减为function_call，最后缩减为expression，还是缩减为constant_function_argument，期待更晚的减少到 constant_function_call，最后减少到 constant_expression?

我认为此时两者都是正确的，在看到 CLOSEBRACKETS 或 COLON 或 PLUS COLON 或 MINUS COLON 之前我们无法确定。

我是否应该添加 bison 的 glr 选项来克隆解析器并使其在发生冲突时消失？有没有不同的语法书写方式？

Answer 1

我对 Verilog 了解不多，OP 中甚至没有文档 link；此外，大多数引用的语法产品也不在 OP 中。因此，我能做的最好的事情就是提供一些一般性指导，结合我对 Verilog 的一些知识片段——据我所知，正确解析这些知识并非易事。

如前所述，在解析 variable_lvalue 时存在（至少）两个问题，尽管最终它们惊人地相似：

Verilog 语法似乎需要在句法上区分常量和非常量表达式；和
hierarchical_variable_name中的[...]（至少）有三种不同的含义，它们的语法略有不同但有重叠。（这里我被一个不同的 SO 问题所引导；这个问题只展示了三种语法中的两种。）

常量和非常量表达式

从技术上讲，语法提供了 constant_expressions 和不合格的 expressions，因为每个表达式上下文将从 expression 或 constant_expression （或某些同义词）产生对于这两个非终端之一）。然而，在自下而上的解析器中，如果两个表达式文法相互排斥会更容易。忽略运算符优先级，基本方案为：

expression             : constant_expression
                       | non_constant_expression;

non_constant_expression: non_constant_primary
                       | unary_operator non_constant_primary
                       | non_constant_expression binary_operator expression
                       | constant_expression binary_operator non_constant_expression

constant_expression    : constant_primary
                       | unary_operator constant_primary
                       | constant_expression binary_operator constant_expression

除了区分 constant_primary 和 non_constant_primary 的问题外，这将工作正常。显然，文字（数字和字符串）是 constant_primary，并且（碰巧）具有至少两个组件的层次结构名称是 non_constant_primary。但简单的标识符可能是其中之一。

对于那些必须在使用前声明标识符的情况（或语言），可以通过在符号 table.[=37 中查找标识符来区分常量和非常量标识符=]

为此，符号 table 需要与词法分析器共享，并且一定数量的关于名称查找的逻辑需要对词法分析器可用，尤其是在语言允许范围名称的情况下。许多 C 解析器正是这样做的，因为有些表达式在不知道标识符是类型还是变量的情况下无法解析。（(something)+1/2，例如：如果 something 是 double，则为 0.5，如果 something 是一个值为 0.0 的变量，则为 0.0。）

但是这个策略在常量函数上失效了，因为常量函数不需要在使用前声明。（允许相互递归常量函数。）尽管如此，由于常量函数调用是在与非常量函数调用不同的阶段求值的，因此为每个调用点决定它是否是常量调用很重要。

此外，在解析器和词法分析器之间共享符号 table 违反了关注点分离。而且它并不像听起来那么容易：词法分析器无法知道标识符的实例是定义还是直接使用。区分使用标识符标记作为非限定名称还是作为层次名称的一部分是非常重要的（对于词法分析器）。（我不知道分层子组件名称是否可以与参数名称相同，但它们可能是合理的；当然，在大多数语言中，结构成员名称可以与全局常量拼写相同，而不会产生任何歧义。）

除了明确需要进行语义分析以确定给定的函数标识符是否有资格成为 constant_function_identifier 之外，在我看来唯一合理的策略是生成 AST，解析表达式而不考虑它们是否应该是常量，然后执行遍历 AST 的验证以验证在那些要求表达式为常量的上下文中是否只出现常量表达式。（可能会有一个中间 AST 来确定哪些函数可以用作常量函数调用。）

这将简化语法，并将常量表达式分析限制在单个明确定义的接口中，而不是将其涂抹在整个语法上。

第二个问题是因为使用了括号：

作为生成名称的选择器（在这种情况下只允许文字整数）
作为数组索引（在这种情况下允许任意表达式）
作为范围定义，它可能看起来像数组索引，但也可能是两个用冒号分隔的常量表达式（但不一定是文字）。

单个选择器可以跟在分层名称中的任何组件之后，而数组索引和范围表达式是跟在分层名称之后的后缀运算符；如果存在，范围表达式必须排在最后。

据我了解，选择器和数组索引是必需的还是禁止的，具体取决于命名对象的声明。但是在不知道标识符声明的情况下，这三种用途并不总是可以区分的：[1] 可能是三种可能性中的任何一种。

理论上，在符号 table 中查找标识符可以解决问题。但是标识符可以出现在许多可能的上下文中；期望词法分析器确定何时适合坚持选择器或索引可能会促使词法分析器重复解析器的太多工作。

所以再一次，似乎在语义规则中进行分析会容易得多。在这种情况下，我相信，可以在解析时进行分析，因为需要预先声明，因此进行检查的适当位置将在 variable_lvalue.

的缩减规则中

如果你走那条路，语法过于复杂是没有意义的。您可以使用接受一些句法错误输入的语法，知道所有此类错误都会被语义规则检测到。最简单的这种语法只接受 .name 和 [...] 后缀的任何序列：（见注释 1）

hierarchical_lvalue: hierarchical_component
                   | hierarchical_lvalue '.' hierarchical_component
                   | hierarchical_lvalue '[' expression ']'
                   | hierarchical_lvalue '[' expression ':' expression ']'
                   | hierarchical_lvalue '[' expression "+:" expression ']'
                   | hierarchical_lvalue '[' expression "-:" expression ']'

备注

在这个回答中，我避免对单字符标记使用笨拙的符号名称，例如 :。 Bison 允许您将其写为 ':'（在 flex 操作中，您 return ':';），甚至不必将其声明为 %token；结果是 IMO 更具可读性并且更容易维护。为了可读性，我还使用了双引号标记别名；而不是写

%令牌PLUS_COLON %% .... : 表达式 PLUS_COLON 表达式 ...

你可以声明别名

%token PLUS_COLON "+:"
%%
.... : expression "+:" expression ...

在这种情况下，词法分析器仍然需要使用符号名，但语法更容易阅读。（错误消息也是如此，如果您使用扩展错误消息：bison 将能够告诉用户 ":", "+:" or "-:" 是预期的。）

Verilog的variable_lvalue怎么能写给Bison呢？

How can Verilog's variable_lvalue be written for Bison?

parsing

verilog

bison

常量和非常量表达式

备注