自己动手写编译器:通过语法编译构建语法树并实现中间代码生成

上一节我们手动构造了语法树，然后调用各个节点实现中间代码生成。语法树的构建由语法解析完成，本节我们要完成语法解析逻辑，在语法解析过程中构造语法树，然后再像上一节那样实现中间代码生成。

这里我们再次回顾一下左递归，例如表达式：

A -> A"a" | "b"|ε

它描述的字符串规律是字符b的前面包含0个或任意个字符a，在这个表达式中右边又有对A的引用，所以出现了左递归。在前面章节中我们给出了左递归的处理办法，这里我们看一个更加简单的处理方式。

左递归的目的是为了描述跟在它后面的不确定个数的对象，例如上面表达式中A"a"描述的就是不确定个数的字符"a"，处理这个问题时，我们可以将递归转换为循环从而破除左递归，因此我们实现上面语法解析时代码可以如下：

func A()  error {if 读取到字符"b":return nilfor 当前读取到字符"a" {获取下一个字符}if 当前读取字符"b"{return nil } else{err_s = "当前读取的字符不是b"return errors.New(err_s)}}

由于左递归是为了表示某些特定字符或字符串的重复，因此我们可以使用while或for循环来实现，也就是我们一直读入token, 如果给定token满足左递归描述的对象，那么循环就一直进行下去，一直到读取的token不再是左递归描述对象时，我们进行下一步处理。

在本节我们要进行的语法解析中存在两个左递归：

decls -> decls decl | ε
stmts -> stmts stmt | ε

第一个表达式用来描述变量定义，例如：

int a;
float b;
bool c;

我们看如何使用循环破除左递归，decls decl 表示0个或多个decl对象的出现，我们再看decl的特点，它总是以"int",“float”,"bool"开头，这些字符串都对应标签BASIC，这样根据前面我们描述的我们使用循环，看看读入的标签是不是BASIC，如果是那么就调用函数decl进行解析，于是decls解析实现的代码为：

func decls() {for s.lexer.Tag  == lexer.BASIC {decl()}
}

同理stmts stmt表示0个或多个stmt对象，因此我们看stmt以怎样的标签开头，目前我们只支持对表达式的解析，而表达式包含有单个分号，也就是";“，这表示空表达式，或者是单个数字或变量，例如"3;”, “a;”, 或者是赋值表达式"c = a;“, 或者它内部又嵌套”{…}“，因此stmt以分号，数字常量，变量名，或是左大括号开始，这么一来，我们只要没有读取到右大括号，也就是”}"，那么我们就进入stmt进行解析，于是stmts的解析代码逻辑如下：

func stmts() {for s.lexer.Lexeme != "}" {stmt()}
}

有了上面处理左递归的方法后，我们进入到语法解析的实现。在语法解析时，我们也要像前面表达式解析那样，需要构建节点的继承关系，如下图所示：
请添加图片描述
在语法解析过程中我们需要生成一系列节点对应不同的解析情况，所有节点都派生自stmt，然后每一种特定的语法结构例如if, for, while, do…while, break等都会对应相应节点，由于我们当前只解析算术表达式，因此我们还会构造一个Expression节点（没有显示在上图中），它继承自stmt，用来封装上图左边的算术表达式节点，首先我们定义语法节点要实现的接口，在inter.go中添加接口定义如下：

type StmtInterface interface {NodeInterface //start, end对应语句的起始标签和结束标签号码Gen(start uint32, end uint32) 
}

然后我们实现节点stmt，增加stmt.go文件，实现代码如下：

package intertype Stmt struct {Node      *Nodeafter     uint32        //用于生成跳转标签enclosing StmtInterface //用于break语句
}func NewStmt(line uint32) *Stmt {return &Stmt{Node:      NewNode(line),after:     0,enclosing: nil,}
}func (s *Stmt) Errors(str string) error {return s.Node.Errors(str)
}func (s *Stmt) NewLabel() uint32 {return s.Node.NewLabel()
}func (s *Stmt) EmitLabel(i uint32) {s.Node.EmitLabel(i)
}func (s *Stmt) Emit(code string) {s.Node.Emit(code)
}func (s *Stmt) Gen(start uint32, end uint32) {//这里需要子节点来实现}

stmt节点仅仅给出了定义的接口，接口具体的实现内容需要它的子类节点实现，由于我们要使用Express节点来封装算术表达式节点，因此我们也要实现它，增加Expression.go，实现代码如下：

package intertype Expression struct {stmt *Stmtexpr ExprInterface
}func NewExpression(line uint32, expr ExprInterface) *Expression {return &Expression{stmt: NewStmt(line),expr: expr,}
}func (e *Expression) Errors(str string) error {return e.stmt.Errors(str)
}func (e *Expression) NewLabel() uint32 {return e.stmt.NewLabel()
}func (e *Expression) EmitLabel(i uint32) {e.stmt.EmitLabel(i)
}func (e *Expression) Emit(code string) {e.stmt.Emit(code)
}func (e *Expression) Gen(start uint32, end uint32) {e.expr.Gen()
}

它的逻辑很简单，就是封装了ExprInterface接口对象，它对应的Gen接口用于生成语句对应的中间代码，它转而调用它封装的接口对象来实现代码生成。接下来我们实现语法解析逻辑，删除list_parser.go里面原来的代码，新增代码如下：

package simple_parserimport ("errors""fmt""inter""lexer"
)type SimpleParser struct {lexer        lexer.Lexertop          *Envsaved        *Envcur_tok      lexer.Token //当前读取到的tokenused_storage uint32 //当前用于存储变量的内存字节数
}func NewSimpleParser(lexer lexer.Lexer) *SimpleParser {return &SimpleParser{lexer: lexer,top:   nil,saved: nil,}
}func (s *SimpleParser) Parse() {s.program()
}func (s *SimpleParser) program() {s.top = nil//stmt 其实是seq所形成的队列的头结点stmt := s.block()begin := stmt.NewLabel()after := stmt.NewLabel()stmt.EmitLabel(begin)stmt.Gen(begin, after)stmt.EmitLabel(after)}func (s *SimpleParser) matchLexeme(str string) error {if s.lexer.Lexeme == str {return nil}err_s := fmt.Sprintf("error token , expected:%s , got:%s", str, s.lexer.Lexeme)return errors.New(err_s)
}func (s *SimpleParser) matchTag(tag lexer.Tag) error {if s.cur_tok.Tag == tag {return nil}err_s := fmt.Sprintf("error tag, expected:%d, got %d", tag, s.cur_tok.Tag)return errors.New(err_s)
}func (s *SimpleParser) move_backward() {s.lexer.ReverseScan()
}func (s *SimpleParser) move_forward() error {var err errors.cur_tok, err = s.lexer.Scan()return err
}

上面代码中实现的是辅助函数和解析起始函数，program函数启动解析流程，move_forward用于读取下一个字符串或是标签，move_backward拥有回滚当前读取的标签或字符串，下面我们进入解析逻辑的实现:

func (s *SimpleParser) block() inter.StmtInterface {// block -> "{" decls statms "}"err := s.move_forward()if err != nil {panic(err)}err = s.matchLexeme("{")if err != nil {panic(err)}err = s.move_forward()if err != nil {panic(err)}s.saved = s.tops.top = NewEnv(s.top)err = s.decls()if err != nil {panic(err)}stmt := s.stmts()if err != nil {panic(err)}err = s.matchLexeme("}")if err != nil {panic(err)}s.top = s.savedreturn stmt
}func (s *SimpleParser) decls() error {/*decls -> decls decl | εdecls 表示由零个或多个decl组成，decl对应语句为:int a; float b; char c;等，其中int, float, char对应的标号为BASIC,在进入到这里时我们并不知道要解析多少个decl,一个处理办法就是判断当前读到的字符串标号，如果当前读到了BASIC标号，那意味着我们遇到了一个decl对应的声明语句，于是就执行decl对应的语法解析，完成后我们再次判断接下来读到的是不是还是BASIC标号，如果是的话继续进行decl解析，由此我们可以破除左递归*/for s.cur_tok.Tag == lexer.BASIC {err := s.decl()if err != nil {return err}}return nil
}func (s *SimpleParser) getType() (*inter.Type, error) {err := s.matchTag(lexer.BASIC)if err != nil {return nil, err}width := uint32(4)switch s.lexer.Lexeme {case "int":width = 4case "float":width = 8case "char":width = 1}p := inter.NewType(s.lexer.Lexeme, lexer.BASIC, width)s.used_storage = s.used_storage + widthreturn p, nil
}func (s *SimpleParser) decl() error {p, err := s.getType()if err != nil {return err}err = s.move_forward()if err != nil {return err}//这里必须复制，因为s.cur_tok会不断变化因此不能直接传入s.cur_toktok := lexer.NewTokenWithString(s.cur_tok.Tag, s.lexer.Lexeme)id := inter.NewID(s.lexer.Line, tok, p)sym := NewSymbol(id, p)s.top.Put(s.lexer.Lexeme, sym)err = s.move_forward()if err != nil {return err}err = s.matchLexeme(";")if err != nil {return err}err = s.move_forward()return err
}func (s *SimpleParser) stmts() inter.StmtInterface {if s.matchLexeme("}") == nil {return inter.NewStmt(s.lexer.Line)}//注意这里，seq节点通过递归形成了一个链表return inter.NewSeq(s.lexer.Line, s.stmt(), s.stmts())
}func (s *SimpleParser) stmt() inter.StmtInterface {return s.expression()
}func (s *SimpleParser) expression() inter.StmtInterface {if s.matchTag(lexer.ID) == nil {s.move_forward()if s.matchTag(lexer.ASSIGN_OPERATOR) == nil {s.move_backward()s.move_backward() //回退到变量名return s.assign()}s.move_backward()}expression := inter.NewExpression(s.lexer.Line, s.expr())return expression
}func (s *SimpleParser) assign() inter.StmtInterface {s.move_forward()sym := s.top.Get(s.lexer.Lexeme)if sym == nil {err_s := fmt.Sprintf("undefined variable with name: %s", s.lexer.Lexeme)err := errors.New(err_s)panic(err)}s.move_forward() //读取=s.move_forward() //读取 = 后面的字符串expr := s.expr()set, err := inter.NewSet(sym.id, expr)if err != nil {panic(err)}err = s.matchLexeme(";")if err != nil {panic(err)}s.move_forward()expression := inter.NewExpression(s.lexer.Line, set)return expression
}func (s *SimpleParser) expr() inter.ExprInterface {x := s.term()var err errorfor s.matchLexeme("+") == nil || s.matchLexeme("-") == nil {tok := lexer.NewTokenWithString(s.cur_tok.Tag, s.lexer.Lexeme)s.move_forward()x, err = inter.NewArith(s.lexer.Line, tok, x, s.term())if err != nil {panic(err)}}return x
}func (s *SimpleParser) term() inter.ExprInterface {x := s.factor()return x
}func (s *SimpleParser) factor() inter.ExprInterface {var x inter.ExprInterfacetok := lexer.NewTokenWithString(s.cur_tok.Tag, s.lexer.Lexeme)if s.matchTag(lexer.NUM) == nil {t := inter.NewType("int", lexer.BASIC, 4)x = inter.NewConstant(s.lexer.Line, tok, t)} else if s.matchTag(lexer.REAL) == nil {t := inter.NewType("float", lexer.BASIC, 8)x = inter.NewConstant(s.lexer.Line, tok, t)} else {sym := s.top.Get(s.lexer.Lexeme)if sym == nil {err_s := fmt.Sprintf("undefined variable with name: %s", s.lexer.Lexeme)err := errors.New(err_s)panic(err)}x = sym.id}s.move_forward()return x
}

上面代码逻辑要想重复理解，最好还是看我的调试演示视频，在b站搜索Coding迪斯尼即可。其中有一些要点需要进一步解析，首先是stmts函数的实现，它在内部以递归的方式来构建一个Seq节点，代码如下：

return inter.NewSeq(s.lexer.Line, s.stmt(), s.stmts())

Seq节点也是继承自stmt的子节点，它的作用是把一系列语句连成队列，这样就能实现一连串中间代码生成，我们先看它的实现，在inter中新建seq.go然后增加代码如下：

package intertype Seq struct {Node  *Nodestmt1 StmtInterfacestmt2 StmtInterface
}func NewSeq(line uint32, stmt1 StmtInterface, stmt2 StmtInterface) *Seq {return &Seq{Node:  NewNode(line),stmt1: stmt1,stmt2: stmt2,}
}func (s *Seq) Errors(str string) error {return s.Node.Errors(str)
}func (s *Seq) NewLabel() uint32 {return s.Node.NewLabel()
}func (s *Seq) EmitLabel(i uint32) {s.Node.EmitLabel(i)
}func (s *Seq) Emit(code string) {s.Node.Emit(code)
}func (s *Seq) Gen(start uint32, end uint32) {_, ok1 := s.stmt1.(*Stmt)_, ok2 := s.stmt2.(*Stmt)if ok1 {s.stmt2.Gen(start, end)} else if ok2 {s.stmt1.Gen(start, end)} else {label := s.Node.NewLabel()s.stmt1.Gen(start, label)s.Node.EmitLabel(label)s.stmt2.Gen(label, end)}
}

它的实现有两个重要字段，分别是构造函数传入的stmt1和stmt2，这两个字段能够让Seq节点形成一个链表形式，假设我们要解析的代码如下：

 x = 1; y = 3.14;c = x + y;

那么stmts执行后，构造的Seq节点会形成如下链表结构：
请添加图片描述
从上图看出，在stmts调用后，它创建了以Seq节点构成的队列，Seq的stmt2字段可以看做是队列的next指针，指向下一个Seq节点，stmt1节点指向Expression节点，里面又包含了相应的ExprInterface节点，当执行语法解析时，我们从头结点开始依次执行，当末尾节点也完成其对应的中间代码生成后，所有代码的中间代码生成就完成了。

由于本节代码逻辑较为复杂，请在b站搜索Coding迪斯尼查看讲解和调试演示视频，本节代码下载路径为：链接: https://pan.baidu.com/s/1KV_KQrWMUjFCDnDiqwwZWg 提取码: p12q，更多干货在这里：http://m.study.163.com/provider/7600199/index.htm?share=2&shareId=7600199

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/40904.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

安卓原神QQ机器人搭建教程

安卓原神QQ机器人搭建教程

1，下载安装Termux 下载地址：https://f-droid.org/packages/com.termux/ 滑到下面点击这个 2，打开Termux，安装Ubuntu 安装模拟权限git，python，执行下面命令 pkg install proot git python -y 3&#xff…
阅读更多...
如何在windows电脑上完成原神签到、祈愿抽卡分析等功能

如何在windows电脑上完成原神签到、祈愿抽卡分析等功能

一款开源的游戏辅助工具——原神助手。支持原神签到、祈愿抽卡分析、查看便签状态和游戏详细数据等。 开发者自述也是偶然间接触到《原神》，于是一发不可收拾，爱上这款游戏了。 在游戏中，如果要查看角色信息等内容，就必须需要登…
阅读更多...
不同服务器的ps4账号吗,原神PC与PS4互通数据吗 不同平台数据互通分析

不同服务器的ps4账号吗,原神PC与PS4互通数据吗 不同平台数据互通分析

原神最近上线了pc版本，那么，你知道PC与PS4互通吗？这是很多玩家关心的问题，不同的平台，数据能否互通呢？比如说，不同平台是否可以一起玩，不同平台帐号是否可以切换，下面就为…
阅读更多...
如何在 Mac 上玩原神？简单三步流畅运行

如何在 Mac 上玩原神？简单三步流畅运行

该方法也是本人一点点摸索出来的，花了很久，已经帮大家踩过坑了，该方法是最简单方便的，而且画质高、运行流畅，甘雨姐姐我来了~ 注意此方法只支持 M 系列芯片 一、安装 playCover github 源码地址 ：https:/…
阅读更多...
指令微调数据集整理

指令微调数据集整理

文章目录 开源指令数据集斯坦福数据链家数据Baize(基于少量种子问题的对话数据) 垂直领域数据集医疗领域的英文数据医疗领域的中文数据法律领域中文数据 COIG数据集（可商用的中文数据集） 开源指令数据集 斯坦福数据 斯坦福52K英文指令数据：…
阅读更多...
Linux下使用Samba做域控

Linux下使用Samba做域控

AI画妹子的工作先暂告一段落。毕竟戗行也是要有门槛的。 企业中使用Windows Server使用活动目录集中管理PC、服务器是很成熟的方案。突然想到，如果有一天出于某种原因不再使用微软方案了，AD该如何替代？问了一下chatGPT，它说&…
阅读更多...
LINUX下设置postgresql的登录密码

LINUX下设置postgresql的登录密码

1、postgresql登录密码主要是修改2个方向：首先用户有密码，其次是在配置文件中设置登录的限制参数 2、修改密码： alter role postgres with password Postgres; 提示面修改完成 3、修改配置文件pg_hub.conf,在IPV4下或者本地local下&#x…
阅读更多...
获取 Panabit Linux 版 root 密码

获取 Panabit Linux 版 root 密码

面包多 - Panabit - root 密码重置工具https://mbd.pub/o/bread/mbd-Y5yTk5hx 可以重置 Panabit Linux 版本的 root 密码，直接获取 root 权限。 下载并在 Panabit 应用商店手动安装后就能看到列表中有新增 root 密码重置工具 打开 工具页面就可以对 root 密码进行重…
阅读更多...
PostgreSQL数据库设置登录数据库密码

PostgreSQL数据库设置登录数据库密码

PostgreSQL数据库安装完以后会默认创建一个管理员的账号postgres用户，默认登录时是不需要密码验证就可以直接登录的 修改用户登录认证密码有两种方式： 1、用命令行的sql语句来进行修改 登录到PostgreSQL数据库里 [rootnode1 ~ 10:51:32]# su postgres b…
阅读更多...
phpMyAdmin中config.inc.php设置密码和修改密码的方法

phpMyAdmin中config.inc.php设置密码和修改密码的方法

phpMyAdmin有3种授权模式： 1. cookie: 显示一个web登录页面，输入mysql的用户名和密码，然后进入管理界面。 $cfg[Servers][$i][auth_type] cookie; /* Server parameters */ $cfg[Servers][$i][host] localhost; $cfg[Servers][$i][connect_…
阅读更多...
使用pgAdmin 4来修改PostgreSQL中的用户密码

使用pgAdmin 4来修改PostgreSQL中的用户密码

参考博客： https://blog.csdn.net/solocoder/article/details/100593380 1、首先是打开我们的软件：pgAdmin 4.app运行起来 2、浏览器会默认打开一个界面如下： 3、然后是依次找到如下的 Servers-> PostgreSQL 11->Login/Group Roles-&…
阅读更多...
ChatGPT一出，这10大职业可能先丢饭碗

ChatGPT一出，这10大职业可能先丢饭碗

转自：新智元 编辑：David 【导读】ChatGPT一出，很多人害怕自己的工作会被AI取代。最近，有外媒盘点了最可能被ChatGPT取代10大高危职位。 自从去年11月发布以来，OpenAI的ChatGPT已经被用来写求职信，创作儿童读…
阅读更多...
Langchain-agent入门笔记（1）

Langchain-agent入门笔记（1）

LangChain里的Agent实现 官方模块介绍文档：Agents — 🦜🔗 LangChain 0.0.191 官网API文档：Agents — 🦜🔗 LangChain 0.0.191 核心要点： （1）需要依赖于用户输入的未…
阅读更多...
5分钟带你了解Android Room

5分钟带你了解Android Room

1、前言 最近在开发中，Room用的比较多，时不时要查资料，干脆写一篇Room的使用和Room的封装。如果写的不好，或者有错误之处，恳请在评论、私信、邮箱指出，万分感谢🙏 2、添加依赖 dependencies …
阅读更多...
AI自动生成代码，是时候冷静下来思考如何保障代码安全了

AI自动生成代码，是时候冷静下来思考如何保障代码安全了

HDC期间可参与华为开发者大会Check新人抽奖活动，活动链接在文末。 华为开发者大会2023将于7月7日与各位开发者进行见面，本次大会的主题演讲内容为：AI重塑千行百业。 自从AI聊天被推出之后，其热度就一直是高居不下。身边的小伙伴们…
阅读更多...
如何将数据表格快速转换成LaTeX格式？

如何将数据表格快速转换成LaTeX格式？

1.首先，在这个网站Comprehensive TEX Archive Network中下载宏文件。不要担心内存问题，很小的，下载后只有几百k。 2.其次，打开你的excel，将下载后的文件直接拖拽到excel表中，excel表格顶部会出现加载项这个…
阅读更多...
油猴Tampermonkey及脚本使用

油猴Tampermonkey及脚本使用

用Chrome浏览器的应该都知道，Chrome的优势之一就是有各种拓展的插件，使得我们浏览，工作效率都更高。 今天给大家推荐的一款”神器插件”叫 油猴，英文为 Tampermonkey 油猴是什么 Tampermonkey 是一款浏览器脚本管理插件&#x…
阅读更多...
油猴（Tampermonkey）使用教程

油猴（Tampermonkey）使用教程

油猴有很大的可玩性，里面只有你想不到的，没有他做不到的。下面是油猴的安装步骤以及使用方法~~ 安装 1.win10系统下，打开“开始”，找到微软的商店 2.打开之后，右上角搜索Tampermonkey。 3.安装油猴APP。&#xff08…
阅读更多...
超简单安装油猴（tampermonkey）脚本及使用教程

超简单安装油猴（tampermonkey）脚本及使用教程

超简单的油猴安装教程 第一步第二步第三步 第一步 下载Tampermonkey.crx (1.24MB) 提取码：nb1l 第二步 点击谷歌浏览器右上角，找到更多工具，然后点击拓展程序。 打开开发者模式 第三步 简单拖拽，把下载好的文件拖拽进第二步…
阅读更多...
Chrome油猴(Tampermonkey)脚本使用及常用脚本分享

Chrome油猴(Tampermonkey)脚本使用及常用脚本分享

在我们使用浏览器的时候总是抱怨他的功能不够强大，缺少这个缺少那个，那么好，浏览器支持的一强大的功能-----扩展，也就是我们常说的插件，在这里我要介绍的是一款特别好用的插件，用来管理用户的脚本&#xff…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023