lex-yacc
lex是一种词法分析器，可以识别文本中的词汇模式，模式可以用正则表达式表示。通过lex编译l文件(词法文件)就可以生产对应的c代码.lex可以参数一系列标记，如果我们想当某个标记序列出现时执行某一动作，该怎么实现呢？Yacc该出场了。通过yacc编译y文件(语法文件)就可以产生对应的c程序了
Yacc&Lex
Lex
lex是一种词法分析器，可以识别文本中的词汇模式，模式可以用正则表达式表示。通过lex编译l文件(词法文件)就可以生产对应的c代码，然后编译连接c代码就可以生成词法分析器了。
一个l文件分为三个部分，每部分通过双百分号(%%)分割。如下所示：
... definitions ...
%%
... rules ...
%%
... subroutines ...
definitions 部分用于定义模式、C语言变量、以及包含c头文件等。 rules 部分用户定义模式对应的动作。 subroutines 部分用于定义c函数等。
一个简单的l文件例子，test.l。
%{
int yylineno;
%}
%%
^(.*)\n printf("%4d\t%s", ++yylineno, yytext);
%%
int main(int argc, char *argv[]) {
yyin = fopen(argv[1], "r");
yylex();
fclose(yyin);
}
int yywrap(void) {
return 1;
}
首先这个l文件在definitions 部分定义了一个int型变量yylineno用于记录行号。然后，在rules定义了一个模式动作：当遇到一行的结尾时，输出当前行号，并输出当前行内容。最后在subroutines部分定义了一个c语言main函数,读取文件，并实现yywrap并返回1表示停止解析。
Yacc( Yet Another Compiler Compiler)
Yacc 的 GNU 版叫做 Bison。它是一种工具，将一种编程语言的语法翻译成针对此种语言的 Yacc 语法解析器。从上文中我们可以知道lex可以参数一系列标记，如果我们想当某个标记序列出现时执行某一动作，该怎么实现呢？Yacc该出场了。通过yacc编译y文件(语法文件)就可以产生对应的c程序了；生成的c代码通过编译链接就可以生产语法分析器了。但是，语法分析的前提是词法分析，因此我们需要lex出现输入文件并生成标记。在讲解y文件(语法文件)之前我们假设以及存在如下l文件(词法文件)：
%{
#include <stdio.h>
#include "y.tab.h"
%}
%%
[0-9]+ return NUMBER;
heat return TOKHEAT;
on|off return STATE;
target return TOKTARGET;
temperature return TOKTEMPERATURE;
\n /* ignore end of line */;
[ \t]+ /* ignore whitespace */;
%%
这个l文件主要是参数y文件定义的各种token，大家可以看到它的subroutines部分为空，因为该词法分析器的结果直接输出到语法分析器，因此不需要额外的函数。下面的y文件都依赖于该l文件。 一个y文件(语法文件)同样包含definitions、rules、subroutines三个部分，每部分同样通过双百分号(%%)分割。各个部分的作用l文件的对应部分也基本一致。 一个简单的y文件例子，test.y。
%{
#include <stdio.h>
#include <string.h>
void yyerror(const char *str);
%}
%token NUMBER TOKHEAT STATE TOKTARGET TOKTEMPERATURE
%%
commands: /* empty */
| commands command
;
command:
heat_switch
|
target_set
;
heat_switch:
TOKHEAT STATE
{
printf("\tHeat turned on or off\n");
}
;
target_set:
TOKTARGET TOKTEMPERATURE NUMBER
{
printf("\tTemperature set\n");
}
;
%%
void yyerror(const char *str)
{
fprintf(stderr,"error: %s\n",str);
}
int yywrap()
{
return 1;
}
main()
{
yyparse();
}
该y文件的definitions部分声明了一个函数，并定义了一系列标记(TOKEN)。然后在rules部分定义了四个模式序列对应(语句)的动作，其中commands是一个递归定义。最后在subroutines部分定义了一个c语言main函数,读取文件，并实现yywrap并返回1表示停止解析。这个y文件实现了以下功能
输入：heat on
输出：Heat turned on or off
输入：target temperature 22
输出：New temperature set!
lex与yacc结合
也许你已经注意到了，l文件的definitions部分往往要包含#include “y.tab.h”。而y.tab.h是yacc对y文件编译后产生的c源文件。因此y文件必须先于l文件进行编译成c源文件，然后将l文件产生的c文件和y文件产生的c文件编译连接生成语法解析器。具体步骤见图
Golang语法解析
AST
Go语法结构(在go/ast当中)
// 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()
}
语法有三个主体,表达式(expression),语句(statement),声明(declaration),Node是基类,用于标记该节点的位置的开始和结束.
整个内容其实就是定义了源文件中可能出现的语法结构.列表如下,这个列表很长,扫一眼就可以,具体可以再回来看.
- 普通Node,不是特定语法结构,属于某个语法结构的一部分.
- Comment 表示一行注释 // 或者 / /
- CommentGroup 表示多行注释
- Field 表示结构体中的一个定义或者变量,或者函数签名当中的参数或者返回值
- FieldList 表示以”{}”或者”()”包围的Filed列表
- Expression & Types (都划分成Expr接口)
- BadExpr 用来表示错误表达式的占位符
- Ident 比如报名,函数名,变量名
- Ellipsis 省略号表达式,比如参数列表的最后一个可以写成arg…
- BasicLit 基本字面值,数字或者字符串
- FuncLit 函数定义
- CompositeLit 构造类型,比如{1,2,3,4}
- ParenExpr 括号表达式,被括号包裹的表达式
- SelectorExpr 选择结构,类似于a.b的结构
- IndexExpr 下标结构,类似这样的结构 expr[expr]
- SliceExpr 切片表达式,类似这样 expr[low:mid:high]
- TypeAssertExpr 类型断言类似于 X.(type)
- CallExpr 调用类型,类似于 expr()
- StarExpr 表达式,类似于 X
- UnaryExpr 一元表达式
- BinaryExpr 二元表达式
- KeyValueExp 键值表达式 key:value
- ArrayType 数组类型
- StructType 结构体类型
- FuncType 函数类型
- InterfaceType 接口类型
- MapType map类型
- ChanType 管道类型
Statements
- BadStmt 错误的语句
- DeclStmt 在语句列表里的申明
- EmptyStmt 空语句
- LabeledStmt 标签语句类似于 indent:stmt
- ExprStmt 包含单独的表达式语句
- SendStmt chan发送语句
- IncDecStmt 自增或者自减语句
- AssignStmt 赋值语句
- GoStmt Go语句
- DeferStmt 延迟语句
- ReturnStmt return 语句
- BranchStmt 分支语句 例如break continue
- BlockStmt 块语句 {} 包裹
- IfStmt If 语句
- CaseClause case 语句
- SwitchStmt switch 语句
- TypeSwitchStmt 类型switch 语句 switch x:=y.(type)
- CommClause 发送或者接受的case语句,类似于 case x <-:
- SelectStmt select 语句
- ForStmt for 语句
- RangeStmt range 语句
Declarations
- Spec type
- Import Spec
- Value Spec
- Type Spec
- BadDecl 错误申明
- GenDecl 一般申明(和Spec相关,比如 import “a”,var a,type a)
- FuncDecl 函数申明
Files and Packages
- File 代表一个源文件节点,包含了顶级元素.
- Package 代表一个包,包含了很多文件.
Parser
package main
import (
"go/ast"
"go/parser"
"go/token"
)
func main() {
fset := token.NewFileSet()
f, err := parser.ParseFile(fset, "", `
package main
func main(){
// comments
x:=1
go println(x)
}
`, parser.ParseComments)
if err != nil {
panic(err)
}
ast.Print(fset, f)
}
output:
0 *ast.File {
1 . Package: 2:1 |PACKAGE token
2 . Name: *ast.Ident { |IDENT token
3 . . NamePos: 2:9 |
4 . . Name: "main" |
5 . } |整个构成了顶部的 package main
6 . Decls: []ast.Decl (len = 1) { |最上层的申明列表
7 . . 0: *ast.FuncDecl { |func main的函数申明
8 . . . Name: *ast.Ident { |IDENT token
9 . . . . NamePos: 3:6 |
10 . . . . Name: "main" |
11 . . . . Obj: *ast.Object { |Objec是一个用于表达语法对象的结构
12 . . . . . Kind: func |表示之前存在过,Decl指向了7,也就是第7行的FuncDecl.
13 . . . . . Name: "main" |
14 . . . . . Decl: *(obj @ 7) |
15 . . . . } |
16 . . . } |
17 . . . Type: *ast.FuncType { |函数类型,也就是函数签名
18 . . . . Func: 3:1 |参数和返回值都是空的
19 . . . . Params: *ast.FieldList { |
20 . . . . . Opening: 3:10
21 . . . . . Closing: 3:11
22 . . . . }
23 . . . }
24 . . . Body: *ast.BlockStmt { |块语句,也就是main的body
25 . . . . Lbrace: 3:12
26 . . . . List: []ast.Stmt (len = 2) { |语句列表
27 . . . . . 0: *ast.AssignStmt { |赋值语句
28 . . . . . . Lhs: []ast.Expr (len = 1) { |左值是x
29 . . . . . . . 0: *ast.Ident {
30 . . . . . . . . NamePos: 5:2 |
31 . . . . . . . . Name: "x"
32 . . . . . . . . Obj: *ast.Object { |
33 . . . . . . . . . Kind: var
34 . . . . . . . . . Name: "x" |
35 . . . . . . . . . Decl: *(obj @ 27)
36 . . . . . . . . }
37 . . . . . . . } |
38 . . . . . . }
39 . . . . . . TokPos: 5:3 |:=和它的位置
40 . . . . . . Tok: :=
41 . . . . . . Rhs: []ast.Expr (len = 1) { |右边是一个数字类型的token
42 . . . . . . . 0: *ast.BasicLit {
43 . . . . . . . . ValuePos: 5:5
44 . . . . . . . . Kind: INT
45 . . . . . . . . Value: "1"
46 . . . . . . . }
47 . . . . . . }
48 . . . . . }
49 . . . . . 1: *ast.GoStmt { |接下来是go语句
50 . . . . . . Go: 6:2
51 . . . . . . Call: *ast.CallExpr { |一个调用表达式
52 . . . . . . . Fun: *ast.Ident { |IDENT token是println
53 . . . . . . . . NamePos: 6:5
54 . . . . . . . . Name: "println"
55 . . . . . . . }
56 . . . . . . . Lparen: 6:12 |左括号的位置
57 . . . . . . . Args: []ast.Expr (len = 1) { |参数列表
58 . . . . . . . . 0: *ast.Ident { |是一个符号INDENT,并且指向的是32行的x
59 . . . . . . . . . NamePos: 6:13
60 . . . . . . . . . Name: "x"
61 . . . . . . . . . Obj: *(obj @ 32)
62 . . . . . . . . }
63 . . . . . . . }
64 . . . . . . . Ellipsis: -
65 . . . . . . . Rparen: 6:14 |右括号的位置
66 . . . . . . }
67 . . . . . }
68 . . . . }
69 . . . . Rbrace: 8:1
70 . . . }
71 . . }
72 . }
73 . Scope: *ast.Scope { |最顶级的作用域
74 . . Objects: map[string]*ast.Object (len = 1) {
75 . . . "main": *(obj @ 11)
76 . . }
77 . }
78 . Unresolved: []*ast.Ident (len = 1) { |这里有个没有定义的符号println,是因为是内置符号,会另外处理
79 . . 0: *(obj @ 52) |从源文件上是表现不出来的.
80 . }
81 . Comments: []*ast.CommentGroup (len = 1) { |评论列表,以及位置和内容.
82 . . 0: *ast.CommentGroup {
83 . . . List: []*ast.Comment (len = 1) {
84 . . . . 0: *ast.Comment {
85 . . . . . Slash: 4:2
86 . . . . . Text: "// comments"
87 . . . . }
88 . . . }
89 . . }
90 . }
91 }