用LL语法标记抽象终端

问题描述 投票:0回答:1

我目前正在为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指定。

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

parsing lexer bnf ll recursive-descent
1个回答
0
投票

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

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

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

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

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

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

热门问题
推荐问题
最新问题