Fl0w3r

carpe diem

词法分析

Posted on In
4.1k 8 mins.

引言

编译原理旨在介绍编译程序构造的一般原理和基本方法。内容包括语言和文法、词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代码优化和目标代码生成，本节主要是对词法分析部分进行展开讲解。

词法分析程序功能

词法分析是对构成源程序的字符串从左到右进行扫描和分解，根据语言的词法规则识别出一个一个具有独立意义的单词

单词符号及输出形式

语言的单词符号是指语言中具有独立意义的最小语法单位。

字母表和字符串

字母表

字母表：元素的非空有穷集合。例如$\Sigma = {a,b,c}$，根据字母表的定义，$\Sigma$是字母表，它由$a、b、c$三个元素组成。

字母表（Alphabet）$\Sigma$是一个非空有穷集合，字母表中的元素也称为该字母表的一个字母（Letter），也叫字符（Charater）。

例如，以下是不同的字母表：

  • ${ a,b,c,d }$
  • ${ a,b,c,…,z }$
  • ${ 0,1 }$
  • ASCII字母表

注意：

  • 字母表中至少包含一个元素
  • 字母表中的元素，可以是字母、数字或其他符号

例如：$\Sigma = { 0,1,a,(,* }$是一个字母表，由$0$，$1$，$a$，$（$，$*$五个元素组成。

字符

字母表中的元素称为字符，例如前述例子中：$a、b、c$是字母表$\Sigma$中的字符；$0、1、a、(、*$是字母表$\Sigma$中的字符。

字符串

字符的有穷序列称为字符串。例如设有字母表$\Sigma = { a,b,c }$，则有串$a,b,ab,ba,cba,abc…$

字符串总是建立在某个特定字母表上的且只由字母表上的有穷多个字符组成。字符串中字符的顺序是很重要的，例如$ab$和$ba$是字母表$\Sigma$上的两个不同的字符串。

不包含任何字符的字符串，称为空字符串，用$\epsilon$表示。空字符串由0个字符组成，其长度$|\epsilon|=0$。

字符串运算

字符串的连结

设$x$和$y$是字符串，则串$xy$称为它们的连结。

例如设$X=ABC$，$Y=10A$，那么$XY=ABC10A$、$YX=10AABC$。对任意一个符号串$X$，有$\epsilon X = X \epsilon = X = ABC$

集合的连接

设$A$和$B$是符号串的集合，则$A$和$B$的连接定义为：$AB={ xy|x \in A,y \in B }$

集合的乘积是满足于$x \in A,y \in B$的所有符号串$xy$所构成的集合。

例如设$A={ c,d }$，$B={ 0,1}$，则：

$AB={c0,c1,d0,d1 }$，$BA ={ 0c,1c,0d,1d}$，$AA = { cc , cd , dc, dd}$，$BB={ 00,01,10,11}$，$BBA={ 00c,01c,10c,11c,00d,01d,10d,11d}$，$ABB={ c00,c01,c10,c11,d00,d01,d10,d11}$

其中$(AB)B=A(BB)$，可以发现集合的运算满足结合律不满足交换律。

对于集合$|A|=2,|B|=2$，则$|AB|=|BA|=|A| \times |B|=4$，$|ABB|=|AB| \times |B| = 8$

特别指出，$\epsilon$是字符串，不是集合，而${\epsilon}$表示由空字符串$\epsilon$所组成的集合。集合$\phi={}$是空集合。

字符串的幂运算

设$x$是字符串，则$x$的幂运算定义为：
$$
X^1=X=abc \\
X^2=XX=abcabc \\
X^3=XXX=abcabcabc \\
X^4=XXXX=abcabcabcabc \\
…… \\
X^n=XX…XXX=abcabc…abcabcabc
$$

集合的幂运算

设$A$是字符串的集合，则集合$A$的幂运算定义为：
$$
A^0={\epsilon} \\
A^1=A \\
A^2=AA \\
…… \\
A^n=AA…A=AA^{n-1}(n>0)
$$
举个例子，设$A={a,b}$，则：
$$
A^0={ \epsilon } \\
A^1={ a,b } \\
A^2={ aa,ab,ba,bb} \\
A^3={ aaa,aab,aba,abb,baa,bab,bba,bbb}
$$

集合的闭包

设$A$是字符串的集合，则$A$的闭包$A*$定义为：
$$
A*=A^0 \cup A^1 \cup A^2 … \cup A^n … \
={\epsilon } \cup A^1 \cup A^2 \cup … \cup A^n …
$$
例如设$A={a},B={b}$，试求：

  1. $A*={\epsilon,a,aa,…a^n…}(n>1)$
  2. $B*={\epsilon,b,bb,…b^n…}(n>1)$
  3. $(AB)*={\epsilon,ab,abab,…(ab)^n…}(n>1)$
  4. $(BA)*={\epsilon,ba,baba,…(ba)^n…}(n>1)$

正规式&正规集

正规表达式

引入正规表达式可以更好的表示单词的构成规则（形式化的规则），便于词法分析器的自动生成。程序设计语言的单词都能用正规式来定义。

正规式运算符

正规集是正规式表示的符号串的集合。设有字母表$\Sigma={a_1,a_2,…,a_n}$，在字母表$\Sigma$上的正规式和它所表示的正规集可用如下规则来定义：

  1. $\phi$是$\Sigma$上的正规式，它所表示的正规集是$\phi$，即空集${}$
  2. $\epsilon$是$\Sigma$上的正规式，它所表示的正规集仅含一空符号串，即${\epsilon}$
  3. $a_i$是$\Sigma$上的一个正规式，它所表示的正规集是由单个字符$a_i$所组成，即${a_i}$是正规集
  4. 如果$e_1$和$e_2$是$\Sigma$上的正规式，它们所表示的正规集分别为$L(e_1)$和$L(e_2)$，则：
    • $e_1|e_2$是$\Sigma$上的一个正规式，它所表示的正规集为$L(e_1|e_2)=L(e_1)\cup L(e_2)$
    • $e_1e_2$也是$\Sigma$上的一个正规式，它所表示的正规集为$L(e_1e_2)=L(e_1)L(e_2)$
    • $(e_1)^*$也是$\Sigma$上的一个正规式，它所表示的正规集为$L((e_1)^*)=(L(e_1))^*$

例如设有字母表$\Sigma={a,b}$，根据正规式与正规集的定义，写出字母表$\Sigma$上的6个正规式和它所表示的正规集。

  1. $a$和$b$是正规式，相应的正规集为$L(a)={a},L(b)={b}$

  2. $a|b$是正规式，相应的正规集为$L(a|b)=L(a) \cup L(b)={a,b}$

  3. $ab$是正规式，相应的正规集为$L(ab)=L(a)L(b)={a}{b}={ab}$

  4. $(a|b)^*$是正规式，相应的正规集为

    $L((a|b)^*)=(L(a|b))^*=(L(a) \cup L(b))^*=({a} \cup {b})^*={a,b}^*={\epsilon,a,aa,aaa,…}$

  5. $ba^*$是正规式，相应的正规集为

    $L(ba^*)=L(b)L(a^*)={b}(L(a))^*={b}{\epsilon,a,aa,aaa,…}={b,ba,baa,baaa,…}$

程序语言字母表是键盘字符集合，则程序语言部分单词符号可用正规式定义，试写出关键字、关系运算符以及算数运算符的正规式及正规式所对应的正规集。

关键字 ：

  • 正规式：$if|else|while|for…$
  • 正规集：${if,else,while,for,…}$

关系运算符：

  • 正规式：$<|<=|>|>=|&&||||!=|==$
  • 正规集：${<,<=,>,>=,&&,||,!=,==}$

算数运算符：

  • 正规式：$+|-|*|/|%$
  • 正规集：${+,-,*,/,%}$

正规式的性质

令$A$，$B$和$C$均为正规式，则：

  • $A|B=B|A$
  • $A|(B|C)=(A|B)|C$
  • $A(BC)=(AB)C$
  • $A(B|C)=AB|AC$
  • $(A|B)C=AC|BC$
  • $A\epsilon|\epsilon A=A$
  • $A^*=AA^*|\epsilon=A|A^*=(A|\epsilon)^*$
  • $(A^*)^*=A^*$

正规式等价

如果正规式$R_1$和$R_2$描述的正规集相同，则称正规式$R_1$与$R_2$等价，记为$R_1=R_2$。

复习回顾

字符串

  1. 由字母表中的字符组成的任何有穷序列称为字符串，例如$001110$是字母表$\Sigma={0,1}$是字符串
  2. 字母表$A={a,b,c}$上的一些字符串有：$ab,c,bc,aaca$
  3. 字符串是有序的，字符串$ab$就不同于$ba$
  4. 可以使用字母表示字符串，如$X=STR$表示“X是由字符$S、T$和$R$并按此顺序组成的字符串”

字符串的长度

如果某字符串$X$有$m$个字符，则称其长度为$m$，表示为$|X|=m$，如$001110$的长度是6

空字符串即不包含任何字符的符号串，用$\epsilon$表示，其长度为0即$|\epsilon|=0$

字符串的连接

设$X$和$Y$是字符串，它们的连接$XY$是把$Y$的字符串写在$X$的字符之后得到的字符串，特殊情况有：$\epsilon X=X \epsilon=X$

例如$X=ST,Y=abu$，则它们的连接$XY=STabu，YX=abuST$看出$|X|=2,|Y|=3,|XY|=5$

字符串集合的连接

  • 若集合$A$中所有元素都是某元素表$\Sigma$上的字符串，则称$A$为字母表$\Sigma$上的字符串集合
  • 两个字符串集合$A$和$B$的连接定义：$AB={XY|X \in A 且Y \in B}$，若$A={ab,cde}$，集合$B={0,1}$，则$AB={ab0,ab1,cde0,cde1}$，$BA={0ab,1ab,0cde,1cde}$

闭包

非空集合$\Sigma$上的一切字符串（包括空字符串$\epsilon$）组成的集合用$\Sigma*$表示，称为$\Sigma$的闭包。

Related Posts