Bonky
Neither believe nor reject anything, because any other person has rejected or believed it. Heaven has given you a mind for judging truth and error, Use it.
By Thomas Jefferson

编译原理 – 词法分析

词法分析程序

词法分析程序的作用是逐个读入源程序字符并按照构词规则切分成一系列单词(Token)。

词法分析程序的任务

  • 读源程序,产生用二元组表示的单词符号
    (单词种类,单词自身的值)。
    单词种类是语法 分析需要的信息,单词自身的值是语义分析和代码 生成阶段需要的信息。
    对某些单词来说,不仅仅需要它的值, 还需要其它信息以方便代码生成。
    如标识符还需要记载它的层次,类别(整形、实形、布尔等),这些属性都收集到一个符号表中。二元组无法描述这多信息,一般将词法分析输出的单词二元表示设计成(标识符,指向该标示符所在符号表中位置指针)。
  • 滤掉空格,跳过注释、换行符
  • 记录源程序的行号,以便出错处理程序准确
    定位源程序的错误
  • 宏展开等……

Lex可以根据一个你的词法规则,生成一个C语言写的的词法分析器。YACC可以生成一个语法分析器。

单词描述工具

⽤正规⽂法或者正则表达式描述单词符号的词法构成

正规文法

正规⽂法G= (VN,VT,P,S),其中P中的产⽣式的形式为A→aB或者A→a,其中AB是⾮终结符号。

正规表达式

  1. \epsilon和中都是字母表上的正规式,对应正规集为{\epsilon}\varnothing
  2. 任何a\in \sum, a\sum上的一个正规式,表示的正规集分别为{a}
  3. 假设e_1e_2,都是\sum上的正规式,表示的正规集分别为L(e_1)L(e_2),则(e_1), e_1|e_2, e_1\cdot e_2, e_1^*,”都是\sum上的正规式,它们表示的正规集分别为L(e_1)L(e_1)\cup L(e_2) , L(e_1)L(e_2), (L(e_2)

正规表达式于正则文法的转换

正则表达式转换为正规文法

  • 选定⼀个⾮终结符S定为识别符号,⽣成规则 S→r;
  • 对于xy是正则式,定义⼀个规则A→xy,然后改写成:A→xB, B→y
  • 对于xy正则式,定义⼀个规则A→xy,然后改写成:A→xB|y, B→xB|y
  • 对于x|y正则式,定义⼀个规则A→x|y

例⼦: r=a(a|d)*对应的正规⽂法
S→aA A→(a|d)* A→(a|d)B|\epsilon
B→(a|d)B|\epsilon A→aB|dB|\epsilon B→aB|dB|\epsilon

正规文法转换为正则表达式

  • S=r;
  • 对于A→xB, B→y规则,定义⼀个正则式A=xy,
  • 对于A→xA|y规则,定义A=x*y正则式
  • 对于规则A→x|y,定义A=x|y正则式

有穷自动机

有穷⾃动机分为两类:确定的有穷⾃动机(Deterministic Finite Automata, DFA)和不确定的有穷⾃动机(Nondeterministic Finite Automata, NFA)

DFA

M = ( S,Σ ,δ,s_0,F )

  • S:有穷状态集。
  • Σ:输入字母表,即输入符号集合。假设ε不是Σ中的元素。
  • δ:将S×Σ映射到S的转换函数。 δ(s,a)表示 从状态s出发,沿着标记为a的边所能到达的状态
  • s_0:开始状态 (或初始状态)。
  • F:接收状态(或终止状态)集合。

    理解:根据输入状态,下一个状态是固定的

NFA

定义与DFA类似,除了δ为将S×Σ映射到2^S的转换函数。δ(s,a)表示从状态s出发,沿着标记为a的边所能到达的状态集合

理解:对于状态0,输入的是a,下一个状态可以是0或者1,输入是b,下一个状态只能是0

带有ε的NFA

正则表达式到NFA


NFA到DFA

如图,这是起始的NFA。

这是对应的DFA。

可以看到在1的时候,a只能去5,b只能去6而c可以去2和6。这个时候{2,6}就是一个新的state。然后就这个一个个的推,直到所有的case都考虑过,就会得到一个DFA。

DFA的化简

有穷⾃动机的化简是说它没有多余状态(死状态),并且它的状态中没有两个是互相等价的(不可区别)。通过消除多余状态和合并等价状态⽽转换成⼀个最⼩的与之等价的有穷⾃动机。
步骤(按分割法)

  • I0 = 非状态元素构成的集合,I1 = 终态元素构成的集合
  • 经过多次划分后,要保证,任意一个Ik中的元素通过move(Ik,某个字符)的结果都同属于一个Iz,这时候划分完成。否则把状态不同的单独划分出去。
  • 重复上一步,直至没有新的I子集增加。
  • 从子集中任选一个代替整体,画出最简DFA。

具体的例子

分割成I0,I1

检验I0中元素的等价性,不等价就分割

检测I2中元素的等价性,不等价就分割

检测I3中元素的等价性,不等价就分割

检测I1中元素的等价性,不等价就分割

检测后发现,不可再分割,所以最终分割结果就是:I2 = {1,2}, I4 = {3}, I5 = {4}, I6 = {5},I7 = {6,7}

画得状态转换图如下

Share

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注