词法分析总体概念
1、词法分析的任务

词法分析是编译的第一个阶段，其任务是：从左至右逐个字符地对源程序（用高级语言编写的）进行扫描，产生一个个单词符号，把字符串形式的源程序改造成为单词符号串形式的中间程序。

2、词法分析器（也叫扫描器）

执行词法分析的程序称为词法分析程序，也称为词法分析器或扫描器。

词法分析器的功能是输入源程序，输出单词符号。

3、词法分析的两种处理结构

（1）把词法分析程序作为主程序。即，把词法分析与语法分析明显分开，由词法分析程序将字符串形式的源程序改造成单词符号串形式的中间程序，以这个中间程序作为语法分析程序的输入。在这种处理结构中，词法分析和语法分析实际上是分别实现的。

（2）把词法分析程序作为语法分析程序调用的子程序。在进行语法分析时，每当语法分析程序需要一个单词时，便调用词法分析程序，词法分析程序每一次调用便从字符串源程序中识别出一个单词交给语法分析程序。在这种处理结构中，词法分析和语法分析实际上是交替进行的。

$\color{green}{词法分析程序，通常采用第2种处理结构→享用更有效的方法来处理单词}$
词法分析器的设计方法
2.1 单词符号

由语法分析程序的任务可以知道：单词符号是程序语言的基本语法单位具有确定的语法意义。

1、程序语言的单词符号通常可以分为以下5种：




保留字
标识符
常数
运算符
界符




也称为基本字，例如C语言中的if、else、while、do等，保留了语言所规定的含义，是编译程序识别各类语言语法成分的依据。几乎所有程序语言都限制用户使用保留字来作为标识符
用来标记常量、数组、类型、变量、过程或函数名等，通常由用户自己定义
包括各种类型的常数，如整型常数、实型常数、布尔型常数等
如“ + ”、“ - ”、“ * ”、“ / ”、“ > ” 等。
在语言中是作为语法上的分界符号使用的，如“ ， ”、“  ；  ”、“ ； ”、“  （ ”、“  ） ”等。


2、词法分析程序输出的单词符号，通常表示为：

（单词种别，单词自身的值）

一词一码的单词符号，二元式中不必写出值（用null代替即可）；一类一码的单词符号，二元式中要写出值。

（1）单词种别

单词种别表示单词的种类，它是语法分析所需要的信息。通常让每种单词对应一个整数码，这样可以最大限度地把各个单词区分开来。

（2）单词自身的值

单词自身的值，是编译中其它阶段所需要的信息。




若一个种别只含有一个单词符号
若一个种别含有多个单词符号




对于这个单词符号，其种别编码就完全代表了它自身的值
对于他的每个单词符号，除了给出种别编码之外，还应给出单词符号自身的值，以便把同一种类的不同单词区别开来








保留字
标识符
常数
运算符
界符




可将其全体视为一种，也可以一词一种
一般统一归为一种
可以统一归为一种，也可按整型、实型、布尔型等分为几种
可采用一符一种的分法，也可以统一归为一种
可采用一符一种的分法，也可以统一归为一种


采用一词一种比较方便






如果一词一类，那么种别编码就代表自身的值
标识符自身的值就是标识符自身的字符串
常数自身的值是常数本身的二进制数值




注：此外，我们也可以用指向某类表格中一个特定项目的指针来区分同类中的不同单词。

eg: 对于标识符，可以用它在符号表的入口指针作为它自身的值；

常数可以用它在常数表的入口指针作为它自身的值

2.2 状态转换图

举例：无符号数的状态转换图：



当到达一类单词符号的终止状态时即可给出相应的单词编码。由于某些终止状态是在读入一个其它不属于该单词的符号后，才得到相应的单词编码，这表明在识别单词的过程中多读入了一个符号，所以识别处单词后应将最后多读入的这个符号予以回退。




a. 对于不含回路的分支状态来说，可以让它对应一个 switch（）语句或者一组if-else语句：


b. 对于含回路的状态来说，可以让它对应一个 while语句。：



终态一般对应一个return（）语句。return 意味着从词法分析器返回到调用段，一般指返回到语法分析器。
一个简单的词法分析器
一个重要的事实是：大多数程序语言的单词符号都可以用状态转换图予以识别。
举例：

1、C语言子集的单词符号及内码表示：

（由于直接使用整数编码不利于记忆，故用一些特殊符号来表示种别编码）



备注：表格中的保留字，采用一词一码的方式处理→种别编码就完全代表了自身的值；

标识符、常数，采用的是一类一码→分别用指向符号表、常数表的一个特定项目的指针来区分同类中的单词；

运算符、界符，采用一词一码的方式处理。

2、在设计的状态转换图中，首先对输入的串做预处理，剔除多余的空白符 → 将保留字作为一类特殊的标识符来处理，即对保留字不单独设置状态转换图，当转换图识别出一个标识符时，先去查对应的表的前5项，确定它是否为一个保留字。（也可以专设一个保留字表来进行处理）

对应的状态转换图为：



注意：

在图中的状态2时，先确定是否为保留字，否则就是标识符。如果是标识符，应该先查符号表，如果表中无此标识符，则将它加入到符号表中，返回它在符号表中的入口指针（地址）作为该标识符的内码值；如果表中已经有此标识符，则给出重名错误信息。

在状态4时，应将识别的常数转换成二进制常数，并将其加入到常数表中，然后返回其在常数表中的入口指针作为该常数的内码值。

3、状态转换图的实现（C语言代码）

最简单的实现状态转换图的方法：让每个状态对应一小段程序。

对于这个例子的状态转换图，引进一组变量和函数：

(1) character: 字符变量，存放新读入的源程序字符

(2)token: 字符数组，存放构成单词符号的字符串

(3) getbe()： 若character中的字符为空白，则调用getchar()， 直至character为非空白字符为止

(4) concatenation():  将token中的字符串与character中的字符连接并作为token 中新的字符串

(5) letter()和 digit():  判断character中的字符是否为字母和数字的布尔函数，是则返回true(即1)，否则返回false(即0)。

(6) reserve（）: 按token数组中的字符串查表中的前五项(即判别其是否为保留字)，若是保留字则返回它的编码，否则返回0值

(7)retract():  扫描指针回退一个字符，同时将character置为空白。

(8) buildlist(): 将标识符登灵到符号表中或将赏数登录到常数表中

(9) error(): 出现非法字符，显示出错信息。

词法分析概述















词法分析器的设计

在编译原理介绍中，我们已经对前端的工作有了大致的了解。
在其中，词法分析器的任务就是读入源程序，对其进行一定的切分，得到记号流。
对于字符流和记号流之间的区别，下面给出一个例子来说明。
if (x > 5)
    y = "hello";
else
    z = 1;
对面上面这段程序，在词法分析器的眼中，是这样表示的：
i, f, " ", (, x, " ",>, " ", 5, ), n, " "," ", y, " ", =, .........
可见词法分析器看到的字符流和我们眼中的字符流是不一样的。 而词法分析器的任务就是对字符进行 切分。将 i 和 f 并在一起做为一个 if 关键字，去除掉没有意义的空格等等。
对于像 IF， LPAREN， IDENT 等的单词，我们都称为记号。
在记号中，有一些记号是没有属性的，类似于 IF 之类的关键字， IDENT(x) 之类的标识符需要表明其中的元素具体是什么。
记号的数据结构定义如下：
enum kind {IF, LPAREN, ID, INTLIT, ...};
struct token{
    enum kind k;
    char *lexname;
}
因此，对于语句 if (x > 5) 可以转变为
token {
    k = IF;
    lexname = 0; //0 表示没有赋任何的值
}
token {
    k = LPAREN;
    laxname = 0;
}
token {
    k = ID;
    laxname = "x";
}
....
通过上面的学习，我们可以知道词法分析器的任务是将字符流转化为记号流。
字符流：和被编译的语言密切相关（ASCII（C）， Unicode（Java,  Swift）， or ...）
记号流：编译器内部定义的数据结构，编码所识别出的词法单元。
原文链接：
编译原理 - 网易云课堂

编译原理实验：词法分析
1. 实验题目：词法分析
实验目的
实验内容
实验要求
输入输出
2. 设计思想
3.算法流程
4. 源程序
5. 调试数据

1. 实验题目：词法分析
实验目的

根据PL/0语言的文法规范，编写PL/0语言的词法分析程序；或者调研词法分析程序的自动生成工具LEX或FLEX，设计并实现一个能够输出单词序列的词法分析器。
通过设计调试词法分析程序，实现从源程序中分出各种单词的方法；加深对课堂教学的理解；提高词法分析方法的实践能力。
掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的法。
掌握词法分析的实现方法。上机调试编出的词法分析程序。

实验内容
 已给PL/0语言文法，输出单词符号（关键字、专用符号以及其它标记）。
实验要求

把词法分析器设计成一个独立一遍的过程。
词法分析器的输出形式采用二元式序列，即：(单词种类,单词的值)

输入输出
输入：

  const a=10;

  var b,c;

  begin

  read(b);

  c:=a+b;

  write( c);

  end.

输出：

  (constsym, const)

  (ident , a)

  (eql, =)

  (number, 10)

  (semicolon, ; )

  (varsym, var)

  (ident,b)

  (comma, ,)

  (ident, c)

  (semicolon, ; )

  (beginsym, begin)

  (readsym, read )

  (lparen,( )

  (ident, b)

  (rparen, ))

  (semicolon, ; )

  (ident, c)

  (becomes, := )

  (ident,  a)

  (plus,  +)

  (ident,b )

  (semicolon, ; )

  (writesym,write)

  (lparen, ( )

  (ident, c)

  (rparen,) )

  (endsym, end )

  (period, .)
2. 设计思想
基本字：




单词（编码）
正规式r




begin(beginsym)
begin


call(callsym)
call


const(constsym)
const


do(dosys)
do


end(endsym)
end


if(ifsym)
if


odd(oddsym)
odd


procedure(proceduresym)
procedure


read(readsym)
read


var(varsym)
var


while(whilesym)
while


write(writesym)
write


then(thensym)
then


标识符：




单词（编码）
正规式r




<标识符>(ident)
（字母)(字母 |数字)*


常数：




单词（编码）
正规式r




<常数>(ident)
（数字)(数字)*


运算符：




单词（编码）
正规式r




+(plus)
+


-(minus)
-


*(times)
*


/(slash)
/


=(eql)
=


<>(neq)
<>


<(lss)
<


<=(leq)
<=


>(gtr)
>


>=(geq)
>=


:=(becomes)
:=


界符：




单词（编码）
正规式r




(  (lparen)
(


)  (rparen)
)


,  (comma)
,


;  (semicolon)
;


.  (period)
.


3.算法流程


词法分析程序打开源文件，读取文件内容，直至遇上文件结束符，然后读取结束。
接下来就要对源文件从头到尾进行扫描了，从头开始扫描，这个时候扫描程序首先要询问当前的字符是不是空格，若是空格，则继续扫描下一个字符，直至不是空格。然后询问这个字符是不是字母，若是则进行标识符和保留字的识别；若这个字符为数字，则进行数字的判断。否则，依次对这个字符可能的情况进行判断（界符和运算符），若将所有可能都走了一遍还是没有知道它是谁，则认定为错误符号，输出该无法识别error，程序结束。每次成功识别了一个单词后，单词都会存在word1[]数组中，然后字符指针往后移，进行下一个单词的识别。
主控程序需要负责对每次识别的种别码进行判断，对于不同的单词种别做出不同的反应，直至文件结束。
本次实验我采用了map这个STL关联容器，主要是考虑到词法分析中的数据映射的关系，因此采用这种结构。map提供一对一的数据处理能力，其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值。这个容器是非常方便使用的，对于查找可以直接使用迭代器进行，利用find（）函数，若一直到末尾都未找到，则是不能识别或为标识符。

4. 源程序
#include<bits/stdc++.h>
using namespace std;
map<string,string> word;//应用map数据结构形成一个string->string的对应
std::map<string,string>::iterator it;//用来遍历整个对应关系的迭代器
void map_init(){//对应关系进行初始化
    word["begin"]="beginsym";
    word["call"]="callsym";
    word["const"]="constsym";
    word["do"]="dosym";
    word["end"]="endsym";
    word["if"]="ifsym";
    word["odd"]="oddsym";
    word["procedure"]="proceduresym";
    word["read"]="readsym";
    word["then"]="thensym";
    word["var"]="varsym";
    word["while"]="whilesym";
    word["write"]="writesym";
    word["+"]="plus";
    word["-"]="minus";
    word["*"]="times";
    word["/"]="slash";
    word["="]="eql";
    word["<>"]="neq";
    word["<"]="lss";
    word["<="]="leq";
    word[">"]="gtr";
    word[">="]="geq";
    word[":="]="becomes";
    word["("]="lparen";
    word[")"]="rparen";
    word[","]="comma";
    word[";"]="semicolon";
    word["."]="period";
}
int main(){
    map_init();//初始化
    char ch;
    char a;
    string word1;//string变量识别单词
    string str;//string变量进行字符识别
    ifstream infile("F:\\编译原理\\第一次实验\\analysis.txt");//文件输入流
    ofstream outfile("F:\\编译原理\\第一次实验\\result.txt");//文件输出流
    ostringstream buf;
    while(buf&&infile.get(ch)) buf.put(ch);//将文件中的字符读出来
    str= buf.str();//将得到的字符储存到string类型变量中
    int csize=str.length();
    for(int i=0;i<csize;i++){//对整个字符串进行遍历
        while(str[i]==' '||str[i]=='\n') i++;//若最开始为空格或换行符，则将指针的位置往后移
        if(isalpha(str[i])){//对标识符和基本字进行识别,调用库函数isalpha()
            word1=str[i++];
            while(isalpha(str[i])||isdigit(str[i])){
                word1+=str[i++];
            }
            it=word.find(word1);
            if(it!=word.end()){//判断是不是基本字，若为基本字则进行输出
                cout<<"("<<word[word1]<<","<<word1<<")"<<endl;
            }
            else{//否则直接输出
                cout<<"(ident"<<","<<word1<<")"<<endl;
            }
            i--;
        }
        else if(isdigit(str[i])){//判断是不是常数，调用库函数isdigit()
            word1=str[i++];
            while(isdigit(str[i])){
                word1+=str[i++];
            }
            if(isalpha(str[i])){
                cout<<"error!"<<endl;
                break;
            }
            else{
                cout<<"(number"<<","<<word1<<")"<<endl;
            }
            i--;
        }else if(str[i]=='<'){//对<,<=分别进行判断
            word1=str[i++];
            if(str[i]=='>'){
                word1+=str[i];
                cout<<"("<<word[word1]<<","<<word1<<")"<<endl;
            }else if(str[i]=='='){
                word1+=str[i];
                cout<<"("<<word[word1]<<","<<word1<<")"<<endl;
            }else if(str[i]!=' '||!isdigit(str[i])||!isalpha(str[i])){
                cout<<"("<<word[word1]<<","<<word1<<")"<<endl;
            }else{
                cout<<"error!"<<endl;
                break;
            }
            i--;
        }else if(str[i]=='>'){//对>,>=分别进行判断
            word1=str[i++];
            if(str[i]=='='){
                word1+=str[i];
                cout<<"("<<word[word1]<<","<<word1<<")"<<endl;
            }else if(str[i]!=' '||!isdigit(str[i])||!isalpha(str[i])){
                cout<<"("<<word[word1]<<","<<word1<<")"<<endl;
            }else{
                cout<<"error!"<<endl;
                break;
            }
            i--;
        }else if(str[i]==':'){//对:=进行判断
            word1=str[i++];
            if(str[i]=='='){
                word1+=str[i];
                cout<<"("<<word[word1]<<","<<word1<<")"<<endl;
            }else{
                cout<<"error!"<<endl;
                break;
            }
            i--;
        }else{//对其他的基本字依次进行判断
            word1=str[i];
            it=word.find(word1);
            if(it!=word.end()){
                cout<<"("<<word[word1]<<","<<word1<<")"<<endl;
            }else{
                cout<<"error!"<<endl;
                break;
            }
        }
    }
    infile.close();
    return 0;
}

5. 调试数据
待输入的文件流：



输出数据：





说明：如上实验仅符合当时实验要求的相关条件，其他的需求略微进行更改就行，思想是一样的，还是很简单的。输入输出自己按自己需求更改即可。