现代编译器设计与实现 课件 李诚 第1-3章 绪论、系统环境搭建- 源语言解析器的设计与实现

面向自主指令集的编译系列实验要点讲解编译原理和技术目标：面向国家战略需求，以系统和创新能力的培养为导向，根据计算机学科发展的趋势和新时代大学生的成长需要构建现代编译实验体系，体现先进性、挑战度，增强学生获得感编译实验体系总览源语言特性中间代码生成器中间代码优化器目标代码生成器基于Cminusf语言，增加对浮点数、数组等复杂特性的支持使用简化版LLVM中间表达子模块和基于访问者模式的编程框架(自研)，自动生成Cminusf程序的中间代码使用封装好的基本块、调用者使用者链表等常用数据结构及其接口(自研)，实现简单/复杂代码优化算法支持龙芯(与龙芯合作研发)、RISC-V等多指令集后端，鼓励对寄存器分配算法、指令选择算法等进行探索验证词法语法分析器使用Flex+Bison工具构造编译器前端，重点考察对Cminusf语言正则表达式和语法产生式的抽象能力编写编译器一定规模性能较优功能较完备基础实验+龙芯后端实验+高阶创新实验有机结合编译实验架构图环境搭建Lab0语言解析器Lab1IR自动生成Lab2LA64代码生成Lab3转化为SSAIRLab4常量传播Lab5.1不变式外提Lab5.2寄存器分配…Others机器无关优化后端优化Lab6目的：熟悉虚拟机、VSCode、git、gdb等工具的使用，完成后端环境安装要求：成功安装虚拟机，并在虚拟机安装龙芯模拟后端环境，熟练使用git命令考核标准：使用clang编译预留c文件，生成的中间代码能输出学生学号成功解决仓库冲突Lab0：环境搭建目的：从无到有完成Cminus-f解析器掌握并运用词法分析、语法分析基础知识掌握flex和bison的原理和使用要求：基于flex生成词法分析器、将字符流转为token流基于bison生成语法分析器、根据token流建立语法树考核标准：对测试样例输出正确的语法树结构Lab1：语言解析器SourcefileLexerTokenstreamParserAbstractSyntaxTree(AST)Lab1…目的：掌握源代码到IR的生成过程要求：使用访问者模式遍历Lab1生成的抽象语法树，调用LightIR库，自动化生成符合Cminus-f语义的

中间代码考核标准：80个分级测试样例用LLVM后端执行所生成的IR文件，根据学生通过的测试样例比例赋分Lab2：IR自动生成Lab1ASTIRLab2LightIR库访问者模式自动化生成…目的：根据LightIR生成LA64汇编要求：使用栈式分配的策略进行后端代码生成考核标准：35个测试样例学生实现的编译器需要生成正确的LA64汇编在本地可以使用龙芯交叉编译工具进行测试，测评服务器直接运行在龙芯机器上Lab3：LA64代码生成IRLA64汇编Lab3龙芯机器码栈式分配翻译模板目的：实现Mem2Reg优化，得到SSAIR要求：理解Mem2Reg算法流程，在实验框架中实现Mem2Reg优化修改后端代码，使编译器能够正确处理phi指令考核标准：正确性：使用与Lab3相同的测试样例，要求开启Mem2Reg优化通过测试性能：3个测试样例，自行对比优化的效果Lab4：转化为SSA

IRLab3IRSSAIR

(with

phi)Lab4Mem2Reg插入phi函数变量重命名冗余指令删除Lab4后端完成相应适配LA64汇编…目的：在中间代码上实现机器无关优化要求：掌握循环搜索算法，在SSAIR格式下，实现常量传播，循环不变式外提的优化考核标准：常量传播与不变式外提各4个测试样例将学生实现的优化效果与baseline进行比较进行赋分Lab5：机器无关优化Lab4SSAIRSSAIRLab5循环搜索常量传播不变式外提IRpass…目的理解寄存器分配原理，能实现图着色或线性扫描寄存器分配算法要求完成活跃区间计算、寄存器分配、phi消除的实现寄存器数量不够的时候需实现变量的溢出操作考核标准：13个测试样例将学生实现的优化效果与baseline进行比较进行赋分Lab6：寄存器分配Lab4/5SSAIRLA64汇编Lab6活跃区间寄存器分配phi消除后端代码生成下期再见！Thanks！

配置实验项目运行环境编译原理和技术MENU使用VirtualBox配置Ubuntu22.04系统在Ubuntu22.04系统中安装实验依赖软件MENU使用VirtualBox配置Ubuntu22.04系统在Ubuntu22.04系统中安装实验依赖软件运行环境：VirtualBox简介及安装VirtualBox免费和开源：开源软件，适用于教学。跨平台性：支持多种操作系统，在任一系统上都可运行。广泛虚拟机支持：可以运行各种不同的虚拟机系统。VirtualBox安装官网下载链接：/Ubuntu22.04操作系统下载Ubuntu免费和开源：免费的开源操作系统。软件中心和包管理：提供方便的应用程序管理。社区支持：拥有庞大的用户社区，支持长期维护。

Ubuntu安装官网下载链接：/中科大镜像源下载链接：/ubuntu-releases/版本选择：ubuntu-22.04.3-live-server-amd64.iso

使用VirtualBox与系统文件搭建运行环境步骤一：打开VB(VirtualBox)，点击新建:使用VirtualBox与系统文件搭建运行环境步骤二：在新建界面中设置名称与操作系统，之后点击下一步:使用VirtualBox与磁盘文件搭建运行环境步骤三：设置虚拟机的内存大小与处理器数量:使用VirtualBox与磁盘文件搭建运行环境步骤四：接下来选择创建虚拟硬盘，设置最大磁盘大小为25~40GB即可：启动与登录虚拟机步骤五：虚拟机启动：选中刚刚创建的虚拟机，点击启动：启动与登录虚拟机步骤六：选中下载好的Ubuntu系统，并挂载并尝试启动:启动与登录虚拟机步骤七：安装Ubuntu22.04系统，剩余操作选择默认后点击回车即可:启动与登录虚拟机步骤八：注册虚拟机用户(用户名和密码需妥善保存):启动与登录虚拟机步骤九：按照默认选择后点击回车直到成功安装系统后选择重启:启动与登录虚拟机步骤十：若出现界面卡顿，点击回车即可:启动与登录虚拟机步骤十一：登录虚拟机,键入注册的用户名和密码:

启动与登录虚拟机步骤十二：点击回车后成功登录虚拟机:

启动与登录虚拟机登录成功界面启动与登录虚拟机登录成功界面成功安装Ubuntu后，接下来的我们会讲解在Ubuntu中安装实验依赖软件MENU使用VirtualBox配置Ubuntu22.04系统在Ubuntu22.04系统中安装实验依赖软件核心软件版本要求实验使用的核心软件版本为Ubuntu22.04LLVM14.0.0Flex2.6.4Bison3.8.2本实验项目运行环境依赖于Ubuntu22.04操作系统注：默认读者已掌握Linuxshell的基本操作实验依赖软件安装安装核心软件：build-essential，Flex，Bison，LLVM，Clang安装的核心软件版本为：LLVM14.0.0Flex2.6.4Bison3.8.2下载依赖于Ubuntu22.04操作系统实验依赖软件安装安装命令：演示登录虚拟机后，在terminal中输入：sudoaptupdate&&sudoaptinstallbuild-essentialflexbisonllvmclang验证软件成功安装：演示登录虚拟机后，在terminal中输入：gcc--version，flex--version，bison--version，llvm-as--version，clang--version如果出现对应软件的版本信息，即该软件安装成功验证成功搭建实验运行环境演示登录虚拟机，在terminal中输入vimgcd.c创建测试文件gcd.c将以下代码输入至gcd.c中并保存int

gcd(int

u,int

v){

if(v==

0)returnu;

else

return

gcd(v,u-u/v*v);}int

main(){

intx;inty;inttemp;

x=

72;

y=

18;

if(x<y){

temp=x;

x=y;

y=temp;

}

return

gcd(x,y);}验证成功搭建实验运行环境演示登录虚拟机，在terminal中输入vimgcd.c创建测试文件gcd.c将以下代码输入至gcd.c中并保存在terminal中执行以下3条命令clang-S-emit-llvmgcd.clligcd.llecho$?返回18则环境配置成功下期再见！Thanks！

实验项目开发环境配置编译原理和技术中国科学技术大学编译原理课程组MENU使用VSCode通过SSH协议登录虚拟机配置VSCode开发环境下的代码自动补全MENU使用VSCode通过SSH协议登录虚拟机配置VSCode开发环境下的代码自动补全SSH协议简介SSH简介：SSH是一种网络协议，用于在计算机之间建立安全的远程连接和数据传输。SSH服务分为client(主机)端和server(服务器)端。下图直观地展示了SSH的工作原理:因此，需要对虚拟机端与主机端的SSH服务分别配置SSHclientSSHserverSSH主机端服务器端虚拟机端配置–启动SSH服务

登录虚拟机并在terminal中输入以下命令演示SSH-Server安装：sudoaptinstallopenssh-serverSSH-Server启动：sudosystemctlstartssh（启动ssh服务器）sudosystemctlenablessh（设置ssh服务器开机自启动)验证：#出现/usr/sbin/sshd类似信息则已启动成功$psaux|grepsshd

启动SSH服务后还需要配置虚拟机的网卡才可以让宿主机顺利连接上虚拟机虚拟机端配置–配置虚拟机网卡步骤一：打开VirtualBox虚拟机设置,点击网络选项虚拟机端配置–配置虚拟机网卡步骤二：确认网卡1已启用，且连接方式为网络地址转换（NAT），然后单击高级，点击端口转发。虚拟机端配置–配置虚拟机网卡步骤三：添加规则虚拟机相关配置好了，接下来需要在VSCode配置SSH。主机端SSH配置–OpenSSH安装连接方式在Windows系统上，我们使用OpenSSHclient来进行SSH连接：

从Windows10开始系统自带OpenSSHclient，在"设置"->"应用"->"可选功能"可以检查是否已经安装OpenSSHclient：主机端配置-安装VSCode简介VisualStudioCode（简称“VSCode”）是针对于编写现代Web和云应用的跨平台源代码编辑器安装下载链接：/使用VSCode通过SSH登录方式来修改虚拟机中实验项目文件配置VSCodeRemote-SSH插件步骤一：在VSCode插件商店中下载插件演示配置VSCodeRemote-SSH插件步骤二：点击VSCode左边列表中红框框出来的RemoteExplorer，然后点击设置标号，打开SSH配置文件配置VSCodeRemote-SSH插件步骤三：将以下配置写入配置文件中，其中Host可以自定义命名，Port端口设置为前面虚拟机内设置的端口，刷新左侧列表Hostvbox HostName User[yourusername] Port2222配置VSCodeRemote-SSH插件步骤四：此时左侧一列中出现了如图所示的项，点开箭头，选择虚拟机平台，输入密码即可通过VSCode登录虚拟机配置VSCodeRemote-SSH插件步骤五：登录虚拟机后打开项目文件夹MENU使用VSCode通过SSH协议登录虚拟机配置VSCode开发环境下的代码自动补全配置VSCode开发环境下的代码自动补全自动补全依赖于整个实验项目的编译，以及VSCode相关插件实验项目使用CMake管理构建并编译步骤一：演示在VSCode中安装以下插件配置VSCode开发环境下的代码自动补全步骤二：演示下载并安装CMake简介CMake是一个用于管理和生成跨平台构建系统的开源工具。它可以帮助开发人员轻松地配置、构建和测试他们的项目。

安装：sudoaptinstallcmake验证#出现版本信息则说明安装已成功$cmake--versioncmakeversion3.22.1配置VSCode开发环境下的代码自动补全步骤三：使用CMake编译整个实验项目演示在虚拟机terminal中输入以下命令$mkdirbuild$cdbuild$cmake..$make编译成功后即可顺利使用自动补全功能下期再见！Thanks！

配置实验项目调试环境编译原理和技术编译原理课程组中国科学技术大学MENUGDB简介及安装GDB命令行调试GDB结合VSCode图形化调试GDB简介及安装GDB简介：GDB(GNUDebugger)是GNU软件系统中的标准调试器，目前GDB所能支持的调试语言有C，C++等。GDB具备各种调试功效，能针对计算机程序的执行进行追踪与警告，使用GDB的调试人员可以监督及修改程序的内部变量值GDB安装演示在虚拟机的terminal中输入sudoaptinstallgdb验证：MENUGDB简介及安装GDB命令行调试GDB结合VSCode图形化调试GDB调试GDB命令行调试

在终端直接使用GDB调试代码。步骤一

生成可执行文件：

演示调试项目C文件：CMake记录了项目文件的依赖关系，需要在项目根目录的CMakeLists.txt设置Debug模式，修改完成后重新编译整个项目。·步骤二：gdb调试可执行文件

演示gdb可执行文件setargs参数1参数2.....GDB调试GDB命令行调试步骤三：list查看代码并打断点

·步骤四：执行到断点

·步骤五：查看变量并继续执行并结束GDB命令调试代码还有很多，就不一一列举，同学们按需学习GDB调试代码MENUGDB简介及安装GDB命令行调试GDB结合VSCode图形化调试在VSCode中配置图形化调试界面步骤零

安装C/C++插件：演示使用快捷键Ctrl+Shift+X呼出扩展面板在搜索框中输入：C/C++再安装由Microsoft提供的名为C/C++插件。命令行调试程序相对繁琐，通过vscode中安装C++/C插件图形化界面能帮助同学们更好调试程序在VSCode中配置图形化调试界面步骤二：生成json文件点击RunandDebug（快捷键：Ctrl+Shift+D），在.vscode/中新建launch.json。如图在launch.json文件中点击右下角的AddConfiguration，选择gdbLaunch。步骤一：生成可执行文件调试项目C文件：CMake记录了项目文件的依赖关系，需要在项目根目录的CMakeLists.txt设置Debug模式，修改完成后重新编译整个项目。在VSCode中配置图形化调试界面步骤三：配置gdbjson文件选择可执行文件的路径，以及启动参数。”program”为待调试程序，“args”为启动该程序的参数，在该图参数是"-emit-llvm"与"${workspaceFolder}/gcd.cminus""${workspaceFolder}"指的是VSCode中打开文件夹的路径）在VSCode中配置图形化调试界面步骤四：图形化调试代码在1处设置完断点，点击2处的三角运行符号，程序将运行至断点处停下，在3处显示变量的值，在4处显示的是目前函数的调用堆栈可以帮助理解函数的调用过程。下期再见！Thanks！

实验项目版本管理编译原理和技术编译原理课程组中国科学技术大学MENU·Git简介·Git使用·配置信息·创建并拉取远程仓库·向远程仓库同步本地修改·版本管理·冲突解决Git简介·本节介绍使用Git对课程实验项目进行版本管理。Git组成部分工作区远程仓库本地仓库暂存区本地文件夹服务器pullclonepushaddcommitcheckoutGitlabGithubGitee·安全性高·开源共享·版本管理Git使用–配置Git信息Git支持共享开发，需要身份信息，来标识每次代码修改的提交者Git命令操作：演示gitconfig--global"Yourname"gitconfig--globaluser.email"Youremail"Git使用–创建并拉取远程仓库步骤一：建立Git远程仓库演示通过fork实验项目的公开仓库，获取自己的远程Git仓库步骤二：克隆远程仓库到本地演示在虚拟机的terminal中执行以下命令，url可从远程仓库页面获得gitclone+<url>Git使用–向远程仓库同步本地修改在工作区中对文件修改后，需要三个阶段同步至远程仓库工作区远程仓库本地仓库暂存区服务器pullclone③push①

add②commitcheckoutGit使用–向远程仓库同步本地修改步骤一：将文件提交到暂存区演示Git

命令，其中

filename是希望提交的修改后的文件gitadd+<filename>步骤二：提交暂存区到本地仓库演示Git命令，其中message是字符串，记录了此次提交用户自定义的修改信息gitcommit-m<message>Git使用–向远程仓库同步本地修改步骤三：将本地修改推送到远程仓库演示Git命令：gitpush<远程主机名><本地分支名>:<远程分支名>

默认为：gitpushGit使用–向远程仓库同步本地修改验证：查看远程仓库文件修改已同步至远程仓库Git使用–冲突合并多人合作开发，出现同时修改相同文件内容，产生冲突原始仓库A本地仓库版本0B本地仓库版本0forkforkT0T1B本地仓库版本1原始仓库A本地仓库版本1T1原始仓库冲突add&commitadd&commitpushpush普通合并

普通合并，Git会自动完成。普通合并是合并进来的分支新增了文件，Git会自动将新增的文件合并到当前分支中。冲突合并

冲突通常满足两个条件：

两个分支都来源于一个原始分支；两个分支都修改了同一份文件中相同的内容。

模拟冲突合并的情况：B同学Fork了A同学仓库，A和B同学在各自仓库分别提交了自己的内容，现在需要将A同学提交的内容更新到B同学仓库中。

Git使用–冲突合并

步骤一：设置上游仓库

演示gitremoteaddupstreamurl命令：将url对应的远程仓库设置为upstream。步骤二：拉取上游仓库文件

演示gitfetch远程仓库

远程仓库分支：拉取远程仓库对应的分支到本地仓库。Git使用–冲突合并fetch是拉取的远程仓库地址push是推送的远程仓库地址这一步是将别名为upstream的远程仓库master分支拉取到本地仓库。

步骤三

合并分支

演示gitmerge分支：将分支合并到当前分支

步骤四

解决冲突

演示

因为同时修改了warm_up.txt文件，无法合并需要手动修改。Git使用–冲突合并

步骤五

重新提交文件到仓库

演示重新添加到暂存区、本地仓库后通过gitlog--merges查看冲突合并分支以后的提交gitlog--merges：仅查看merge的提交历史记录。Git使用–冲突合并Git使用–版本管理步骤一：查看历史提交节点演示Git命令，gitlog查看历史提交。

步骤二：切换到以前的节点

演示Git命令，其中commitid标识了某次提交节点gitcheckout<commitid>下期再见！Thanks！

编译后端环境安装编译原理和技术编译原理课程组中国科学技术大学MENU·LoongArch交叉编译调试环境简介·LoongArch交叉编译及调试环境安装·获取LoongArch交叉编译及调试软件·传输LoongArch交叉编译及调试软件·解压安装LoongArch交叉编译及调试软件·查看LoongArch交叉编译及调试软件版本·验证使用LoongArch交叉编译及调试软件MENU·LoongArch交叉编译调试环境简介·LoongArch交叉编译及调试环境安装·获取LoongArch交叉编译及调试软件·传输LoongArch交叉编译及调试软件·解压安装LoongArch交叉编译及调试软件·查看LoongArch交叉编译及调试软件版本·验证使用LoongArch交叉编译及调试软件LoongArch交叉编译调试环境简介LoongArch是由龙芯中科公司研发，具有自主知识产权的处理架构。为了助力国产软硬件技术发展，实验选用了LoongArch作为编译器后端架构。虚拟机和宿主机都是x86架构，不能直接运行龙芯程序，需要通过交叉编译，让LoongArch后端代码在X86架构生成可执行代码。龙芯后端环境loongarch64-clfs-3.0-cross-tools-gcc-glibcqemu-6.2.50.loongarch64loongarch64-unknown-linux-gnu-gdb生成龙芯汇编、可执行文件模拟运行龙芯二进制文件调试生成的龙芯程序MENU·LoongArch交叉编译调试环境简介·LoongArch交叉编译及调试环境安装·获取LoongArch交叉编译及调试软件·传输LoongArch交叉编译及调试软件·解压安装LoongArch交叉编译及调试软件·查看LoongArch交叉编译及调试软件版本·验证使用LoongArch交叉编译及调试软件LoongArch交叉编译及调试环境安装步骤一：获取LoongArch交叉编译及调试软件

演示按需从以下任一网盘链接获取软件：链接一：/share/d8c57580-669d-11ee-8794-d542ef642531（校内）链接二：/s/1pI9bF3z6bsOOMwotLXXf1g?pwd=jdth（校外）LoongArch交叉编译及调试环境安装步骤二：传输LoongArch交叉编译及调试软件

演示通过scp命令将文件传入到虚拟机~/Downloads目录下。·scp-P端口号（为ssh端口）源文件目标文件夹步骤三：解压安装LoongArch交叉编译及调试软件

演示到~/Downloads目录下解压文件到/opt目录·sudotarxafloongarch64-clfs-3.0-cross-tools-gcc-glibc.tar.xz-C/opt·sudotarxafqemu-6.2.50.loongarch64.tar.gz-C/opt·sudotarxafgdb.tar.gz-C/opt·echo"exportPATH=\$PATH:/opt/cross-tools.gcc_glibc/bin:/opt/gdb/bin:/opt/qemu/bin">>~/.bashrc&&source~/.bashrcLoongArch交叉编译及调试环境安装步骤四：查看LoongArch交叉编译及调试软件版本

演示查看软件版本号是否正常输出·loongarch64-unknown-linux-gnu-gcc-v·qemu-loongarch64-version·loongarch64-unknown-linux-gnu-gdb-vLoongArch交叉编译及调试环境安装步骤五：验证使用LoongArch交叉编译及调试软件

演示解压test-env.tar.gz文件并进入该文件夹能看见如下文件，执行make命令验证安装test-envbubble-sort.Shello-world.Sinline-assembly.cMakefile使用make自动测试gcc和qemu是否安装成功内嵌汇编的c程序输出helloworld的汇编实现冒泡排序的汇编实现下期再见！Thanks！

语言解析器编译原理和技术CONTENT正则表达式Flex简介Bison简介Flex和Bison联动CONTENT正则表达式Flex简介Bison简介Flex和Bison联动正则表达式正则表达式是一种用于描述文本模式的强大工具，特别是在处理文本搜索、替换和验证等任务时非常有用。importre

def

find_email(text):

email_pattern=

r'\b[A-Za-z0-9._%+-]+@[A-Za-z0-9.-]+\.[A-Z|a-z]{2,}\b'

matches=re.findall(email_pattern,text)

returnmatches

text=

"我的电子邮件是example@，你可以联系我。"

emails=find_email(text)

foremailinemails:

print(email)正则表达式匹配文本输出：example@正则表达式正则表达式规则（仅列举部分）：[0-9]：匹配数字0-9中的一个字符；. ：匹配任何单个字符；*

：匹配前面的元素零次或多次，比如0*匹配由0构成的字符串；+ ：匹配前面的元素一次或多次；? ：匹配前面的元素零次或一次；\d ：匹配一个数字字符，等价于[0-9]；……正则表达式本次实验使用的正则表达式规则来自Flex文档安装完毕Flex后，可通过info指令打开，选择Patterns章节正则表达式正则表达式核心规则是通用的，可以在以下在线正则表达式平台学习：/front-end/854/正则表达式在线测试CONTENT正则表达式Flex简介Bison简介Flex和Bison联动FlexFlex（FastLexicalAnalyzerGenerator）是一种用于生成词法分析器的工具。Flex可以根据用户提供的正则表达式规则，将输入文本分割成一个个的词法单元（token），用于后续的语法分析或语义分析。FlexFlex工作流程以.l为后缀的源程序中的规则被转换成状态转换图，生成对应的代码，包括核心的yylex()函数，保存在lex.yy.c文件中。生成的lex.yy.c文件可以通过C编译为可执行文件。最终，可执行文件将输入流解析成一系列的标记（tokens）。Flexdemo/*filenamedemo.l*/%optionnoyywrap%{#include

<string.h>intchars=

0;intwords=

0;%}

%%[a-zA-Z]+

{chars+=

strlen(yytext);words++;}.

{}%%

int

main(){

yylex();

printf("look,Ifind%dwordsof%dchars\n",

words,chars);

return

0;}

编译和运行该demo.l文件，其实现了一个单词和字母的统计功能Flexdemo/*filenamedemo.l*/%optionnoyywrap%{#include

<string.h>intchars=

0;intwords=

0;%}

%%[a-zA-Z]+

{chars+=

strlen(yytext);words++;}.

{}%%

int

main(){

yylex();

printf("look,Ifind%dwordsof%dchars\n",

words,chars);

return

0;}

声明部分规则部分C代码部分Flex声明部分声明部分包含名称声明和选项设置，%{和%}之间的内容会被原样复制到生成的C文件头部，可用于编写C代码，如头文件声明和变量定义等。/*filenamedemo.l*/%optionnoyywrap%{#include

<string.h>intchars=

0;intwords=

0;%}声明部分生成的lex.yy.c中的内容原样复制Flex规则部分规则部分位于两个%%之间，包括多条规则，每个规则由正则表达式定义的模式和与之匹配的C代码动作组成。当词法分析程序识别出某模式时，执行相应的C代码。%%[a-zA-Z]+

{chars+=

strlen(yytext);words++;}.

{}%%共有两条规则Flex规则部分规则部分位于两个%%之间，包括多条规则，每个规则由正则表达式定义的模式和与之匹配的C代码动作组成。当词法分析程序识别出某模式时，执行相应的C代码。%%[a-zA-Z]+

{chars+=

strlen(yytext);words++;}.

{}%%共有两条规则正则表达式，该正则表达式匹配所有单词当匹配到该正则表达式时，执行的对应动作。其中yytext为匹配到的字符串。Flex规则部分规则部分位于两个%%之间，包括多条规则，每个规则由正则表达式定义的模式和与之匹配的C代码动作组成。当词法分析程序识别出某模式时，执行相应的C代码。%%[a-zA-Z]+

{chars+=

strlen(yytext);words++;}.

{}%%共有两条规则匹配任意内容不执行任何动作Flex规则部分Flex在进行词法分析时，可能会遇到二义性的情况。二义性指的是输入文本可以被多个正则表达式规则匹配的情况，导致分析器无法确定选择哪个规则。当存在二义性时，Flex采用以下策略解决：最长匹配原则（LongestMatchRule）：Flex默认采用最长匹配原则。当输入文本可以匹配多个规则时，选择匹配长度最长的规则。规则顺序优先级：Flex中规则的顺序决定了它们的优先级，按规则顺序进行匹配。Flex规则部分%%\+{returnADD;}={returnASSIGN;}\+={returnASSIGNADD;}%%对于以上规则，对于字符串“+=”，第三条规则“\+={returnASSIGNADD;}”被触发，遵循最长匹配原则，而不是分别触发一次第一条和第二条规则%%ABC{return

1;}[a-zA-Z]+{return

2;}%%对于以上规则，对于字符串“ABC”，第一条规则“ABC{return

1;}”被触发，遵循规则顺序优先级。尽管字符串“ABC”可以同时触发正则表达式“ABC”

和“[a-zA-Z]+”，但是“ABC”对应的规则优先被定义。FlexC代码部分C代码部分可包括main()函数，用于调用yylex()执行词法分析。yylex()是由Flex生成的词法分析例程，默认从stdin读取输入文本。

int

main(){

yylex();

printf("look,Ifind%dwordsof%dchars\n",

words,chars);

return

0;}

原样复制lex.yy.c文件中的内容FlexC代码部分C代码部分可包括main()函数，用于调用yylex()执行词法分析。yylex()是由Flex生成的词法分析例程，默认从stdin读取输入文本。

int

main(){

yylex();

printf("look,Ifind%dwordsof%dchars\n",

words,chars);

return

0;}

原样复制lex.yy.c文件中的内容yylex()是由Flex根据规则自动生成的，用于开始执行词法分析。其从stdin读取输入开始匹配。Flex中的关键变量在Flex中，以"yy"开头的变量和函数是Flex生成的词法分析器中的一些特定名称，用于处理词法分析过程。yyin、yyout、yytext、yyleng、yylex、yywrap……yytext：这是一个字符串变量，用于存储当前匹配的词法单元的文本。当Flex匹配成功时，yytext将包含匹配的字符串。yylex()：这是Flex生成的词法分析器的主函数。它用于从输入流中读取字符并进行词法分析，返回下一个词法单元的标识符。下期再见！Thanks！

语言解析器编译原理和技术编译原理课程组中国科学技术大学CONTENT正则表达式Flex简介Bison简介Flex和Bison联动BisonBison是一种工具，用于根据给定的语法规则生成语法分析器。Bison通过读取用户提供的上下文无关文法规则来生成这样的语法分析器。Bison采用上下文无关文法，采用LALR（Look-AheadLeft-to-RightRightmostderivation）方法进行语法分析。Bison被广泛应用于编译器设计、解析器生成和其他需要进行语法分析的领域。Bison源程序通常以.y为后缀。BisonDemo/*filename:bison_demo.y*//*Part1*/%{#include

<stdio.h>int

yylex(void);void

yyerror(const

char

*s);%}

%startreimu%tokenREIMU

%%reimu:REIMU{puts("\nFind\n");}%%

int

yylex(void){

intc=

getchar();

switch(c){

case

EOF:returnYYEOF;

case

'H':returnREIMU;

default:

returnYYUNDEF;

}}

/*filename:bison_demo.y*//*Part2*/

void

yyerror(const

char

*s){

fprintf(stderr,"%s\n",s);}

int

main(void){

yyparse();//启动解析

return

0;}编译和运行Bison源程序BisonDemo/*filename:bison_demo.y*//*Part1*/%{#include

<stdio.h>int

yylex(void);void

yyerror(const

char

*s);%}

%startreimu%tokenREIMU

%%reimu:REIMU{puts("\nFind\n");}%%

int

yylex(void){

intc=

getchar();

switch(c){

case

EOF:returnYYEOF;

case

'H':returnREIMU;

default:

returnYYUNDEF;

}}

Bison对语法规则进行解析得到C程序编译C程序得到可执行文件运行C程序输入H后，按Ctrl+D，此时执行规约reimu<-REIMU，并执行动作puts("\nFind\n")/*filename:bison_demo.y*//*Part2*/

void

yyerror(const

char

*s){

fprintf(stderr,"%s\n",s);}

int

main(void){

yyparse();//启动解析

return

0;}编译和运行Bison源程序BisonDemo/*filename:bison_demo.y*/%{#include

<stdio.h>int

yylex(void);void

yyerror(const

char

*s);%}

%startreimu%tokenREIMU

%%reimu:REIMU{puts(“\nFind\n");}%%

int

yylex(void){

intc=

getchar();

switch(c){

case

EOF:returnYYEOF;

case

'H':returnREIMU;

default:

returnYYUNDEF;

}}

void

yyerror(const

char

*s){

fprintf(stderr,"%s\n",s);}

int

main(void){

yyparse();//启动解析

return

0;}

声明部分定义部分规则部分C代码部分BisonDemo声明部分包括C语言代码、头文件引用、宏定义、全局变量定义和函数声明等内容，位于%{和%}之间。/*filename:bison_demo.y*/%{#include

<stdio.h>int

yylex(void);void

yyerror(const

char

*s);%}

%startreimu%tokenREIMU

%%reimu:REIMU{puts(“\nFind\n");}%%

int

yylex(void){

intc=

getchar();

switch(c){

case

EOF:returnYYEOF;

case

'H':returnREIMU;

default:

returnYYUNDEF;

}}

void

yyerror(const

char

*s){

fprintf(stderr,"%s\n",s);}

int

main(void){

yyparse();//启动解析

return

0;}

声明部分定义部分规则部分C代码部分BisonDemo定义部分进行结符和非终结符定义和声明，常见定义与声明包括%token、%union、%start、%type、%left、%right等。-%token:声明终结符的类型-%union:定义联合类型，用于在语法分析过程中传递数据类型信息-%start:指定语法分析器的起始符号-%type:指定非终结符的数据类型-%left:指定左结合的运算符-%right:指定右结合的运算符/*filename:bison_demo.y*/%{#include

<stdio.h>int

yylex(void);void

yyerror(const

char

*s);%}

%startreimu%tokenREIMU

%%reimu:REIMU{puts(“\nFind\n");}%%

int

yylex(void){

intc=

getchar();

switch(c){

case

EOF:returnYYEOF;

case

'H':returnREIMU;

default:

returnYYUNDEF;

}}

void

yyerror(const

char

*s){

fprintf(stderr,"%s\n",s);}

int

main(void){

yyparse();//启动解析

return

0;}

声明部分定义部分规则部分C代码部分BisonDemo规则部分由归约规则和动作组成。规则基本按照巴科斯范式（BNF）描述。规则中目标或非终端符放在左边，后跟一个冒号：然后是产生式的右边，之后是对应的动作（用{}包含）/*filename:bison_demo.y*/%{#include

<stdio.h>int

yylex(void);void

yyerror(const

char

*s);%}

%startreimu%tokenREIMU

%%reimu:REIMU{puts(“\nFind\n");}%%

int

yylex(void){

intc=

getchar();

switch(c){

case

EOF:returnYYEOF;

case

'H':returnREIMU;

default:

returnYYUNDEF;

}}

void

yyerror(const

char

*s){

fprintf(stderr,"%s\n",s);}

int

main(void){

yyparse();//启动解析

return

0;}

声明部分定义部分规则部分C代码部分BisonDemoC代码部分为C代码，会被原样复制到Bison生成的C文件中，这里一般自定义一些函数。主要包括调用Bison的语法分析程序yyparse()。其中yyparse函数由Bison根据语法规则自动生成，用于语法分析。/*filename:bison_demo.y*/%{#include

<stdio.h>int

yylex(void);void

yyerror(const

char

*s);%}

%startreimu%tokenREIMU

%%reimu:REIMU{puts(“\nFind\n");}%%

int

yylex(void){

intc=

getchar();

switch(c){

case

EOF:returnYYEOF;

case

'H':returnREIMU;

default:

returnYYUNDEF;

}}

void

yyerror(const

char

*s){

fprintf(stderr,"%s\n",s);}

int

main(void){

yyparse();//启动解析

return

0;}

声明部分定义部分规则部分C代码部分BisonDemoyylex和yyparse的关系：yyparse函数在需要词法单元时调用yylex函数，并从yylex返回的词法单元中获取相关信息进行语法分析。这样，yyparse可以根据词法分析器提供的词法单元逐步解析输入。int

yyparse(void){

......

if(yychar==YYEMPTY)

{

YYDPRINTF((stderr,"Readingatoken\n"));

yychar=

yylex();

}

......}生成的yyparse函数中，调用yylex函数得到相关信息/*filename:bison_demo.y*/%{#include

<stdio.h>int

yylex(void);void

yyerror(const

char

*s);%}

%startreimu%tokenREIMU

%%reimu:REIMU{puts(“\nFind\n");}%%

int

yylex(void){

intc=

getchar();

switch(c){

case

EOF:returnYYEOF;

case

'H':returnREIMU;

default:

returnYYUNDEF;

}}

void

yyerror(const

char

*s){

fprintf(stderr,"%s\n",s);}

int

main(void){

yyparse();//启动解析

return

0;}

CONTENT正则表达式Flex简介Bison简介Flex和Bison联动Flex&BisonDemo在Bisondemo中，使用自定义的yylex函数对字符串进行解析。如果将yylex函数替换成Flex生成的函数，即可实现Flex和Bison的联动：Flex进行词法分析，Bison对得到的Tokens进行语法分析；Bison在协同工作中担任主导角色生成yyparse函数；而Flex辅助生成yylex函数；yylex函数在yyparse函数执行过程中被调用。Flex&BisonDemo尝试使用Flex和Bison实现以下一个极简语法，以识别一个最简单的程序并输出其语法树。语法：program<-intmain(){statements}statements<-statementstatement<-;|return;程序：int

main(){

return;}Flex&BisonDemoFlex程序识别各种token关键字：int、main、return符号：{、}、（、）、；换行符等：\n、……program<-intmain(){statements}statements<-statementstatement<-;|return;Flex&BisonDemoFlex程序%optionnoyywrap%{#include

"bison.tab.h"

//引入Bison生成的头文件%}

%%"int"

{returnINT;}"main"

{returnMAIN;}"("

{returnLPAREN;}")"

{returnRPAREN;}"{"

{returnLBRACE;}"}"

{returnRBRACE;}";"

{returnSEMICOLON;}"return"

{returnRETURN;}\n

{/*忽略*/

}.

{

/*忽略*/

}%%在Bison程序中定义，由bison.tab.h传递给Flex程序Flex&BisonDemoBison程序：1.实现语法program<-intmain(){statements}statements<-statementstatement<-;|return;program:INTMAINLPARENRPARENLBRACEstatementsRBRACE;statements:statement;statement:SEMICOLON|RETURNSEMICOLON;Flex&BisonDemoBison程序：2.定义tokenstructTreeNode{

char*type;

structTreeNode*left;

structTreeNode*right;};......%union{

structTreeNode*node;

charop;}%tokenINTMAINLPARENRPARENLBRACERBRACESEMICOLONNEWLINERETURN%type<node>programstatementstatements%startprogramFlex&BisonDemoBison程序：3.结合语法定义动作，构建语法树program:INTMAINLPARENRPARENLBRACEstatementsRBRACE

{gt=createTreeNode(“Program”);//gt是一个全局变量

$$=

gt;

$$->left=$6;};

statements:statement{$$=

createTreeNode("statements");

$$->left=$1;};

statement:SEMICOLON

{$$=

createTreeNode("EmptyStatement");}

|RETURNSEMICOLON

{$$=

createTreeNode("ReturnStatement");};Flex&BisonDemoBison程序：/*filenamebison.ypart1声明与定义部分*/%{#include

<stdio.h>#include

"syntax_tree.h“

intyylex(void);voidyyerror(const

char*s);intyyparse();

//GlobalsyntaxtreestructTreeNode*gt;%}

%union{structTreeNode*node;charop;}

%tokenINTMAINLPARENRPARENLBRACERBRACESEMICOLONNEWLINERETURN%type<node>programstatementstatements%startprogramFlex&BisonDemoBison程序：/*filenamebison.ypart2规则部分*/%%program:INTMAINLPARENRPARENLBRACEstatementsRBRACE

{gt=createTreeNode(“Program”);//gt是一个全局变量

$$=

gt;

$$->left=$6;};statements:statement{$$=

createTreeNode("statements");

$$->left=$1;};

statement:SEMICOLON

{$$=

createTreeNode("EmptyStatement");}

|RETURNSEMICOLON

{$$=

createTreeNode("ReturnStatement");};%%Flex&BisonDemoBison程序：/*filenamebison.ypart3C代码部分*/struct

TreeNode*parse(){

yyparse();

returngt;}

voidyyerror(const

char*s){

fprintf(stderr,"%s\n",s);}Flex&BisonDemo编译与运行#编译#!/bin/bashbison

-d

bison.yflex

flex.lgcclex.yy.c

bison.tab.c

main.c

syntax_tree.c

#生成可执行文件a.out#运行➜catinput.txtintmain(){return;}

➜./a.out<input.txtProgram

Statements

ReturnStatementFlex&BisonDemoFlex和Bison联动的工作流Flex源程序(*.l)#include“*.tab.h”Bison输出头文件（*.tab.h)Bison输出文件（*.tab.c)Flex输出文件（lex.yy.c)Bison源文件（*.y)函数parse()bison–d*.yflex*.lFlex&Bison更多关于Flex的内容：➜infoflex(在命令行中执行)更多关于Bison的内容：/software/bison/manual/bison.html下期再见！Thanks！Lab1：源语言解析编译原理和技术编译原理课程组中国科学技术大学Lab1：源语言解析实验要求完成词法分析器：补全src/parser/lexical_analyzer.l完成语法分析器：补全src/parser/syntax_analyzer.yLab1相关目录结构项目编译位于项目目录下（labn）创建并进入build目录：mkdirbuildcdbuild使用cmake生成Makefile等：cmake..（寻找CMakeLists.txt文件，读取项目编译信息，生成Makefile等）使用make编译出最新的程序并安装到系统路径make–j（-j表示开启多线程编译，使用全部CPU核心）sudomakeinstall（安装到系统路径下，普通用户执行需要sudo权限）每次改动代码都需要重新执行第3步Lab1：源语言解析实验测试手动测试编译成功后，会在build文件夹下找到lexer和parser可执行文件，用于对Cminusf文件进行词法和语法分析；使用方法：lexer/parser<input_file>以1-return.cminus为例，运行lexer和parser的结果如下图所示voidmain(void){return;}1-return.cminuslexer运行示例lexer输出词法分析结果parser运行示例，parser输出分析树Lab1：源语言解析实验测试自动测试实验框架提供了te