标记化 LL 语法中的抽象终端

Question

我目前正在为 XML 编写一个基本的解析器。作为练习，我正在实现一个 LL table 驱动的解析器。

这是我的 BNF 语法示例：

%token name data string

%% /* LL(1) */

doc          :  elem

elem         :  "<" open_tag

open_tag     :  name attr close_tag

close_tag    :  ">" elem_or_data "</" name ">"
             |  "/>"
             ;

elem_or_data :  "<" open_tag elem_or_data
             |  data elem_or_data
             |  /* epsilon */
             ;

attr         :   name ":" string attr
             |  /* epsilon */
             ;

这个语法正确吗？

每个终端文字都在引号之间。抽象终端由 %token.

指定

我正在编写一个手写的词法分析器，以将我的输入转换为标记列表。我将如何标记抽象终端？

Answer 1

经典方法是为每个可能的终端编写正则表达式（或其他识别器）。

您所说的 "abstract" 终端，非常具体，实际上是终端，其相关模式可识别多个可能的输入字符串。实际识别的字符串（或该字符串的某些计算函数）应作为标记的语义值传递给解析器。

名义上，在输入字符串的每一点，分词器将运行所有识别器并选择匹配最长的那个。（这就是所谓的 "maximal munch" 规则。）这通常可以优化，尤其是当所有模式都是正则表达式时。例如，(F)lex 将为您进行优化。

在你的情况下，一个复杂的问题是你的语言的标记化是依赖于上下文的。特别是，当目标是 elem_or_data 时，唯一可能的标记是 <、</ 和 "data"。但是，在标签内，"data" 是不可能的，"name" 和 "string" 标签是可能的（等等）。

属性的值也可能具有与键（即名称）相同的词法形式。在 XML 本身，属性值必须是带引号的字符串，使用不带引号的字符串将被标记为错误，但肯定有 "XML-like" 语言（例如 HTML）哪些没有空格的属性值可以不加引号插入。

由于词法分析取决于上下文，因此必须向词法分析器传递（或访问）定义词法上下文的附加信息。这通常表示为单个枚举值，可以根据返回的最后几个标记或根据当前解析器堆栈的第一个集合计算。

标记化 LL 语法中的抽象终端

Tokenize abstract terminals in LL grammar

parsing

recursive-descent

bnf

lexer

ll