编译原理复习-第三章

词法分析器的功能

        词法分析器就是将构成源程序的字符串转换成“等价的”单词(记号)序列的程序。

        词法分析器读入表示源程序的字符流,按照程序功能等价的要求,将其转换成对应的单词序列,并剔除其中的空格、注解等不影响程序语义的字符。

单词的分类与表示

        在分类和编码的基础上，将单词表示成二元组的形式：（种别，属性值）。”种别“表示相应的单词所属的类别，通常采用整数编码表示，这种整数编码又称为种别码；”属性值“表示单词相应的值。这种二元组形式又称为单词的内部表示形式。

词法分析器输出

p67-68

源程序的输入缓冲与预处理

p68-70

词法分析阶段的错误处理

p70-72

词法分析器的位置

p72-73

单词描述

正则文法

        正则文法就是第二章中的3型文法。

        单词是程序设计语言的基本语法单位。如果把程序设计语言中的每类单词都看做一种语言,则多数程序设计语言单词的词法都能用正则文法来描述,而且基于单词的这种形式化描述会给词法分析器的设计与实现带来很大的方便,甚至支持词法分析器的自动构造。

        主要讲述使用正则文法描述单词（词法分析器的输出）（p73-74）

正则表达式

        除了利用正则文法来描述单词，还可以利用正则表达式来描述单词。

正则表达式的定义

        正则表达式所表示的语言称为正则集。

        可以证明,正则表达式与正则文法是等价的。也就是说,给定任意的正则文法G,存在正则表达式r.使得L(r)=L(G):同样,给定任意的正则表达式r,存在正则文法 G,使得L(G)=L(r)。因此,正则集与正则语言是同义词。

例子

以下例子用于更好的理解正则表达式和正则集：

代数定律

正则表达式遵循一些代数定律，可以用于正则表达式的等价变换：

闭包

在正则表达式中,由于某些结构出现频繁,为方便起见,可以用缩写形式（正闭包、克林闭包等）来表示它们。

正则表达式与正则文法的等价性（重点）

正则文法转正则表达式

定义

给定正则文法G,构造一个正则表达式r,使得L(r)=L(G)。

解决思路

(1)根据正则文法G构造正则表达式联立方程

(2)解联立方程组，求等价的正则表达式r

例题

以下是书上的解题思路，但我感觉不直观，且有点小问题：

第一步按照规则写出各个产生式的方程式：

第二步用代入消元法消除除S以外的所有变量：

        图片第一个红框已经将C=c*C和C=c替换成了C=c*c，第二个红框中不知道为什么还有C=c？而且第二个红框中应该使用的是代入消元规则的3而不是4？？

本人的解题思路：

（1）构造方程式

S = a*S | aB
B = b*B | bc | a*B | bS => B=(a|b)*B | bC | bS
C = c*C | c

首先看S，能够根据规则4进行替换成：

S = a*aB

要得到S，需要消除变量B。B的方程式如下：

B = (a|b)*B | bC | bS

B产生式右部有C，先消除C。C的方程式如下：

C = c*C | c

利用规则4将C的方程式替换成如下：

C = c*c

在利用规则3，替换B方程式的右部变量C，替换后B方程式如下：

B = (a|b)*B | bc*c | bS

此时B方程式右部还有变量B，利用两次规则4，一次是对(a|b)*B|bc*c，一次是对(a|b)*B|bS，得到替换后的B的方程式如下：

B = (a|b)*bc*c | (a|b)*bS

变量B的方程式右部已经消除了所有除S以外的变量，利用规则3代入变量S方程组得：

S = a*a(a|b)*bc*c | a*a(a|b)*bS

调换一下位置：

S = a*a(a|b)*bS | a*a(a|b)*bc*c 

利用规则4得：

S = (a*a(a|b)*b)*a*a(a|b)*bc*c 

跟书上结果不一样的地方是

书上：

本人：

除了这个变量，其它地方是一样的。

正则表达式转正则文法

定义

解决思路

方法本质是引入语法变量。

例题

复杂一点的如下：

有穷状态自动机

有穷状态自动机是正则语言的另一种等价描述它从语言识别的角度实现对相应语言的刻画。

定义

分类-DFA和NFA

DFA和NFA一个是确定的有穷状态机，一个是不确定的有穷状态机，它们是等价的。

正则表达式转有穷自动机

有穷自动机分为DFA和NFA。有穷自动机转DFA是要先求解有穷自动机装转NFA，再由NFA转DFA实现。正则表达式转NFA（反过来也同样重要）是重点，NFA转DFA考的概率不大。

正则表达式转NFA

【【编译原理】哈工大公开课（高清版）】 3-5从正则表达式到有穷自动机_哔哩哔哩_bilibili

正则表达式转DFA

【【编译原理】哈工大公开课（高清版）】 3-6从NFA到DFA的转换_哔哩哔哩_bilibili

两个视频都看比较好，第二个视频还涉及重点有关根据NFA判断求出其识别的字符串以及带空边的NFA的考虑。

考点

正则文法和正则表达式的相互转换

如何理解正则表达式和正则文法和自动机本质上的等价性：

1. 对于任何正则文法都能构造等价的正则表达式，反之亦然。
2. 对于任何正则文法都能构造等价的有穷自动机，反之亦然。
3. 对于任何正则表达式都能构造等价的有穷自动机，反之亦然。

有穷自动机表达（接受）的字符串（带空的DFA和NFA会难一点）：

视频【【编译原理】哈工大公开课（高清版）】 3-4有穷自动机的分类_哔哩哔哩_bilibili有所涉及，可以看看。

DFA和NFA的等价性：

1. 对任何NFA，存在识别同一语言的DFA
2. 对任何DFA，存在识别同一语言的NFA

正则表达式转NFA，NFA转正则表达式

NFA转DFA（考的机率不大）