2

我重新表述了我之前提出的一个问题。目的是了解优先级在解析中的工作原理。

我想解析一个语句a(3).value = 100。parser.mly如下在读取后停止.，并返回错误。

但是，如果我将专用于argument_list(en-globed by beginand end) 的部分移动到文件的末尾（因此它位于 之后l_expression），则解析效果很好。

在语句被解析的情况下，它被简化为 a let_statementof data_manipulation_statement; a(3).value减少到member_access_expression; a(3)被简化为index_expression; 并3减少到argument_list。

在无法解析语句的情况下，它似乎试图将语句的开头减少为 a call_statementof control_statement... 它以错误结束。

我一直认为，无论优先级是什么，解析总是拒绝那些不能以成功结束的归约。但那里似乎尝试过又失败了，拒绝尝试其他可能性……

谁能帮忙澄清一下？

statement:
| control_statement { $1 }
| data_manipulation_statement  { BS_DMS $1 }

control_statement: | control_statement_except_multiline_if { BS_CSEMI $1 }
control_statement_except_multiline_if: | call_statement { $1 }
call_statement: | simple_name_expression argument_list { CSEMI_SNE_AL ($1, $2) }
data_manipulation_statement: | let_statement { $1 }
let_statement: | l_expression EQUAL expression { DMS_let (None, $1, $3) } 

simple_name_expression: | name { $1 } 
index_expression: | l_expression LPAREN argument_list RPAREN { IE_LE_AL ($1, $3) }
member_access_expression: | l_expression DOT unrestricted_name { MAE_LE_UN ($1, $3) }
literal_expression: | INTEGER { LIE_INT $1 }

unrestricted_name: | name { UN_N $1 }
name: | untyped_name { N_UN $1 }
untyped_name: | IDENTIFIER { UN_I $1 } 

expression: 
| l_expression { E_LE $1 }
| value_expression { E_VE $1 }

value_expression:
| literal_expression { VE_LIE $1 }
| parenthesized_expression { VE_PE $1 }

(***** begin argument_list *****)
argument_list: | positional_or_named_argument_list { AL_PONAL $1 }

positional_or_named_argument_list:
| positional_argument_COMMAs required_positional_argument { PONAL_PAs_RPA (List.rev $1, $2) }
positional_argument_COMMAs:
  /* empty */ { [] }
| positional_argument_COMMAs positional_argument COMMA { $2 :: $1 }

positional_argument: | argument_expression { $1 }
required_positional_argument: | argument_expression { $1 }
argument_expression: | expression { AE_expression (None, $1) }
(***** end argument_list *****)

l_expression:
| simple_name_expression { LE_SNE $1 } 
| index_expression { LE_IE $1 } 
| member_access_expression { LE_MAE $1 }
4

1 回答 1

3

关于解析如何进行没有绝对的规则。这取决于解析器。可以说，一个正确的解析器应该“总是拒绝不能以成功结束的归约”，但通常不能使用线性时间从左到右的解析器来做到这一点。GLR 解析器（bison 可以生成）可以做到这一点，可能在立方时间内，具体取决于语法。回溯解析器——例如大多数解析组合库——可以做到这一点，但估计算法的复杂性并不容易。但是我认为您正在使用的 *LR(1) 解析器根据您的标签只能解析 *LR(1) 语法，而您的语法不是其中之一。

LR(1) 解析器从左到右 ( L ) 处理输入，一次一个标记。在读取每个标记后，它会“减少”（即匹配一个产生式）所有以输入的最右侧标记 ( R ) 结尾的产生式。为此，它使用尽可能多的关于解析进度（“解析堆栈”）和下一个(1)标记（“前瞻”）的信息。它们与有限状态下推自动机一起工作，并且有几种构建这些自动机的方法，它们为理想的 PDA 提供了不同的近似值，但对于您的语法而言，这并不重要。我相信 ocamlyacc 会生成 LALR(1) 解析器，就像原始的 yacc 一样，但你的语法甚至不是 LR(1)，所以它肯定不是

在上面的描述中，我没有使用“优先”这个词，因为它不适用于 LR 解析。有诸如优先级解析器之类的东西——它们通常不如 LR 解析器强大，但也更容易构建——但它们不再那么常见，除非以手写解析器的形式出现。（我不确定是否有优先语法解析器生成器；一旦发现 LALR(1) 解析，它就迅速占领了解析器生成器市场，因为它比优先或 LL(1) 解析更强大。）然而，yacc在其发展的早期阶段，为了应对模棱两可的语法，添加了“优先级” ；或者，通常是可以明确写出但在模棱两可的形式上更紧凑的语法。

当 LR 解析器决定做什么时，可能有不止一种选择。这可能是因为存在不止一种可能的归约（“归约-归约”冲突），或者因为尚不清楚可用归约是否正确（“轮班归约”冲突）。出现冲突的原因是语法不明确，或者因为不能仅使用指定的前瞻来进行 LR 解析。

在任何一种情况下，一个迂腐的 LR 解析器生成器都会报告失败。但是一个实用的解析器生成器可能会尝试找出哪个替代方案是所需的，并相应地进行。一种简单的方法是基于一些程序员提供的声明（“优先级声明”）或基于一些启发式（“优先于语法文件中的任何内容” ）。从某种意义上说，这种启发式方法很危险，因为它们可能导致解析器实际上无法解析您希望解析的语言；恕我直言，任何解析器生成器都不应该应用启发式算法，至少不会警告您它已经这样做了。

现在，实际问题：为什么你的语法不是 LR(1)。

让我们从以下摘录开始。

call_statement: simple_name_expression argument_list
let_statement: l_expression EQUAL expression
l_expression: index_expression
l_expression: simple_name_expression
index_expression: l_expression LPAREN argument_list RPAREN

现在考虑输入：a (. 也就是说，我们刚刚读取了令牌a，而前瞻令牌是(. a必须简化为simple_name_expression（通过几个单元制作，但细节无关紧要）。现在，解析器状态将包括：（·表示产生式中的当前“点”）：

call_statement:   simple_name_expression · argument_list
index_expression: l_expression · LPAREN argument_list RPAREN
l_expression:     simple_name_expression ·

也就是说，我们可以simple_name_expression保持原样继续收集argument_list，或者我们可以减少simple_name_expression到l_expression以继续收集其余的index_expression。哪一个？

不幸的是，我们至少要等到匹配的时候才能知道答案RPAREN。即使这样，我们也可能不知道答案，因为下一个标记可能是扩展 an 的东西l_expression（例如 a.或 another LPAREN），在这种情况下，我们需要继续扫描。不知道我们什么时候会找到答案，所以没有有限的前瞻就足够了，而且这个语法——尽管可能是明确的——不是任何 k 的 LR(k)。（而且优先启发式也不起作用。）

顺便说一句，我不清楚你的语法call_statement是你想要的。anargument_list可以以 an 开头，(因为它必须以 an 开头，expression并且expression可以用括号括起来，但它不必以括号开头。所以以下将是一个合法的 call_statement：

print a(3), value

如果那是你想要的，那很好。

于 2013-10-22T21:20:53.010 回答