代码之家  ›  专栏  ›  技术社区  ›  chiborg Alessandro Minoccheri

解析器和lexer的设计指南?

  •  6
  • chiborg Alessandro Minoccheri  · 技术社区  · 15 年前

    我正在编写一个lexer(带有re2c)和一个解析器(带有lemon),用于稍微复杂的数据格式:类似csv,但在特定位置具有特定的字符串类型(仅限字母数字字符、字母数字字符和减号、除引号和逗号之外的任何字符,但带有平衡大括号等)、大括号内的字符串以及类似函数调用的字符串。带有可包含参数的左大括号和右大括号。

    我的第一张照片是一个有许多州的lexer,每个州都适合特定的字符串格式。但是,在lexer发出了许多无用的“意外输入”消息(消息变得很大)之后,我意识到它可能正试图完成解析器的工作。我放弃了第一次尝试,使用了一个只有一个状态、许多字符标记的lexer,以及一个将标记组合成不同字符串类型的解析器。这样做效果更好,当关闭某个选项时,我会从解析器中得到更多有用的语法错误,但仍然感觉不太对劲。我正在考虑向lexer添加一个或两个状态,但是从解析器启动状态,解析器有一个更好的“概述”,在给定的实例中需要哪些字符串类型。总的来说,我觉得有点笨:(

    我没有正式的CS背景,对数学重理论有点害羞。但是也许在某个地方有一个教程或书可以解释lexer应该(和不应该)做什么,以及解析器应该做什么工作。如何构造好的令牌模式,何时使用lexer状态,何时以及如何使用递归规则(使用lalr解析器),如何避免不明确的规则。讲授基础知识的实用食谱。“lex和yacc primer/howto”不错,但还不够。因为我只想解析数据格式,所以关于编译器构建的书籍(比如红龙书)对我来说有点过大。

    或者有人可以给我一些简单的规则。

    2 回复  |  直到 14 年前
        1
  •  7
  •   Borealid    15 年前

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

    • Lexer负责接收您的输入并告诉您 终端 你有。
    • 解析器负责匹配一系列 终端 非终结符 到一个生产规则,重复,直到您有一个分析树或一个分析失败。

    lexer不负责输入验证,除非拒绝不可能的字符,以及其他 非常基础 位。解析器完成所有这些。

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

        2
  •  5
  •   SasQ    14 年前

    一个很好的试金石测试来决定是否应该由解析器或lexer来做一些事情,那就是问你自己一个问题:

    语法是否有任何递归的、嵌套的、自相似的元素?
    (例如嵌套括号、大括号、标记、子表达式、子上下文等)。

    如果不是这样,纯正则表达式就足够了,它可以由lexer完成。
    如果是的话,它应该由解析器进行分析,因为它至少是一种上下文无关的语法。

    lexer通常用于查找语言的“单词”,并对它们进行分类(它是名词吗?动词?形容词?等等)。
    解析器是为了找到合适的“句子”,对它们进行结构化,以确定它们在给定的语言中是否是合适的句子。