xdu

2023-06-06 13:39| 来源: 网络整理| 查看: 265

编译原理词法分析词法分析器功能识别出源程序中的各个单词符号,并将其转换为内部编码形式. 删除无用的空白符,回车符以及无用的非实质性字符. 删除注释进行语法检查工作方式词法分析器作为编译器独立执行任务词法分析器作为语法分析器的子程序执行任务词法分析器和语法分析器并行工作形式化描述语言

定义:有限字母表上$\Sigma$上有限长度的字符串的集合

常用名词

前缀:移走字符串尾部的任意个符号后余下的部分后缀:移走字符串头部的任意个符号后余下的部分子串:移走前缀和后缀的字符串余下的部分子序列:从字符串中的任意个位置删除任意个符号后余下的部分逆转:将字符串中的符号按相反次序写出的字符串连接:x和y是字符串,连接xy是将y的符号接在x的符号之后幂:一个字符串和自身的n-1次连接

运算

$L$和$M$都是一个字符串集合

合并:$$L\cup M={s\mid s\in L\vee s\in M}$$ 连接:$$LM={st\mid s\in L\wedge t\in M}$$ 幂:$$L^0={\epsilon},L^1=L,L^2=LL,L^n=L^{n-1}L$$ Kleene闭包:$$L^*=\overset{\infin}{\cup}L^i=L^0\cup L^1\cup \cdots\quad i\geq 0$$ 正闭包:$$L^+=\overset{\infin}{\cup}L^i=L^1\cup L^2\cup\cdots\quad i\geq 1$$ 正规式和正规集

常用名词:

1.L(r)表示由字母表r构成的语言 2.正规集表示用正规式描述的语言

定义字母表$\Sigma$上的正规式 $\epsilon,\emptyset$是$\Sigma$上的正规式,表示的正规集为${\epsilon},\emptyset$ $\forall a\in \Sigma$,$a$是$\Sigma$上的正规式,表示的正规集为${a}$ 假定$e_1,e_2$为$\Sigma$上的正规式,表示的正规集为$L(e_1),L(e_2)$则 $(e_1\mid e_2)$为正规式,表示的正规集为$L(e_1)\cup L(e_2)$ $(e_1\cdot e_2)$为正规式,表示的正规集为$L(e_1)L(e_2)$ $(e_1)^$为正规式,表示的正规集为$(L(e_1))^$ 有限使用以上三个步骤定义的表达式称为$\Sigma$上的正规式

运算顺序闭包运算优先级最高,左结合连接运算优先级第二,左结合或运算优先级最低,左结合

运算性质

常用运算性质:

$A|B = B|A$

$A|(B|C)=(A|B)|C$

$A(BC)=(AB)C$

$A(B|C)=AB|AC\qquad(A|B)C=AC|BC$

$\epsilon A=A\quad A\epsilon = A$

$A^=(A|\epsilon)^$

$A^{**}=A^*$

简化正规式正闭包:$r$为表示$L(r)$正规式,$r^+$为表示$(L(r))^+$的正规式且$$r^+=rr^*=r^r,r^=r^+\mid\epsilon$$ 可缺省:$r$为表示$L(r)$正规式,$r?$为表示$L(r)\cup{\epsilon}$的正规式字符组: 枚举方式:$$[abc]=a|b|c$$ 分段方式:$$[0-9]=[0123456789]$$ 非字符组:若$[r]$是一个正规式,则$[^r]$表示$\Sigma-L(r)$ 有限状态自动机状态转换图

由一组矢量线连接的有限个节点组成的有向图,每个节点均代表识别单词时语法分析器所处的状态

例如:从状态一输入x则读入x到状态2,输入y则读入y到状态3

graph LR D1((1)) D2((2)) D3((3)) D1-- x -->D2 D1-- y -->D3

例如:可以识别一定的字符串

graph LR D0((0)) D1((1)) D2((2)) D0-- 字母 -->D1 D1-- 字母或其他数字 -->D1 D1-- 其他字符 -->D2 非确定型有限状态自动机(NFA) 定义

NFA是一个五元组:$$M=(S,\Sigma,move,s_0,F)$$

$S$:一个有限的状态集合 $\Sigma$:一个输入符号的集合 $move$:$S\times\Sigma\rarr S$是一个状态转移函数,$move(s_i,ch)=s_j$表示$s_i$状态遇到输入字符$ch$转移到$s_j$状态 $s_0$为初始状态 $F$为终态集合,$F\subseteq S$

确定型有限自动机 DFA定义 DFA是NFA的一种任何状态没有$\epsilon$转换对任何状态$s_j$和任意输入符号$a$,最多只有一条标记着$a$的便离开$s_j$. 正规式到词法分析器由正规式构造等价的NFA(Thompson算法)

步骤:

对于$\epsilon$构造NFA如下

graph LR D0((s0)) D1((f)) D0-- ε --> D1

对于$\Sigma$中的每个符号$a$构造NFA

graph LR D0((s0)) D1((f)) D0-- a --> D1

如果$M(p)$和$M(q)$分别是正规式$p$和$q$的NFA则

对于正规式$p|q$构造合成NFA:$M(p|q)$结果如下:

graph LR D0((s0)) D1((Sp)) D2((Sq)) D3((Fp)) D4((Fq)) D5((f)) subgraph "M(q)" D1-->D3 end subgraph "M(p)" D2-->D4 end D0-- ε -->D1 D0-- ε -->D2 D3-- ε -->D5 D4-- ε -->D5

对于正规式$pq$构造合成NFA:$M(pq)$结果如下:

graph LR D0((s0)) D1((sf)) D2((f)) D3((sf)) subgraph "M(p)" D0-->D1 end subgraph "M(q)" D1-- ε -->D3 D3-->D2 end

对于正规式$p^*$构造如下

graph TD D0((s0)) D1((Sp)) D2((Fp)) D3((f)) subgraph "M(p)" D2-- ε -->D1 end D0-- ε -->D1 D2-- ε -->D3

对于括起来的正规式$(p)$用$M(p)$本身作为它的NFA

NFA到DFA

名词定义: 1.$\epsilon$_CLOSURE($I$): 如果$q\in I$,则$q\in \epsilon _CLOSURE(I)$ 如果$q\in I$,则$q'$为经过任意条$\epsilon$边可以到达的状态，这些状态都属于$\epsilon$_CLOSURE($I$） $I$是状态集的一个子集,$a\in \Sigma$,定义$I_a = \epsilon _CLOUSURE(J)$,其中J是从I中的任意一个状态节点出发经过一条$a$边和任意条$\epsilon$边能到达的状态的全体

NFA到DFA的确定化方法

构造一张表格,该表格有n列,n为字母表的个数,可以将每一列命名为$I_x$,x为字母表中的字母.

首先置第一行第一列为$\epsilon$_CLOSURE($X$),X为初态,该项为初态的闭包. 根据上述的定义依次在后面的每一行填入相应$I_x$ 检查填入的$I_x$,如果它没有在第一列出现过,将其填入到第一列的末尾空项中,如果出现过则略过这一项对未填入$I_x$的每一行重复该过程,直到表所有产生的$I_x$在第一列都出现过为止. 将表中的每一项赋予一个新的状态名根据新的状态转移表画DFA

例如: NFA如下:

graph LR D0((0)) D1((1)) D2((2)) D3((3)) D4((4)) D5((5)) D6((6)) D7((7)) D8((8)) D9((9)) D10((10)) D0-- ε -->D1 D0-- ε -->D7 D1-- ε -->D2 D1-- ε -->D4 D2-- a -->D3 D4-- b -->D5 D3-- ε -->D6 D5-- ε -->D6 D6-- ε -->D1 D6-- ε -->D7 D7-- a -->D8 D8-- b -->D9 D9-- b -->D10

由于字母表中有两个元素a,b所以状态转化矩阵共有三列,如下所示:

$I$ $I_a$ $I_b$ ${0,1,2,4,7}$ ${3,8,6,7,1,2,4}$ ${5,6,7,1,2,4}$ ${3,8,6,7,1,2,4}$ ${8,3,6,7,1,2,4}$ ${9,5,6,7,1,2,4}$ ${5,6,7,1,2,4}$ ${8,3,6,7,1,2,4}$ ${5,6,7,1,2,4}$ ${9,5,6,7,1,2,4}$ ${8,3,6,7,1,2,4}$ ${10,5,6,7,1,2,4}$ ${10,5,6,7,1,2,4}$ ${8,3,6,7,1,2,4}$ ${5,6,7,1,2,4}$

将其重命名可以得到如下矩阵其

S a b A B C B B D C B C D B E E B C

生成的DFA如下

graph LR D0((A)) D1((B)) D2((C)) D3((D)) D4((E)) D0-- a -->D1 D0-- b -->D2 D1-- a -->D1 D1-- a -->D3 D1-- b -->D3 D2-- b -->D2 D2-- a -->D1 D3-- b -->D4 D4-- a -->D1 D4-- b -->D2 状态转移表的化简

如果对于任意的输入x,p和q转移后的状态相同,认为p和q等价,可以将等价的状态合一.

语法分析上下文无关文法CFG CFG的定义

一个CFG为一个四元组G=(N,T,P,S) N为一个非空有限集合,元素为非终结符,非终结符定义了终结符串的集合 T为一个非空有限集合,元素为终结符,$T\cap N=\emptyset$ P为产生式的集合,产生式为$A\rarr a$,$A\in N,a\in(T\cup N)^*$,指出了终结符和非终结符组成串的形式 S为开始符号

语法分析的术语推导

利用产生式生成句子的过程,使用产生式$A\rarr \gamma$的右部代替文法符号序列$\alpha A\beta$中的A得到$\alpha\gamma\beta$的过程称为$\alpha A\beta$直接推导出$\alpha\gamma\beta$记作$\alpha A\beta\rArr\alpha\gamma\beta$

【本文地址】

公司简介

联系我们