解析器和词法分析器的设计指南？

Question

我正在编写一个词法分析器(re2c)和一个解析器(Lemon)，用于稍微复杂的数据格式:类似CSV，但在特定位置具有特定的字符串类型(仅包含字母数字字符、字母数字字符和减号、除引号和逗号外的任何字符但带有平衡的大括号等)，大括号内的字符串和看起来像函数调用的字符串，其中开放和关闭的括号可以包含参数。

我的第一次尝试是使用多个状态的词法分析器，每个状态都满足特定的字符串格式。但是，在词法分析器中遇到许多无用的“意外输入”消息(词法分析器变得非常庞大)后，我意识到它可能试图做解析器的工作。我放弃了第一次尝试，使用了只有一个状态、许多字符令牌和一个将令牌组合成不同字符串类型的解析器。这个方法工作得更好，如果出现问题，解析器会提供更有用的语法错误信息，但仍然感觉不太对。我考虑增加一个或两个状态到词法分析器，但是从解析器中初始化状态，解析器能够更好地了解在给定情况下需要哪种字符串类型。总体来说，我感觉有点愚蠢：(

我没有正式的计算机科学背景，对数学理论有点害羞。但也许有教程或书籍可以解释词法分析器应该做什么(和不应该做什么)，以及解析器应该做哪些工作。如何构建好的标记模式，何时使用词法分析器状态，何时以及如何使用递归规则(与LALR解析器一起)，如何避免歧义规则。一个教授基础知识的实用菜谱。 “Lex and YACC primer/HOWTO” 不错，但不够好。由于我只想解析数据格式，编译程序构建的书籍(如红龙书)对我来说似乎有点过大了。

或者也许有人能在这里给我一些简单的规则。

- chiborg

Answer 1

你真正需要做的是为你的语言编写一个语法规则。一旦完成，边界就很容易确定：

• 词法分析器负责接收你的输入并告诉你哪个终端符号被使用。
• 语法分析器负责将一系列终端符号和非终端符号匹配到一个产生式规则中，重复执行该过程，直到你有一个抽象语法树(AST)或解析失败。

词法分析器不负责除拒绝不可能字符和其他非常基本的部分以外的输入验证。这些都由语法分析器完成。

看一下https://www.cs.rochester.edu/u/nelson/courses/csc_173/grammars/parsing.html. 这是一份关于解析的介绍性计算机科学课程页面。

- Borealid

---

谢谢，这很有帮助。我总是被诱惑要为我的终端创建聪明的正则表达式。所以在将来，我会在我的解析器中使用更多的生产规则。 - chiborg

Answer 2

一个衡量是否应该由解析器或词法分析器处理的好方法是问自己一个问题：

这个语法是否有任何递归、嵌套、自相似的元素？（例如：嵌套的括号、大括号、标签、子表达式、子句等）。

如果没有这样的元素，那么纯正则表达式就足够了，可以通过词法分析器完成。

如果有这样的元素，则应该由解析器分析，因为它至少是一种上下文无关文法。

词法分析器通常用于查找您语言中的“单词”，并对它们进行分类（它是名词？动词？形容词？等）。

解析器用于查找正确的“句子”，组织它们并查找它们是否在给定语言中是合适的句子。

- SasQ