编译原理动手实操:词法解析算法的一些概念说明

前端之家收集整理的这篇文章主要介绍了编译原理动手实操:词法解析算法的一些概念说明前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

大家好,欢迎大家来到Coding迪斯尼,在深入探究词法解析算法前,我们需要了解一些基本概念。了解基本概念有点像背单词,它有些无聊,但你又不得不做。好在这类事情在我们的课程里不多。大家过过眼,留个心眼就好。


阅读博客的朋友可以到我的网易云课堂中,通过视频的方式查看代码的调试和执行过程:

http://study.163.com/course/courseMain.htm?courseId=1002830012


在词法解析中有一个概念叫字母表,字母表并不是单单指字母组成的集合,它是指一组数量有限的符号的集合。例如C语言中常用的ASCII字符集就可以称作字母表。所有汉字的集合也可以称作字母表。{‘0’,‘1’}是二进制的字母表。

字符串或者叫单词,是字母表中一系列符号的组合,例如英语单词,中文的词组都可以称之为字符串。在实际运用中,字符串就是字母数组。有一种特殊的字符串叫空字符串,也就是不包含任何字母的字符串。在C语言中可以用只包含’\0’的数组作为空字符串,char buf[10] = {‘\0’}。

有一个概念叫“语言”,他是指所有字符串的集合,比“语言”小的概念叫“句子“,他是一系列字符串组成的集合。也就是说,有限个字符串组成的集合叫句子,所有可能句子组成的集合叫语言。拿我们中文来举例,我们的句子其实是一系列中文词组的集合,那么中文就是所有句子的集合。

词组必须依照某些规则组合才能形成有意义的句子,这种规则我们就称之为语法。

大家注意到,语法跟词组其实是无关的,跟词组的组合规则有关,这就是为什么在编译器中,词法解析和语法解析可以分开来,词法解析的主要任务就是识别有效词组。

前缀:一个字符串的前缀是指,将字符串尾部的0个或若干个字符删除后剩下的部分。例如“in”是单词”inconsequential” 的前缀,大家要注意,根据定义,”inconsequential”本身也是它自己的前缀。如果把整个字符串都删了,得到的空字符串,也是合法的前缀。

后缀:它是指将字符串从前头删掉0个或若干个字符后剩下的部分。”ible”是”incomprehensible” 的后缀。当然如果从前头将整个字符串删除后得到的空字符串也是合法后缀。

子字符串:它是指将字符串的前缀后后最都删除后,剩下的那部分。例如”age”是”unmanageable” 的子字符串。如果删除的前缀和后缀合在一起是整个字符串,那么删除后的空字符串也是合法的子字符串。

真子集:前缀中有两个特殊成员,一个是空字符串,一个是原来字符串本身。例如” inconsequential”的前缀中,空字符串和“inconsequential“也是它的前缀,如果把这两个特殊的字符串从前缀中去掉,所剩下的集合叫做前缀的真子集。后缀和子字符串做同样的操作后也可得到各自的真子集。

子序列:它是指在字符串中,任意删除0个或多个字符后剩下的字符串,剩下的字符,他们的位置不一定是连续的,例如:iiii,ssss 都是字符串”Mississippi”的子序列

在字符串的基础上,我们可以定义一系列操作。两个字符串的连接操作(concatenation),是将一个字符串添加到另一个字符串的后面,例如”fire” . “water” = “firewater”. 空字符串可以和任何字符串相连接,连接后得到的字符串不变,连接操作可以用符号”.”表示,大家如果用过PHP的话,PHP字符串的连接操作用的就是点号。

如果把连接操作看做是一种乘法,那么X^n,也就是X的n次幂就是将X字符串本身连接n次。假设有一个字母表如下:

L(octal) = {0,1,2,3,4,5,6,7}. 那么L^3,表示的就是有三位数的八进制数。

如果L(Binary) = {0,1}. 那么 L^n 就表示所有二进制数。

(大家要有不理解的地方可以在讨论区提出)

两个集合的连接实际上就是在第一个集合任意选取一个元素,在第二个集合任意选取一个元素,将这两个元素连接起来,所有这种操作的结果就是两个集合连接的结果,例如L(Binary) ^2 = L(Binary) . L(binary). 计算的方式是在第一个{0,1}中任意选一个元素例如0,第二个集合{0,1}中任意选一个元素例如1,得出结果01,这种选取结合的方式有4种,得到4种结果: 00,01,10,11.

这种运算,说的专业点也叫“笛卡尔乘积”

Kleene 闭包:像上面提到的,L^n,n>=0 时所形成的集合叫Kleene闭包。我们用L*来标记

假定集合L1只包含一个字符串,”Va”,集合L2只包含字符串”Voom”,那么

L1* .L2 就是

Voom,VaVoom,VaVaVoom,VaVaVaVoom …… (Va在Voom 前面出现零次或多次)

上面提到的公式L^n,n>=0,如果把n>=0 改成n>=1,那么我们把这种情况叫做正闭包,用 L+ 表示。

我们可以把上面的连接操作和闭包操作用到下面两组集合上:

L(digit) = {0,7,8,9}.

L(alpha)= {a,b,c,…. z}.

L(digit)+ 就是C语言中的所有数字常量。

L(aPHPa) . ( L(alpha) . L(digit))* 就是C语言中,所有合法的变量名。例如a,ab12,times13 这些都是C语言变量名;

正则表达式

正则表达式实际上就是上面提到的连接和闭包操作的各种组合运用。正则表达式描述了字母组合的某种规则,然后看给定的字符串中的字母,他们的组合方式是否跟正则表达式所描述的规则相符合。

最简单的正则表达式是一系列单个字符,匹配输入中的对应字符,正则表达式中还有一些特殊字符,用来表达一些特殊的含义,正则表达式完全可以写成一本书,在这里我们只关注用得到的一些内容,我们只要关注以下几种规则:

1.单字符匹配。字母表中每一个字符都是一个正则表达式。例如字符c,匹配单个字符”c”.

2.ee 两个正则表达式前后连接,用于判断输入的字符串中,是否存在前一部分匹配第一个正则表达式,后一部分匹配第二个正则表达式。例如字符a,n,d分别匹配字母”a”,“n”,“d”,那么正则表达式and 则匹配输入字符串中的”and”

3.通用匹配符 . (括号前面有一个点) ,. 可以匹配任何单个字符,例如a . y 可以匹配any,amy,agy。

4.^开头匹配符, 例如^and 匹配任何以and开头的字符串

5.$末尾匹配符,例如and$, 用于匹配任何以and结尾的字符串。

6.字符类,任何包含在 [ 和 ] 之间的字符构成字符类,例如[0123456789]匹配任何单个数字,一般简写成[0-9]. [0-9A-Fa-f]匹配任何一个十六进制数。[a-zA-Z]匹配任何字母,符号 ^ 如果出现在括号里,那表示取反,例如[^a-z]匹配任何不是小写字母的字符。

7.三种符号*+?,如果正则表达式后面跟着*号,例如a*,它匹配字母a的零次或多次从复。a+ 匹配字母a的一次或多次重复。a? 匹配字母a的零次或一次重复。ll?ama匹配llama,lama. l+ama 匹配lama,llama,lllllllllllama(很多个l和ama). l*ama 匹配ama(l出现零次),lama,lllllllama….等等. 0[xX][0-9a-fA-F]+ 匹配所有十六进制数。

8.e | e,两个正则表达式被一个竖杆分开,如果一个字符串匹配其中任何一个表达式,那么该字符串就匹配这个表达式。例如either | or 匹配字符串either 和or. (frank | john)ie 匹配字符串frankie 和 johnie。而(frank |john)(ie)? 匹配frankie,john,frankie,johnie。

正则表达式作用有限,它可以匹配字母组成的字符串,但无法识别例如:

((()()(())) 这种括号是否正确匹配的问题,这种问题其实是语法解析器的工作。

接下来我们要谈谈一个相对重要也相当有用的概念,叫有限状态自动机(FMS)。

FMS 是 Finite statemachine 的缩写,FMS包含以下一些特点

1.一组有限的状态集合

2.一组从一个状态到另一个状态的转换,每一个转换对应一个输入字符。

3.一个特殊状态叫初始状态。

4.一组特殊状态叫接收状态。

我们看个例子:

图中每一个圆圈表示一个状态,里面的数字表示状态的编号。状态0是初始状态,状态机开始就处于状态0. 状态间的连线就是状态的转换。从初始状态开始,如果读入字符h,那么状态机就从状态0转到状态1. 如果接下来读到字符e那就从状态1转到状态2. 如果读到的字符是i那么就从状态1转到状态5. 如果读取字符c 使得状态机从状态N转到状态M,我们用next(N,c) = M 来表示。Next就叫做转换函数。有两个圈的状态叫接收状态。一旦进入接收状态,就表明当前进入状态机的字符组成的字符串可以被状态机接受。一般来说,一旦进入接受状态后会采取一些行动,根据我们以前的编译器中的词法解析器为例,进入接受状态要做的操作就是打标签。如果输入的字母没有对应的转换,那么状态机会默认的进入错误状态,例如从状态0开始,如果输入的字母是x,但图中没有对应x的转换,因此状态机进入错误状态。

在程序中,我们一般用二维数组来实现有限状态机。另外用一个数组来表述状态机中的状态,我们看看一组伪码:

Transition_table 是有限状态自动

Accepting 数组是状态数组

下一个状态可以从输入字符input_character,和当前状态current_state读出

next_state =Transition_table[current_state][input_character].

If (Accepting[next_state] == true) {

do_an_accepting_action(next_state);

}

其中Transition_table用来表示有限状态机中的转换关系,Accepting数组用来表示各个状态,如果给定状态是接收状态,那么它在数组中的值为true.


下一节我们将用程序来实现一个有限状态自动机,它的功能是用来判断输入的字符串是整形,还是浮点型,例如识别12306是整形,3.1416926是浮点数

原文链接:https://www.f2er.com/regex/359459.html

猜你在找的正则表达式相关文章