1.词法分析

1.1词法分析器分类

词法分析器有两类

  • 一类是仅作为语法分析的子程序：

  • 另一类是作为编译器的独立一遍处理器：

1.2单词类型的划分

单词：是指语言中具有独立含义的最小的语义单位

1.3单词的描述工具

1.3.1正则表达式

例子：((y|z)*x(y|z)*x)*(y|z)*

1.3.2自动机

例子：

2.正则表达式

2.1基本概念

  • 字母表（非空性有穷性）

  • 符号串

    • 符号串连接

    • 符号串的方幂

  • 符号串集合

    • 符号串集的乘积

    • 符号串集合的方幂

    • 符号串集合的正闭包：A+=A1∪A2∪A3 …∪An

    • 符号串集合的星闭包：A*=A0∪A1∪A2∪A3 …∪An…=A0∪A+

2.2正则表达式

在词法分析中，正则表达式e根据语义函数解释所得到的符号串集合称为正则表达式e的正则集。

正则集取值如下：

2.3正则表达式的性质

2.4用正则表达式描述不同类型单词

2.5正则表达式的局限性

  • 正则表达式不能用于描述配对或嵌套的结构

  • 正则表达式不能用于描述重复串

2.6正则示例

example 1：

example 2：

  • 长度为1的串，空串

  • 长度为2的串：00 01 10 11

  • 长度为4的串：2个2串的连接

  • 长度为偶数的串：（00|01|10|11）*  也可以是两位（（0|1）（0|1））*

example 3：

  • ((y|z)*x(y|z)*x)*(y|z)*

  • ((x|z|yx|yz)*(y|)

3.有限自动机（DFA）

3.1有限自动机定义

终止状态集:不止接受一个终止状态

对于两个DFA M1和M2，若有L(M1)=L(M2)则称M1和M2等价(即M1和M2识别的字符串集合相同，参考3.3DFA接受的串）

3.2DFA的表示

3.2.1状态转换矩阵

3.2.2状态转换图

3.3DFA接受的串

例子1：

例子2：

3.3自动机示例

3.4用DFA描述不同类型单词

3.5自动机的实现

3.5.1直接转换法

每个状态对应一个带标号的switch语句转向边对应goto语句

3.5.2状态转换矩阵

自动机存储在矩阵中，状态比较多，每次都去查表，跳转。

3.5.3比较

  • 直接转换：基于状态转换图

    • 多段代码

    • 书写复杂，效率高，占用储存空间小

    • 适合状态数少

  • 状态转换矩阵：基于状态转换矩阵

    • 只有一段代码

    • 书写简单，但要储存表

    • 通用

4.非确定有限自动机(NFA)

4.1非确定有限自动机定义

和有限状态机的区别：

  • 一个状态的不同输出边可以标有相同符号

  • 允许有多个开始状态

  • 允许有空边

存在的问题：

  • NFA所能接受的串与DFA的定义是相同的

  • NFA更为灵活，易于很多问题的描述

  • 实现起来很困难

  • 问题示例：

等价：设A1和A2是同一个字母表上的自动机，如果有L(A1)=L(A2),则称A1和A2等价。

对于每一个非确定自动机A,存在一个确定自动机A’,使得L(A)=L(A’).（定理）

4.2NFA到DFA的转换

与DFA相比, NFA的非确定性体现在：

  • 允许有多个开始状态

  • 在没有任何输入的情况下允许进行状态转换

接下来分点给出步骤

4.2.1合并空边

另外一种消除空边的转换方式：

4.2.2整合规则

4.2.3确定化

NFA确定化后会使得状态转换函数成为单值函数

4.2.4整体流程

题目：

第一步

第二步

4.3自动机的最小化

最小（最简）自动机：如果DFA M 没有无关状态，也没有等价状态，则称M 为最小自动机。

任一DFA都可以化为最简自动机，即任一DFA M都存在DFA M'，使得L(M)=L(M')，且M'是最简自动机

NFA确定化之后会使得状态转换函数变成单值函数

4.3.1等价状态

4.3.2无关状态

开始到不了；到不了终点

4.4自动机的化简

为了找到最小自动机，状态分离法是为了判断不等价。

在一个自动机中，终止状态和非终止状态肯定是不等价的。所以我们首先把状态集分成两部分，第一部分是终止状态，第二部分是非终止状态。这两部分不等，下面我们再进行区分，我们要做什么呢？

比方说有两个s1和s2，他们针对两个字符，可能映射到不同的组里，那这两个状态肯定不等价。例如s1接受a到1组了，s2接受a到2组了，那他俩肯定是不等价的。基于这种想法，我们就把不等价的又分开了，同样的道理继续划分，这样做下去，直到每一个组都不能再划分了，那这一组中的状态应该是等价的，因为不等价的都又继续分了，剩下的没法分了。这样的话我们就把这一组看成是一个状态、另一组看成是另一个状态。就达到了把等价状态合并了的目的。

如果原来的自动机就是最简自动机的话，那么用这种方法分完以后，分完的自动机跟原来是一样的。

example 1：

example 2：

{1235}{4678}

先从终止分，暂时不能分

再看1235

1都1组 2a 到缺省 b到2组，所以不等的

变成了{1 3}{2 5}前面不能分离的现在可能也可能分离了，因为原来在一组，现在分成两组了

再做，然后发现都不能分离了，就分离结束了

example 3:

5.设计词法分析器

5.1自动机与正则表达式的相互转换

5.1.1正则表达式向自动机转换

b+就把不能忽略的空边忽略了就行

例 ：有正规表达式(a|b)*aa,为之构造等价的NFA.

5.1.2自动机向正则表达式转换



例子

5.2例题

example 1:

example 2:

总结

参考资料：

吉林大学编译原理课程PPT（刘宇舟）