自己动手写编译器:通过语法编译构建语法树并实现中间代码生成
自己动手写编译器:通过语法编译构建语法树并实现中间代码生成
上一节我们手动构造了语法树，然后调用各个节点实现中间代码生成。语法树的构建由语法解析完成，本节我们要完成语法解析逻辑，在语法解析过程中构造语法树，然后再像上一节那样实现中间代码生成。
这里我们再次回顾一下左递归，例如表达式：
A -> A"a" | "b"|ε
它描述的字符串规律是字符b的前面包含0个或任意个字符a，在这个表达式中右边又有对A的引用，所以出现了左递归。在前面章节中我们给出了左递归的处理办法，这里我们看一个更加简单的处理方式。
左递归的目的是为了描述跟在它后面的不确定个数的对象，例如上面表达式中A”a”描述的就是不确定个数的字符”a”，处理这个问题时，我们可以将递归转换为循环从而破除左递归，因此我们实现上面语法解析时代码可以如下：
func A() error {
if 读取到字符"b":
return nil
for 当前读取到字符"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 inter
type Stmt struct {
Node *Node
after 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 inter
type Expression struct {
stmt *Stmt
expr 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_parser
import (
"errors"
"fmt"
"inter"
"lexer"
)
type SimpleParser struct {
lexer lexer.Lexer
top *Env
saved *Env
cur_tok lexer.Token //当前读取到的token
used_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 error
s.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.top
s.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.saved
return 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 = 4
case "float":
width = 8
case "char":
width = 1
}
p := inter.NewType(s.lexer.Lexeme, lexer.BASIC, width)
s.used_storage = s.used_storage + width
return 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_tok
tok := 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 error
for 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.ExprInterface
tok := 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 inter
type Seq struct {
Node *Node
stmt1 StmtInterface
stmt2 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