0

我正在 ocamllex 和 ocamlyacc 中编写一个词法分析器和解析器，如下所示。function_name和table_name是相同的正则表达式，即只包含英文字母的字符串。确定字符串是否是function_name或是table_name检查其周围环境的唯一方法。例如，如果这样的字符串被[and包围]，那么我们就知道它是 a 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 $2 }

... ...

正如我| function_name as s { FUNCTIONNAME s }之前写| table_name as s { TABLENAME s }的，上面的代码无法解析[haha]；它首先在词法分析器中被认为haha是a function_name，然后在解析器中找不到任何对应的规则。如果它可以在词法分析器中被haha视为 a table_name，那么它将[haha]在解析器中匹配为表。

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

4

1 回答 1

0

您应该避免试图让词法分析器完成解析器的工作。词法分析器应该只识别词位；它不应该试图找出一个词位适合语法的位置。因此，在您的（简化的）示例中，应该只有一种词法类型name. 解析器将从那里弄清楚。

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

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

如果多个正则表达式匹配输入的前缀，则应用“最长匹配”规则：选择匹配输入的最长前缀的正则表达式。在 tie 的情况下，选择规则中较早出现的正则表达式。

大多数时候，这就是它所需要的：首先将两个模式的交集定义为基于词位，然后添加每个上下文类型的完整词汇模式以提供额外的匹配。然后，您的解析器必须name | function_name在一个上下文和name | table_name另一个上下文中匹配。但这还不算太糟糕。

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

于 2020-08-12T06:08:36.530 回答