下载文档原格式
【编译原理】词法分析：正则表达式与有限⾃动机基础引⾔： 编译语⾔设计的精髓在于⾃动化过程，即如果要设计⼀门编程语⾔，那么⼀定要设计⼀个⾃动化系统，能够⾃⾏读⼊分析程序员写⼊的程序，将其翻译为机器能够识别的指令等信息。
当然⾼级语⾔的编译不是⼀蹴⽽就的，⽽是通过若⼲步的分解、规约、转换、优化，最后得到⽬标程序。
具体的编译步骤如下： 源程序就是我们写⼊的⾼级语⾔，编译的第⼀步叫做“词法分析”。
词法分析的本质，就是要拆解出语句的每⼀个单词，然后对这个单词的类型进⾏辨识。
⾸先拿中⽂来举例。
⽐如有⼀句话是“我喜欢你”，那么⾸先我们要把这句话拆成“我”、“喜欢”、“你”，然后再逐个分析他们的类型，得到“我”->主语；“喜欢”->谓语；“你”->宾语。
这样我们就把这句话每个单词都分析出来了，也就完成了中⽂的“词法分析”。
那么回到编程语⾔，它的词法分析就是将字符序列转换为单词（Token）序列的过程。
翻译成俗话，就是把我们写的⼤⽚语⾔⽂本分解为⼀个⼀个单词，再输出每个单词的类型。
举⼀个例⼦：int p = 3 + a; 这个语句⾮常简单，即定义⼀个变量p，它的初值为变量a与3的加和。
那么接下来我们要对这个语句进⾏词法分析，⾸先我们要把这段⽂本拆解成单词，拆出来就是'int'、'p'、'='、'3'、'+'、'a'、';'。
对这些单词再进⾏类型的辨识，那么就得到以下结果：语素语⾔类型int关键字p标识符=运算符3数字+运算符a标识符 这样我们就把这段⽂本中的每个单词的类型都分析出来了。
乍⼀看⾮常简单对不对，对于⼈类⽽⾔你只需要⽤⾁眼就可以轻松观察出来每个单词的类型，但对于计算机⽽⾔，它可没有⼈类那样的智能。
如果想要计算机能够识别并分析语素的类型，那就需要我们⼈类来为它构造⼀个⾃动化输⼊和分析的系统。
乔姆斯基和句法分析乔姆斯基之于语言学和认知科学，就像图灵之于计算机科学。
没有这些“先知”，我们不知还要在黑暗中摸索多久。
这个说法不只是比喻性的：乔姆斯基的句法频谱后来被证明和几种自动机有着深刻的关联：乔姆斯基3型文法（正则表达式）等价于有限自动机，2型文法（上下文无关文法）等价于下压自动机，1型文法（上下文相关文法）等价于线性有界非确定图灵机，0型文法等价于图灵机。
乔姆斯基的句法研究导致了乔姆斯基在哲学上的理性主义立场，这与英美的经验主义主流不合拍。
其实乔姆斯基的理性主义与欧陆传统的理性主义并不完全一致，倒是和丘奇-图灵论题可互为佐证。
这话展开了讲太长，语言学和哲学系找不到课题的博士生可以试试这个。
乔姆斯基决定干语言学其实缘于他的政治兴趣。
他是结构主义语言学开山哈里斯（Zellig Harris）的学生，他们都是犹太人，有同样的政治主张。
大二时，乔姆斯基对学业困惑，准备退学，哈里斯劝他说：你干嘛不试试语言学呢，可先从数学和哲学入手。
哈里斯给了他一本自己尚未出版的《结构语言学方法》一书的草稿，乔姆斯基从此开了窍，走上了语言学之路。
传统的人文范儿的语言学家必是那些懂多种语言的人才。
但哈里斯把语言学从人文转变成科学，他在宾夕法尼亚大学（UPenn）建立了美国第一个语言学系。
乔姆斯基在宾大得了本科和硕士学位后，在那时还在宾大哲学系教书的古德曼（Nelson Goodman）的影响下，前往哈佛投奔当时美国哲学界的领袖蒯因（Quine），他在哈佛还被选为初级研究员（Fellow）。
哈佛的这个Fellow是给那些明日学术之星准备的，在乔姆斯基之前，王浩、库恩等都得过。
在哈佛期间，乔姆斯基发表了他的第一篇学术论文“句法分析系统”（Systems of Syntactic Analysis）。
值得一提的是，这篇文章并未发表在语言学杂志上，而是在数理逻辑最权威的《符号逻辑杂志》（JSL ）上。
这本杂志由丘奇创办，从杂志创刊开始，丘奇就为JSL 写评论，一直写到他80岁高龄。
正则表达式（Regular Expression）是一种用于匹配字符串的强大工具，而NFA（Non-deterministic Finite Automaton，非确定性有限自动机）是一种可以用于匹配正则表达式的模型。
下面是将正则表达式转换为NFA的一般步骤：1. 将正则表达式转换为Brzozowski标准形式。
Brzozowski标准形式是一种将正则表达式转换为后缀形式的方法。
在Brzozowski标准形式中，每个操作符都被放在括号中，例如(ab)*c表示匹配零个或多个ab，后面跟着一个c。
2. 将Brzozowski标准形式转换为Thompson构造法。
Thompson构造法是一种通过构建一组字符串来模拟正则表达式的匹配过程的方法。
在Thompson构造法中，每个操作符都被表示为一个特定的字符串，例如星号(*)表示重复零个或多个次数的字符串，括号()表示匹配括号内字符串的重复次数。
3. 将Thompson构造法转换为NFA。
在Thompson构造法中，每个字符串都表示一个状态转换。
因此，可以将每个字符串转换为一个状态，并根据字符串之间的顺序将这些状态连接起来。
在NFA中，每个状态都表示一个可能的输入序列，而状态之间的转换则表示输入序列的下一个可能的输入。
4. 确定NFA的起始状态和终止状态。
在NFA中，起始状态是开始匹配正则表达式的状态，而终止状态是匹配结束的状态。
可以根据Thompson构造法中每个字符串的顺序来确定起始状态和终止状态。
例如，如果最后一个字符串是正则表达式的结尾，那么它对应的状态就是终止状态。
5. 确定NFA的转换函数和接受集。
转换函数是将一个状态和一个输入字符映射到下一个状态的函数。
接受集是一个状态集合，当自动机达到这个状态集合时，它就匹配成功。
可以根据NFA中的状态转换来确定转换函数和接受集。
通过以上步骤，可以将正则表达式转换为NFA，以便进行字符串匹配。
1.写出表示下列语言的正则表达式。
⑴ {0, 1}*。
解：所求正则表达式为：(0+1)*。
⑵ {0, 1}+。
解：所求正则表达式为：(0+1)+。
⑶ { x│x∈{0,1}+ 且x中不含形如00的子串 }。
解：根据第三章构造的FA，可得所求正则表达式为：1*(01+)*(01+0+1)。
⑷ { x│x∈{0,1}*且x中不含形如00的子串 }。
解：根据上题的结果，可得所求正则表达式为：ε+1*(01+)*(01+0+1)。
⑸ { x│x∈{0,1}+ 且x中含形如10110的子串 }。
解：所求正则表达式为：(0+1)*10110(0+1)*。
⑹ { x│x∈{0,1}+ 且x中不含形如10110的子串 }。
解：根据第三章的习题，接受x的FA为：要求该FA对应的正则表达式，分别以q0、q1、q2、q3、q4为终结状态考虑：q为终态时的正则表达式：(0*(11*0(10)*(ε+111*11*0(10)*)0)*)*q1为终态时的正则表达式：0*1(1*(0(10)*111*1)*(0(10)*00*1)*)*q2为终态时的正则表达式：0*11*0((10)*(111*11*0)*(00*11*0)*)*q3为终态时的正则表达式：0*11*0(10)*1(11*11*0((10)*(00*11*0)*)*1)*q4为终态时的正则表达式：0*11*0(10)*11(1*(11*0((00*11*0)*(10)*)*11)*)*将以上5个正则表达式用“+”号相连，就得到所要求的正则表达式。
⑺ { x│x∈{0,1}+ 且当把x看成二进制数时，x模5与3同余和x为0时，│x│=1且x≠0时，x的首字符为1}。
解：先画出状态转移图，设置5个状态q0、q1、q2、q3、q4，分别表示除5的余数是0、1、2、3、4的情形。
另外，设置一个开始状态q.由于要求x模5和3同余，而3模5余3,故只有q3可以作为终态。
由题设，x=0时，│x│=1，模5是1，不符合条件，所以不必增加关于它的状态。
