6

我正在为稍微复杂的数据格式编写词法分析器（使用 re2c）和解析器（使用 Lemon）：类似于 CSV，但在特定位置具有特定的字符串类型（仅限字母数字字符、字母数字字符和减号，除此之外的任何字符引号和逗号，但带有平衡的大括号等），大括号内的字符串和看起来像函数调用的字符串，带有可以包含参数的左大括号和右大括号。

我第一次尝试它是一个有许多状态的词法分析器，每个状态都迎合特定的字符串格式。但是在来自词法分析器的许多无用的“意外输入”消息（变得非常大）之后，我意识到它可能正在尝试完成解析器的工作。我放弃了我的第一次尝试，使用了一个只有一个状态、许多字符标记和一个将标记组合成不同字符串类型的解析器的词法分析器。这效果更好，当某些东西关闭时，我会从解析器中得到更多有用的语法错误，但仍然感觉不太正确。我正在考虑向词法分析器添加一个或两个状态，但从解析器启动状态，它对给定实例中需要哪种字符串类型有更好的“概述”。总的来说我觉得有点傻:(

我没有正式的 CS 背景，并且对数学很重的理论有点回避。但也许某处有一个教程或书籍来解释词法分析器应该（和不应该）做什么以及解析器应该做什么工作。如何构建良好的标记模式，何时使用词法分析器状态，何时以及如何使用递归规则（使用 LALR 解析器），如何避免模棱两可的规则。一本讲授基础知识的实用食谱。“Lex and YACC Primer/HOWTO”很好，但还不够。因为我只是想解析一种数据格式，所以关于编译器构建的书（比如红龙书）对我来说看起来有点过大。

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

4

2 回答 2

7

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

  • 词法分析器负责接受您的输入并告诉您您拥有哪个终端。
  • 解析器负责将一系列终结符和非终结符与生产规则重复匹配，直到出现抽象语法树 (AST)或解析失败。

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

看看https://www.cs.rochester.edu/u/nelson/courses/csc_173/grammars/parsing.html。这是一个关于解析的介绍性 CS 课程页面。

于 2010-07-07T07:16:11.393 回答
5

一个很好的决定是否应该由解析器或词法分析器完成的试金石是问自己一个问题：

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

如果没有，简单的正则表达式就足够了，它可以由词法分析器完成。
如果是，它应该由解析器分析，因为它至少是一个上下文无关的语法。

Lexer 通常用于查找您的语言的“单词”，并对它们进行分类（它是名词吗？动词？形容词？等等）。
Parser 用于查找正确的“句子”，如果它们是给定语言中的正确句子，则将它们结构化。

于 2010-09-01T05:01:37.983 回答