c - 通过生成源代码与原始代码进行比较来验证您的 flex 和 yacc 代码是否正常工作

Question

我正在从事一个项目，将用 Second Life 的 LSL 语言编写的脚本转换为 Lua。我正在为这个项目学习 flex 和 btyacc。实际上，这是一个更大的项目，这只是其中的一部分。 http://www.sqlite.org/cgi/src作为第一步，我想确保我生成的 AST 是输入的准确反射(reflect)。所以我的想法是从那个 AST 生成一个新文件，然后比较它们。这意味着我需要在 AST 中包含空格和注释，这样当我使用它生成结果文件时，它包含完全相同的空格和注释。

我在处理空白区域时遇到了问题。搜索和试验了好几天，但一无所获。我看到的每个例子都只是忽略了空白，而不是存储它以备后用。我想我会遇到与评论完全相同的问题，因为它们基本上只是另一种形式的可以忽略的空间。

我原以为这是一件标准的事情，但我找不到任何例子。有人知道类似事情的例子吗？

源代码在 github 上，如果有人想查看它并提出一种方法。

https://github.com/onefang/SledjHamr/blob/experimental/LuaSL/src LuaSL_yaccer.l、LuaSL_yaccer.y、LuaSL_LSL_tree.h 和 LuaSL_LSL_tree.c

识别空格的弹性线的 Action 被注释掉了。如果我取消评论，我会收到一个解析错误。

解决方案

我使用了 bdonlan 的解决方案，但在实现过程中我将项目转移到使用 lemon 而不是 btyacc。这就是我所做的。下面的源代码是经过简化的。

使用 lemon，您可以创建一个调用词法分析器的循环，然后获取词法分析器调用的结果并将其传递给解析器。我的循环每次都分配一个新的 yylval 结构，这个结构包含一个用于空白或注释的 char 指针。我也使用这个 yylval 作为我的 AST 节点结构，因为它已经包含了我需要的大部分内容，并且节省了重新分配内存或复制内容的时间。

struct AST_node
{
    struct AST_node  *left;
    struct AST_node  *right;
    char             *white_space;
    struct AST_token *token;    /* common() stashes a pointer to a token structure here.  */
    int               line, column;
    union
    {
        /* The various types of symbols are stored here as per usual, including this one - */
        int operationValue;
    } value;
}

struct AST_node *lval = calloc(1, sizeof(struct AST_node);

while((yv = yylex(lval)) != 0)
{
    Parse(pParser, yv, lval);
    lval = calloc(1, sizeof(struct AST_node));
}

在词法分析器中，我有一个从每个正则表达式操作部分调用的 common() 函数。除其他事项外，如果是注释或空白，我会将文本保存到静态累加器中。如果不是注释或空格，那么我将累加器(如果存在)存储在 yylval 结构中，并清除累加器。此累加器将空白和注释聚集在一起，因此 yylval 中的任何给定的都可以包含两者。

如果它只是空白/注释，词法分析器不会返回一个符号，因此它会累积它们直到它开始发出一个实际的符号。

在 lemon 中，所有终端和非终端都是用于 yylval 的类型，因此我可以将其传递给操作部分中的 C 代码。例如-

expr(A) ::= expr(B) LSL_ADD(D) expr(C).  { A = addOperation(D, LSL_ADD, B, C); }

LSL_ADD 是词法分析器发出的符号，D 是它的值，它是我在主循环中创建的要传递给词法分析器的 yylval。在这种情况下，addOperation() 将指向左右 AST 节点(B 和 C)的指针添加到 AST 结构(D)中，并将符号塞入其中(以便我后来知道这个特定操作是一个加法) .

struct AST_node *addOperation(struct AST_node *lval, int type, struct AST_node *left, struct AST_node *right)
{
    lval->left = left;
    lval->right = right;
    lval->value.operationValue = type;
    return lval;
}

后来，当我从 AST 重构原始源代码时，我只是在同一个 AST 节点中输出符号之前输出空白/注释。

是的，我知道上面的代码有一些重复，不需要在 token 成员和 union 中都存储类型。稍后我会从我的代码中清除它。不过现在，它只是为了说明正在发生的事情。

Answer 1

很少有 AST 是原始源的精确、可逆转换。例如，括号可能会在解析过程中丢失(仅用于优先级但在最终 AST 中被省略)，或者空格可能被消除。

存储标记的行和/或字符偏移量以便错误消息可以引用它们的来源是相当常见的，但这还不足以实现完全可逆性。

我建议不要使用完全可逆的 AST，而是使用已知 AST 结果和生成它们的输入的测试套件。但是，如果必须，您可以将所有空格与终端标记一起存储 - 例如，如果您有如下代码:

1 + /* this is a comment */ 2

那么 + 对应的 AST 节点将包含 + 之前的单个空格，而 2 的节点将包含 /* 这是一条注释 */ 作为额外的空白数据。然后，当您反转转换时，您可以随时恢复此空白。当然，这也需要对括号等语法特征进行显式编码。

使用 lex/yacc，您可以通过维护一个单独的空白/注释累加器(或输入缓冲区的索引)来实现这一点；当您看到空格或注释时，更新此累加器但不发出 token 。当您命中任何其他 token (包括 EOF)时，将此数据移动到不同的累加器并重置主累加器。一旦您返回到 yacc，您的 yacc 终端就可以检查这个辅助累加器，并将它们存储到您分配给终端的任何数据结构中。