string - 解析器和词法分析器的设计准则？

Question

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

我的第一枪是一个有很多州的词法分析器，每个州都适合特定的字符串格式。但是在来自词法分析器的许多无用的“意外输入”消息(变得非常大)之后，我意识到也许它正在尝试执行解析器的工作。我放弃了第一次尝试，选择了只有一个状态的词法分析器，许多字符标记和一个将标记组合成不同字符串类型的解析器。这种方法效果更好，当出现问题时，我会从解析器中获得更多有用的语法错误，但仍然感觉不太正确。我正在考虑向词法分析器添加一个或两个状态，但是要从解析器中启动状态，该解析器对于给定实例中需要哪种字符串类型具有更好的“概览”。总的来说，我觉得有点愚蠢:(

我没有正式的CS背景，并且对数学繁重的理论不屑一顾。但是也许某处有教程或书可以解释词法分析器应该(以及不应该)做什么以及解析器应该做什么工作。如何构造良好的 token 模式，何时使用词法分析器状态，何时以及如何使用递归规则(使用LALR解析器)，如何避免模棱两可的规则。一本实用的菜谱，教授基础知识。 “Lex和YACC底漆/方法”很好，但还不够。由于我只想解析数据格式，因此对我来说，有关编译器构建的书籍(如《红龙书》)看起来有些过大。

也许有人可以在这里给我一些简单的规则。

Answer 1

您真正应该做的是为您的语言编写语法。一旦有了这些，边界就很容易了:

词法分析器负责接受您的输入并告诉您您拥有哪个终端。

解析器负责反复将一系列终端和非终端与生产规则进行匹配，直到您遇到解析树或解析失败为止。

除了拒绝不可能的字符和其他 非常基本的位之外，该词法分析器不负责输入验证。解析器完成所有这些工作。

看一看 http://www.cs.rochester.edu/~nelson/courses/csc_173/grammars/parsing.html。这是有关解析的CS入门类(class)页面。