C# 词法分析器(七)总结
系列导航
- (一)词法分析介绍
- (二)输入缓冲和代码定位
- (三)正则表达式
- (四)构造 NFA
- (五)转换 DFA
- (六)构造词法分析器
- (七)总结
在之前的六篇文章中,我比较详细的介绍了与词法分析器相关的算法。它们都比较关注于实现的细节,感觉上可能比较凌乱,本篇就从整体上介绍一下如何定义词法分析器,以及如何实现自己的词法分析器。
第二节完整的介绍了如何定义词法分析器,可以当作一个词法分析器使用指南。如果不关心词法分析器的具体实现的话,可以只看第二节。
一、类库的改变
首先需要说明一下我对类库做的一些修改。词法分析部分的接口,与当初写《C# 词法分析器》系列时相比,已经发生了不小的改变,有必要做一下说明。
1. 词法单元的标识符
词法单元(token)最初的定义是一个 Token 结构,使用一个 int 属性作为词法单元的标识符,这也是很多词法分析器的通用做法。
但后来做语法分析的时候,感觉这样非常不方便。因为目前还不支持从定义文件生成词法分析器代码,只能在程序里面定义词法分析器。而 int 本身是不具有语义的,作为词法单元的标识符来使用,不但不方便还容易出错。
后来尝试过使用字符串作为标识符,虽然解决了语义的问题,但仍然容易出错,实现上也会复杂些(需要保存字符串字典)。
而既简单,又具有语义的解决方案,就是使用枚举了。枚举名称提供了语义,枚举值又可以转换为整数,而且还能够提供编译期检查,完全避免了拼写错误,所以现在的词法单元便定义为 Token
2. 命名空间
之前的命名空间是 Cyjb.Compiler 和 Cyjb.Compiler.Lexer,现在被改成了 Cyjb.Compilers 和 Cyjb.Compilers.Lexers,毕竟命名空间名称还是比较适合使用复数。
3. 词法分析器上下文
之前对词法分析器上下文的切换,可以使用上下文的索引、标签或 LexerContext 实例本身。但现在只能够通过标签进行切换,这样实现起来更简单些,使用上也不会受到过多影响。
4. DFA 的表示
原先 LexerRule 类中对 DFA 的表示有些简单粗暴,对于不了解具体实现的人来说,很难理解 DFA 的表示。现在重新规划了 LexerRule
二、定义词法分析器
这一节是 Cyjb.Compilers 类库中词法分析器的使用指南,包含了完整的文档、实例以及相关注意事项。类库的源码可以从 Cyjb.Compilers 项目找到,类库文档请参见 wiki。
1. 定义词法单元的标识符
前面说到,目前是使用枚举类型作为词法单元的标识符,这个枚举类型中的字段可以任意定义,没有任何限制。不过,为了方便之后的语法分析部分,特别要求枚举值必须是从 0 开始的整数,枚举值最好是连续的,因为不连续的枚举值会导致语法分析部分浪费更多的空间。
使用特殊的值 -1 来表示文件结束(EndOfFile),该值可以从 Token
这里仍然使用计算器作为示例,以下代码便定义了作为标识符的枚举:
在使用的时候,显然会比整数更加方便。
2. 定义词法分析器的上下文
词法分析器的所有定义都是从 Cyjb.Compilers.Grammar
词法分析器的上下文,可以用来控制规则是否生效。上下文有两种类型:包含型或者排除型。
- 如果当前是包含型上下文,那么会激活当前上下文的所有规则,同时会激活所有没有指定任何上下文的规则。
- 如果当前是排除型上下文,那么只会激活当前上下文的所有规则,其它任何规则都不会被激活。
使用以下的方法来分别定义排除型和包含型的词法分析器上下文,label 参数即为上下文的标签:
默认的词法分析器上下文是 "Initial",通过该标签可以切换到默认的上下文中。需要特别注意的是,由于实现上的原因,上下文必须先于所有终结符定义。
例如,以下的代码定义了一个包含型上下文 Inc,以及一个排除型上下文 Exc。
3. 定义正则表达式
使用以下的方法来定义正则表达式:
正则表达式可以通过 Cyjb.Compilers.RegularExpressions.Regex 类的相关方法构造得到,也可以直接使用表示正则表达式的字符串,相关定义的规则可以参考 《C# 词法分析器(三)正则表达式》。
注意,这里定义的正则表达式仅仅用于简化终结符定义,方便重复使用一些通用或复杂的正则表达式,并没有其它的作用。这里定义的正则表达式也不可以包含向前看符号(/)、行首限定符(^)、行尾限定符($)或者上下文(
例如,以下代码定义了一个名为 digit 的正则表达式,以后需要表示数字的时候,就可以直接通过 “{digit}” 来引入,而不需要每次都写 “[0-9]+”。
4. 定义终结符
使用 Grammar
这些重载被分成了三组。第一组重载,接受 T id 作为与词法单元对应的标识符,和相应的正则表达式及其上下文。当相应的终结符被匹配后,自动返回标识符为 id 的 Token
第二组重载,具有额外的参数 action,这是只包含一个 ReaderController
最后一组重载,缺少了标识符 id,也就无法自动返回 Token
终结符的动作
在成功匹配某个终结符时,就会执行相应的动作,该动作是一个 Action
ReaderController
Accept 方法会接受当前的匹配,词法分析器会返回表示当前匹配的 Token
More 方法会通知词法分析器,保留本次匹配的文本。假设本次匹配的文本是 "foo",下次匹配的文本是 "bar",如果本次匹配时调用了 More 方法,下次匹配的文本就会变成 "foobar"。
Reject 方法会拒绝当前的匹配,转而使用次优的规则继续尝试匹配。详细信息请参考《C# 词法分析器(六)构造词法分析器》的 2.4 节“支持 Reject 动过的词法分析器”。
Accept 方法和 Reject 方法不能够在一次匹配中同时调用,因为它们是互斥的动作。如果在一次匹配中两个方法都没有调用,那么词法分析器会什么都不做——丢弃本次匹配的结果,直接进行下一次匹配。
对于词法分析器上下文的控制,简单的用法就是利用上下文来切换匹配的规则集,以实现一些“次级语法”,可以参考《C# 词法分析器(六)构造词法分析器》的 3.3 节给出的示例“转义的字符串”。
下面给出计算器的终结符定义。其中,Id 的定义是通过引入正则表达式 digit 来完成的,而且它定义了自己的动作,会将自己对应的文本转换为 double 类型,并保存到 Token
5. 构造词法分析器
以上四步便完成了词法分析器的定义,接下来就是构造词法分析器。使用以下四个方法,就可以直接构造出相应的词法单元读取器(TokenReader
如果调用的是 GetReader 方法重载,则认为动作中不包含拒绝(Reject),会返回比较简单但更高效的词法分析器实现。如果调用的是 GetRejectableReader 方法重载,则认为动过中包含拒绝(Reject),会返回功能更强大但效率略低的词法分析器实现。
其规则是:
- 如果不包含向前看和拒绝动作,则返回 SimpleReader
的实例。 - 如果只包含定长的向前看(不包含变长的向前看或拒绝动作),则返回 FixedTrailingReader
的实例。 - 如果只包含拒绝动作(不包含向前看),则返回 RejectableReader
的实例。 - 如果包含变长的向前看,或者同时包含拒绝动作和向前看(无论是否变长),则返回 RejectableTrailingReader
的实例。
关于其中实现的细节,请参考《C# 词法分析器(六)构造词法分析器》。
所有的词法单元读取器,都继承自 TokenReader
TokenReader
以下是构造出计算器的词法单元读取器,并输出所有读取到的词法单元的代码:
最后是完整的构造计算器的代码:
代码的输出结果如下图所示:
可以看到,最后总是会以特殊值 -1 结束,表示文件结束。
三、自定义词法分析器
Cyjb.Compilers 项目中,提供了完整的词法分析器实现。但是,在实际的使用中,难免会遇到各种各样的需求,可能已实现的词法分析器是无法满足的,此时就必须自己完成词法分析器了。
在完成定义词法分析器后,可以从 Grammar
下图是与 LexerRule
图 1 与 LexerRule
LexerRule
LexerRule
LexerRule
LexerRule
以上就是词法分析器所需的信息,只要获取了这些信息,就可以根据需要,构造自己的词法分析器。详细的实现,请参考《C# 词法分析器(六)构造词法分析器》中提供的算法,甚至可以将数据写入 .cs 文件中(甚至可以使用其它语言实现,因为数据本身是不影响实现的),实现词法分析器的生成(虽然现在我还仍未实现这点)。
以上的数据,全部是以比较容易理解的形式存储的,未进行压缩,所以可能会占用比较多的空间。在具体的实现中,可以根据需要改变数据存储格式,或选用一些压缩算法(如使用四数组压缩 DFA 状态)。