时间戳

首页 > 解决方案 > 可以在 LALR(1) 解析器 (PLY) 中解析这种表面上的歧义吗？

parsing - 可以在 LALR(1) 解析器 (PLY) 中解析这种表面上的歧义吗？

问题描述

我在 PLY (Python Lexx Yacc) 中有一个很大的语法，用于在解析方面有一些特殊挑战的语言。该语言允许两种调用的前导语法看起来几乎相同，直到调用非终端结束。这为减少/减少冲突提供了很多机会，因为沿途令牌的语义是不同的，但可以从相同的终端令牌构建。我已经提取了以下语法的简单前后版本，我会稍微解释一下。

最初，表达式是一种典型的“分层语法”，将调用和文字等变为初级，然后通过一元进行初级，然后将二进制变为一般表达式。问题在于Call_expr，两个参数与Iter_expr在“/”之前以两个 ID 开头的版本冲突。在调用中的第一个参数之后，冲突出现在逗号上，因为最初Expr -> ... -> Primary_expr -> Name_expr -> Id是允许的。解析器可以减少Id到Expr匹配Call_expr，或者让它匹配Iter_expr. 展望逗号并没有帮助它做出决定。如果调用的第一个参数只是一个标识符（如变量），这是合法的歧义。考虑输入id > id ( id , id ...。

我的方法是制作一种不能只是Id. 我通过所有表达式添加了生产链，以赋予它们“ _nn”版本--“不是名称。” 然后我可以为它定义产生Call_expr式，在第一个参数中使用任何语法，使其不仅仅是一个名称（例如运算符、调用等），以将其简化为BinOp_expr_nn，并且还允许一个只有一个Id作为第一个参数的调用产生式. 这应该说服解析器只是转移，直到它可以解决或者Iter_expr解决Call_expr解决（或至少知道它在哪条路径上。）

正如您可能已经猜到的那样，这把一切都搞砸了:)。修补表达式链也修补Primary_expr，我仍然需要允许减少到Id. 但现在，这是一个减少/减少冲突——每个人都Primary_expr可以留在那里或继续Unary_expr. 我可以命令他们做出选择（这可能会奏效），但我希望我最终会追逐一个又一个。

所以，我的问题是：是否有人可以阐明如何允许相同的标记表示不同的语义（即 expr vs id）仍然可以像 PLY 一样用 LALR(1) 解析的技术？除此之外，还有什么有用的技巧可以帮助解决问题吗？这可以消除歧义吗？

terminals:  '+' '^' ',' '>' '(' ')' '/' ':' 'id' 'literal' 
   (i.e. punctuation (besides '->' and '|', initial-lower-case words)
non-terminals:  initial-Upper-case words

原文语法：

S'-> S
S -> Call_expr
   | Iter_expr
Expr -> BinOp_expr
BinOp_expr -> Unary_expr
BinOp_expr -> BinOp_expr '+' BinOp_expr
Unary_expr -> Primary_expr
   | '^' BinOp_expr
Primary_expr -> Name_expr
   | Call_expr
   | Iter_expr
   | Literal_expr
Name_expr -> Id
Args -> Expr
   | Args ',' Expr
Call_expr -> Primary_expr '>' Id '(' ')'
   | Primary_expr '>' Id '(' Args ')'
Iter_expr -> Primary_expr '>' Id '(' Id '/' Expr ')'
   | Primary_expr '>' Id '(' Id ':' Id '/' Expr ')'
   | Primary_expr '>' Id '(' Id ',' Id ':' Id '/' Expr ')'
Literal_expr -> literal
Id -> id

我试图消除第一个论点的歧义Call_expr：

S'-> S
S -> Call_expr
   | Iter_expr
Expr -> BinOp_expr_nn
   | BinOp_expr
BinOp_expr -> BinOp_expr_nn
   | Unary_expr
BinOp_expr_nn -> Unary_expr_nn
   | BinOp_expr '+' BinOp_expr
Unary_expr -> Primary_expr
   | Unary_expr_nn
Unary_expr_nn -> Primary_expr_nn
   | '^' BinOp_expr
Primary_expr -> Primary_expr_nn
   | Name_expr
Primary_expr_nn -> Call_expr
   | Iter_expr
   | Literal_expr
Name_expr -> Id
Args -> Expr
   | Args ',' Expr
Call_expr -> Primary_expr '>' Id '(' ')'
   | Primary_expr '>' Id '(' Expr ')'
   | Primary_expr '>' Id '(' Id , Args ')'
   | Primary_expr '>' Id '(' BinOp_expr_nn , Args ')'
Iter_expr -> Primary_expr '>' Id '(' Id '/' Expr ')'
   | Primary_expr '>' Id '(' Id ':' Id '/' Expr ')'
   | Primary_expr '>' Id '(' Id ',' Id ':' Id '/' Expr ')'
Literal_expr -> literal
Id -> id

标签： parsingyaccplylalr

解决方案

尽管您的帖子标题，但您的语法并不模棱两可。由于您提到的原因，它根本不是 LR(1)：输入

A ( B ,

可以是 aCall_expr或a 的开始Iter_expr。在第一种情况下，B必须将其简化为 an Expr，然后再简化为Args; 在第二种情况下，它不能被归约，因为id当右手id '(' id ',' id ':' id '/' Expr ')'被归约时它仍然需要是一个。不能简单地通过查看单个前瞻标记（the ,）来做出决定，因此存在移位减少冲突。

,这种冲突最多可以通过两个额外的前瞻标记来解决，因为只有在紧跟着 anid然后是 a的情况下，移位才是有效的动作:。这样就形成了语法 LALR(3)。不幸的是，Ply 不生成 LALR(3) 解析器（yacc/bison 也不生成），但有一些替代方案。

1.使用不同的解析算法

由于语法是明确的，因此可以使用 GLR 解析器毫无问题（并且无需任何修改）对其进行解析。Ply 也不产生 GLR 解析器，但 Bison 可以。这对你来说可能没有多大用处，但我想我应该提一下，以防你没有被 Python 锁定。

2.使用允许一些无效输入的语法，并通过语义分析将其丢弃

这几乎可以肯定是最简单的解决方案，也是我通常会推荐的。如果将定义更改Iter_expr为：

Iter_expr : id '(' id '/' Expr ')'
          | id '(' Args ':' id '/' Expr ')'

那么它仍然会识别每个有效输入（因为id和id , id都是 的有效实例Args）。这消除了班次减少冲突；实际上，它让解析器避免在遇到 a )（表示 a Call_expr）或 a :（表示 a Iter_expr）之前做出决定。（第一个替代方案没有问题，因为转移而不是减少Iter_expr的决定不需要额外的前瞻。）/id

当然，第二个产生式 forIter_expr会识别出很多无效的迭代表达式：超过 2 个项目的列表，以及包含比单个 . 更复杂的表达式的列表id。但是，这些输入根本不是有效的程序，因此它们可以在 for 的操作中被简单地拒绝Iter_expr。识别有效迭代的精确代码将取决于您如何表示您的 AST，但这并不复杂：只需检查以确保 的长度Args是一个或两个，并且列表中的每个项目都只是一个id.

3. 使用词法技巧

弥补前瞻信息缺乏的一种方法是在词法分析器中收集它，方法是将必要的前瞻信息收集到缓冲区中，并且仅在其句法类别已知时才输出词位。在这种情况下，词法分析器可以查找序列'(' id ',' id ':'并标记第一个id，以便它只能在Iter_expr. 在这种情况下，对语法的唯一更改是：

Iter_expr : id '(' id '/' Expr ')'
          | id '(' id ':' id '/' Expr ')'
          | id '(' iter_id ',' id ':' id '/' Expr ')'

虽然这在这种特殊情况下可以正常工作，但它不是很容易维护。特别是，它依赖于能够定义一个可以在词法分析器中实现的简单且明确的模式。由于该模式是语法的简化，因此很可能未来的一些句法添加将创建一个也匹配相同模式的语法。（这被称为词汇“hack”是有原因的。）

4. 求一个 LALR(1) 文法

如前所述，这个语法是LALR(3). 但是没有LALR(3) 语言这种东西。或者更准确地说，如果一种语言有LALR(k)语法，那么它也有LALR(1)语法，并且可以从语法中机械地产生LALR(k)语法。此外，给定单符号前瞻文法的解析，可以重建原始文法的解析树。

因为机械生成的文法比较大，这个过程不是很吸引人，我也不知道算法的实现。相反，最常见的是尝试只重写部分语法，就像您在原始问题中所尝试的那样。这当然可以做到，但最终结果并不完全直观。

然而，这并不难。例如，这里是您的语法的一个稍微简化的版本，删除了多余的单元产生式并修复了运算符优先级（可能不正确，因为我不知道您的目标是什么语义）。

名称以结尾的N产生式不产生ID。对于它们中的每一个，都有一个对应的产生式，而没有Nwhich add ID。一旦完成，就必须重写Args以使用ExprN产生式，以及允许以一或两个IDs 开头的各种参数列表。Chain制作只是为了避免一些重复。

Start   : Call
        | Iter
Expr    : ID
        | ExprN
ExprN   : UnaryN
        | Expr '+' Unary
Unary   : ID
        | UnaryN
UnaryN  : ChainN
        | '^' Chain
Chain   : ID
        | ChainN
ChainN  : PrimaryN
        | Chain '>' CallIter
PrimaryN: LITERAL
        | Call
        | Iter
        | '(' Expr ')'
Call    : ID '(' ')'
        | ID '(' ID ')'
        | ID '(' ID ',' ID ')'
        | ID '(' Args ')'
Iter    : ID '(' ID '/' Expr ')'
        | ID '(' ID ':' ID '/' Expr ')'
        | ID '(' ID ',' ID ':' ID '/' Expr ')'
Args    : ExprN ExprList
        | ID ',' ExprN ExprList
        | ID ',' ID ',' Expr ExprList
ExprList:
        | ExprList ',' Expr

我没有像我想要的那样测试这个，但我认为它产生了正确的语言。

推荐阅读