使用 yysindex 和 yyrindex 的 YACC 表达式的含义
Meaning of YACC expression using yysindex and yyrindex
在一个基于 yacc 的项目中，我遇到了一个复杂的表达式，但我不明白它的作用。表达式重复多次，因此看起来像复制粘贴。事实上，YACC 骨架 (byacc-1.9) 中也出现了完全相同的表达式，因此我假设它具有某些特定含义。
表达式如下：
if (((yyn = yysindex[lastyystate]) && (yyn += tok) >= 0 &&
yyn <= YYTABLESIZE && yycheck[yyn] == tok) ||
((yyn = yyrindex[lastyystate]) && (yyn += tok) >= 0 &&
yyn <= YYTABLESIZE && yycheck[yyn] == tok)) {
如果你对它进行分区，你会得到
((yyn = yysindex[lastyystate]) && (yyn += tok) >= 0 && yyn <= YYTABLESIZE && yycheck[yyn] == tok)
或
((yyn = yyrindex[lastyystate]) && (yyn += tok) >= 0 && yyn <= YYTABLESIZE && yycheck[yyn] == tok))
我对解析器生成器相当熟悉并且知道 yacc 是 LALR(1)。我猜
yysindex 是 "shift table"yyrindex 是 "reduce table"yyn <= YYTABLESIZE 只是范围检查
鉴于这两个部分的相似性，并且假设我的猜测是正确的，它们似乎都在 packed/coded 解析 table 中寻找某些东西。我还没有深入研究 yacc 如何存储解析 tables 的细节，如果有人对此有更多了解，那可能会有所帮助。
在这种情况下，tok 是（显然）令牌号。但是为什么 += tok 什么是 yycheck table?
此代码是源代码完成的一部分，例如使用 TAB，如果这有助于解释事情的话。
如果你能用一句话解释，比如给一个函数名，这个复杂表达式的意图是什么，加分。
"Next+check" transition table compression，通常也称为 comb 算法，在 Dragon book 的第 3.9 节中描述了关于词法分析器的内容，第 4 章中有关于其使用的注释使用解析器 tables.
该算法通过叠加行来存储稀疏矩阵，以便有效条目仅与缺失条目重叠。要在压缩的 table 中查找值，您需要每行的起始索引向量。然后将要查找的列号添加到该起始索引。最后，您需要知道该条目是否对应于您正在查找的行； check 向量包含每个 table 条目有效的行数。
之所以称为梳状压缩，是因为每一行就像一把梳子，上面有许多断齿。
在解析器框架中，该代码（或类似代码）将用于确定与令牌对应的解析器操作。可能的答案是：
移动令牌并转到状态 S。（将令牌压入堆栈并读取新的先行）。
用生产号P减栈。（弹出右边出栈，执行减量动作，从查询GOTOtable转到找到的状态pop 显示的状态和减少的非终结符的数量，将减少的非终结符压入堆栈，然后继续使用相同的先行标记。）
发出错误信号。
接受输入。 （仅当前瞻标记是输入结束标记时。这种可能性通常是特殊情况。）
我想你是对的，他们是分开的转变和减少行动 tables。如果您单独压缩操作，行可能会更好地重叠，尽管压缩必须好得多才能补偿额外的检查数组。
鉴于该代码用于构建完成列表，我想它被用于模拟每个可能的下一个标记的解析，以确定有效的下一个标记候选是什么。语句 returns true 如果令牌可以被执行（如果不能，候选人可以简单地从完成列表中删除）并将 yyn 设置为下一个操作。有必要区分 Shift 和 Reduce 操作。在某些解析器框架中，动作的符号用于此目的，但还有其他可能性。
所以我会调用函数 find_parse_action（或者 find_parse_action_if_any，如果你喜欢更冗长的名字）。
请注意，在 LALR 解析器中，模拟将需要迭代地应用减少操作，因为直到实际遇到移位操作时才知道令牌的可接受性。模拟缩减涉及弹出堆栈，如果应用于真正的解析器堆栈，这将是破坏性的。所以部分代码可能会创建和管理一个模拟堆栈。 （尽管 byacc 也有可能使用意大利面条堆栈。我从未真正看过它的骨架。）
Bison 使用类似的代码来实现 "Lookahead Correction" (LAC)，用于生成信息更丰富的错误消息。 （"Expecting X or Y or Z"，这是另一个补全列表activity。）所以你可以在Bison骨架中看到另一种可能的实现技术。 IIRC，它复制堆栈以模拟 pops。
在一个基于 yacc 的项目中，我遇到了一个复杂的表达式，但我不明白它的作用。表达式重复多次，因此看起来像复制粘贴。事实上，YACC 骨架 (byacc-1.9) 中也出现了完全相同的表达式，因此我假设它具有某些特定含义。
表达式如下：
if (((yyn = yysindex[lastyystate]) && (yyn += tok) >= 0 &&
yyn <= YYTABLESIZE && yycheck[yyn] == tok) ||
((yyn = yyrindex[lastyystate]) && (yyn += tok) >= 0 &&
yyn <= YYTABLESIZE && yycheck[yyn] == tok)) {
如果你对它进行分区，你会得到
((yyn = yysindex[lastyystate]) && (yyn += tok) >= 0 && yyn <= YYTABLESIZE && yycheck[yyn] == tok)
或
((yyn = yyrindex[lastyystate]) && (yyn += tok) >= 0 && yyn <= YYTABLESIZE && yycheck[yyn] == tok))
我对解析器生成器相当熟悉并且知道 yacc 是 LALR(1)。我猜
yysindex是 "shift table"yyrindex是 "reduce table"yyn <= YYTABLESIZE只是范围检查
鉴于这两个部分的相似性，并且假设我的猜测是正确的，它们似乎都在 packed/coded 解析 table 中寻找某些东西。我还没有深入研究 yacc 如何存储解析 tables 的细节，如果有人对此有更多了解，那可能会有所帮助。
在这种情况下，tok 是（显然）令牌号。但是为什么 += tok 什么是 yycheck table?
此代码是源代码完成的一部分，例如使用 TAB，如果这有助于解释事情的话。
如果你能用一句话解释，比如给一个函数名，这个复杂表达式的意图是什么，加分。
"Next+check" transition table compression，通常也称为 comb 算法，在 Dragon book 的第 3.9 节中描述了关于词法分析器的内容，第 4 章中有关于其使用的注释使用解析器 tables.
该算法通过叠加行来存储稀疏矩阵，以便有效条目仅与缺失条目重叠。要在压缩的 table 中查找值，您需要每行的起始索引向量。然后将要查找的列号添加到该起始索引。最后，您需要知道该条目是否对应于您正在查找的行； check 向量包含每个 table 条目有效的行数。
之所以称为梳状压缩，是因为每一行就像一把梳子，上面有许多断齿。
在解析器框架中，该代码（或类似代码）将用于确定与令牌对应的解析器操作。可能的答案是：
移动令牌并转到状态 S。（将令牌压入堆栈并读取新的先行）。
用生产号P减栈。（弹出右边出栈，执行减量动作，从查询GOTOtable转到找到的状态pop 显示的状态和减少的非终结符的数量，将减少的非终结符压入堆栈，然后继续使用相同的先行标记。）
发出错误信号。
接受输入。 （仅当前瞻标记是输入结束标记时。这种可能性通常是特殊情况。）
我想你是对的，他们是分开的转变和减少行动 tables。如果您单独压缩操作，行可能会更好地重叠，尽管压缩必须好得多才能补偿额外的检查数组。
鉴于该代码用于构建完成列表，我想它被用于模拟每个可能的下一个标记的解析，以确定有效的下一个标记候选是什么。语句 returns true 如果令牌可以被执行（如果不能，候选人可以简单地从完成列表中删除）并将 yyn 设置为下一个操作。有必要区分 Shift 和 Reduce 操作。在某些解析器框架中，动作的符号用于此目的，但还有其他可能性。
所以我会调用函数 find_parse_action（或者 find_parse_action_if_any，如果你喜欢更冗长的名字）。
请注意，在 LALR 解析器中，模拟将需要迭代地应用减少操作，因为直到实际遇到移位操作时才知道令牌的可接受性。模拟缩减涉及弹出堆栈，如果应用于真正的解析器堆栈，这将是破坏性的。所以部分代码可能会创建和管理一个模拟堆栈。 （尽管 byacc 也有可能使用意大利面条堆栈。我从未真正看过它的骨架。）
Bison 使用类似的代码来实现 "Lookahead Correction" (LAC)，用于生成信息更丰富的错误消息。 （"Expecting X or Y or Z"，这是另一个补全列表activity。）所以你可以在Bison骨架中看到另一种可能的实现技术。 IIRC，它复制堆栈以模拟 pops。