Yacc/Bison用于Verilog分层和数组标识符

Question

我正在尝试解析Verilog语言中的标识符。完整的语法在这里。

可以有以下形式:

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和[在堆栈中，它无法区分index和start。

这是我学到的语法:

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

你的分析是正确的。在你的语法中，hierarchical_identifier必须在解析器开始扫描bracketed_range_expression之前进行约简，但是它不能知道IDENTIFIER之后的[是否开始了bracketed_range_expression(在这种情况下，需要进行约简)，或者[是否在'[' UNSIGNED_NUMBER ']'中(在这种情况下，它应该被移动)。

对于bison，我们可以使用GLR解析器来解决这个问题，但是对于jison，我们仅限于LALR(1)。幸运的是，语言仍然是LALR(1);所需要做的就是通过扩展一些非终结符并稍后减少它们来推迟shift/reduce决策。

不幸的是，结果有点难看，因为它需要一定数量的重复。因为我们需要始终能够移动[，我们最终"非规范化"语法(借用数据库设计中的术语)。

这里有一个解决方案，用jison在线工具进行了测试。(这些操作只是为了显示语法将范围附加到整个层次列表，而不仅仅是附加到列表中的最后一个标识符。)

/* 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 $1; }
       ;
primary: NUMBER
       | hierarchical_identifier
       | hierarchical_identifier_with_range
       ;
indexed_identifier
       : IDENTIFIER '[' NUMBER ']' { $$ = { "id": $1, "idx": $3}; } ;
postfix_range
       : '[' NUMBER ':' NUMBER ']' { $$ = [ $2, $4 ]; } ;
hierarchical_identifier
       : IDENTIFIER         { $$ = []; $$.push({ "id": $1}); }
       | indexed_identifier { $$ = [ $1 ]; }
       | hierarchical_identifier '.' IDENTIFIER
                            { $$ = $1; $$.push({ "id": $3}); }
       | hierarchical_identifier '.' indexed_identifier
                            { $$ = $1; $$.push($3); }
       ;
hierarchical_identifier_with_range
       : IDENTIFIER postfix_range
                            { $$ = { "idlist": [{"id": $1}],
                                     "lo": $2[0], "hi": $2[1]}; }
       | indexed_identifier postfix_range
                            { $$ = { "idlist": [$1],
                                     "lo": $2[0], "hi": $2[1]}; }
       | hierarchical_identifier '.' IDENTIFIER postfix_range
                            { $1.push({"id": $3});
                              $$ = { "idlist": $1,
                                     "lo": $4[0], "hi": $4[1]}; }
       | hierarchical_identifier '.' indexed_identifier postfix_range
                            { $1.push($3);
                              $$ = { "idlist": $1,
                                     "lo": $4[0], "hi": $4[1]}; }
       ;

如果您最终计划使用bison，您可能会发现GLR解析器更容易，而不会增加太多的解析开销(因为您的语法确实是明确的)。