0

我正在尝试解析 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 错误，它根本不想解析 line foo[1:0]。它期望 a]代替:. 有什么办法可以解决这个问题？

4

1 回答 1

1

你的分析是正确的。使用您的语法，hierarchical_identifier必须在解析器开始扫描之前进行归约bracketed_range_expression，但它无法知道[后面的 an 是IDENTIFIER开始 a bracketed_range_expression（在这种情况下需要归约）还是[in '[' UNSIGNED_NUMBER ']'（在这种情况下应该转移）。

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

不幸的是，结果有点难看，因为它需要一定数量的重复。因为我们需要始终能够转换[，所以我们最终会“反规范化”语法（借用数据库设计中的一个术语）。

这是一种解决方案，使用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 解析器更容易，而不会增加太多解析开销（因为您的语法确实是明确的）。

于 2015-08-02T05:14:19.417 回答