让词法分析器在确定标记之前考虑解析器？

Question

我正在 ocamllex 和 ocamlyacc 中编写词法分析器和解析器，如下所示。 function_name 和 table_name 是相同的正则表达式，即只包含英文字母的字符串。确定字符串是 function_name 还是 table_name 的唯一方法是检查其周围环境。例如，如果这样一个字符串被[和]包围，那么我们就知道它是一个table_name。这是当前代码：

在lexer.mll,

... ...

let function_name = ['a'-'z' 'A'-'Z']+
let table_name = ['a'-'z' 'A'-'Z']+

rule token = parse
  | function_name as s { FUNCTIONNAME s }
  | table_name as s { TABLENAME s }

... ...

在parser.mly中：

... ...

main: 
| LBRACKET TABLENAME RBRACKET { Table  }

... ...

因为我在| table_name as s { TABLENAME s }之前写了| function_name as s { FUNCTIONNAME s }，上面的代码解析失败[haha]；它首先在词法分析器中将 haha 视为 function_name，然后在解析器中找不到任何对应的规则。如果它可以将 haha 视为词法分析器中的 table_name，它将匹配 [haha] 作为解析器中的 table。

一个解决方法是在词法分析器中更加精确。例如，我们在词法分析器中定义 let table_name_with_brackets = '[' ['a'-'z' 'A'-'Z']+ ']' 和 | table_name_with_brackets as s { TABLENAMEWITHBRACKETS s }。但是，我想知道是否还有其他选择。难道不能让词法分析器和解析器一起工作来确定标记和归约吗？

Answer 1

您应该避免试图让词法分析器完成解析器的工作。词法分析器应该只识别词位；它不应该试图弄清楚词素在语法中的位置。所以在你的（简化的）例子中，应该只有一种词法类型，name。解析器将从那里找出答案。

但从评论来看，在未简化的原文中，这两个模式似乎是重叠的，而不是相同的。这更烦人，尽管它只是稍微复杂一点。基本上，您需要将通用模式分离为一种词法类型，然后将其他匹配项添加为一种或两种其他词法类型（取决于一种模式是否是另一种模式的严格超集）。

这可能并不难，具体取决于两个模式之间的精确关系。通过以正确的顺序编写模式，您可能会找到一个非常简单的解决方案，例如，因为最长的匹配规则：

If several regular expressions match a prefix of the input, the “longest match” rule applies: the regular expression that matches the longest prefix of the input is selected. In case of tie, the regular expression that occurs earlier in the rule is selected.

大多数时候，仅此而已：首先将两个模式的交集定义为基础词素，然后添加每个上下文类型的完整词法模式以提供额外的匹配。然后，您的解析器必须在一个上下文中匹配 name | function_name，在另一个上下文中匹配 name | table_name。但这还不算太糟糕。

它会失败的地方是当输入流不能明确地划分为词素时。例如，假设在函数上下文中，名称可以包含 ? 字符，但在 table 上下文中，? 是有效的后记运算符。在这种情况下，您必须主动防止 foo? 在 table 上下文中被分析为单个标记，这意味着词法分析器必须知道解析器上下文。

让词法分析器在确定标记之前考虑解析器？

Make lexer consider parser before determining tokens?

parsing

lexer

ocamllex

ocamlyacc

menhir