首页 > 程序开发 > 软件开发 > Java >

用java开发编译器之Thompson构造:正则表达式的词法解析

2016-04-25

Thompson构造:正则表达式的词法解析 大家好,欢迎大家来到coding迪斯尼,阅读博客的朋友可以到我的网易云课堂中,通过视频的方式查看代码的调试和执行过程: http: study 163 com course courseMai

    Thompson构造:正则表达式的词法解析

大家好,欢迎大家来到coding迪斯尼,阅读博客的朋友可以到我的网易云课堂中,通过视频的方式查看代码的调试和执行过程:

继上一节我们开发了闭包替换功能后,这一节,我们继续推进Thompson 构造算法的开发。我们的目标是,给定一组正则表达式后,把他转换为NFA有限状态自动机。无论是正则表达式,还是最终的有限状态自动机,他们的本质都是对输入文本进行判定。例如正则表达式:
{D}+
({D}+|{D}.{D}+|{D}+.{D})(e{D}+)

用来判别输入是否是整形或浮点型字符串。其对应的有限状态自动机:
这里写图片描述vcbVzajX1rf7o6zO0sPH1qq1wKOsxtXNqNfWt/vGpcXky/y21NOmtcRhc2NpadfWt/ujrMD9yOfX1rf7IGEgxqXF5CDL/LbU06a1xGFzY2lp19a3+yAmbHNxdW87YSZyc3F1bzsuILWrxtXNqNfWt/u6zczYyuLX1rf7veG6z9Ta0rvG8Mqxo6zO0sPH0OjSqr340NCyu82stcS94rbBo6zA/cjnIFthLXpdIMalxeTL+dPQ0KHQtNfWxLiho8bVzajX1sS4uPrXqtLlt/u94brPyrGjrNKy0OjSqr340NCyu82stcS94rbBo6zA/cjno7o8L3A+DQo8cD5cYiCx7cq+YmFja3NwYWNlo6wgz+C1sdPavPzFzLXEZGVsZXRlPGJyIC8+DQpcbiCx7cq+u7vQ0DxiciAvPg0KXHIgse3KvrvYs7U8YnIgLz4NClxzILHtyr6/1bjxPGJyIC8+DQpcZSCx7cq+vPzFzLXEIGVzYyC8/DxiciAvPg0KXGRkZCBkse3Kvsr919ajrFxkZGQgse3Kvsj9zruwy7341sbK/TxiciAvPg0KXHhkZGQgse3Kvsj9zrvKrsH5vfjWxsr9PGJyIC8+DQpcXkMg0ru49re00LG43KOs0ru49snPvOLAqLrFo6xDtPrC68jO0uLSu7j219bEuKOsy/ux7cq+vPzFzLz8Q3RybCC807bU06bX1sS4tcTX6brPPGJyIC8+DQpcYyDSu7j216rS5bf7vNPIzrrO0ru49tfWt/ujrLHtyr7GpcXk1eK49tfWt/uxvsntoaPA/cjnIC4gvs3GpcXk19a3+yAuPGJyIC8+DQrI57n7w7vT0NCxuNyjrC4g1NrV/dTyse2078q91tDKx9K7uPbNqMXkt/uhoyAqILHtyr7GpcXk19a3+yAmbHNxdW87PGVtPiZyc3F1bzssIMjnufvDu9PQ0LG43KOsIDwvZW0+1NrV/dTyse2078q91tCx7cq+sdWw/LLZ1/eho9Kyvs3Kx8zYyuLX1rf7x7DD5srH16rS5bf7tcS7sKOsy/y+zbK71Nm+39PQzNjK4rqs0uWhozwvcD4NCjxwPtPQ0rvQqczYyuK3+7rFo6zA/cjnXiCx7cq+v6rNt8alxeSjrCBeW2Etel0gse3KvsalxeTIzrrO0tTQodC019a3+7+qzbe1xNfWt/u0rqOsW2Etel0kIMalxeTIzrrO0tTQodC019bEuL3hzrK1xNfWt/u0rqGjeyCx7cq+uuq2qNLltcS/qsq8o6wgfbHtyr666rao0uW1xL3hyvihozwvcD4NCjxwPtTay6vS/brFJnJkcXVvOyAmcmRxdW87INbQtcTIzrrOzNjK4tfWt/u2vLK71Nm+37G4zNjK4rqs0uWjrMD9yOcg1f3U8rHttO/KvSAmbGRxdW87KzxlbT4/JnJkcXVvOyC+zda7xqXF5Mj9uPbX1rf7ICsgPC9lbT4/LjwvcD4NCjxwPrTKt6i94s72xve1xMq1z9ajuijM9LP2ZWNsaXBzZSk8YnIgLz4NCrv509rS1MnPveHC26OsztLDx7/J0tS/qsq8yei8xrTKt6i94s72xveho7bU1f3U8rHtyr7Kx6OstMq3qL3izvaxyL3PvPK1paOsztLDx9a70qrSu7TOtsHI69K7uPbX1rf7o6yyore1u9i4w9fWt/u21NOmtcSx6sepvs2/ydLUwcuho9TatPrC69bQo6w8YnIgLz4NCs7Sw8e4+MO/uPbM2Mri19a3+7a8uLPT6MzYyuK1xLHqx6mjrLb4ttTT2sbVzajX1rf7o6zO0sPHzbPSu7j40ru49rHqx6m90CBMICwgse3KviBMaXRlcmFsILy019a3+7Ojwb+jrNTatPrC69bQo6zTw2VudW0gwOC2qNLlwcvM2Mri19a3+7XEserHqda1o7o8YnIgLz4NCjxpbWcgYWx0PQ=="这里写图片描述" src="http://www.2cto.com/uploadfile/Collfiles/20160425/201604250940311102.png" title="\" />

由于我们要处理的字符,基本上只有ascii 码字符,因此字符总共才128个。我们用一个长度为128字节的数组来存放每一个字符所对应的标签,在代码里这个数组叫tokenMap, 词法解析器读入一个字符,获取该字符对应的ascii 码值,根据ascii 码值在tokenMap中去获取对应标签值, 例如, 如果输入的是符号 .
, “.” 对应的ascii 码值是62, 于是tokenMap[62]得到的值就是enum Token 中的ANY.
我们接下来看tokenMap的初始化代码:
这里写图片描述
解析器在构造时,先给tokenMap的每一个元素赋初值Token.L, 然后再对特殊字符设置对应的标签。

Lexer 类的advance 接口用来读入字符,然后返回字符对应的标签:
这里写图片描述
在advance函数中,我们先从exprHandler中获取已经处理好的正则表达式字符串。然后从获取的字符串中依次取出字符,进行逐个解析,charIndex用来表示当前解析字符所在的正则表达式字符串中的下标。EOS表示当前正则表达式的字符串已经分析完毕,当下次在进入advance 时, 一旦发现当前标签是EOS, 则从exprHandler 中读入新的正则表达式字符串。

再往下看:
这里写图片描述
当我们读到的字符是双引号时,我们需要做标记,因为在双引号中的所有字符,不管是普通字符,还是特殊字符,我们都把他们当做普通字符处理。如果读到转义符,那就要进行相应处理。对转义符进行处理的函数是handleEsc, 在advance函数的最后,我们看看当前解析的字符是否处于双引号中或字符被转义了,前面提到过转义符后面跟着的任何字符或处于双引号中的字符都会被当做普通字符处理,如果不是这种情况,则在tokenMap中查找字符对应的标签。

我们再看看对转义符的专门处理函数handleEsc, 如果正则表达式[\b]被解析时,字符 \ 和 字符 b 会连在一起解读,解读他们的函数就是handleEsc:
这里写图片描述

大家可以看到 \ 和 b 会被连在一起解读成 ‘\b’, ‘\b’ 在ASCII表中表示为回删符,也就是键盘上的Delete键。继续往下看:
这里写图片描述
如果表达式中遇到字符串 \^A, 前面我们提到过,这表示在键盘上的Ctrl+A, 在代码注释中,我给出了如何对类似的字符进行转换。接着的代码处理的是将\xDDD解读成三位十六进制数。在后面的调试演示中,我们会详细的理解这段代码的运作原理。

在主函数main 中,执行runLexerExample, 就可以调试词法解析器的功能了:
这里写图片描述
在runLexerExample中,词法解析器从控制台中读入正则表达式,然后逐个解析表达式的字符,并把字符对应的标签含义显示到控制台中,例如输入的正则表达式宏替换后是[0-9]+, 那么runLexerExample会输出结果如下:
这里写图片描述

在下一节,我们将进行代码的调试演示。让大家对词法解析器的实现原理有进一步的理解。

相关文章
最新文章
热点推荐