编译原理之美-宫文学-学习摘要 [TOC]
这里的“前端”指的是编译器对程序代码的分析和理解过程。 “后端”则是生成目标代码，跟目标机器有关。
词法分析是把程序分割成一个个Token的过程，可以通过构造有限自动机来实现。
辅助工具:Lex
语法分析是把程序的结构识别出来，并形成一棵便于由计算机处理的抽象语法树。可以用递归下降的算法来实现。
mac上使用下面的命令可以体验下ast树
clang -cc1 -ast-dump hello.c
辅助工具：Yacc、Antlr、JavaCC等。更多列表参考
语义分析是消除语义模糊，生成一些属性信息，让计算机能够依据这些信息生成目标代码。
示例程序分析以下语句
age >= 45
int age = 40
2 + 3*5
intA = 10
作者的实现代码
要实现一个词法分析器，首先需要写出每个词法的正则表达式，并画出有限自动机，之后，只要用代码表示这种状态迁移过程就可以了。
golang可以参考json的实现方式。
主要是 语法分析的原理和递归下降算法，上下文无关文法。 本课稍有单独，需要看原文。 作者源码 自己手动实现一遍有助于理解。
巴科斯范式 BNF
add ::= mul | add + mul
扩展巴科斯范式 EBNF
add -> mul ( + mul ) *
一个规律：
对于左结合的运算符，递归项要放在左边；而右结合的运算符，递归项放在右边。
但是左递归有个无限循环的问题。
解决办法是修改文法：
add -> mul add'
add' -> + mul add' | ε
可以用EBNF表达为
add -> mul ( + mul ) *
就是进一步扩展代码
antlr官网 mac 可以直接用homebrew 安装。 antlr语法参考
antlr规则文件以.g4结尾。
示例 Hello.g4
lexer grammar Hello; //lexer 关键字意味着这是一个词法规则文件，名称是 Hello，要与文件名相同
// 关键字
If : 'if';
Int : 'int';
// 字面量
IntLiteral: [0-9]+;
StringLiteral: '"' .*? '"' ; // 字符串字面量
// 操作符
AssignmentOP: '=' ;
RelationalOP: '>'|'>='|'<' |'<=' ;
Star: '*';
Plus: '+';
Sharp: '#';
SemiColon: ';';
Dot: '.';
Comm: ',';
LeftBracket : '[';
RightBracket: ']';
LeftBrace: '{';
RightBrace: '}';
LeftParen: '(';
RightParen: ')';
// 标识符
Id : [a-zA-Z_] ([a-zA-Z_] | [0-9])*;
// 空白字符，抛弃
Whitespace: [ \t]+ -> skip;
Newline: ( '\r' '\n'?|'\n')-> skip;
生成golang的需要参考
go get github.com/antlr/antlr4/runtime/Go/antlr
编译词法规则
antlr -Dlanguage=Go Hello.g4
生成了3个文件Hello.interp Hello.tokens hello_lexer.go
手写一个grun.go
package main
import (
parser "GoPlayWithCompiler/antlrdemo"
"fmt"
"github.com/antlr/antlr4/runtime/Go/antlr"
"os"
)
func main() {
input, _ := antlr.NewFileStream(os.Args[1])
lexer := parser.NewHello(input)
stream := antlr.NewCommonTokenStream(lexer, 0)
stream.Fill()
for _, token := range stream.GetAllTokens() {
fmt.Println(token)
}
}
执行以下命令获取token:
go run cmds/hello/main.go antlrdemo/Hello/hello.play
生成如下文本：
[@0,0:2='int',<2>,1:0]
[@1,4:6='age',<19>,1:4]
[@2,8:8='=',<5>,1:8]
[@3,10:11='45',<3>,1:10]
[@4,12:12=';',<10>,1:12]
[@5,14:15='if',<1>,2:0]
[@6,17:17='(',<17>,2:3]
[@7,18:20='age',<19>,2:4]
[@8,22:23='>=',<6>,2:8]
[@9,25:26='17',<3>,2:11]
[@10,27:27='+',<8>,2:13]
[@11,28:28='8',<3>,2:14]
[@12,29:29='+',<8>,2:15]
[@13,30:31='20',<3>,2:16]
[@14,32:32=')',<18>,2:18]
[@15,33:33='{',<15>,2:19]
[@16,37:42='printf',<19>,3:2]
[@17,43:43='(',<17>,3:8]
[@18,44:59='"Hello old man!"',<4>,3:9]
[@19,60:60=')',<18>,3:25]
[@20,61:61=';',<10>,3:26]
[@21,63:63='}',<16>,4:0]
[@22,64:63='<EOF>',<-1>,4:1]
PlayScript.g4
grammar PlayScript;
import CommonLexer; // 导入词法定义
/* 下面的内容加到所生成的 Java 源文件的头部，如包名称，import 语句等。*/
@header {
package antlrtest;
}
expression
: assignmentExpression
| expression ',' assignmentExpression
;
assignmentExpression
: additiveExpression
| Identifier assignmentOperator additiveExpression
;
assignmentOperator
: '='
| '*='
| '/='
| '%='
| '+='
| '-='
;
additiveExpression
: multiplicativeExpression
| additiveExpression '+' multiplicativeExpression
| additiveExpression '-' multiplicativeExpression
;
multiplicativeExpression
: primaryExpression
| multiplicativeExpression '*' primaryExpression
| multiplicativeExpression '/' primaryExpression
| multiplicativeExpression '%' primaryExpression
;
生成目标文件antlr -Dlanguage=Go PlayScript.g4
手写个交互式脚本来解析语法，并画出ast树。具体参考
json的这个语法很简单，适合学习。