野牛的相互递归

Question

我想创建一个解析器使用flex /野牛的类似verilog语言（或更具体的Verilog与一些额外的结构，用于生成verilog代码），我无法找出如何构建我的野牛规则来处理语言中可用的一般类型的构造。

该构建体的一般实例是这样的：

(
output wire   up_o, 
input wire [4:0] up_i, 
/////////////////////////////////////////////////////////// 
// A comment 
/////////////////////////////////////////////////////////// 
`my_if (`$a eq `$b) 
    input wire  a_{n}_clk_i, 
    output wire  a_{n}_rst_o, 
`my_endif 
output wire           out_o 
); 

原则上my_if可以嵌套和();一切内可以是my_if块内，而没有任何my_if。这使我相信我目前的想法是有缺陷的，而且我根本不明白如何做这个相互递归。

什么似乎导致我的问题是,终止块内的每一行，除了最后一行。我的词法分析器忽略注释并将线条标记为好，我还专门解析my_if行。

下面是相关野牛规则我现在有，

portdecla: 
'(' ports ')' ';' 
; 

ports: 
port 
| ports ',' port 
| ports ',' ifs 
| ifs 
; 

ifs: 
ifhead ports TENDIF 
| if 
; 

的ifhead和port解析my_if和输入/输出线的罚款。

如何建立这些规则的任何想法，将是非常赞赏

Answer 1

我有一点麻烦了解你的问题。如果你已经描述了这个问题，那将会容易得多，而不是模糊地断言它可能与逗号有关。当然，这与逗号有关：您的语法坚持在ifs之后以及在port之后有一个逗号。 （另外，无论是你没有复制和粘贴正确或有一些非常奇怪的约ifs）

其实，你并不需要ifs，但你需要在一个末端的if区分声明，任何其他if：

port_declaration: tail_ports; 

ports: port ',' 
    | port ',' ports 
    | if 
    | if ports 
    ; 
tail_ports 
    : port 
    | tail_if 
    | port ',' tail_ports 
    | if tail_ports 
    ; 
if : IF '(' condition ')' ports END_IF 
    ; 
tail_if 
    : IF '(' condition ')' tail_ports END_IF 
    ; 

（我写了右递归，因为它更容易理解，恕我直言，这也更容易建立AST出右递归名单见莱文，第66页。在现代机器上，解析堆栈的增长实际上没有问题;默认最大堆栈深度为10,000;如果这还不够，可以增加它。）

编辑：我想我终于得到了上面的权利。

这类问题通常通过解析两遍来解决;首先是一个预处理过程，其输出被输入到真正的解析器中。 Tokenizing只做一次;预处理解析器不区分语言标记;它只关心它自己的令牌。 （C预处理器可以使用##运算符来融合令牌，但它不会拆分令牌;这通常是一种合理的方法。）这可以通过bison实现，尽管正确地获取数据流是一个挑战;我个人比较喜欢lemon的方法，即词法分析器将令牌推送给解析器，因为这更容易扩展。

你的具体情况，但是，你要预处理器只接受完整的短语（port）这样的挑战，就像你说的，是越来越,的权利，即使在最后port被深埋的if建筑内。因此，上述方法区分if和tail_if。

有几种方法可以构建AST，具体取决于您是否可以在分析时评估条件。如果可以的话，那么你可以完全放弃不需要的端口，这可能是最简单的解决方案。

如果您需要申请的条件之前做整个解析，那么你仍然有几个选择：建立一个树的节点是要么port或conditional_list，或代码生成的风格明显的一个在其中有效地建立一个操作向量build-port和jump-if-condition-false。这两个选项都需要某种形式的标记联合。

/编辑（以下仍是不正确。）

typedef struct PortList { 
    Port* port; 
    struct PortList* next; 
} PortList; 

typedef struct ConditionalPortList { 
    Condition* cond; /* Optional condition; if absent, unconditional */ 
    PortList* ports; 
} ConditionalPortList; 

typedef struct PortDeclaration { 
    ConditionalPortList* clause; 
    struct PortDeclaration *next; 
} PortDeclaration; 

这很容易建立（它可能比这个片段更容易，我有一点练出来的。）（警告：未尝试过）：

%union { 
    PortList*   port_list; 
    ConditionalPortList* conditional; 
    PortDeclaration*  port_declaration; 
    /* ... */ 
} 
%type <port_list> ports 
%type <conditional> if always 
%type <port_declaration> port_tail port_declaration 
/* ... */ 

%% 

ports: port    { $$ = NewPortList($1, NULL); } 
    | port ',' ports { $$ = NewPortList($1, $3); } 
    ; 

if: IF '(' condition ')' ports ENDIF 
         { $$ = NewConditionalPortList($3, $5); } 
    ; 

always: ports   { $$ = NewConditionalPortList(NULL, $1); } 
     ; 

port_tail: if 
     | if port_tail { $$ = NewPortDeclaration($1, $2); } 
     | if always port_tail 
         { $$ = NewPortDeclaration($1, NewPortDeclaration($2, $3); } 
     ; 

port_declaration: 
      '(' always ')' ';' { $$ = $2; } 
     | '(' port_tail ')' ';' { $$ = $2; } 
     | '(' always port_tail ')' ';' 
           { $$ = NewPortDeclaration($2, $3); } 
     ;