编译原理——第3章

Chapter 3 词法分析与有穷自动机

3.1 词法分析程序的功能

词法分析程序用于将输入的字符转化为单词符号，之后与语法分析器进行互动，逐词输入到语法分析器中用于语法分析器进行语法分析。

3.2 单词符号即输出单词的形式

3.2.1 语言的单词符号

语言的单词符号指语言中具有独立意义的最小语法单位，即单词符号是程序语言的基本语法单位。程序语言的单词符号一般可以分为下面5种：

• 关键字：表示语义的词语，如if、while等
• 标识符：各种名字，如变量名、常量名等
• 常数：整数、小数、布尔型等
• 运算符：加减乘除
• 界符：分号、括号等

3.2.2 词法分析程序输出单词的形式

通常表示为二元式：（单词种别，单词自身的值）。单词种别指单词的种类，通常给一个单词对应一个整数码，目的是最大限度地把各个单词区别开。单词自身的值是编译中其他阶段需要的信息，如果一个种别只对应一个单词符号，那么这个单词的种类编码就能够完全代表其自身的值，如if关键字只需要一个种别码就可以知道读取到了if，而不需要额外指定值。如果一个种别对应多个单词符号，则需要给出单词自身的值。如定义整数的种类对应的编码为10，则词法分析程序遇到整数5时则会记录一个二元式：(10, 5)。

3.3 语言单词符号的两种定义方式

3.3.1 正规式和正规集

正规式实际上类似于多种编程语言中都在使用的正则表达式。其正式定义采用递归定义的形式：设有字母表$Σ={a1, a2,…, an}$ ，在字母表$Σ$上的正规式和它所表示的正规集用规则1-4定义：

• 1. $Φ$是$Σ$上的正规式，它所表示的正规集是$Φ$， 即空集$\{\}$。
• 2. $ε$是$Σ$上的正规式，正规集：空符号串集合，$\{ε\}$。
• 3. $a_i$是$Σ$上的一个正规式，它所表示的正规集是由单个符号$a_i$所组成，即$\{a_i\}$。
• 4. 如果$e_1$和$e_2$是$Σ$上的正规式，它们所表示的正规集为$L(e_1)$和$L(e_2)$ ，则有：
  • (1) $e_1|e_2$是$Σ$上的一个正规式，它所表示的正规集为：$L(e_1|e_2)=L(e_1)∪L(e_2)$
  • (2) $e_1e_2$是$Σ$上的一个正规式， 它所表示的正规集为：$L(e_1e_2)=L(e_1)L(e_2)$
  • (3) $(e_1)^*$是$Σ$上的一个正规式， 它所表示的正规集为：$L((e_1)^*)=(L(e_1))^*$

注意：虽然$(a|b)^*$是正规式，对应正规集为$\{a,b\}^*$，但对于$\{a,b\}^*$的任一子集不能认为是一个正规集。这句话说的很容易让人误解，它指的是不是所有的子集都是正规集。如$\{a^nb^n|n\ge 1\}$就不是一个正规集，因为它不能由正规文法进行表示。凡是不能使用正规文法表示的符号串集合都不能被称为正规集。

如果两个正规式描述的正规集相同，称这两个正规式等价，可以使用等号连接。

正规式的性质：令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ε | εA = A$
• $A^* = AA^* | ε = A | A^* = (A | ε )^*$
• $(A^* )^* = A^*$

3.3.2 正规文法与正规式

正规文法与正规式之间可以进行转换。

正规文法转换为正规式

固定方法：

• 将正规文法中的每一个非终结符表示成关于它的一个正规式方程，获得一个联立方程组。
• 按照求解规则：
  • 若$x=\alpha x|\beta$，则解为$x=\alpha^*\beta$
  • 若$x=x\alpha|\beta$，则解为$x=\beta\alpha^*$

正规式转换为正规文法

固定方法：

• 令$V_T=\Sigma$
• 对任意正规式$R$选择一个非终结符$Z$生成规则$Z\rightarrow R$，并令$S=Z$
• 若$a$和$b$都是正规式，对于形如$A\rightarrow ab$的规则转换为$A\rightarrow aB$和$B\rightarrow b$两个规则，其中新增非终结符$B$
• 在已经转换的文法中，将形如$A\rightarrow a^*b$的规则进一步转换为$A\rightarrow aA|b$
• 不断使用规则3和4进行转换直到每一条规则最多含有一个非终结符为止。

3.4 正规式和有穷自动机

有穷自动机是具有离散输入和离散输出系统的一种抽象数学模型。

3.4.1 确定有穷自动机（DFA）

确定有穷自动机$M$是一个五元组$M=(Q,\Sigma,f,S,Z)$，其中

• $Q$: 是有穷状态集合，每一个元素称为一个状态；
• $Σ$: 是有穷输入字母表，每个元素称为一个输入字符；
• $f$: 是一个从$Q×Σ$到$Q$的单值映射；$f(q_i,a)=q_j$表示当前状态为$q_i$，接受字符$a$之后转换到状态$q_j$。$q_j$称为$q_i$的一个后继状态。
• $S$: $S∈Q$ ，是唯一的一个初态；
• $Z$: $Z⊆Q$ ，是一个终态集。

一个DFA可以使用矩阵表示，行表示状态，列表示输入符号，矩阵元素表示$f(q,a)$的值。该矩阵称为状态转换矩阵或转换表。一个DFA也可以表示为一个状态转换图。对于$\Sigma^*$中的任何符号串$\beta$，如果存在一条从初态到终态的道路，且这条路上所有弧的标记连接称的符号串等于$\beta$，则称$\beta$被DFA $M$所接受。DFA所识别的符号串的全体记为$L(M)$，称为DFA $M$所识别的语言。

3.4.2 非确定有穷自动机（NFA）

NFA与DFA不同之处在$f$和$S$。
状态转移函数不是单值函数，而成为多值函数。
$S\subset Q$为非空初态集。即初态可能不止一个结点。

对于任意一个NFA $M$都存在一个DFA $M'$使得$L(M)=L(M')$，因此可以将NFA转化为DFA便于计算机编程编写词法分析程序。

3.4.3 由正规表达式R构造NFA

方法如下：

• 首先引进初始结点X和终止结点Y，将R表示为拓广转换图：
• 分析$R$的语法结构，使用如下规则对$R$中每一个基本符号构造NFA：
  • 若$R=\empty$，则构造：
  • 若$R=\varepsilon$，则构造：
  • 若$R=a(a\in\Sigma)$，则构造：
  • 若$R$为复合正规式，则按照下面的规则进行分裂和加入新结点，直到每一条边上只有一个符号或$ε$为止：
  • 整个分裂过程中，所有新结点均采用不同名字，保留X和Y为全图唯一初态结点和终态结点。

3.4.4 NFA确定化为DFA的方法

$\varepsilon$闭包（$\operatorname{\varepsilon-CLOSURE}(I)$）

设$I$是NFA $N$的一个状态子集，$\operatorname{\varepsilon-CLOSURE}(I)$定义如下：

• 若$s\in I$，则$s\in\operatorname{\varepsilon-CLOSURE}(I)$。
• 若$s\in I$，则从s出发经过任意条$\varepsilon$弧能够到达的任何状态$s'$。均属于$\operatorname{\varepsilon-CLOSURE}(I)$。

即$I$中所有元素出发经过$\varepsilon$道路能够到达的NFA中所有状态组成的集合。

NFA $N$转换为DFA $M$算法

• 置DFA $M$中的状态集$Q'$和$Z'$为空集。
• 给出$M$的初态$S'=\operatorname{\varepsilon-CLOSURE}(|S|)$，并将$S'$置为未标记状态后加入到$Q'$中（未标记状态表示新状态）
• 如果$Q'$中存在未标记状态$T=\{q_1,...,q_n\},q_i\in Q$，则进行如下变换求$f'(T,a)$的后继状态：
  • 对于每一个$a\in\Sigma$，置$J=f(\{q_1,...,q_n\},a)=f(q_1,a)\cup...\cup f(q_n,a),U=\operatorname{\varepsilon-CLOSURE}(J)$。如果$U$不在$Q'$中，将$U$置为无标记状态添加到$Q'$中，并将状态转移$f'(T,a)=U$添加到$M$中，如果$U$中至少含有1个元素是$N$的终态，则将$U$设置为$M$的终态添加到$Z'$中。
  • 对$T$置标记（表示$T$不再是新加入状态）
• 重复步骤3直到$Q'$中不再含有未标记的状态为止。
• 重新命名$Q'$中状态，获得等价DFA $M$。

说人话：就是根据闭包确定原NFA的结点集合应该如何划分（注意这些集合可能会有重叠），首先求起始点的闭包，然后看闭包中的元素接收某一个符号$a$之后能到哪些结点，对这些结点再求一个闭包构成DFA的另外一个结点，以此类推可以找到所有DFA的结点与NFA中结点的对应关系。

3.4.5 DFA的化简

DFA的化简的目标是找到一个状态数量更少的等价的DFA。化简后DFA中没有多余状态，状态集中没有两个状态是相互等价的。

有穷自动机的多余状态指无论如何也无法到达的状态。

等价状态指在有穷自动机中两个状态$s,t$对于任意的相同字符输入都能到达等价的状态。且$s,t$一定均为终态或均为非终态。即$\{Q,\Sigma,f,S_0,F\}$中$\forall\alpha\in\Sigma^*,f(s,\alpha)\in F\Leftrightarrow f(t,\alpha)\in F$

化简算法：

• 将DFA $M$的状态集$Q$分为两个子集：终态集$F$和非终态集$\lnot F$，形成原始分划$\Pi$。
• 对$\Pi$建立新分划$\Pi_{new}$，对$\Pi$的每个状态子集$G$进行如下变换：
  • 将$G$分划为新的子集，使得$G$的两个状态$s,t$属于同一子集，当且仅当对任何输入符号$a$，状态$s,t$转换到的状态都属于$\Pi$的同一个子集。
  • 用$G$分划出的所有新子集替换$G$，形成新的分划$\Pi_{new}$。
• 如果$\Pi_{new}=\Pi$，则执行下一步，否则令$\Pi=\Pi_{new}$重复上一步
• 分划结束后对分划中每一个子集选出一个状态为代表，删去其他所有等价状态，并将指向其他状态的箭头改为指向这个代表状态。算法结束。

说人话：首先把终态集和非终态集分开，然后一个集合一个集合验证，如果这个集合中所有状态对于一个相同的输入都能到达相同的集合，那么这个集合中所有元素都等价；如果不能，那么看哪些到达这个集合，哪些到达那个集合，按照到达的集合来对这个集合进行划分。重复上面的操作直到没有办法划分为止。最终每一个划分只留一个状态，调整一下箭头走向。算法结束。

3.4.6 有穷自动机到正规式的转换

也就是从正规式到有穷自动机转换的逆过程，是一个去结点合并表达式的过程。

3.5 正规文法与有穷自动机

3.5.1 右线性正规文法到有穷自动机的转换方法

对于右线性正规文法$G=(V_N,V_T,P,S)$，对应的有穷自动机$M=(Q,\Sigma,f,q_0,Z)$。注意右线性正规文法指右式中非终结符在最右边。

• 将$V_N$中每一个非终结符视为$M$中一个状态，并增加一个状态$D$使得$D\notin V_N$，令$Q=V_N\cup\{D\},Z=\{D\},\Sigma=V_T,q_0=S$。
• 对于$G$中每一个形如$A\rightarrow aB$的产生式$(A,B\in V_N,a\in V_T\cup\{\varepsilon\})$，令$f(A,a)=B$。
• 对于$G$中每一个形如$A\rightarrow a$的产生式$(A\in V_N,a\in V_T)$，令$f(A,a)=D$。
• 对于$G$中每一个形如$A\rightarrow\varepsilon$的产生式$(A\in V_N)$，令$A$为接受状态或$f(A,\varepsilon)=D$。

按照上述方法可以构造一个右线性正规文法的NFA，能够识别这个文法的语言。

说人话：将文法中所有非终结符看成一个状态，如果规则右部有非终结符，就从规则左部画箭头标右部的终结符指向右部的非终结符。如果规则右部没有非终结符，就从规则左部画箭头标右部的终结符指向终结状态，这个终结状态不在非终结符中，是另外创建的唯一一个状态。如果规则右部是空字符，可以让规则左部非终结符变成终态或指一个空字符的箭头到终态。

3.5.2 左线性正规文法到有穷自动机的转换方法

对于左线性正规文法$G=(V_N,V_T,P,S)$，对应的有穷自动机$M=(Q,\Sigma,f,q_0,Z)$。注意左线性正规文法指右式中非终结符在最左边。

• 将$V_N$中每一个非终结符视为$M$中一个状态，并增加一个初始状态$q_0$使得$q_0\notin V_N$，令$Q=V_N\cup\{q_0\},Z=\{S\},\Sigma=V_T$。
• 对于$G$中每一个形如$A\rightarrow Ba$的产生式$(A,B\in V_N,a\in V_T\cup\{\varepsilon\})$，令$f(B,a)=A$。
• 对于$G$中每一个形如$A\rightarrow a$的产生式$(A\in V_N,a\in V_T)$，令$f(q_0,a)=A$。

说人话：将文法中所有非终结符看成一个状态，文法开始符号是终态。如果规则右部有非终结符，就从规则右部非终结符画箭头标右部的终结符指向左部。如果规则右部没有非终结符，就从初始状态画箭头标右部的终结符指向规则左部，这个初始状态不在非终结符中，是另外创建的唯一一个状态。箭头指向和右线性文法到有穷自动机是反着来的。

3.5.3 有穷自动机到正规文法的转换方法

对于有穷自动机$M=(Q,\Sigma,f,q_0,Z)$，构造正规文法$G=(V_N,V_T,P,S)$的方式：

• $V_N=Q,V_T=\Sigma,S=q_0$。
• 若$f(A,a)=B$且$B\notin Z$时，将规则$A\rightarrow aB$加入到$P$中。
• 若$f(A,a)=B$且$B\in Z$时，将规则（$A\rightarrow aB|a$或$A\rightarrow aB$），$B\rightarrow\varepsilon$加入到$P$中。
• 若文法的开始符号$S$是一个终态，则将产生式$S\rightarrow\varepsilon$加入到$P$中。

上述只考虑了右线性正规文法，因为构造为右线性正规文法符合我们的习惯，容易理解不易出错。

说人话：右线性正规文法到有穷自动机反着来。

3.6 词法分析程序的编写方法

这部分与实验有关，极其重要！需要掌握Flex词法分析程序的原理。

关键字处理

将所有用户不得用作标识符的关键字定义为一类特殊的标识符来处理，并将它们事先安排在一个表格之中，称为关键字表。利用状态转换图识别一个标识符时需要查询关键字表中是否有这个标识符。

空白符

关键字、标识符与常数之间如果没有确定运算符作为界符分隔，则必须需要至少一个空白符作为填充。此时这里的空白符就有了意义。

所需函数与变量

• ch：字符变量保存当前读入的源程序字符
• token：字符数组，保存当前单词符号的字符串
• getch()：读一个字符，函数将缓冲区中读入源程序的下一个字符放在ch中，并更新读指针
• getbc()：读空白符，每一次调用检查ch中字符是否是空白符，如果是则反复调用getbc()直到遇到一个非空白字符为止。
• concat()：拼接函数，将当前读取的字符与token相连接。
• letter(ch)：检查ch中字符是否为字母
• digit(ch)：检查ch中字符是否为数字
• reserve()：返回当前保存的token的种别编码，标识符的种别码为10。该函数会查询关键字表。
• retract()：读字符指针回退一个字符
• return()：收集并携带必要信息返回调用程序，返回语法分析程序
• dtb()+进制转换函数：将token中的字符串转换为数字并返回

实验对接——flex文件（*.l）格式与示例

/*  预定义段  */  
%{  
	/* 在此添加头文件包含 */
%}  
/* 在此添加正规式，定义正规式 */
%%  
/*  规则段  */  
%%  
/*  用户子程序段，定义main函数等函数  */

示例：（编译原理实验lab-1，task-2）

%{
  //Add a head file here
%}
DIGIT [0-9]			// 使用DIGIT定义数字，避免下面重复书写
ID [a-z][a-z0-9]*	// 标识符
%%
{DIGIT}+                 {printf( "An integer: %s (%d)\n", yytext,atoi( yytext ) );}
{DIGIT}+"."{DIGIT}?      {printf( "A float: %s (%g)\n", yytext,atof( yytext ) );
}
if|then|begin|end|procedure|function {printf( "A keyword: %s\n", yytext );}
{ID} printf( "An identifier: %s\n", yytext );
"+"|"-"|"*"|"/"         printf( "An operator: %s\n", yytext );
"{"[^}\n]*"}" 	/* eat up one-line comments */
[ \t\n]+ 		/* eat up whitespace */
.       printf( "Unrecognized character: %s\n", yytext );
%%
int main( argc, argv )
int argc;
char **argv;
{
++argv, --argc; /* skip over program name */
if ( argc > 0 )
        yyin = fopen( argv[0], "r" );
else
        yyin = stdin;
        yylex();
}       

注意：

• 规则段中越靠上的规则优先级越大，如上面例子中一众关键字就放在ID的上面一行，是因为它们需要首先进行处理，能够决定整个程序的语法结构。
• 规则定义部分上方的正规式定义部分互相不存在优先级，也与定义的先后无关。但正规式的匹配采用贪心的策略，即尽量多地进行匹配，如果两个正规式的匹配长度相同，则选择定义靠前的那一个。

下面是更加全面的例子：（编译原理试验lab-1，task-4）

/* PL词法分析器 */
/* 功能：能够识别出PL支持的所有单词符号并给出种别值 */
/* 说明：在下面的begin和end之间添加代码，已经实现了标识符和整常量的识别，你需要完成剩下的部分，加油吧！ */
/* 提示：因为是顺序匹配，即从上至下依次匹配规则，所以需要合理安排顺序～ */
%{
#include <stdio.h>
%} /*** begin ****/
INTCON			[\-]?[1-9][0-9]*|0
IDENT			[A-Za-z][A-Za-z0-9]*
CHARCON			'([^\']|\n)*'
PLUS			\+
MINUS			-
TIMES			\*
DIVSYM			\/
EQL				=
NEQ				<>
LSS				<
LEQ				<=
GTR				>
GEQ				>=
OFSYM			of
ARRAYSYM		array
PROGRAMSYM		program
MODSYM			mod
ANDSYM			and
ORSYM			or
NOTSYM			not
LBRACK			\[
RBRACK			\]
LPAREN			\(
RPAREN			\)
COMMA			,
SEMICOLON		;
PERIOD			\.
BECOME			:=
COLON			:
BEGINSYM		begin
ENDSYM			end
IFSYM			if
THENSYM			then
ELSESYM			else
WHILESYM		while
DOSYM			do
CALLSYM			call
CONSTSYM		const
TYPESYM			type
VARSYM			var
PROCSYM			procedure
%%
{OFSYM}			{printf("%s: OFSYM\n", yytext);}
{ARRAYSYM}		{printf("%s: ARRAYSYM\n", yytext);}
{PROGRAMSYM}	{printf("%s: PROGRAMSYM\n", yytext);}
{MODSYM}		{printf("%s: MODSYM\n", yytext);}
{ANDSYM}		{printf("%s: ANDSYM\n", yytext);}
{ORSYM}			{printf("%s: ORSYM\n", yytext);}
{NOTSYM}		{printf("%s: NOTSYM\n", yytext);}
{BEGINSYM}		{printf("%s: BEGINSYM\n", yytext);}
{ENDSYM}		{printf("%s: ENDSYM\n", yytext);}
{IFSYM}			{printf("%s: IFSYM\n", yytext);}
{THENSYM}		{printf("%s: THENSYM\n", yytext);}
{ELSESYM}		{printf("%s: ELSESYM\n", yytext);}
{WHILESYM}		{printf("%s: WHILESYM\n", yytext);}
{DOSYM}			{printf("%s: DOSYM\n", yytext);}
{CALLSYM}		{printf("%s: CALLSYM\n", yytext);}
{CONSTSYM}		{printf("%s: CONSTSYM\n", yytext);}
{TYPESYM}		{printf("%s: TYPESYM\n", yytext);}
{VARSYM}		{printf("%s: VARSYM\n", yytext);}
{PROCSYM}		{printf("%s: PROCSYM\n", yytext);}

{INTCON}		{printf("%s: INTCON\n", yytext);}
{CHARCON}		{printf("%s: CHARCON\n", yytext);}
{IDENT}			{printf("%s: IDENT\n", yytext);}
{PLUS}			{printf("%s: PLUS\n", yytext);}
{MINUS}			{printf("%s: MINUS\n", yytext);}
{TIMES}			{printf("%s: TIMES\n", yytext);}
{DIVSYM}		{printf("%s: DIVSYM\n", yytext);}
{EQL}			{printf("%s: EQL\n", yytext);}
{NEQ}			{printf("%s: NEQ\n", yytext);}
{LSS}			{printf("%s: LSS\n", yytext);}
{LEQ}			{printf("%s: LEQ\n", yytext);}
{GTR}			{printf("%s: GTR\n", yytext);}
{GEQ}			{printf("%s: GEQ\n", yytext);}
{LBRACK}		{printf("%s: LBRACK\n", yytext);}
{RBRACK}		{printf("%s: RBRACK\n", yytext);}
{LPAREN}		{printf("%s: LPAREN\n", yytext);}
{RPAREN}		{printf("%s: RPAREN\n", yytext);}
{COMMA}			{printf("%s: COMMA\n", yytext);}
{SEMICOLON}		{printf("%s: SEMICOLON\n", yytext);}
{PERIOD}		{printf("%s: PERIOD\n", yytext);}
{BECOME}		{printf("%s: BECOME\n", yytext);}
{COLON}			{printf("%s: COLON\n", yytext);}
[ \n\t]+		{}
.				{printf("%s: ERROR\n", yytext);}
%% /*** end ***/
int yywrap() { return 1; }
int main(int argc, char **argv)
{
	if (argc > 1) {
		if (!(yyin = fopen(argv[1], "r"))) {
			perror(argv[1]);
			return 1;
		}
	}
	while (yylex());
	return 0;
}

在上面的例子中，如果识别到一个字符串while，从正规式的定义可以发现，这个字符串可以与两个正规式匹配，分别是代表标识符的CHARCON和代表while关键字的WHILESYM。此时flex分析器会根据这两个匹配结果再规则中逐一查找，首先找到的是WHILESYM，因此这个字符串被解释为关键字while而不是标识符while。

实验对接——bison文件（*.y）格式与示例

%{  
Prologue 定义段  
%}  
Bison declarations Bison声明区  
%%  
Grammar rules 规则段  
%%  
Epilogue 用户子程序段

示例：（编译原理试验lab-1，task-5）

 %{
  #include <ctype.h>
  #include <stdio.h>
  #include <math.h>
  int yylex (void);
  void yyerror (char const *);
%}

%token NUM
%define api.value.type {double}
%left '+' '-'
%left '*' '/'
%right 'n'
%right '^'

%% 
/* Grammar rules and actions follow.  */
input:
  %empty
| input line
;

line:
  '\n'
| exp '\n'      { printf ("%.10g\n", $1); }
;

exp:
  NUM          {$$ = $1;}
  |exp exp '+' {$$=$1+$2;}
  |exp exp '-' {$$=$1-$2;}
  |exp exp '*' {$$=$1*$2;}
  |exp exp '/' {$$=$1/$2;}
  |exp exp '^' {$$=pow($1, $2);}
  |exp 'n'     {$$=-$1;}
;

%%

/* The lexical analyzer returns a double floating point
   number on the stack and the token NUM, or the numeric code
   of the character read if not a number.  It skips all blanks
   and tabs, and returns 0 for end-of-input.  */

int yylex (void)
{
  int c;
  /* Skip white space.  */
  while ((c = getchar ()) == ' ' || c == '\t')
    continue;

  /* Process numbers.  */
  if (c == '.' || isdigit (c))
    {
      ungetc (c, stdin);
      scanf ("%lf", &yylval);
      return NUM;
    }

  /* Return end-of-input.  */
  if (c == EOF)
    return 0;
  if (c == '!')
  	return 0;
  /* Return a single char.  */
  return c;
}

int main (int argc, char** argv)
{
   yyparse();
   return 0;
}


/* Called by yyparse on error.  */
void yyerror (char const *s)
{
  fprintf (stderr, "%s\n", s);
}

各个段的用途：

• 定义段：包含C和C++头文件、全局文件、全局变量、类型定义、词法分析器yylex和错误打印函数声明。
• 声明区：定义之后需要用到的终结符、非终结符和操作符优先级，以%开头表示类型属性：
  • %token NUM /*定义终结符NUM*/
  • %nonassoc ‘<’ /*表示该终结符无结合性,不能出现a<b<c*/
  • %left ‘+’ ‘-’ /*左结合,a+b+c=(a+b)+c*/
  • %left ‘*’ ‘/’ /*规则4在3下面，操作符比其上的优先级高*/
  • %right NEG /*NEG表示非*/
  • %right ‘^’ /*幂运算右结合;最下面，优先级最高*/
• 语法规则段：定义了文法的规则。如上面的实例所示，一条规则的格式如下：
  • 左式：左式名:
  • 右式：候选式1 {语义} | 候选式2 {语义} | ...;
  • 其中语义内$$表示这条规则对应的语义输出结果，$n（n为正整数）表示这条规则右式第几个符号的值。如上例中有一条规则是exp:exp exp + {$$=$1+$2}表示这条规则表示的语义是第一个符号和第二个符号（均为exp）的和。
• 用户代码段：定义前面定义段中声明的函数，或者也可以定义其他代码。

下面是更加全面的例子：（编译原理实验lab-1，task-7）

%{
/*
Filename:lab107.y
Author:
Date:
Makefile:
______________
scanner:lab107.l lab107.y
	bison -v -d lab107.y
	flex lab107.l
	gcc -o scanner 406.tab.c lex.yy.c -lm -lfl
.PHONY:clean
clean:
	rm scanner lab107.tab.c lex.yy.c lab107.tab.h
_______________
Description:

*/
// Notice: '-' using as -5+2=-3 ;or 5-2, need something special. By LM. 2021 using 
// with %precedence NEG used as the highest token, higher than '^', then we can get -2^2=4; without %prec NEG in the rule, SUB is lower than ^, then -2^2=-4
#include <stdio.h>
#include <math.h>
extern int yylineno;
int yylex();
void yyerror(const char *s);
%}

%define api.value.type {double}
%token NUM
%token EOL
%token ADD 
%token SUB 
%token MUL 
%token DIV
%token EXPO
%token LP
%token RP

%%
calclist:
	%empty
	|calclist exp EOL {printf("=%.10g\n",$2);}
	
exp:term {$$=$1;}
   	|exp ADD term {$$=$1+$3;}
	|exp SUB term {$$=$1-$3;}
	|error {}
	;

term:term2 {$$=$1;}
	|term MUL term2 {$$=$1*$3;}
	|term DIV term2 {$$=$1/$3;}
	;

term2: term3 {$$=$1;}
	|term3 EXPO term2 {$$=pow($1, $3);}

term3: NUM {$$=$1;}
	|SUB term3 {$$=-1*$2;}
%%

int main(int args,char **argv){
	yyparse();
	return 0;
}
void yyerror(char const *s){
	fprintf(stderr,"MyError:%s yylineno:%d\n",s,yylineno);	
}

注意上面例子中yyerror函数内的yylineno指当前所在行数。

题型总结

1. 正规文法与正规式的相互转化

例-1：（课本课后习题3-5）给出下列文法对应的正规式：
$S\rightarrow aA$
$A\rightarrow bA|aB|b$
$B\rightarrow aA$

解：
正规文法到正规式的转换，最为便捷的方法就是：先代换再套公式。
将上述文法中第二条规则的$B$带换掉：
$A\rightarrow bA|aaA|b$，即$A\rightarrow (b|aa)A|b$，代入公式可得$A=(b|aa)^*b$。
那么易得$S=a(b|aa)^*b$

例-2：将例-1中求出的正规式转化为正规文法。
解：在这里第一步，我们既可以将$a(b|aa)^*$看做整体处理，也可以将
$(b|aa)^*b$看做整体处理。

如果处理$a(b|aa)^*$，那么将上面的正规式分解为两条规则：
$S\rightarrow Ab$
$A\rightarrow a(b|aa)^*$
然后改写第二条规则：
$A\rightarrow Ab|Aaa|a$
由此可得第一种答案：
$S\rightarrow Ab$
$A\rightarrow Ab|Aaa|a$
所求的即为左线性正规文法。

一个正规式可以用多个等价的正规文法进行表示，正规文法之间只有是否简约的区别，表达的含义相同。

如果处理$(b|aa)^*b$，那么将上面的正规式分解为两条规则：
$S\rightarrow aA$
$A\rightarrow bA|aaA|b$
所求的即为右线性正规文法。

技巧：左/右线性正规文法对$ab^*$和$a^*b$的处理

对于左线性正规文法而言

• 处理$ab^*$：$A\rightarrow Ab|a$。
• 处理$a^*b$：必须使用两条语句：$A\rightarrow Bb,B\rightarrow Ba|\varepsilon$

对于右线性正规文法而言

• 处理$ab^*$：必须使用两条语句：$A\rightarrow aB,B\rightarrow bB|\varepsilon$
• 处理$a^*b$：$A\rightarrow aA|b$。

由此可见，要想让最终获得的文法的规则数量尽可能少，对于左线性正规文法要避免产生$a^*b$这样的右式，对于右线性正规文法要避免产生$ab^*$这样的右式。

2. 正规式与NFA的相互转化

由于NFA形式自由，所以正规式与NFA的相互转化比较易于理解和操作，将正规式转化为NFA只需要无脑怼箭头加状态即可，将NFA转化为正规式只需要无脑删状态组表达式即可。只此3条规则就是记不住也可以很容易推导出来。

例-3：将例-1中求出的正规式转化为NFA。
解：首先定义初态为$S$，终态为$T$。
然后添加路径并拓广：

最后一张图即为求得的NFA。

例-4：将例-3中求得的NFA还原回正规式。
上面的过程逆着来就行，可以尝试一下不同的顺序合并。

3. NFA转化为DFA

这部分涉及对$\varepsilon$-闭包的理解，需要记住其中的操作原理与步骤，画表能够让我们的思路更加清晰。

例-5：将例-3中求得的NFA转化为DFA。

画表构造DFA的状态：

DFA状态名	对应NFA状态集	输入a转到状态集闭包	输入b转到状态集闭包
$S$	$\{S\}$	$\{A,B,C\}$	不存在
$A$	$\{A,B,C\}$	$\{D\}$	$\{B,C\}$
$B$	$\{D\}$	$\{B,C\}$	不存在
$C$	$\{B,C\}$	$\{D\}$	$\{B,C,T\}$
$D$	$\{B,C,T\}$	$\{D\}$	$\{B,C,T\}$

注意这里画表的流程：画完一行之后如果发现后面两行生成的状态集闭包还有没有被DFA收为状态集的，在DFA中定义新的状态，对应NFA状态集就是这个状态集。在第一行画完后发现输入a转到状态集闭包$\{A,B,C\}$在DFA当前定义的状态中不存在，于是新增一个DFA状态对应NFA状态集$\{A,B,C\}$。第二行画完后发现多了$\{D\}$和$\{B,C\}$这两个状态集，于是下面定义的两行就是这两个状态集。以此类推。最终包含NFA终态的所有DFA状态都是DFA的终态。

接下来画出该NFA等价的DFA：

4. DFA化简

DFA化简实际上就是一个不断划分子集的过程。

例-6：将例-5中求得的DFA化简为最简DFA。

分析：化简DFA的第一步就是将终态和非终态划分为两个集合，在上图中就应该是$\{S,A,B,C\}$和$\{D\}$这两个子集。对于终态集$\{D\}$，由于其只有一个状态不能在接着划分，因此无需对其进行处理。下面我们来看一下对非终态集的划分过程。

首先看非终态集4个状态接受符号$a$后会转入哪里：
$S\stackrel{a}\rightarrow A$
$A\stackrel{a}\rightarrow B$
$B\stackrel{a}\rightarrow C$
$C\stackrel{a}\rightarrow B$
转入集合$\{A,B,C\}\subset\{S,A,B,C\}$。记作$\{S,A,B,C\}a=\{A,B,C\}$
然后看接受符号$b$后会转入哪里：
$A\stackrel{b}\rightarrow C$
$C\stackrel{a}\rightarrow D$
记作$\{S,A,B,C\}b=\{C,D\}$
可以看到其中$D$状态并不在$\{S,A,B,C\}$中，因此需要对非终态集进行划分。按照符号$b$的转入状态可以将$A$和$C$归为不同集合。既然$A$和$C$已经确定分属不同集合，那么再回过头看一下接收符号$a$时的情况，$S\stackrel{a}\rightarrow A$，$B\stackrel{a}\rightarrow C$，因此$S$和$B$属于不同集合。有时在DFA中，某些状态可能不能接受一些符号的输入，如本题中状态$B$不能接收输入$b$，虽然$\{B,C\}a=\{B,C\}$，但不能将$B$和$C$划为一个集合，因为不允许状态$A$接受字符$a$之后接受$b$。在本题中，已经确定$A$和$C$不在一个集合，$S$和$B$不在一个集合，而且$S$和$B$都不能接受$b$输入，因此$S$和$B$也一定不能和$A$、$C$中任何一个属于同一个集合。所以本题的DFA无法化简，已经是最简形式。

注意状态等价的定义：一个集合中任意两个状态等价当且仅当对于任意输入，任意两个状态到达的下一个状态都相等。一个不接受某个符号输入的状态和一个接受该符号输入的状态一定不在一个状态集中！

5. 正规文法和有穷自动机的相互转换

前面已经通过例题介绍了正规文法到正规式、正规式到有穷自动机的转换，如果不嫌麻烦可以用两次转换实现本问题。但更好的方法是直接进行转换。

例-7：将例-1中的正规文法转换为NFA。
$S\rightarrow aA$
$A\rightarrow bA|aB|b$
$B\rightarrow aA$
分析：这是一个右线性正规文法，在画图的之后要注意箭头指向哪里，不要指反了。首先还是定义状态。第一步需要明确开始符号$S$应该是初态还是终态。如果存在规则$S\rightarrow aA$，那么$S$应该作为初态，因为它必须接受一个符号$a$才能转到状态$A$，有状态转换$S\stackrel{a}\rightarrow A$。如果存在规则$S\rightarrow Aa$，那么$S$应该作为终态，因为一个句子必须以$a$结尾才能结束，有状态转换$A\stackrel{a}\rightarrow S$。由此可以推断出本题的$S$应该作为初态。另外定义状态$A$和$B$以及一个终态$T$。

凡是$A\rightarrow aB$一律添加$A\stackrel{a}\rightarrow B$，凡是$A\rightarrow Ba$一律添加$B\stackrel{a}\rightarrow A$。可以画出下面的NFA：

与例-3中画出的NFA等价。

例-8：将例-7中求出的NFA转换为正规文法。
分析：遍历NFA中所有的路径，添加规则。

由$S\stackrel{a}\rightarrow A$可添加规则$S\rightarrow aA$
由$A\stackrel{a}\rightarrow B$可添加规则$A\rightarrow aB$
由$A\stackrel{b}\rightarrow A$可添加规则$A\rightarrow bA$
由$B\stackrel{a}\rightarrow A$可添加规则$B\rightarrow aA$
由$A\stackrel{b}\rightarrow T$可添加规则$A\rightarrow b$

求得正规文法：
$S\rightarrow aA$
$A\rightarrow bA|aB|b$
$B\rightarrow aA$

6. 实验对接

在考试中，很可能会结合实验的内容进行设计，如标识符识别、关键字识别等实用的例子。

例-9（综合例题）：在编译原理实验1中，我们完成了对一门小语言的词法分析程序，有关其中对于数字（含正负数、浮点数）的识别，回答下列问题：
（1）设初态为$S$，终态为$T_i,T_f$，分别表示识别到整数和浮点数，错误状态为$E$，所有数字（0-9）统一使用符号$d$表示，小数点以符号".“表示，加号以”+“表示，减号以”-"表示，即整个文法的终结符集合为$\{d,.,+,-\}$。画出能够识别所有数字（正数（如+21、42）、负数（如-12）、浮点数（如0.5、-12.43、000.12000、23.））的NFA。注：只要出现小数点就识别为浮点数。小数点右边允许没有数字但左边不允许没有数字。

解：要做本题，首先要搞清楚字符出现的顺序与规律。这里面正负号或者不出现，或者出现在第一位，小数点最多只会出现1次，且只要出现小数点，就必然要识别为浮点数，否则识别为整数。

整数的格式：正负号（可选）+若干位数字
浮点数的格式：正负号（可选）+若干位数字+小数点+若干位数字（可选）

注意到两种识别前面有相同的一部分，所以可以合并前面的识别部分。

将识别正负号作为一个状态，识别整数部分作为一个状态，识别小数点作为一个状态，识别小数部分作为一个状态，画出如下NFA：

注意这里的画图技巧：当识别到一个状态发现前面的句子已经能够识别出来，就将这个状态设置为终态。这样可以减少一些状态的设置。另外，最好让任何一个状态接收任何一个输入都有意义，如这里的终态$E$表示错误状态，不加下面的箭头看上去可以，但实际上这就让识别过程终止了。如果识别如12345.+12355这样的错误字符串，小数点后遇到加号会立即报错，如果不加下面的箭头就会从12355开始新一轮识别，最终识别出来一个数字12355，这显然是错误的，应该让错误状态接收完所有非空字符之后再结束。

（2）你第1题画出来的NFA是否是DFA？若是，说明理由并化简DFA，若不是，将其转换为DFA并化简。画出最简DFA。化简之后想一想使用最简DFA去识别数字是否合适？为什么？

分析：图中并没有一个状态对于一个输入有多个输出的情况，因此这是一个DFA。下面来判断一下这个DFA是否可以化简。

首先划分终态集$\{E,T_i,T_f\}$和非终态集$\{S,A\}$。注意到终态集中状态的所有输入对应的下一个状态都属于终态集，因此终态集整个集合中3个状态等价。对于非终态集而言，状态$S$输入正负号转到状态$A$，状态$A$输入正负号却转到终态，因此这两个状态并不等价，需要拆分，因此最后划分的状态集为$\{\{S\},\{A\},\{E,T_i,T_f\}\}$。最简DFA：

这个最简DFA识别数字并不实用，因为它将所有数字以及错误情况全部识别为一个终态，这样无法将整数、浮点数与错误这三种情况区分开，因此在实际应用中还是应该使用第1题中求出的DFA。

（3）根据前面两题的结果，补全下面的bison代码，用于识别上面的数字。（方括号内为答案，后接题目序号）

%{
#include <stdio.h>
#include <math.h>
extern int yylineno;
int yylex();
void yyerror(const char *s);
%}

%token num		// 0-9这10个数字字符
%token plus		// 加号
%token minus	// 减号
%token dot		// 小数点

%%

unsigned_integer: num	{$$ = $2.value;}	// .value属性为字符对应的数值
	| unsigned_integer num	{[$$ = $1 * 10 + $2;]<1>}

number: [plus number]<2> 	{$$=$2;}
	| [minus number]<3> 	{$$=-$2;}
	| unsigned_integer dot unsigned_integer		{$$=$1 + $3 * 1.0 / pow(10, $3.length);}		// $2.length表示[小数位的总位数]<4>
%%
......