20220622编译原理读书笔记

 

 

 

20220622编译原理读书笔记

1.引论

基础知识和概念,不细说
编译程序的定义:语言翻译程序
编译程序的功能:源语言程序翻译为目标语言的等价程序的程序(按这个定义是不是能算元程序了hhhh生成程序的程序)

编译过程:
词法分析:源程序->单词(符号、单词符号、token)序列
语法分析:token序列->语法树
语义分析:语法树->语义树、图 这个阶段才有类型检查
中间代码生成:就是字面意思
代码优化:无效代码删除、优化
目标代码生成:翻译到目标语言

前端:到中间代码之前的部分,与目标语言和平台无关
后端:中间代码到目标代码的部分,与源语言和平台无关
编译过程可以是一遍或多遍扫描源码完成

解释执行和编译执行
解释执行不需要完整的源码,编译执行需要完整编译后才能运行

EBNF:扩展的巴克斯范式

练习题
else没有匹配的if,语法分析阶段检查
数组下标越界,语义分析阶段检查或代码生成阶段,甚至运行时才知道
使用的函数没有定义,语义分析阶段检查
数中出现非数字字符,词法分析阶段检查

2.文法和语言

程序设计语言是记号系统,完整定义包含语法和语义

语法只定义怎么写,不管含义例如a=b+c是合法的表达式,但如果c未定义,语法检查是检查不出来的
语义分为
静态语义:类型匹配检查,在满足语法限定的情况下,什么样的写法是合法的
动态语义:变量作用域检查,表明程序要做什么

文法:用来定义语法的工具
语义:目前(书上说没有,实际不知道)没有公认的形式系统可以用来自动构造正确的编译系统
形式语义学:这个可以再查查资料,对这个比较好奇,这本书居然不讲

文法:用有穷规则集合表示句子的无穷集合,描述语言的语言,所以也叫元语言
规则:左侧符号=>右侧符号序列,=>表示使用左侧符号可以产生右侧符号

字母表:符号组成的集合,所以也叫符号集,这里的符号层次就是字母、数字、标点之类的类型,不是token.符号这个词的含义在不同语境下会容易混淆,因此尽量避免,一般意思是token
符号串:有穷的符号序列,允许为空

表示法
若符号串x中有m个符号,则|x|=m
连接,x=臻臻,y=真厉害,xy=臻臻真厉害
方幂,x=臻ab,x^0=空,x^2=臻ab臻ab
符号串集合:乘积定义为两个集合元素的连接运算,区分先
对字母表C,C的闭包表示C上有穷长串的集合,也就是C^0∪C^1...C^n
排除C^0后的集合称为正闭包

2.3 形式定义

规则又称重写规则、产生式、生成式
写作A::=B或A=>B,A是左部,B是右部

文法G定义为(Vn,Vt,P,S)
Vn:非终结符(语法实体、变量)集合, 这里的符说的是抽象定义,也就是终结符有限集的划分
Vt:终结符集合,注意这里的符是字母那个层次的
P:规则集
S:识别符、开始符

因此这里的文法主要是词法分析使用,最终Vn的闭包将作为产物给语法分析(上学时候就糊涂,希望这次没说错

2.4 文法类型

文法G定义为(Vn,Vt,P,S), 产生式为a=>b
0型:a和b均属于V=Vn∪Vt的闭包 且a至少含有一个非终结符
特性:递归可枚举、能力等价于图灵机
1型:上下文有关,除S->空以外,|b|>=|a|
另一种描述 aBc=>aDc(D不为空),更能描述上下文,仅B出现在ac这种上下文时才能替换成D
2型:上下文无关,a是非终结符,b属于V的闭包
另一种描述 A=>B,A属于Vn,也就是取代A的时候无需关心A的上下文
3型:正规文法,产生式形如A=>aB或A=>a,A,B属于Vn,a属于Vt的闭包

定义限制是逐层增加的,因此满足3型的一定满足2、1、0
上下文无关说的是生成式看起来上下文无关,所以实际上上下文无关文法都是上下文有关的hhhh

例如C → a b 这条规则将一个单独的非终端符 C 变换为两个连续的终端符 “a b”
“a b” 这个序列能出现在什么位置是由右部出现 C 的其他规则决定的,只能出现在特定的上下文中,因此是上下文有关的。

明天继续2.5语法树
往后翻了翻终于知道为啥上学的时候糊涂了,第二章讲完了文法,第三章退回到词法了,所以概念理解上很容易乱
mark当前26页

 

0 Comments
Leave a Reply