用LL语法标记抽象终端

Question

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

这是我的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

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

你所谓的“抽象”终端，它们是完全具体的，实际上是终端，其相关模式识别多个可能的输入字符串。实际识别的字符串（或该字符串的某些计算函数）应作为令牌的语义值传递给解析器。

名义上，在输入字符串中的每个点处，标记器将运行所有识别器并选择具有最长匹配的识别器。 （这就是所谓的“最大咀嚼”规则。）这通常可以优化，特别是如果所有模式都是正则表达式。 （F）lex将为您进行优化，例如。

您的案例中的一个复杂因素是您的语言的标记化取决于上下文。特别是，当目标是elem_or_data时，唯一可能的标记是<，</和“data”。但是，在标签内部，“数据”是不可能的，并且“名称”和“字符串”标签是可能的（以及其他）。

属性的值也可以具有与键相同的词法形式（即名称）。在XML本身中，属性值必须是带引号的字符串，并且使用不带引号的字符串将被标记为错误，但是肯定存在“类似XML”的语言（例如HTML），其中可以插入没有空格的属性值不带引号的。

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