《现代编译原理-C语言描述》（2）- 词法分析

虎书 编译原理
底层
发布日期:   2019-03-14

词法的(lex-i-cal): 与语言的单词或词汇有关。但有别于语言的文法和结构。 —-韦氏词典

第二章 词法分析

编译器前段执行分析，后端执行合成。
分析一般分为三种：

词法分析：将输入分解成一个个独立的词法符号，即单词符号‘tocken’，简称单词
语法分析：分析程序的短语结构
语义分析：推算程序的含义

2.1词法单词

典型的程序设计语言的一些单词有：ID，NUM，REAL，IF，COMMA，NOTEQ，LPAREN，RPAREN等。
非单词的例子是：

注释                    /* try again */
预处理命令              #include<stdio.h>
预处理命令              #define NUMS 5,6
宏                      NUMS
空格符，换行符和制表符

一些能力较弱而需要宏处理器的语言中，由预处理器处理源程序的字符流，生成新字符流，然后词法分析器读入新字符流。
如对于下面这段程序：

dobule match0(char *s) /*find 0*/
{if(!strcmp(s,"0.0",3))
     return 0;
}

词法分析器会返回：

FLOAT  ID(match0)  LPAREN  CHAR  STAR  ID(s)  RPAREN
LARACE  IF  LPAREN  BANG  ID(strcmp)  LPAREN  ID(s)
COMMA  STRING(0,0)  COMMA  NUM(3)  RPAREN  RPAREN
RETURN  REAL(0.0)  SEML RBRACE  EOF

任何合理的程序设计语言都可以实现特定的词法分析器，我们将用正则表达式的形式语言来指明词法单词，用确定的有限自动机来实现词法分析器，并用数学的方法将两者联系起来。

2.2正则表达式

语言是字符串组成的集合，字符串是符号的有限序列，符号本身来自有限字母表。

每个正则表达式代表一个字符串集合。

  • 符号(symbol)：对于语言字母表中的每个符号 $a$ ，正则表达式 $a$ 表示仅包含字符串 $a$ 的语言。
  • 可选（alternation）：对于给定的两个正则表达式 $M$ 和 $N$ ，可选操作符（|）形成一个新的正则表达式 $1$ 。如果一个字符串属于语言 $M$ 或 $N$ ，则它属于语言 $M|N$ 。因此$a，b$组成的语言包含 $a$ 和 $b$ 这两个字符串。
  • 联结（concatenation）：对于给定的两个正则表达式 $M$ 和 $N$ ，联结操作符（·）形成一个新的正则表达式 $M·N$。如果一个字符串是任意两个字符串 $\alpha$ 和 $\beta$ 的联结，且 $\alpha$ 属于语言 $M$ ， $\beta$ 属于语言 $N$ ，则该字符串属于$M·N$组成的语言，因此正则表达式$（a|b）·a$定义了包含两个字符串 $aa$ 和 $ab$ 的语言。
  • $\epsilon$ （epsilon）：正则表达式 $\epsilon$ 表示仅含一个空字符串的语言。因此正则表达式$(a·b)|\epsilon$表示语言$|” “,”ab”|$。
  • 重复（repetition）：对于给定的正则表达式 $M$ ，它的克林闭包（Kleene closure）是$M^$，如果一个字符串是有 $M$ 中的字符串经过（0～无数）次联结运算的结果，则该字符串属于$M^$。

运算优先级：克林闭包>联结运算>可选运算，缩写形式[abcd]表示(a|b|c|d)，[b-g]表示[bcdefg]， $M？$ 表示 $（M|\epsilon）$, $M^+$ 则表示 $（M·M^*）$ ,但是这些缩写并没有扩充正则表达式的描述能力。

我们通过正则表达式来描述词法单词，这样对于一段单词我们就可以判断它是何种类型的词法单词。

正则表达式 C语言
if {return IF;}
[a-z][a-z0-9]* {return ID;}
[0-9]+ {return NUM;}
([0-9]+”.”[0-9]*)｜([0-9]*[0-9]+) {return REAL;}
(“–”[a-z]*“\n”)｜(“ “｜”\n”｜”\t”)+ {/*注释*/}
. {error( );}

其中注释的识别后,并不会提交给语法分析器,而是忽略他们重新开始词法分析。这个语言的注释是以爽横线开始，只包含字母字符，并以换行符结束。

词法规范应该是完整的，它应当总是可以与输入中的某些子串相匹配，但是我们的规则存在二义性，比如if8，应该是标识符还是两个单词if和8，Lex和其他词法分析器对于二义性应用两条规则：

  • 最长匹配：取可以与正则表达式匹配的最长的那个字符串；
  • 规则优先：正则表达式的书写顺序有意义，第一个与之匹配的正则表达式决定了子串的单词类型。

2.3有限自动机

通过正则表达式我们可以指明词法单词，但是我们还需要一种使用计算机程序来实现的形式化方法，这里我们可以使用有限自动机。有限自动机有一个有限状态的集合和一些从一个状态通向另一个状态的边，每条边上标记有一个符号；其中一个状态是初态，某些状态是终态。
A3i4mQ.png
圆圈表示状态，双圆圈表示终态，初态是入边无来源的圆圈，标有多个字符的边是多条平行边的缩写。

在确定的有限自动机（DFA）中，不会有从同一状态出发的两条边标有相同的符号。DFA从初始状态出发，对于输出字符串的每个字符，自动机都将沿着一条确定的边到达另一个状态，这条边必须是标有输入字符的边。对n个字符的字符串进行了n次状态转换后，如果自动机达到了终态，自动机将接受该字符串其他情况如没有到达终态或找不到和输入字符匹配的边，自动机将拒绝（露伴自动机：达卡口度挖鲁）。由一个自动机识别的语言是该自动机接受的字符集合。

将上面所示的6个独立的自动机合并为一个可以作为词法分析器的自动机，注意要避免二义性原则，所以我们将IF和ID自动机合并，并优先将接受单词的类型标记为IF。
A3kE80.png
这个自动机可以用一个转换矩阵来表示。转换矩阵是一个二维数组，一个元素是向量的向量，数组的下标是状态编号和输入字符。其中有一个停滞状态（status 0），这个状态对于任何输入都返回到自身，用status0来表示不存在的边。

int edges[][256]={  /*...0 1 2 ... - ... e f g h i j ...*/
/*status 0*/     {0,0,...0,0,0 ... 0 ... 0,0,0,0,0,0 ...},
/*status 1*/     {0,0,...7,7,7 ... 9 ... 4,4,4,4,2,4 ...},
/*status 2*/     {0,0,...4,4,4 ... 0 ... 4,3,4,4,4,4 ...},
/*status 3*/     {0,0,...4,4,4 ... 0 ... 4,4,4,4,4,4 ...},
/*status 4*/     {0,0,...4,4,4 ... 0 ... 4,4,4,4,4,4 ...},
/*status 5*/     {0,0,...6,6,6 ... 0 ... 0,0,0,0,0,0 ...},
/*status 6*/     {0,0,...6,6,6 ... 0 ... 0,0,0,0,0,0 ...},
/*status 7*/     {0,0,...7,7,7 ... 0 ... 0,0,0,0,0,0 ...},
/*status 8*/     {0,0,...8,8,8 ... 0 ... 0,0,0,0,0,0 ...},
et cetera
}
另外还需要有一个终结（finality）数组，将状态编号映射到动作
如何识别最长匹配

使用两个变量Last-final(最近遇到的终态的编号)和Input-Position-at-Last-Final(最近遇到终态时的字符)来记住自动机最后一次处于终态时的时机，每次进入一个终态时，词法分析器都能更新这两个变量。当到达停滞Status 0 （无出口转换的非终结状态时）时，通过这两个变量来求最长匹配。
A3AO6f.png
上图展示了自动机求最大匹配的过程。

2.4非确定有限自动机

非确定有限自动机（NFA）是一种需要对从一个状态出发的多条标有相同符号的边进行选择的自动机，它也可能存在 $\epsilon$ 的边，这种边可以在不接受输入字符的情况下进行状态转化。

NFA必须进行猜测来决定走那一条边，同时必须进行正确的猜测。

下图是同样的两个NFA，他们能接受长度是2的倍数或长度是3
的倍数由a构成的字符串。
A3E1c6.png
A3EGnO.png

2.4.1将正则表达式转化为NFA

NFA可以很容易的将一个静态的，说明性的正则表达式，转化为一个可模拟的，准可执行的NFA。

一般而言，任何一个正则表达式都有一个具有头和尾的NFA。其中头为末端状态，尾是开始边。

NFA的几种形式：
A3VuqS.png

根据前面正则表达式ID，IF，NUM，error构造的NFA：
A3VJx0.png

2.4.2将NFA转化为DFA

显而易见的是大多数计算机并没有足够的硬件实现NFA，但是DFA的实现较容易。

我们形式化的定义 $\epsilon$ 闭包如下。令 $edge(s,c)$ 是从状态 $s$ 沿着标有 $c$ 的一条边可到达的所有NFA状态的集合.对于状态集合 $S$ , $closure(S)$ 是从 $S$ 的状态中出发,无需接受任何字符,即只通过 $\epsilon$ 边便可以达到的集合.这种经过 $\epsilon$ 边的概念可用数学方法表述,即 $closure(S)$ 是满足如下条件的最下集合 $T$ :

$T=S \cup (\bigcup\limits_{s \in T}edge(s,\epsilon))$
我们可以用迭代法来算出 $T$ :

$T \leftarrow S$

repeate $T’ \leftarrow T$

$$T \leftarrow T’ \cup (\bigcup\limits_{s \in T’}edge(s,\epsilon))$$

util $T=T’$

这个算法是正确的,因为 $T$ 只会不断扩大,所以最终的 $T$ 一定包含 $S$ ,如果第一次迭代之后有了 $T=T’$ ,则 $T$ 也一定包含 $\bigcup \limits_{s \in T’}edge(s,\epsilon)$ 。因为NFA中只有有限个不同的状态所以算法一定会中止。

现在当用前面的方法来模拟NFA时位于状态集合 $d={s_i,s_k,s_l}$ 中,从d中的状态出发,并输入一个符号c,将到达NFA的一个新的状态集合;我们称这个集合为 $DFAedge(d,c)$ :

$$DFAedge(d,c)=closure(\bigcup \limits_{s \in d}edge(s,
c))$$
利用DFAedge能够更形式化的写出NFA模拟算法，如果NFA的初态是$s_1$,输入字符为$c_1,\cdots,c_n$,则算法为:

$d \leftarrow closure({s_1})$

$for\ i \leftarrow\ 1 \ to \ k$

$$ \quad d \leftarrow DFAedge(d,c_i) $$

状态集合运算是代价很高的运算,对于每个源程序都进行这样的词法分析是不现实的.但是我们可以预先计算出所有的状态集合。可以由NFA构造一个DFA，使得NFA每一个状态集合都对应于DFA的一个状态。因为NFA个数有限，所以DFA也有限$(2^n)$

DFA的状态 $d_1$ 就是 $closure（s_1）$ ,这和NFA模拟算法一样，抽象而言，如果 $d_j=DFAedge(d_i,c)$ ,则存在一条从 $d_i$ 到 $d_j$ 的标记为c的边。令 $\sum$ 是字母表。

states[0] <-- {};  states[1] <-- closure([s1])
p <-- 1; j <-- 0
while j<=p
   foreach c ∈ ∑
               e <-- DFAedge(states[j],c)
            if e = states[i] for some i<=p
                then trans[j,c] <-- i
                else p <-- p+1
                    states[p] <-- e
                    trans[j,c] <-- p
 j <-- j+1

这个算法不访问DFA的不可到达状态，原则上DFA有$2^n$个状态，但实际上一般只能找到n个状态是从初态可到达的，这一点可以避免DFA解释器的转换表出现指数级膨胀。

只要states[d]中有任何一个状态是NFA的终态，状态d就是DFA的终态，我们还要标记终态所映射的单词，并且states[d]中还可能有多个状态是这个NFA的终态，我们使用正则表达式中最先出现的那个单词来标记，这样就完成了规则优先的实现方法。

构造DFA后只需保留转换数组即可用于词法分析。

但是通过这种方法构造出来的自动机并不是最理想的，我们可以删除自动机中重复的多个状态中，只保留一个有效的状态。

若$s_1$和$s_2$同为终态或同为非终态，且对于任意符号c，trans[s1,c]=trans[s2,c]，则显然它们两者等价。

2.5Lex：词法分析器的生成器

在输入语言需要大量运算的时候，通过手工的方式完成DFA的构造显然不显示，而且构造DFA是一种机械性的工作，我们可以使用词法分析器的生成器Lex来构造DFA。

Lex是第一个基于正则表达式的词法分析器的生成器。将还未经过 $\epsilon$ 转换检查的状态保存在一个队列或栈中，可以更加高效的计算 $\epsilon$ 闭包。正则表达式可以直接转换称DFA而不需经过NFA。DFA转换表可能是个非常大的稀疏表，实际会对表进行压缩。不通过转换表，直接jiangDFA转换为可执行代码（case），其速度可以和手工编写的词法分析器一样快，例如Flex（fast Lexical analyzer generator）。

Lex由词法规范生成一个C程序。对于要进行分析的程序设计语言中的每一种单词类型，该规范包含一个正则表达式和一个动作（将单词类型和其他信息传递给编译器的下一阶段）。

我们使用Lex对前面给出的6个正则表达式进行生成：

%{
/*C Declarations: */
#include "tockens.h"
#include "errormsg.h" /*definitions of ID,IF,NUM*/
union { int ival; string sval; double fval;} yylval;
int charPos=1;
#define ADJ (EM_tokPos=charPos, charPos+=yyleng)
%}
/*Lex Definitions:*/
digits [0-9]+
%%
/*Regular Expressions and Actions:*/
if                   {ADJ; return IF; }
[a-z][a-z0-9]*       {ADJ; yylval.sval=String(yytext);}
{digits}             {ADJ; yylval.sval=atoi(yytext);
                           retrun ID;}
({digits}"."[0-9]*)|([0-9]*"."{digits})     {ADJ;
                         yylval.fval=stof(yytext);
                         return REAL;}
("--"[a-z]*"\n")|(" "|"\n"|"\t")+      {ADJ;}
                      {ADJ; EM_error("illegal character!");}
开始状态

正则表达式是静态的和说明性的，自动机是动态的和命令式的。Lex有一种将状态和正则表达式混合到一起 的机制。你可以声明一组初态，每个正则表达式前面可以有一组对它而言是合法的初态作为其前缀，动作代码可以明显的改变初态。就相当于我们的有限自动机的边标记的是正则表达式而不是符号。

但是尽管与整个注释变大时相匹配的单个正则表达式，但是随着注释的越来越复杂，特别是在允许注释嵌套的情况下，正则表达式会变的更复杂，甚至不可能。

程序设计：词法分析

惊了，本章未对词法分析器应当如何初始化以及如何与编译器通信做出说明，你可以从Lex使用手册中学得你看看这说的是人话吗，您老也知道自己没讲啊。fine，开干。

总的来说就是用Lex为Tiger语言生成一个词法分析器tiger.lex，并且写文档说明自己是如何处理注释，字符串，错误处理，文件结束处理的，还有你自己构想实现的一些feature。

打开chap2目录，ls一下有这样几个文件：

driver.c
errormsg.c //报错信息模块，产生含文件名和行号的报错信息
errormsg.h //报错信息模块，产生含文件名和行号的报错信息
makefile  //编译所有文件
tiger.lex  //lex初始代码
tokens.h //词法单词常数以及yylval的定义
util.c
util.h

先来熟悉熟悉一下，如何检测，首先打开$Tiger/testcase然后复制程序test1.tig到目录chap2，然后输入：

$ make
$ ./lextest test1.tig

会输出：

test1.tig:1.1: illegal token
...
test1.tig:4.8: illegal token
       INT   88 1
test1.tig:4.10: illegal token
...
test1.tig:7.4: illegal token

我们还没有完成，所以全是报错信息。

然后我们再来看一下附录中对Tiger语言的描述。

在这里我使用Flex来生成tiger.lex，你可以通过

$ sudo apt-get update
$ sudo apt-get install flex

来获得Flex。或者通过源码编译安装westes/flex
work-step
这是Flex 的工作流程图，所以接下来我们要做的就是修改tiger.lex中的内容，使之能对tiger语言进行词法分析。make可以帮助我们省去繁琐的通过lex先处理.lex文件的方式。

这次的程序分析题比第一次友好很多啊,只需要修改一个文件tiger.lex就行了,内容也不难就是写几个正则表达式（两天前我是这样想的）。实际实施并不是这么简单啊。这是我第一次编辑的内容

%{
#include <string.h>
#include "util.h"
#include "tokens.h"
#include "errormsg.h"

int charPos=1;

int yywrap(void)
{
 charPos=1;
 return 1;
}


void adjust(void)
{
 EM_tokPos=charPos;
 charPos+=yyleng;
}

%}

digits  [0-9]+
d (0|1|2|3|4|5|6|7|8|9)

%%

  /* The Comment */
/*[a-z]**/     {adjust();}

  /* The Identidier */
if             {adjust(); return IF;}
for             {adjust(); return FOR;}
while          {adjust(); return WHILE;}
to             {adjust(); return TO;}
break          {adjust(); return BREAK;}
let            {adjust(); return LET;}
in             {adjust(); return IN;}
end            {adjust(); return END;}
function       {adjust(); return FUNCTION;}
var            {adjust(); return VAR;}
type           {adjust(); return TYPE;}
array          {adjust(); return ARRAY;}
then           {adjust(); return THEN;}
else           {adjust(); return ELSE;}
do             {adjust(); return DO;}
of             {adjust(); return OF;}
nil            {adjust(); return NIL;}

  /* The Signal*/
" "           {adjust(); continue;}
\n           {adjust(); EM_newline(); continue;}
","            {adjust(); return COMMA;}
":"           {adjust(); return COLON;}
";"           {adjust(); return SEMICOLON;}
"("           {adjust(); return LPAREN;}
")"           {adjust(); return RPAREN;}
"["           {adjust(); return LBRACK;}
"]"           {adjust(); return RBRACK;}
"{"           {adjust(); return LBRACE;}
"}"           {adjust(); return RBRACE;}
"+"           {adjust(); return PLUS;}
"-"           {adjust(); return MINUS;}
"*"           {adjust(); return TIMES;}
"·"             {adjust(); return DOT;}
"/"           {adjust(); return DIVIDE;}
"="               {adjust(); return EQ;}
"<"               {adjust(); return LT;}
">"               {adjust(); return GT;}
"<="           {adjust(); return LE;}
">="           {adjust(); return GE;}
"&"            {adjust(); return AND;}
"|"            {adjust(); return OR;}
":="           {adjust(); return ASSIGN;}
"<>"           {adjust(); return NEQ;}
[a-z][a-z0-9]* {adjust(); yylval.sval=String(yytext); return ID;}

  /*The String Literal*/
"[a-z0-9\n\t\^c\{d}{d}{d}\"\\\ff\]*"      {adjust(); yylval.sval=String(yytext); return STRING;}

  /*The Integer Literal*/
{digits}       {adjust(); yylval.ival=atoi(yytext); return INT;}

  /*The Illrgal Token*/
.           {adjust(); EM_error(EM_tokPos,"illegal token");}

测试：

$ make
$ ./lextest test1.tig

对test1.tig文件测试，输出:

    DIVIDE    1
     TIMES    2
        ID    4 an
     ARRAY    7
      TYPE   13
        ID   18 and
        ID   22 an
     ARRAY   25
        ID   31 variable
     TIMES   40
    DIVIDE   41
test1.tig:1.42: illegal token
       LET   44
test1.tig:2.4: illegal token
test1.tig:3.1: illegal token
      TYPE   50
        ID   56 arrtype
        EQ   64
     ARRAY   66
        OF   72
        ID   75 int
test1.tig:3.30: illegal token
test1.tig:4.1: illegal token
       VAR   81
        ID   85 arr1
     COLON   89
        ID   90 arrtype
    ASSIGN   98
        ID  101 arrtype
    LBRACK  109
       INT  110 10
    RBRACK  112
        OF  114
       INT  117 0
test1.tig:4.39: illegal token
        IN  120
test1.tig:5.3: illegal token
test1.tig:6.1: illegal token
        ID  125 arr1
test1.tig:6.6: illegal token
       END  131
test1.tig:7.4: illegal token

从输出中我们可以看到词法分析器并没有跳过注释，而且对于换行符无法识别，但是对于ID，和Tiger语言保留符，运算符识别正确。而且还有一个显而易见的问题是对String类型的处理不够完美，会将String两边的引号也收入字符串中。

首先增加跳过换行符的正则表达式

[\r\t]         {adjust(); continue;}

然后增加对大写字母的支持

[a-zA-Z][a-zA-Z0-9]* {adjust(); yylval.sval=String(yytext); return ID;}

针对字符串我们特别设定一种规则，当读入"号时自动开始字符串的处理过程，而注释也采用自己的独特规则，这里特别要注意的一点是，前面我们有提到过，为了保证语法不会有二义性，书写正则表达式时的顺序也有含义所以我们优先书写String类型的正则表达式。

对于String，当我们读入"首先初始化一个32个元素字符数组strbuf，然后开始STRING_STATE，如果在字符串中再次遇到"符，表示字符串结束，我们就返回字符串。通过append_char2str_buf函数创造新的两倍长度的数组。而对于注释我们是使词法分析器直接跳过，唯一比棘手的情况就是嵌套注释，所以我们定义一个commentNesting来记录注释嵌套的情况。

%{
#include <string.h>
#include "util.h"
#include "tokens.h"
#include "errormsg.h"

int charPos = 1;

int yywrap(void)
{
 charPos=1;
 return 1;
}

void adjust(void)
{
 EM_tokPos=charPos;
 charPos+=yyleng;
}

int commentNesting = 0;

/* String buffer. */
const int INITIAL_BUFFER_LENGTH = 32;
char *string_buffer;
unsigned int string_buffer_capacity;
unsigned int STRING_START = 0;

void init_string_buffer(void)
{
  string_buffer = checked_malloc(INITIAL_BUFFER_LENGTH);
  string_buffer[0] = 0;
  string_buffer_capacity = INITIAL_BUFFER_LENGTH;
}

void append_char_to_stringbuffer(char ch)
{
    size_t new_length = strlen(string_buffer) + 1;
    if (new_length == string_buffer_capacity)
    {
        char *temp;

        string_buffer_capacity *= 2;
        temp = checked_malloc(string_buffer_capacity);
        memcpy(temp, string_buffer, new_length);
        free(string_buffer);
        string_buffer = temp;
    }
    string_buffer[new_length - 1] = ch;
    string_buffer[new_length] = 0;
}

%}

%x COMMENT_STATE STRING_STATE

%%
  /* Skip white spaces. */
[ \r\t]     {adjust(); continue;}
\n     {adjust(); EM_newline(); continue;}


  /* Reserved words. */
while     {adjust(); return WHILE;}
for       {adjust(); return FOR;}
to        {adjust(); return TO;}
break     {adjust(); return BREAK;}
let       {adjust(); return LET;}
in        {adjust(); return IN;}
end       {adjust(); return END;}
function  {adjust(); return FUNCTION;}
var       {adjust(); return VAR;}
type      {adjust(); return TYPE;}
array     {adjust(); return ARRAY;}
if        {adjust(); return IF;}
then      {adjust(); return THEN;}
else      {adjust(); return ELSE;}
do        {adjust(); return DO;}
of        {adjust(); return OF;}
nil       {adjust(); return NIL;}

  /* Punctuation symbols. */
","   {adjust(); return COMMA;}
":"   {adjust(); return COLON;}
";"   {adjust(); return SEMICOLON;}
"("   {adjust(); return LPAREN;}
")"   {adjust(); return RPAREN;}
"["   {adjust(); return LBRACK;}
"]"   {adjust(); return RBRACK;}
"{"   {adjust(); return LBRACE;}
"}"   {adjust(); return RBRACE;}
"."   {adjust(); return DOT;}
"+"   {adjust(); return PLUS;}
"-"   {adjust(); return MINUS;}
"*"   {adjust(); return TIMES;}
"/"   {adjust(); return DIVIDE;}
"="   {adjust(); return EQ;}
"<>"  {adjust(); return NEQ;}
"<"   {adjust(); return LT;}
"<="  {adjust(); return LE;}
">"   {adjust(); return GT;}
">="  {adjust(); return GE;}
"&"   {adjust(); return AND;}
"|"   {adjust(); return OR;}
":="  {adjust(); return ASSIGN;}

  /* Identifiers. */
[a-z|A-Z]+[a-z|A-Z|0-9|_]*  {
  adjust();
  yylval.sval = yytext;
  return ID;
}

  /* Integer literals. */
[0-9]+     {
  adjust();
  yylval.ival=atoi(yytext);
  return INT;
}

  /* String literals. */
\"  {
    adjust();
    init_string_buffer();
    STRING_START = charPos - 1;
    BEGIN(STRING_STATE);
}

  /* Comments. */
"/*" {
     adjust();
     commentNesting += 1;
     BEGIN(COMMENT_STATE);
   }

"*/" {
     adjust();
     EM_error(EM_tokPos, "Comment not open!");
     yyterminate();
   }

.     {adjust(); EM_error(EM_tokPos,"illegal token");}

<STRING_STATE>{
    \" {
          adjust();
          // printf("%s\n",string_buffer);
          if(string_buffer[0]=='\0'){
            yylval.sval = "(null)";
          }else{
            yylval.sval = string_buffer;
          }

          EM_tokPos = STRING_START;

          BEGIN(INITIAL);

          return STRING;
       }

    \n {
         adjust();
         EM_error(EM_tokPos, "Unterminated string constant!");
         yyterminate();
       }

    \\n {adjust();append_char_to_stringbuffer('\n');}
    \\t {adjust();append_char_to_stringbuffer('\t');}
    \\r {adjust();append_char_to_stringbuffer('\r');}
    \\b {adjust();append_char_to_stringbuffer('\b');}
    \\f {adjust();append_char_to_stringbuffer('\f');}

    "\\\"" {adjust();append_char_to_stringbuffer('"');}
    "\\'" {adjust();append_char_to_stringbuffer('\'');}
    "\\/" {adjust();append_char_to_stringbuffer('/');}

    "\\\\" {adjust();append_char_to_stringbuffer('\\');}

    <<EOF>> {
              EM_error(EM_tokPos, "Encounter EOF.");
              yyterminate();
            }

    . {
      adjust();
      char *yptr = yytext;
      while (*yptr) {
        append_char_to_stringbuffer(*yptr++);
      }
    }
}


<COMMENT_STATE>{
    "/*" {
           adjust();
           commentNesting += 1;
           continue;
         }

    "*/" {
           adjust();
           commentNesting -= 1;
           if (commentNesting == 0) {
             BEGIN(INITIAL);
           }
         }

    <<EOF>> {
              EM_error(EM_tokPos, "Encounter EOF.");
              yyterminate();
            }

    \n  {
      adjust();
      EM_newline();
      continue;
    }

    . {
      adjust();
      }

}

对test1.tig测试得到输出：

       LET   44
      TYPE   50
        ID   56 arrtype
        EQ   64
     ARRAY   66
        OF   72
        ID   75 int
       VAR   81
        ID   85 arr1
     COLON   89
        ID   90 arrtype
    ASSIGN   98
        ID  101 arrtype
    LBRACK  109
       INT  110 10
    RBRACK  112
        OF  114
       INT  117 0
        IN  120
        ID  125 arr1
       END  131

习题

2.1

推荐阅读

1.Flex (Fast Lexical Analyzer Generator )

2.yihui-he/Modern-Compiler-Implementation-in-C

3.控制字符列表

文章作者: Jinzhengxu
文章链接: http://jinzhengxu.github.io/2019/03/14/xian-dai-bian-yi-yuan-li-c-yu-yan-miao-shu-2/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Jinzhengxu !
虎书 编译原理
赏
评论
 上一篇
Ubuntu18.04下通过Vultr服务搭建vps科学上网 Ubuntu18.04下通过Vultr服务搭建vps科学上网
购买vps服务器 通过ssh连接服务器 安装科学上网软件 连接vps科学上网 1.购买vps服务器Vultr（www.vultr.com )是一家云基础架构提供商，面向软件开发人员提供虚拟专用服务器（VPS），具有许多性价比很高的服务器
2019-03-14 软件工具
Linux CentOS 服务器 科学上网
下一篇 
Titanic: Machine Learning from Disaster Titanic: Machine Learning from Disaster
初识KaggleKaggle 是一个流行的数据科学竞赛平台。由 Goldbloom 和 Ben Hamner 创建于 2010 年。在这里可以打比赛。 Get startTitanic: Machine Learning from Disa
2019-03-03 机器学习
机器学习 Kaggle
  目录