在线时间:8:00-16:00
迪恩网络APP
随时随地掌握行业动态
扫描二维码
关注迪恩网络微信公众号
系列导航 现在最核心的 DFA 已经成功构造出来了,最后一步就是根据 DFA 得到完整的词法分析器。 由于目前还不能像 Flex 那样支持词法定义文件,所以仍然需要在程序中定义规则,而且也不能非常灵活的自定义词法分析器,不过基本的东西完全够用了。 一、词法规则的定义词法分析器用到的所有规则都在 Grammar<T> 类中定义,这里的泛型参数 T 表示词法分析器的标识符的类型(必须是一个枚举类型)。定义规则方法包括:定义上下文的 DefineContext 方法、定义正则表达式的 DefineRegex 方法和定义终结符的 DefineSymbol 方法。 调用 DefineContext 方法定义的词法分析器上下文,会使用 LexerContext 类的实例表示,它的基本定义如下所示:
在词法分析器中,仅可以通过标签来切换上下文,因此 LexerContext 类本身被设置为 internal。 上下文的类型就是包含型或者排除型,等价于 Flex 中的 %s 和 %x 定义(可参见 Flex 的 Start Conditions)。这里简单的解释下,在进行词法分析时,如果当前上下文是排除型的,那么仅在当前上下文中定义的规则会被激活,其它的(非当前上下文中定义的)规则都会失效。如果当前上下文是包含型的,那么没有指定任何上下文的规则也会被激活。 默认上下文标签为 "Initial"。 Grammar<T> 中定义正则表达式的 DefineRegex 方法,就等价于 Flex 中的定义段(Definitions Section),可以定义一些常见的正则表达式以简化规则的定义,例如可以定义
在正则表达式的定义中,就可以直接使用 "{digit}" 来引用预先定义的正则表达式。 最后是定义终结符的 DefineSymbol 方法,就对应于 Flex 中的规则段(Rules Section),可以定义终结符的正则表达式和相应的动作。 终结符的动作使用 Action<ReaderController<T>> 来表示,由 ReaderController<T> 类来提供 Accept,Reject,More 等方法。 其中,Accept 方法会接受当前词法单元,并返回 Token 对象。Reject 方法会拒绝当前匹配,转而寻找次优的规则,这个操作会使词法分析器的所有匹配变慢,需要谨慎使用。More 方法通知词法分析器,下次匹配成功时,不替换当前的文本,而是把新的匹配追加在后面。 Accept 方法和 Reject 方法是相互冲突的,每次匹配成功只能调用其中的一个。如果两个都未调用,那么词法分析器会认为当前匹配是成功的,但不会返回 Token,而是继续匹配下一个词法单元。 二、词法分析器的实现2.1 基本的词法分析器由于多个规则间是可能产生冲突的,例如字符串可以与多个正则表达式匹配,因此在说明词法分析器之前,首先需要定义一个解决冲突的规则。这里采用与 Flex 相同的规则:
基本的词法分析器非常简单,它只能实现最基础的词法分析器功能,不能支持向前看符号和 Reject 动作,但是大部分情况下,这就足够了。 这样的词法分析器几乎相当于一个 DFA 执行器,只要不断从输入流中读取字符送入 DFA 引擎,并记录下来最后一次出现的接受状态就可以了。当 DFA 引擎到达了死状态,找到的词素就是最后一次出现的接受状态对应的符号(这样就能保证找到的词素是最长的),对应多个符号的时候只取第一个(之前已经将符号索引从小到大进行了排序,因此第一个符号就是最先定义的符号)。 简单的算法如下: 输入:DFA D
s=s0
while (c != eof) {
s=D[c]
if (s∈FinalStates) {
slast=s
}
c = nextChar();
}
slast 即为匹配的词素
实现该算法的代码可见 SimpleReader<T> 类,核心代码如下: 2.2 支持定长的向前看符号的词法分析器接下来,将上面的基本的词法分析器进行扩展,让它支持定长的向前看符号。 向前看符号的规则形式为 t 可以匹配的字符串长度是固定的,就称作定长的向前看符号;如果都不是固定的,则称为变长的向前看符号。 例如正则表达式 abcd 或者 [a-z]{2},它们可以匹配的字符串长度是固定的,分别为 4 和 2;而正则表达式 [0-9]+ 可以匹配的字符串长度就是不固定的,只要是大于等于一都是可能的。 区分定长和变长的向前看符号,是因为定长的向前看符号匹配起来更容易。例如正则表达式 a\*/bcd,识别出该模式后,直接回退三个字符,就找到了 a* 的结束位置。 对于规则 abc/d*,识别出该模式后,直接回退到只剩下三个字符,就找到了 abc 的结束位置。 我将向前看符号可以匹配的字符串长度预先计算出来,存储在 int?[] Trailing 数组中,其中 null 表示不是向前看符号,正数表示前面(t)的长度固定,0 表示长度都不固定。 所以,只需要在正常的匹配之后,判断 Trailing 的值。如果为 null,不是向前看符号,不用做任何操作;如果是正数 n,则把当前匹配的字符串的前 n 位取出来作为实际匹配的字符串;如果是负数 -n,则把后 n 位取出来作为实际匹配的字符串。实现的代码可见 FixedTrailingReader<T> 类。 2.3 支持变长的向前看符号的词法分析器对于变长的向前看符号,处理起来则要更复杂些。因为不能确定向前看的头是在哪里(并没有一个确定的长度),所以必须使用堆栈保存所有遇到的接受状态,并沿着堆栈向下找,直到找到包含 int.MaxValue - symbolIndex 的状态(我就是这么区分向前看的头状态的,可参见上一篇《C# 词法分析器(五)转换 DFA》的 2.4 节 DFA 状态的符号索引)。 需要注意的是,变长的向前看符号是有限制的,例如正则表达式 ab\*/bcd\*,这时无法准确的找到 ab\* 的结束位置,而是会找到最后一个 b 的位置,导致最终匹配的词素不是想要的那个。出现这种情况的原因是使用 DFA 进行字符串匹配的限制,只要是前一部分的结尾与后一部分的开头匹配,就会出现这种问题,所以要尽量避免定义这样的正则表达式。 实现的代码可见 RejectableTrailingReader<T> 类,沿着状态堆栈寻找目标向前看的头状态的代码如下: 在沿着堆栈寻找向前看头状态的时候,不必担心找不到这样的状态,DFA 执行时,向前看的头状态一定会在向前看状态之前出现。 2.4 支持 Reject 动过的词法分析器Reject 动作会指示词法分析器跳过当前匹配规则,而去寻找同样匹配输入(或者是输入的前缀)的次优规则。 比如下面的例子:
对字符串 "abcd" 进行匹配,最后输出的结果是: abcd abc ab a bcd 具体的匹配过程如下所示: 第一次匹配了第 4 个规则 "abcd",然后输出字符串 "abcd",并 Reject。 所以词法分析器会尝试次优规则,即第 3 个规则 "abc",然后输出字符串 "abc",并 Reject。 接下来继续尝试次优规则,即第 2 个规则 "ab",然后输出字符串 "ab",并 Reject。 继续尝试次优规则,即第 1 个规则 "a",然后输出字符串 "a",并 Reject。 然后,继续尝试次优规则,即第 6 个规则 ".",此时字符串 "a" 被成功匹配。 最后,剩下的字符串 "bcd" 恰好与规则 5 匹配,所以直接输出 "bcd"。 在实现上,为了做到这一点,同样需要使用堆栈来保存所有遇到的接受状态,如果当前匹配被 Reject,就沿着堆栈找到次优的匹配。实现的代码可见 RejectableReader<T> 类。 上面这四个小节,说明了词法分析器的基本结构,和一些功能的实现。实现了所有功能的词法分析器实现可见 RejectableTrailingReader<T> 类。 三、一些词法分析的例子接下来,我会给出一些词法分析器的实际用法,可以作为参考。 3.1 计算器我首先给出一个计算器词法分析程序的完整代码,之后的示例就只包含规则的定义了。 3.2 字符串下面的例子可以匹配任意的字符串,包括普通字符串和逐字字符串(@"" 这样的字符串)。由于代码中的字符串用的都是逐字字符串,所以双引号比较多,一定要数清楚个数。
3.3 转义的字符串下面的例子利用了上下文,不但可以匹配任意的字符串,同时还可以对字符串进行转义。
可以看到,这里的输出结果,恰好是 3.2 节的输出结果转义之后的结果。需要注意的是,这里利用 c.Accept() 方法修改了要返回的词法单元,而且由于涉及到多重转义,在设计规则的时候一定要注意双引号和反斜杠的个数。 现在,完整的词法分析器已经成功构造出来,本系列暂时就到这里了。相关代码都可以在这里找到,一些基础类(如输入缓冲)则在这里。 作者:CYJB 系列导航 现在最核心的 DFA 已经成功构造出来了,最后一步就是根据 DFA 得到完整的词法分析器。 由于目前还不能像 Flex 那样支持词法定义文件,所以仍然需要在程序中定义规则,而且也不能非常灵活的自定义词法分析器,不过基本的东西完全够用了。 一、词法规则的定义词法分析器用到的所有规则都在 Grammar<T> 类中定义,这里的泛型参数 T 表示词法分析器的标识符的类型(必须是一个枚举类型)。定义规则方法包括:定义上下文的 DefineContext 方法、定义正则表达式的 DefineRegex 方法和定义终结符的 DefineSymbol 方法。 调用 DefineContext 方法定义的词法分析器上下文,会使用 LexerContext 类的实例表示,它的基本定义如下所示:
在词法分析器中,仅可以通过标签来切换上下文,因此 LexerContext 类本身被设置为 internal。 上下文的类型就是包含型或者排除型,等价于 Flex 中的 %s 和 %x 定义(可参见 Flex 的 Start Conditions)。这里简单的解释下,在进行词法分析时,如果当前上下文是排除型的,那么仅在当前上下文中定义的规则会被激活,其它的(非当前上下文中定义的)规则都会失效。如果当前上下文是包含型的,那么没有指定任何上下文的规则也会被激活。 默认上下文标签为 "Initial"。 Grammar<T> 中定义正则表达式的 DefineRegex 方法,就等价于 Flex 中的定义段(Definitions Section),可以定义一些常见的正则表达式以简化规则的定义,例如可以定义
在正则表达式的定义中,就可以直接使用 "{digit}" 来引用预先定义的正则表达式。 最后是定义终结符的 DefineSymbol 方法,就对应于 Flex 中的规则段(Rules Section),可以定义终结符的正则表达式和相应的动作。 终结符的动作使用 Action<ReaderController<T>> 来表示,由 ReaderController<T> 类来提供 Accept,Reject,More 等方法。 其中,Accept 方法会接受当前词法单元,并返回 Token 对象。Reject 方法会拒绝当前匹配,转而寻找次优的规则,这个操作会使词法分析器的所有匹配变慢,需要谨慎使用。More 方法通知词法分析器,下次匹配成功时,不替换当前的文本,而是把新的匹配追加在后面。 Accept 方法和 Reject 方法是相互冲突的,每次匹配成功只能调用其中的一个。如果两个都未调用,那么词法分析器会认为当前匹配是成功的,但不会返回 Token,而是继续匹配下一个词法单元。 二、词法分析器的实现2.1 基本的词法分析器由于多个规则间是可能产生冲突的,例如字符串可以与多个正则表达式匹配,因此在说明词法分析器之前,首先需要定义一个解决冲突的规则。这里采用与 Flex 相同的规则:
基本的词法分析器非常简单,它只能实现最基础的词法分析器功能,不能支持向前看符号和 Reject 动作,但是大部分情况下,这就足够了。 这样的词法分析器几乎相当于一个 DFA 执行器,只要不断从输入流中读取字符送入 DFA 引擎,并记录下来最后一次出现的接受状态就可以了。当 DFA 引擎到达了死状态,找到的词素就是最后一次出现的接受状态对应的符号(这样就能保证找到的词素是最长的),对应多个符号的时候只取第一个(之前已经将符号索引从小到大进行了排序,因此第一个符号就是最先定义的符号)。 简单的算法如下: 输入:DFA D
s=s0
while (c != eof) {
s=D[c]
if (s∈FinalStates) {
slast=s
}
c = nextChar();
}
slast 即为匹配的词素
实现该算法的代码可见 SimpleReader<T> 类,核心代码如下: 2.2 支持定长的向前看符号的词法分析器接下来,将上面的基本的词法分析器进行扩展,让它支持定长的向前看符号。 向前看符号的规则形式为 t 可以匹配的字符串长度是固定的,就称作定长的向前看符号;如果都不是固定的,则称为变长的向前看符号。 例如正则表达式 abcd 或者 [a-z]{2},它们可以匹配的字符串长度是固定的,分别为 4 和 2;而正则表达式 [0-9]+ 可以匹配的字符串长度就是不固定的,只要是大于等于一都是可能的。 区分定长和变长的向前看符号,是因为定长的向前看符号匹配起来更容易。例如正则表达式 a\*/bcd,识别出该模式后,直接回退三个字符,就找到了 a* 的结束位置。 对于规则 abc/d*,识别出该模式后,直接回退到只剩下三个字符,就找到了 abc 的结束位置。 我将向前看符号可以匹配的字符串长度预先计算出来,存储在 int?[] Trailing 数组中,其中 null 表示不是向前看符号,正数表示前面(t)的长度固定,0 表示长度都不固定。 所以,只需要在正常的匹配之后,判断 Trailing 的值。如果为 null,不是向前看符号,不用做任何操作;如果是正数 n,则把当前匹配的字符串的前 n 位取出来作为实际匹配的字符串;如果是负数 -n,则把后 n 位取出来作为实际匹配的字符串。实现的代码可见 FixedTrailingReader<T> 类。 2.3 支持变长的向前看符号的词法分析器对于变长的向前看符号,处理起来则要更复杂些。因为不能确定向前看的头是在哪里(并没有一个确定的长度),所以必须使用堆栈保存所有遇到的接受状态,并沿着堆栈向下找,直到找到包含 int.MaxValue - symbolIndex 的状态(我就是这么区分向前看的头状态的,可参见上一篇《C# 词法分析器(五)转换 DFA》的 2.4 节 DFA 状态的符号索引)。 需要注意的是,变长的向前看符号是有限制的,例如正则表达式 ab\*/bcd\*,这时无法准确的找到 ab\* 的结束位置,而是会找到最后一个 b 的位置,导致最终匹配的词素不是想要的那个。出现这种情况的原因是使用 DFA 进行字符串匹配的限制,只要是前一部分的结尾与后一部分的开头匹配,就会出现这种问题,所以要尽量避免定义这样的正则表达式。 实现的代码可见 RejectableTrailingReader<T> 类,沿着状态堆栈寻找目标向前看的头状态的代码如下: 在沿着堆栈寻找向前看头状态的时候,不必担心找不到这样的状态,DFA 执行时,向前看的头状态一定会在向前看状态之前出现。 2.4 支持 Reject 动过的词法分析器Reject 动作会指示词法分析器跳过当前匹配规则,而去寻找同样匹配输入(或者是输入的前缀)的次优规则。 比如下面的例子:
对字符串 "abcd" 进行匹配,最后输出的结果是: abcd abc ab a bcd 具体的匹配过程如下所示: 第一次匹配了第 4 个规则 "abcd",然后输出字符串 "abcd",并 Reject。 所以词法分析器会尝试次优规则,即第 3 个规则 "abc",然后输出字符串 "abc",并 Reject。 接下来继续尝试次优规则,即第 2 个规则 "ab",然后输出字符串 "ab",并 Reject。 继续尝试次优规则,即第 1 个规则 "a",然后输出字符串 "a",并 Reject。 然后,继续尝试次优规则,即第 6 个规则 ".",此时字符串 "a" 被成功匹配。 最后,剩下的字符串 "bcd" 恰好与规则 5 匹配,所以直接输出 "bcd"。 在实现上,为了做到这一点,同样需要使用堆栈来保存所有遇到的接受状态,如果当前匹配被 Reject,就沿着堆栈找到次优的匹配。实现的代码可见 RejectableReader<T> 类。 上面这四个小节,说明了词法分析器的基本结构,和一些功能的实现。实现了所有功能的词法分析器实现可见 RejectableTrailingReader<T> 类。 三、一些词法分析的例子接下来,我会给出一些词法分析器的实际用法,可以作为参考。 3.1 计算器我首先给出一个计算器词法分析程序的完整代码,之后的示例就只包含规则的定义了。 3.2 字符串下面的例子可以匹配任意的字符串,包括普通字符串和逐字字符串(@"" 这样的字符串)。由于代码中的字符串用的都是逐字字符串,所以双引号比较多,一定要数清楚个数。
3.3 转义的字符串下面的例子利用了上下文,不但可以匹配任意的字符串,同时还可以对字符串进行转义。
可以看到,这里的输出结果,恰好是 3.2 节的输出结果转义之后的结果。需要注意的是,这里利用 c.Accept() 方法修改了要返回的词法单元,而且由于涉及到多重转义,在设计规则的时候一定要注意双引号和反斜杠的个数。 现在,完整的词法分析器已经成功构造出来,本系列暂时就到这里了。相关代码都可以在这里找到,一些基础类(如输入缓冲)则在这里。 |
请发表评论