1

(LA)LR解析器的一个缺点是 reduce 仅在规则末尾处理。这是具有范围变量的编程语言中的一个问题，例如javascript.

例子：

var a = 2;
function (a) {
   a = 4;
}

请参见上面的代码示例。解析器可能如下所示：

program : instruction program {}
        | {}
        ;

instruction : command {}
            | function {}
            ;

command : "var" identifier "=" literal ";" {}
        ;

function : "function" "(" arguments ")" "{" program "}" {/*1*/}
         ;

arguments : identifier {}
          | identifier "," arguments {}
          | {}
          ;

现在很清楚，每次解析器都会消耗一个标识符。可以在寄存器中注册标识符。然而问题是一个函数（行/*1*/）只在函数的末尾被考虑。因此，在函数中使用标识符（如 ;）的指令a = 4不能在解析器时绑定到本地/全局标识符，因为当时它是未知的。

解决这个问题有哪些好的做法，C#（标准库）提供了哪些功能来处理这种情况？

4

1 回答 1

2

免责声明

您问题中的语法是yacc格式，所以我假设您打算使用yacc- 兼容的解析器生成器。因此，我不知道您对 C# 标准库有什么期望。这个答案一般适用于yacc和bison其他一些使用相同输入格式的解析器生成器。对于jison，请参阅下面关于中间规则操作的注释。

标准 Yacc 解决方案

yacc及其衍生产品允许您编写具有中间规则操作的规则；这些操作在规则其余部分的任何减少之前执行。这使得插入设置和拆卸操作变得非常容易。例如：

function: "function"    { start_scope(); }
          '(' arguments ')'
          '{' body '}'  { end_scope(); /* ... */ }
        ;

中间规则动作不会为上下文无关语法添加任何功能，因为它们可以用另一种方式编写（见下文），但它们有时更容易阅读和编写。中间规则动作具有与产生式的任何其他组件一样的值，并且可以被以后的动作引用。例如，执行以下操作可能很有用：

function: "function"    { $$ = new_scope(); }
          '(' arguments ')'
          '{' body '}'  { close_scope($2); /* ... */ }
        ;

尽管即使在那里，如果您希望在初始解析期间将名称查找应用于当前范围，也有必要使用持久状态来记录当前范围。

此外，向 (LA)LR(1) 语法添加中间规则操作可能会删除 (LA)LR(1) 属性。bison手册中有一个示例，这并非完全巧合地与局部变量的作用域问题完全相关。

范围规则

尽管这种策略很诱人，但它对许多语言的帮助并没有你想象的那么大。例如，在 javascript 中，在定义局部变量之前引用它是完全合法的。例如，考虑以下内容：

a=42;
function geta() {
  var rv = a;
  var a = 43;
  return rv;
}
geta();

的结果geta是未定义的，因为当rv从 初始化时，在 的范围内的a那个特定的还没有被赋值。如果将下一行更改为then将返回，因为现在是对封闭范围内变量的引用。Python 作用域大致相同（尽管语言在局部函数的作用域上有所不同），但它远非通用；可能还有更多的语言，其作用域规则类似于 Lua，可以从左到右进行作用域，其中 in 的第一个使用是指外部，而内部的作用域agetavar b = 43;geta42aagetaaa从它的声明开始并延伸到块的末尾。（当然，Lua 的语法略有不同，所以你不能只喂它那个例子。）

C 和大多数 C 衍生物基于“使用前声明”规则，但 C++ 不要求内联类成员函数的主体中使用的名称在函数定义之前已声明，除非名称是模板或 typedef。因此在 C++ 中，名称解析的语法部分可以从左到右完成，您可以决定(foo)*(bar)是强制转换还是乘积，但您仍然需要重新访问表达式才能进行名称解析。

因此，通常最好在 AST 的后续遍历中将名称附加到范围，在这种情况下，在减少生产之前，范围不附加到函数不再重要function。

没有中间规则操作的解析器生成器的替代方案

并非所有 LALR(1) 解析器生成器都允许中间规则操作。例如，两者都没有jison——否则它使用非常相似的语法格式——也没有lemon实现该功能。（有一个相当长的未完成的jison 功能请求。）但这并不重要，因为 MRA 只是语法糖。有时，它们可以通过具有唯一名称且右侧为空的产品来实现。换句话说，规则：

X: a b c { /* mid-rule action */ } d e f { /* final action */ };

可以转换成类似的东西：

@32: /* empty */ { /* mid-rule action */ };
X: a b c @32 d e f { /* final action */ };

@32其中，当减少时，即在 和 的减少之前，将d执行中间规则动作。ef

很多时候，MRA 需要能够在右侧引用其左侧符号的语义值，因此将 MRA 视为前缀的语法糖会更准确右：

X: @32 d e f { /* final action (with semantic values renumbered) */ };
@32: a b c   { /* mid-rule action */ }

实际的 bison 实现更接近于上面的第一个建议，因为 bison 知道当@32减少时，堆栈顶部的三个元素将始终是a,b和c。这是有效的，因为创建的非终结符只出现在语法中的一个地方。（Bison 允许您访问此堆栈探测功能，但请不要使用它，除非您真的知道自己在做什么。）因此，如果您需要与 MRA 等效的解决方案，则更有可能使用前缀解决方案吉森或柠檬。

您可能仍然会遇到问题，因为最终操作可能会引用现在已被前缀规则包含的语义值。为了处理这种情况，您可能需要利用前缀规则的语义值通过前缀规则传递一个或多个语义规则。幸运的是，这些情况很少见。

于 2014-08-05T21:23:59.000 回答