自己动手写编译器:创建由 C 语言编译而成的语法解析器

2023-11-05 16:52

本文主要是介绍自己动手写编译器:创建由 C 语言编译而成的语法解析器,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

在上一章节,我们完成了由 c 语言设计的输入系统,本节我们看看如何在前一节的基础上完成一个由 c 语言设计并编译出来的词法解析器。整个解析器的基本设计思路是:
1,由我们上一节设计的输入系统将字符串从文件中读入。
2,由我们前面 GoLex 程序设计生成的状态机代码负责读入步骤 1 读入的字符串进行识别。
3,由 c 语言设计的模板代码驱动步骤1 和 2 的执行
我们看看具体的操作情况。首先我们需要将上一节设计的输入系统对应的函数放入头文件,在 CLex 项目中增加一个头文件l.h,其代码内容如下:

#ifndef __L_H
#define __L_H
extern  int ii_newfile(char* name);
extern  unsigned char* ii_text();
extern  int ii_flush(int force);
extern  int ii_length();
extern  int ii_lineno();
extern  unsigned char* ii_ptext();
extern  int ii_plength();
extern  int ii_plineno();
extern  unsigned  char* ii_mark_start();
extern  unsigned  char* ii_mark_end();
extern  unsigned  char* ii_move_start();
extern  unsigned  char* ii_to_mark();
extern  unsigned  char* ii_mark_prev();
extern  int ii_advance();
extern  int ii_flush(int force);
extern  int ii_fillbuf(unsigned  char* starting_at);
extern  int ii_look(int n);
extern  int ii_pushback(int n);
extern  void ii_term();
extern  void ii_unterm();
extern  int ii_input();
extern  void ii_unput(int c);
extern  int ii_lookahead(int n);
extern  int ii_flushbuf();
#endif

接着在 GoLex 中生成状态机的 c 语言代码,在 main.go 中代码如下(这些代码我们在前面章节讲解和调试过):

func main() {lexReader, _ := nfa.NewLexReader("input.lex", "output.py")lexReader.Head()parser, _ := nfa.NewRegParser(lexReader)start := parser.Parse()parser.PrintNFA(start)nfaConverter := nfa.NewNfaDfaConverter()nfaConverter.MakeDTran(start)nfaConverter.PrintDfaTransition()nfaConverter.MinimizeDFA()fmt.Println("---------new DFA transition table ----")nfaConverter.PrintMinimizeDFATran()//nfaConverter.DoPairCompression()nfaConverter.DoSquash()nfaConverter.PrintDriver()
}

上面代码运行后,我们会在本地生成 lex.yy.c 的文件,我们将文件中的所有代码拷贝到 CLex 的 main.c 文件中。接下来我们需要一段驱动输入系统读入数据,然后调用生成的状态机代码进行字符串识别的”胶水“代码,其名为 yylex,依然在 main.c 中,输入 yylex 函数对应的代码如下:

int yylex() {static int yystate = -1;int yylastaccept;int yyprev;int yynstate;int yylook;  //预读取字符int yyanchor;if(yystate == -1) {//将数据读入缓冲区ii_advance();//ii_advance 使得 Next 指针移动了一位,因此在我们还没有读入任何字符时,需要将其后退回去ii_pushback(1);}yystate = 0;yyprev = 0;yylastaccept = 0;ii_unterm();ii_mark_start();while(1) {/** 这里我们采取贪婪算法,如果当前识别的字符串已经进入识别状态,* 但是还有字符可以读取,那么我们先缓存当前识别状态,然后继续识别后续字符,* 直到文件抵达末尾或者输入的字符导致识别失败,此时我们再返回到上次识别状态* 进行处理,这种方法让我们尽可能获得能进入完成状态的最长字符串*/while(1) {yylook = ii_look(1);if (yylook != EOF) {yynstate = yy_next(yystate, yylook);break;} else {if (yylastaccept) {/** 如果文件数据读取完毕,并且我们抵达过完成状态,那么设置下一个状态为* 非法状态*/yynstate = YYF;break;}else if(yywrap()) {yytext = "";yyleng = 0;return 0;}else {ii_advance();ii_pushback(1);}}}// inner whileif (yynstate != YYF) {//跳转到下一个有效状态printf("Transation from state %d ", yystate);printf(" to state %d on <%c>\n", yynstate, yylook);if (ii_advance() < 0) {//缓冲区已满printf("Line %d, lexeme too long. Discarding extra characters.\n", ii_lineno());ii_flush(1);}yyanchor = Yyaccept[yynstate];if (yyanchor) {yyprev = yystate;yylastaccept = yynstate;ii_mark_end(); //完成一个字符串的识别}yystate = yynstate;} else {//跳转到无效状态,说明输入字符串不合法if (!yylastaccept) {//忽略掉非法字符printf("Ignoring bad input\n");ii_advance();} else {//回退到上一次接受状态ii_to_mark();if (yyanchor & 2) {//末尾匹配,将末尾回车符号放回缓冲区ii_pushback(1);}if (yyanchor & 1) {//开头匹配,忽略掉字符串开头的回车符号ii_move_start();}ii_term();//获取当前识别的字符串,极其长度和所在行号yytext = (char*) ii_text();yyleng = ii_length();yylineno = ii_lineno();printf("Accepting state%d, ", yylastaccept);printf("line %d: <%s>\n", yylineno, yytext);switch (yylastaccept) {/** 这里根据接受状态执行其对应的代码,实际上这里的代码* 后面会由 GoLex 生成*/case 3:case 4:printf("%s is a float number", yytext);return FCON;default:printf("internal error, yylex: unkonw accept state %d.\n", yylastaccept);break;}}ii_unterm();yylastaccept = 0;yystate = yyprev;}}// outer while
}

最后我们在 main 函数中调用 yylex 函数,驱动识别进程,main 函数内容如下:

int main() {int fd = ii_newfile("/Users/my/Documents/CLex/num.txt");if (fd == -1) {printf("value of errno: %d\n", errno);}yylex();return 0;
}

完成上面代码后,我们就对 c 语言代码进行编译,生成可执行文件,注意在上面代码中,我们使用输入系统的 ii_newfile 函数读入了一个名为 num.txt 的文件,这个文件的内容包含要识别的字符串,实际上这个文件地址可以作为程序参数输入,这里为了简单,我们直接写入代码中,在本地创建文件 num.txt,在里面输入一个数字字符串 3.14 然后保存,最后我们执行 c 语言代码编译的程序,输出结果如下:

Transation from state 0  to state 4 on <3>
Transation from state 4  to state 3 on <.>
Transation from state 3  to state 3 on <1>
Transation from state 3  to state 3 on <4>
Accepting state3, line 1: <
3.14>

这里我们可以看到,创建的 c 语言代码能正确的识别给定文件里的字符串为浮点数,同时他打印出了状态机在识别每个字符时的状态跳转,由此基本断定,我们 c 语言代码的设计基本正确,下一节我们的目的是将当前”手动“的阶段全部用程序来替代,例如将 GoLex 生成的代码进行粘贴等操作我们都用代码来完成,当这些代码生成和代码粘贴的动作都由 GoLex 完成后,那么它就变成了在编译原理工具链里有名的 Flex 应用,更多详细内容,请大家在 b 站搜索 Coding 迪斯尼,代码下载:
链接: https://pan.baidu.com/s/1MHkg0qNV8QIEqtC_y0XjnA 提取码: 1r4x

这篇关于自己动手写编译器:创建由 C 语言编译而成的语法解析器的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/351209

相关文章

IntelliJ IDEA2025创建SpringBoot项目的实现步骤

《IntelliJIDEA2025创建SpringBoot项目的实现步骤》本文主要介绍了IntelliJIDEA2025创建SpringBoot项目的实现步骤,文中通过示例代码介绍的非常详细,对大家... 目录一、创建 Spring Boot 项目1. 新建项目2. 基础配置3. 选择依赖4. 生成项目5.

Linux线程之线程的创建、属性、回收、退出、取消方式

《Linux线程之线程的创建、属性、回收、退出、取消方式》文章总结了线程管理核心知识:线程号唯一、创建方式、属性设置(如分离状态与栈大小)、回收机制(join/detach)、退出方法(返回/pthr... 目录1. 线程号2. 线程的创建3. 线程属性4. 线程的回收5. 线程的退出6. 线程的取消7.

MySQL 多列 IN 查询之语法、性能与实战技巧(最新整理)

《MySQL多列IN查询之语法、性能与实战技巧(最新整理)》本文详解MySQL多列IN查询,对比传统OR写法,强调其简洁高效,适合批量匹配复合键,通过联合索引、分批次优化提升性能,兼容多种数据库... 目录一、基础语法:多列 IN 的两种写法1. 直接值列表2. 子查询二、对比传统 OR 的写法三、性能分析

深入理解Go语言中二维切片的使用

《深入理解Go语言中二维切片的使用》本文深入讲解了Go语言中二维切片的概念与应用,用于表示矩阵、表格等二维数据结构,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习吧... 目录引言二维切片的基本概念定义创建二维切片二维切片的操作访问元素修改元素遍历二维切片二维切片的动态调整追加行动态

创建Java keystore文件的完整指南及详细步骤

《创建Javakeystore文件的完整指南及详细步骤》本文详解Java中keystore的创建与配置,涵盖私钥管理、自签名与CA证书生成、SSL/TLS应用,强调安全存储及验证机制,确保通信加密和... 目录1. 秘密键(私钥)的理解与管理私钥的定义与重要性私钥的管理策略私钥的生成与存储2. 证书的创建与

java使用protobuf-maven-plugin的插件编译proto文件详解

《java使用protobuf-maven-plugin的插件编译proto文件详解》:本文主要介绍java使用protobuf-maven-plugin的插件编译proto文件,具有很好的参考价... 目录protobuf文件作为数据传输和存储的协议主要介绍在Java使用maven编译proto文件的插件

Go语言中make和new的区别及说明

《Go语言中make和new的区别及说明》:本文主要介绍Go语言中make和new的区别及说明,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1 概述2 new 函数2.1 功能2.2 语法2.3 初始化案例3 make 函数3.1 功能3.2 语法3.3 初始化

Go语言中nil判断的注意事项(最新推荐)

《Go语言中nil判断的注意事项(最新推荐)》本文给大家介绍Go语言中nil判断的注意事项,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1.接口变量的特殊行为2.nil的合法类型3.nil值的实用行为4.自定义类型与nil5.反射判断nil6.函数返回的

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性:

Go语言数据库编程GORM 的基本使用详解

《Go语言数据库编程GORM的基本使用详解》GORM是Go语言流行的ORM框架,封装database/sql,支持自动迁移、关联、事务等,提供CRUD、条件查询、钩子函数、日志等功能,简化数据库操作... 目录一、安装与初始化1. 安装 GORM 及数据库驱动2. 建立数据库连接二、定义模型结构体三、自动迁