Yacc/Bison 用于 Verilog 分层和排列标识符

Question

我正在尝试解析 Verilog 语言中的标识符。完整的语法是 here.

他们可以有以下形式：

name
name[index]
name[start:stop]
name[index][start:stop]
name.(any of the above)
name[index].(any of the above)
name[index].name[index]... .name[index][start:stop]

或 EMBF 格式：

(name ([index])?)+ ([start:stop])?

这里的name是大多数编程语言中的典型标识符，而index、start和stop是整数。

我是 yacc 的新手（我实际上使用的是 Jison），但我不确定是否可以通过单个先行标记限制正确解释这一点。如果 name 和 [ 在堆栈中，它无法区分索引和开始。

到目前为止，这是我的语法：

primary 
: number
| hierarchical_identifier bracketted_range_expression
| hierarchical_identifier
;

primary 
: number
| hierarchical_identifier
| hierarchical_identifier bracketted_range_expression
;

hierarchical_identifier
: IDENTIFIER
| IDENTIFIER '[' UNSIGNED_NUMBER ']'
| hierarchical_identifier '.' IDENTIFIER
| hierarchical_identifier '.' IDENTIFIER '[' UNSIGNED_NUMBER ']'
;

bracketted_range_expression
: '[' range_expression ']';

range_expression
: UNSIGNED_NUMBER ':' UNSIGNED_NUMBER

这会产生几个 shift/reduce 和 reduce/reduce 错误，它根本不想解析某些行 foo[1:0]。它期望 ] 而不是 :。有什么办法可以解决这个问题？

Answer 1

您的分析是正确的。使用您的语法，必须在解析器开始扫描 bracketed_range_expression 之前减少 hierarchical_identifier，但它无法知道 IDENTIFIER 之后的 [ 是否启动 bracketed_range_expression（在这种情况下，减少是必要的）或者是 '[' UNSIGNED_NUMBER ']' 中的 [（在这种情况下，它应该被移动）。

对于 bison，我们可以使用 GLR 解析器解决这个问题，但对于 jison，我们仅限于 LALR(1)。好在语言还是LALR(1)；所需要的只是通过扩展一些非终结符并在以后减少它们来推迟 shift/reduce 决定。

不幸的是，结果有点难看，因为它需要一定数量的重复。因为我们需要始终能够移动 [，所以我们最终得到 "denormalizing" 语法（借用数据库设计中的一个术语）。

这是一种解决方案，已使用 the jison on-line tool 进行测试。（这些操作只是为了表明语法将范围附加到整个层次列表，而不仅仅是列表中的最后一个标识符。）

/* lexical grammar */
%lex
%%

\s+                   /* skip whitespace */
[0-9]+                return 'NUMBER'
[a-zA-Z][a-zA-Z0-9]*  return 'IDENTIFIER'
.                     return yytext[0]
<<EOF>>               return 'EOF'

/lex

%start expr

%% /* language grammar */

expr   : primary EOF { return ; }
       ;

primary: NUMBER
       | hierarchical_identifier
       | hierarchical_identifier_with_range
       ;

indexed_identifier
       : IDENTIFIER '[' NUMBER ']' { $$ = { "id": , "idx": }; } ;

postfix_range
       : '[' NUMBER ':' NUMBER ']' { $$ = [ ,  ]; } ;

hierarchical_identifier
       : IDENTIFIER         { $$ = []; $$.push({ "id": }); }
       | indexed_identifier { $$ = [  ]; }
       | hierarchical_identifier '.' IDENTIFIER
                            { $$ = ; $$.push({ "id": }); }
       | hierarchical_identifier '.' indexed_identifier
                            { $$ = ; $$.push(); }
       ;

hierarchical_identifier_with_range
       : IDENTIFIER postfix_range
                            { $$ = { "idlist": [{"id": }],
                                     "lo": [0], "hi": [1]}; }
       | indexed_identifier postfix_range
                            { $$ = { "idlist": [],
                                     "lo": [0], "hi": [1]}; }
       | hierarchical_identifier '.' IDENTIFIER postfix_range
                            { .push({"id": });
                              $$ = { "idlist": ,
                                     "lo": [0], "hi": [1]}; }
       | hierarchical_identifier '.' indexed_identifier postfix_range
                            { .push();
                              $$ = { "idlist": ,
                                     "lo": [0], "hi": [1]}; }
       ;

如果您最终计划使用 bison，您可能会发现 GLR 解析器更简单，而且不会增加太多解析开销（因为您的语法确实没有歧义）。

Yacc/Bison 用于 Verilog 分层和排列标识符

Yacc/Bison for Verilog hierarchical and arrayed identifiers

yacc

jison