GO/ast编程(二)-编译原理学习之语法分析

作者: 温岭夹糕 | 来源:发表于2024-01-12 15:41 被阅读0次

1.语法分析器的任务

语法分析器主要是将记号流转为语法树

image.png

语法分析器从词法分析器获取记号流，
语法分析器根据某种语言的语法规则构造出一棵语法分析树，并将其传递给编译器前端其余部分处理 image.png
我们也期望语法分析器能用易懂的方式来报告错误 image.png

2.上下文无关文法

2.1文法

文法是以有穷集合描述无穷集合的一个工具。
以汉语为例，我们无法列出全部句子，但我们可以列出规则，用这些规则来说明句子组成结构

比如“我是大学生”是一个汉语句子，
汉语句子可以由主语和谓语组成，
谓语可以由动词和直接宾语表示

我们采用EBNF来表示这种句子构成的规则

<句子>∷=<主语><谓语> 
<主语>∷=<代词>|<名词> 
<代词>∷=我|你|他 
<名词>∷=王明|学生|工人|英语 
<谓语>∷=<动词><直接宾语>
 <动词>∷=是|学习 
<直接宾语>∷=<代词>|<名词> 
/** EBFN([拓展巴克斯范式](https://www.zhihu.com/search?q=%E6%8B%93%E5%B1%95%E5%B7%B4%E5%85%8B%E6%96%AF%E8%8C%83%E5%BC%8F&search_source=Entity&hybrid_search_source=Entity&hybrid_search_extra=%7B%22sourceType%22%3A%22answer%22%2C%22sourceId%22%3A2868685525%7D)). 是一种简洁易读的语法描述. 
其中的一些符号说明如下: 
<> 用尖括号括起来的中文字表示语法构成成分.
::= 表示左部的语法单位由右部定义, 可读作"定义为". 
| 表示"或", 即多选项. 
**/

所以“我是大学生”符合上述规则，“我大学生是”不符合，它不是句子。用这些规则描述汉语，这样的语言描述成为汉语的文法

<句子>⇒<主语><谓语>
      ⇒<代词><谓语>
      ⇒我<谓语>
      ⇒你<动词><直接宾语>
      ⇒你是<直接宾语>
      ⇒你是<名词>
      ⇒你是大学生

2.2文法的形式定义

image.png

文法用G表示，由四个元素组成

Vt：终结符集合。终结符是文法所定义的语言基本符号，上述Vt={我，是，大学生}
Vn：非终结符集合，也叫语法变量，每个非终结符号表示一个终结符号串的集合
上述Vn={<句子>,<主语>,<谓语>,<代词>....}
P产生式的集合，每个产生式包括一个成为产生式头或左部的非终极符号，一个箭头，和一个产生式体或右部的由终结符号和非终结符号组成的序列
上述P={<句子>⇒<主语><谓语>,<句子>⇒<代词><谓语>....}
S开始符号，表示该文法最大的语法成分
上述S=<句子>

这也是上下文无关文法的四要素

2.3推导

给定文法G，从G的开始符S开始，用产生式的右部替换左侧的非终结符
此过程不断重复，直到不出现非终结符为止
最终的串称为句子
如上面“我是大学生”,S=<句子>，开始不断对产生式右部替换

<句子>⇒<主语><谓语>
      ⇒<代词><谓语>
      ⇒我<谓语>
      ⇒你<动词><直接宾语>
      ⇒你是<直接宾语>
      ⇒你是<名词>
      ⇒你是大学生

再来一个例子，有如下产生式

S=>NVN
N=> s | t | g | w
V=>e|d

S=S，Vn={S，N,V}，Vt={s,t,g,w,e,d}，开始替换成句子

S=>NVN
   =>N d N
   => s d w

sdw就是一个句子，当然不唯一
推导也分为最左推导(每次总选择最左侧的符号进行替换)和最右推导(反之)

2.4推导与分析树

我们也可以用树的形式来分析S=>NVN的推导过程

image.png

我们发现该树有以下特点：

每个内部节点代表非终结符
每个叶子节点代表终结符
每一步推导代表如何从双亲节点生成它的直接孩子节点

加法表达式的分析树例子
该加法例子的结论：分析树的含义取决于树的后序遍历
举例解释就是3+45可能会根据文法构造出不同的两棵树，一棵树后续遍历结果是(3+4)5=35
另一颗是3+4*5=23，两者结果不同

2.5二义性文法

给定G，如果存在句子s，它有两颗不同的分析树，那么称G是二义性文法，从编译角度看就是：

同一个程序有不同含义，因此运行结果不唯一

解决方案：文法的重写，写一个更好的

3.自顶向下分析

给定一个文法G和句子s，回答s是否能够从G推导？
我们的基本思想是：

从G的开始符号出发，随意推出某个句子t
比较t==s，是则回答是
t!=s，则回溯整个过程直到t==s

这种从开始符号出发推出句子，被称作自顶向下分析，因为要不停回溯，我们也能想到这种效率是多低

4.递归下降分析算法

是自顶向下的扩展，基本思想和分治差不多：

每个非终结符构造一个分析函数
用前看符号指导产生式规则的选择

5.LL(1)算法

LL（1）也是自顶向下算法中的一种扩展，跟词法分析器类似，目标也是产生一个语法分析器

6.LR(0)算法

LR0是自底向上算法中的一种
自底向上的基本思想也就是自顶向下的逆过程，从句子归约(从句子推导产生式)文法

image.png

7.SLR和LR（1）分析算法

视频在这里

8.语法制导的翻译

语法分析除了检查语法是否合法外，还得完成后续工作，比如：

类型检查
目标代码生成
中间代码生成
。。。
这些后续工作一般通过语法制导的翻译完成
在解析输入字符串时，在特定位置执行指定的动作；换而言之就是根据文法G把输入的字符串翻译为一串动作。
特定位置是通过“指定动作”(语义动作)嵌入到语法规则中指定的
如有以下文法

E->NUM+NUM

那么一个嵌入了语义动作的语法制导定义可以是

E -> NUM + { println("found op plus"); }NUM { println("value = " + ($1.value + $4.value)); }

这个例子花括号包围的代码就是语义动作，而其位置指定了在parse到什么地方的时候要执行该语义动作。例如第一组语义动作位于"+"之后、第二个NUM之前，那么parse到这个"+"之后就要执行这个语义动作。
总结：

给每条产生式P规则附加一个语义动作(一个代码片段)
语义动作的执行时机是产生式"归约"的时候

9.ast抽象语法树

image.png

image.png
因此需要对分析树进行进一步抽象，把无关的节点给砍掉

image.png
具体语法是语法分析器使用的语法，

抽象语法是用来表达语法结构的内部表示
在编译器中，为了定义抽象语法树，需要使用实现语言(go程序就用go语言)来定义一组数据结构

如下是c语言加法的抽象语法树定义

image.png

ast抽象树就是对文法G推导出的分析树的抽象！

10.go的语法分析

10.1文法

go的文法位于src/cmd/compile/internal/syntax/parser.go的注释中，go/parser中虽然也有，但还是这个比较完整

image.png
每一个go的源文件最终都会被解析成ast，ast的最顶层都是sourceFile

10.2go的ast结构体

go/ast/ast.go定义了抽象语法树AST的结构体：

抽象语法树由节点(Node)组成，节点类型主要有三种：表达式节点(Expressions and type nodes 即 ast.Expr)、语句节点（Statement nodes即ast.Stmt）和声明节点（Declaration nodes即 ast.Decl）。

// All node types implement the Node interface.
type Node interface {
  Pos() token.Pos // position of first character belonging to the node
  End() token.Pos // position of first character immediately after the node
}

// All expression nodes implement the Expr interface.
type Expr interface {
  Node
  exprNode()
}

// All statement nodes implement the Stmt interface.
type Stmt interface {
  Node
  stmtNode()
}

// All declaration nodes implement the Decl interface.
type Decl interface {
  Node
  declNode()
}

看到Pos()和End()方法返回的都是token.Pos我们就知道了所有节点都包含标识其在源代码中开头和结尾位置的信息，具体实现即全部节点类型在官方文档中都有指出

image.png
我们看到除了上面3个主要节点外还有其他的注释节点和包节点等

10.3语法解析

go/parser负责读取Token流生成AST，核心方法是ParserFile

func ParseFile(fset *token.FileSet, filename string, src any, mode Mode) (f *ast.File, err error)

type Mode uint

const (
    PackageClauseOnly    Mode             = 1 << iota // stop parsing after package clause
    ImportsOnly                                       // stop parsing after import declarations
    ParseComments                                     // parse comments and add them to AST
    Trace                                             // print a trace of parsed productions
    DeclarationErrors                                 // report declaration errors
    SpuriousErrors                                    // same as AllErrors, for backward-compatibility
    SkipObjectResolution                              // don't resolve identifiers to objects - see ParseFile
    AllErrors            = SpuriousErrors             // report all errors (not just the first 10 on different lines)
)

ParserFile会解析单个Go源代码，并返回相应的ast.File节点，所以go的一个文件就是会变成一颗ast
参数fset上一节学习过了，无非就是token.NewFileSet生成
src!=nil，函数会解析src中的源文件，此时filename无意义，仅用于记录位置信息时使用；若src==nil，则函数去解析filename指定的文件
如果无法读取源文件，则返回ast为nil和错误信息；如果读取了源文件，但发现语法错误，则返回部分AST(ast.Bad节点表示错误的代码片段)

    text, err := readSource(filename, src)
    if err != nil {
        return nil, err
    }

mode==0表示不选择其他解析器功能
ParserFile返回的ast.File是节点类型，和token.File文件不同

type File struct {
    Doc     *CommentGroup // associated documentation; or nil
    Package token.Pos     // package关键字的位置
    Name    *Ident        // 包名
    Decls   []Decl        // top-level declarations; or nil

    FileStart, FileEnd token.Pos       // start and end of entire file
    Scope              *Scope          // package scope (this file only)
    Imports            []*ImportSpec   // imports in this file
    Unresolved         []*Ident        // unresolved identifiers in this file
    Comments           []*CommentGroup // list of all comments in the source file
}

ast.File是ast的顶层节点，或者说根节点，一个File节点表示单个GO源文件
Doc指的通常是写在package之前的注释
Package和Name，分别存储package关键字的位置和包名(直观理解就是package后面跟的字符串)，Ident是标识符节点(Expr node类型)，具体如下

    // An Ident node represents an identifier.
    Ident struct {
        NamePos token.Pos // identifier position
        Name    string    // identifier name
        Obj     *Object   // denoted object; or nil
    }
type Object struct {
    Kind ObjKind
    Name string // declared name
    Decl any    // corresponding Field, XxxSpec, FuncDecl, LabeledStmt, AssignStmt, Scope; or nil
    Data any    // object-specific data; or nil
    Type any    // placeholder for type information; may be nil
}

object描述了一个已经命名的语言实体，如包，常量，类型，变量函数(包括方法) 或标签，这些也是Kind能表示的类型，也是Ident能表示的类型
回到ast.File

Decl是声明节点decl node的切片
Scope是作用域，那么这里就是包的作用域

type Scope struct {
    Outer   *Scope // 紧靠该作用域(外层)的作用域
    Objects map[string]*Object //在该作用域中声明的语言实体
}

Imports是文件导入的节点切片
Unresolved 为解析的标识符列表
Comments 注释的列表

ParseFile具体实现就不分析了，就是前文一大堆算法的汇总

10.4网页端输出抽象语法树

我们访问这个地址来看一下代码生成的抽象语法树
输入最基本的打印代码

image.png
我们可以看到它输出的抽象树结构不就是和Ast.File差不多吗

image.png

10.5 实战ast

ast直接输出是很难看懂的，我们借用ast包的方法来帮助观察
1.使用ast.Print直接输出，注意这里的模式选择解析注释的模式

func TestAstbuild(t *testing.T) {
    str :=
        `//@auther zjb
    package ast
    
    //@hi
    func main(){
    
    }
`
    src := []byte(str)
    fset := token.NewFileSet()
    f, err := parser.ParseFile(fset, "src.go", src, parser.ParseComments)
    if err != nil {
        t.Fatal(err)
    }
    ast.Print(fset, f)
}

2.利用Inspect和walk遍历AST，并获取包注解信息
inspect实际上是对Walk的封装

func Inspect(node Node, f func(Node) bool) {
    Walk(inspector(f), node)
}

func Walk(v Visitor, node Node)

一边打断点，一边改造Visitor

type AstVistor struct {
    Com map[string]string
}

func (v *AstVistor) Visit(node ast.Node) (w ast.Visitor) {
    switch x := node.(type) {
    case *ast.File:
        if x.Doc != nil && len(x.Doc.List) > 0 {
            for _, value := range x.Doc.List {
                text := strings.TrimLeft(value.Text, "//@")
                if text == "" {
                    return v
                }
                texts := strings.Split(text, " ")
                key := texts[0]
                val := ""
                if len(texts) > 1 {
                    val = texts[1]
                }
                v.Com[key] = val
            }
        }
        return v
    }
    return v
}

var _ ast.Visitor = (*AstVistor)(nil)

func TestAstbuild(t *testing.T) {
    str :=
        `//@auther zjb
    package ast
    
    //@hi
    func main(){
    
    }
`
    src := []byte(str)
    fset := token.NewFileSet()
    f, err := parser.ParseFile(fset, "src.go", src, parser.ParseComments)
    if err != nil {
        t.Fatal(err)
    }
    var v AstVistor
    v.Com = make(map[string]string)
    ast.Walk(&v, f)
    t.Log(v.Com)
}

输出

 map[auther:zjb]

参考

1.什么是文法

ast编程

GO/ast编程(二)-编译原理学习之语法分析

目录

1.语法分析器的任务

2.上下文无关文法

2.1文法

2.2文法的形式定义

2.3推导

2.4推导与分析树

2.5二义性文法

3.自顶向下分析

4.递归下降分析算法

5.LL(1)算法

6.LR(0)算法

7.SLR和LR（1）分析算法

8.语法制导的翻译

9.ast抽象语法树

10.go的语法分析

10.1文法

10.2go的ast结构体

10.3语法解析

10.4网页端输出抽象语法树

10.5 实战ast

参考

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读