实验一 词法分析器

一、实验目的

通过本实验的编程实践，使学生了解词法分析的任务，掌握词法分析程序设计的原理和构造方法，使学生对编译的基本概念、原理和方法有完整的和清楚的理解，并能正确地、熟练地运用。

二、实验内容

用 VC++/VB/JAVA 语言实现对 C
语言子集的源程序进行词法分析。通过输入源程序从左到右对字符串进行扫描和分解，依次输出各个单词的内部编码及单词符号自身值；若遇到错误则显示“Error”，然后跳过错误部分继续显示
；同时进行标识符登记符号表的管理。

以下是实现词法分析设计的主要工作：

（1） 从源程序文件中读入字符。

（2） 统计行数和列数用于错误单词的定位。

（3） 删除空格类字符，包括回车、制表符空格。

（4） 按拼写单词，并用（内码，属性）二元式表示。(属性值——token 的机内表示)

（5） 如果发现错误则报告出错

（6） 根据需要是否填写标识符表供以后各阶段使用。

三、实验代码

代码文件详见根目录下实验一文件夹

四、功能描述

本程序能够实现对C语言子集的词法分析过程，并按照指定格式输出词法分析的结果，涵盖错误处理过程。

五、程序技术栈

本程序采用Python
3编写，采用B/S架构完成程序的界面化，采用MVC架构。界面化所涉及的技术栈如下：

后台：Python Flask Web框架

前端：Bootstrap 4 UI库

运行环境：

腾讯云服务器，配置为1核1G，10M带宽。运行CentOS 7 操作系统。

文件结构说明:

│ app.py Web主程序

│ parse.py 词法分析主程序

│ req.txt 需求文件

│ remove.py 去除注释的功能模块

│ test.py

│ test.txt 测试文件

│ uwsgiconfig.ini uwsgi配置文件

│

├─templates MVC的视图模板文件夹

│ index.html

│ result.html

│

└─__pycache__ Python运行所产生的cache文件

parse.cpython-36.pyc

remove.cpython-36.pyc

运行说明：

①安装并执行nginx，以CentOS为例：

yum install nginx

nginx

②安装Python依赖包，需要提前创建虚拟环境req.txt在根目录下

python -m venv test

source ./test/bin/active

pip install -r req.txt

③使用uwsgi执行主程序，如需后台运行，请使用nohup指令

uwsgi uwsgiconfig.ini

六、代码结构

6.1 预处理

首先，对接受的代码要进行预处理，包括以下内容：

1. 统计原代码各个单词的行数以及列数
2. 去除注释，包括//注释以及/*注释 */
3. 去除换行符，制表符

注意这里需要先将单词定位，因为去除注释之后，原代码的位置会发生改变。去除注释部分我使用了正则表达式来去除，代码如下：

由于python字符串本身需要/转义，所以可以使用r”默认字符串不转义。另外，由于正则表达式本身需要转义。例如在正则表达式中代表任意字符。所以想要匹配需要使用/来转义。去除换行符、制表符使用replace函数即可。

单词的定位我这里有些投机取巧，保存的原本的代码字符串，去除注释及选择出单词token后，在源程序中再次定位。但是由于代码可能存在字符串重复的问题，这会造成定位失败。目前为了避免这一问题，使用截断的方法，定位后去除已经定位的内容，避免重复匹配。

6.2 词法分析

在这个过程中，我封装了一个类AccidenceParse，来完成对一个词法的分析过程。

这个类初始化函数如下：

AccidenceParse(source,table_k,table_p,table_s)

pre_prase()

预处理函数，主要对源代码进行预处理，例如去除注释、换行符、制表符等操作。

table_p_include(word)

word的type为list。判断word内值是否在分隔符表内，如果存在，则返回第一分隔符在word的index，否则返回-1

locate()

对待词法分析的代码进行各种符号的定位，方便最后的结构化输出。该方法对外隐藏，由prase()函数调用

toprint()

debug函数，在调试时用来输出结构化结果，在B/S架构中该函数无用

prase()

词法分析主函数

整个分析过程如下图所示：

7 软件测试

7.1 测试样例一

**测试结果：**能够去除注释并分析代码词法

7.2 测试样例二

待分析代码:

sda3#fjkl=123.213

**测试结果：**能够识别浮点数

7.2 测试样例三

待分析代码：

e=。

**测试结果：**对于不能分析的字符，如句号，能够判断出错

实验总结

经过了这次的实验，在不断踩坑的过程之中，我加深了对Python语言数据结构的理解，以及Python语言的一些细枝末节。比如，Python的浅层拷贝与深层拷贝、Python中的set不能包含list元素，因为list无法被hash。

实验二 LL(1)分析法

一、实验目的

通过完成预测分析法的语法分析程序，了解预测分析法和递归子程序法的区别和联系。使学生了解语法分析的功能，掌握语法分析程序设计的原理和构造方法，训练学生掌握开发应用程序的基本方法。有利于提高学生的专业素质，为培养适应社会多方面需要的能力。

二、实验内容

（1）根据某一文法编制调试 LL （ 1 ）分析程序，以便对任意输入的符号串进行分析。

（2）构造预测分析表，并利用分析表和一个栈来实现对上述程序设计语言的分析程序。

（3）分析法的功能是利用 LL（1）控制程序根据显示栈栈顶内容、向前看符号以及
LL（1）分析表，对输入符号串自上而下的分析过程。

三、实验代码

代码文件详见根目录下实验二文件夹

文件结构说明:

│ app.py Web主程序

│ main.py LL(1)分析主程序

│ req.txt 需求文件

│ test.py

│ test.txt 测试文件

│ uwsgiconfig.ini uwsgi配置文件

│

├─templates MVC的视图模板文件夹

│ index.html

│ result.html

│

└─__pycache__ Python运行所产生的cache文件

四、功能描述

本程序能够实现对任意语法的LL(1)的分析，并按照指定格式输出词法分析的结果，涵盖错误处理过程。并会格式化的打印生成的FIRST集与FOLLOW集以及预测分析表。

五、程序技术栈

同实验一程序技术栈部分

六、代码结构

整个分析过程如下流程图所示：

6.1 生成FIRST集和FOLLOW集

本程序封装了一个类LL1Parse，来完成对一个语法的LL(1)分析过程。

这个类初始化函数如下：

LL1Parse(text)

text的type为str，是语法的描述文件。下面是一个text的语法实例：
E->TG

G->+TG|~

T->FH

H->*FH|~

F->(E)|i

语法使用->表示推导，使用~表示空集，特别注意的是，语法的第一个字符，必须是开始符号。

LL1Parse类有两个方法可以对传入的语法生成FIRST集和FOLLOW集，他们分别是：

generate_first()

generate_follow()

生成FIRST集和FOLLOW集的程序算法步骤依靠书上给出的算法步骤。程序使用first_dic和follow_dic这两个变量表示，利用dic自带的hash功能查询，dic的key为字符，value的type为set，避免出现字符的重复。

First集求解算法

设Vt为文法的终结符集合，Vn为非终结符集合，对于每一个文法符号X∈Vt∪Vn，使用如下规则，直到每个集合都不再变大为止。

（1）若X∈Vt，则First（X）={X}。

（2）若X∈Vn，且有产生式X->a……，则把a加入到First（X）中；若X->ε，也是一条产生式，则把ε也加入到First（X）中。

（3）若X->Y…是一个产生式且Y∈Vn，则把First（X）中所有非ε元素都加入到First（X）中；若X->Y1Y2…Yk；Y1，…，Yi-1都是非终结符，如果1-(i-1)的非终结符都含有ε，则将Yi的First集中非ε元素加入First（X）；特别是，若所有的Fir（Yi）都含有ε，则把ε也加入到First（X）。

Follow集求解算法（α是任意符号串，包括空串）

对于文法的每个非终结符A构造Follow（A）的办法是，连续使用下面的规则，直到每个Follow不再增大为止。

（1）对于文法的开始符号S，置#于Follow（S）中；

（2）若A->αBβ是一个产生式，则把First（β）中的非ε元素加入到Follow（B）中；

（3）若A->αB是一个产生式，或A->αBβ是一个产生式而β->ε（即ε属于First（B）），则把Follow（A）加至Follow（B）中。

需要指出的是，书上的算法步骤指出，当FIRST集和FOLLOW集依靠算法步骤计算直至不增加时，构建这两个集合就完成了。这里，需要使用Python内置的copy()函数对原本的集合进行拷贝，处理完成后，对first_dic（follow_dic）与之前拷贝进行比较，如果相等，则证明dic没有增加，算法结束。

6.2 构造预测分析表

LL1Parse类有一个方法generate_table()，来实现构造预测分析表，同样，它的算法步骤参见书上给出的算法。这里也使用了上述的copy()方法来判断算法是否结束。

分析表的构造算法（分析表以数组形式表示——M[ ]）

（1）对于文法的每个产生式A->α，执行第二步和第三步；

（2）对于每个终结符a∈First（α）加至M [ A,a ]中；

（3）若ε∈First（α），则对于任何b∈Follow（A），把A->ε加至M [ A,b ]中；

（4）把所有无定义的M [ A,a ]设置为Error。

6.3 对语法进行分析

LL1Parse类的另一个方法parse(input)能够对传入的input串进行语法分析。input串无需再最后加上‘#’结束符，程序会自动加上。

另外，在分析前，parse方法会自动调用上述的generate_first()、generate_follow()、generate_table()三个函数，完成分析前的准备操作。

7 软件测试

7.1 测试样例一

**待分析串：**ii+i+i+ii

分析结果：

FIRST集：

FOLLOW集：

分析过程：

7.2 测试样例二

**待分析串：**ii+ii+ii+ii+ii+ii+ii+ii+ii+ii+ii+ii+ii+ii+i

分析结果：

总共146步，因篇幅原因，只截取最后一部分

7.3 测试样例三

待分析串：(i+i*i)

分析结果：

7.4 测试样例四

**待分析串：***i+_

分析结果：

能够完成错误处理。

实验三 词法分析器

一、实验目的

构造
LR(1)分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子，了解
LR（K）分析方法是严格的从左向右扫描，和自底向上的语法分析方法。

二、实验内容

对下列文法，用 LR（1）分析法对任意输入的符号串进行分析：

（1） E-> E+T

（2） E->T

（3） T-> T*F

（4） T->F

（5） F-> (E)

（6） F-> i

三、实验代码

代码文件详见根目录下实验三文件夹

文件结构说明:

│ app.py Web主程序

│ parse.py LR(1)分析主程序

│ req.txt 需求文件

│ test.py 测试文件

│ uwsgiconfig.ini uwsgi配置文件

│

├─templates MVC的视图模板文件夹

│ index.html

│ result.html

├─lr1 lr(1)分析过程代码文件

│ lr_automaton.py 构建自动机

│ lr_parsing_table.py 构造预测分析表

│ lr_processor.py 分析过程

│ grammar.py 语法规则结构体

└─__pycache__ Python运行所产生的cache文件

四、功能描述

本程序能够实现对指定文法的LR（1）分析过陈，按照指定格式输出分析的结果及预测分析表，涵盖错误处理过程。并且，本程序还能打印构造的DFA转换图。

五、程序技术栈

技术栈大体上同实验一实验二，但不同的是，打印输出DFA转换图，我使用了百度的Echarts来完成可视化操作。

六、代码结构

由于LR(1)分析过程较为复杂，这里我才用了分文件的模式，用单个文件表示LR(1)分析过程中的某一个模块。

grammar.py

本代码文件主要完成语法的格式化录入。我构建了Rule类表示一条语法，他有left、right_list、order三个变量表示一条语法的关系。特别注意的是，为了方便处理，每个符号之前都应该加上空格隔开。

lr_automaton.py

本代码主要完成DFA的构建，我构建了一个Node类表示DFA中的每个节点，同时用用[Rule,
dot_position, look_ahead]表示自动机中的一行。

构建了LrAutomaton类，其中generate方法来生成自动机

lr_parsing_table.py

这里构建了TableItem类来表示分析表中的一个项目。同时构建了ParsingTable类用来产生LR(1)分析表。

lr_processor.py

这个文件代码会利用上述代码所构建出的LR(1)分析表，对传入的待分析串进行分析操作，并最后输出分析步骤，保存再数组内返回。

整个代码的流程图如下：

7 软件测试

7.1 测试样例一

**待分析串：**i * i + i

分析结果：

生成的DFA图

分析过程

预测分析表

八、实验总结

Python在写类似程序时，代码量由于语法特性的关系，比C++、JAVA之类的代码量要少得多。例如，实验二的代码，我只使用了300多行代码就完成了对一个词法的分析过程。而使用JAVA、或C++语言时，大家貌似都写到了快1k行代码。

但需要注意的时，Python的语法特性虽然用起来很爽，但是由于是弱类型语言，在写这中type很多的程序时，非常容易把类搞混淆，导致debug的时间增加。而类似于JAVA的强类型语言则结构更为清晰，不会出现此类的问题。