-
编译原理
2019-01-21 23:02:03如果你敲累了代码,想喝喝咖啡,顺便看点儿可以当...是的,你可以看成和中文、英文等语言平等的存在。是语言就得有语言的解析规则,不懂得规则自然无法理解语言的意思。就跟看没字幕的美剧一样,真是痛苦。╮(╯﹏╰...如果你敲累了代码,想喝喝咖啡,顺便看点儿可以当佐料的文章那本文应该比较适合现在的你。(•̀ᴗ•́)و ̑̑
我们一天天都在和代码打交道,但是你了解代码的运行原理么?为什么你的一行代码就能被执行出五花八门的效果嘞?
其实代码这玩意儿就是一门语言。是的,你可以看成和中文、英文等语言平等的存在。是语言就得有语言的解析规则,不懂得规则自然无法理解语言的意思。就跟看没字幕的美剧一样,真是痛苦。╮(╯﹏╰)╭
中文有中文的语义、语法、句子、句法、文法,那么编程语言也有自己的语言系统。
我们知道,我们写的代码被编译器或者解释器所执行,那它们是按照什么文法来理解你的代码呢?这就是文法。
本文也不会深入去解析文法,不然可以直接转语言学了(笑~)。本文只是简单介绍文法的一些概念。如果您喝着咖啡,看完之后,能有些许收获,微微一笑,那本文的目的也就达到了。^_^
工欲善其事必先利其器。在谈文法之前,我们先介绍几个概念。
一.文法涉及的几个简单概念
假设Σ是一个有限的字母表集合,它的每一元素都是一个符号。Σ上的一个符号串就是指由Σ中的符号组成的一个有限序列。如果一个符号串不包含任何符号,就叫它空串,记为ε。现在再定义一个集合U和V的连接积的概念:
UV = {αβ | α∈U,β∈V}
比如A = {a,b},B = {1,2},则AB={a1,a2,b1,b2}。很简单的概念,是不是?
那么相信你也能知道V1,V2等的幂的概念了。
还有几个:
ok,定义结束,现在来谈谈咱们本次的主角——文法。一个比较拗口的定义,
文法是描述语言的语法结构的形式规则(即语法规则)。
这啥意思啊?可能你一脸黑人问号……
其实,就是指怎么由一堆符号组成一个有含义的句子的规则和协议。
所谓的上下文无关文法就是文法的一种,它所定义的语法单位是完全上下文无关的。比如我们在程序语言 中,碰到一个算数表达式时,我们完全可以对它“就事论事”,不用去考虑它上下有啥东西。当然,在自然语言(中文、英文等)中,一个语法单位(字、词、句子)肯定和上下文环境有关,不然当年我们中文考试的阅读理解题也就不会出现“根据上下文,解释xx句子的含意”了。(ˇˍˇ) 想~
所以说,上下文无关文法不能用来描述自然语言,但是对于当今的程序语言来说,上下文无关文法基本够用了。下文中的“文法”,如果没有特殊说明,都是之指“上下文无关文法”。
下面类比自然语言的具体例子,谈谈我们今天要说的文法。
一个英文句子:
He gave me a book.
这个句子满足英语的语法规则,是一个语法正确的句子。如果我们用“→”表示“由...组成”或者“定义为”,按照我们中学的语法,可以分解一下这个句子:
这样,通过这样的一个个规则(又叫“产生式”),就把一个句子分解到了单词的层次。或者这么说,有了这些规则,我们可以这么干:
我们可以画一个更形象的图(语法分析树)来说明这种推导。
上面定义英文句子的规则就可以说是一个上下文无关文法。其中,<句子>被称为开始符号,<主语><谓语><代词>之类的被称为非终结符号,He、gave之类的被称为终结符号。
归纳起来,一个上下文无关文法G包括四个部分:终结符号,非终结符号,开始符号,产生式。
终结符号就是一门语言中最基本的符号。在程序语言中,基本字、标识符、常数、运算符号等都算终结符号。
非终结符号更像一个抽象的集合,比如“算数表达式”、“赋值句”都可以看做非终结符号。
产生式就是推导规则。
下面上精确定义:
二.递归定义的例子
有时候,只用一个产生式是不足以定义一个语法单位的,需要几个产生式的相互配合。有时候会需要递归的形式。举个栗子:
假设要定义一类含有+、*的算术表达式,这个定义可以这么说:
- 变量是一个算术表达式;
- 如果E1和E2是算术表达式,那么E1+E2、E1*E2、(E1)也是算术表达式。
我们用产生式的形式描述它:
- E→i
- E→E+E
- E→E*E
- E→(E)
其中 E 代表算术表达式, i 代表变量。这四个产生式的全体才定义了什么是“算术表达式”。后三个都是递归的形式。
还可以简化为:E→i | E+E | E*E | (E)。其中的“|”代表“或”,是一种元语言符号。
三.文法与语言的推导
假设G是一个文法,S是开始符号,如果S经过零步或者若干步推出α,那么称α是一个句型。只包含终结符号的句型是一个句子。文法G产生的所有句子构成一门语言,记为L(G)。
那么怎么从文法推导出它代表的语言嘞?
为了方便,我们引入一些符号。
方法:把产生式看成替换规则,把当前符号串中的非终结符号用其产生式右边的符号来替换。
再看有文法G2->语言L(G2)例子。
推导过程如下:
语言L(G2)-> G2 的例子。
由上面的两个例子我们可以知道,一个文法可以唯一确定一个语言,但是一个语言不一定唯一对应一个文法。
四.语法分析树与二义性
我们发现从一个句型到另一个句型的推导过程不是唯一的。例如从E+E->i+i,存在两个推导过程:
- E+E->E+i->i+i 最右推导,每个推导过程都是从最右边的非终结符号的替换开始
- E+E->i+E->i+i 最左推导,每个推导过程都是从最左边的非终结符号的替换开始
当然为了对句子的结构进行一个确定性的分析,我们一般只考虑最左推导或者最右推导。
前面我们提到过用一种树形的图示来表示这个句型的推导过程,这棵树就被称为”语法分析树“,简称”语法树“。
比如从E->(i+i) 的过程:
对于一个文法,如果它的某些句子对应两棵不同的语法树,这个文法就属于“二义性文法”。
注意,文法的二义性和我们通常所说的语言的二义性不同,我们可能有两个不同的文法G1,G2,一个是二义性,一个是非二义性,但是可能L(G1) = L(G2)。对于程序语言来说,我们常常希望它的文法是非二义性的,但是,只要我们能够控制和驾驭文法的二义性,文法二义性的存在也不一定是坏事。
现在已经证明了,文法二义性是不可判定的。也就是说不存在一个算法,在有限步骤内算出一个文法是不是二义性的。我们能做的事儿,就是找一组充分条件来说明非二义性。比如,规定运算符号的优先级和结合性。
对于我们上面使用的那个文法:E->E+E | (E) | E*E | i
如果限定*的优先级高于+,并且都是左结合的,那么上述文法就变成了非二义性文法。读者大大可以试试推导E->(i*i+i)。
-
编译原理 文法
2020-02-22 14:33:30什么是文法?我们从一个自然语言的例子讲起: 这是一个简化版本的英文文法。比如一个句子是由名词短语和动词短语构成的。名词短语由形容词和名词短语构成。从这个例子中我们能够看出语法的基本构成。用尖括号括...什么是文法?我们从一个自然语言的例子讲起:
这是一个简化版本的英文文法。比如一个句子是由名词短语和动词短语构成的。名词短语由形容词和名词短语构成。从这个例子中我们能够看出语法的基本构成。用尖括号括起来的部分是语法成分,而没有被尖括号括起来的部分是语言的基本符号。英文的基本符号就是单词了。
那么编译语言的文法形式化定义是什么呢?
文法G = (Vt, Vn, P, S)是由四元组Vt,Vn,P,S所构成的。
其中:
Vt是终结符集合,是文法定义语言的基本符号,就像是英文中的单词一样。
Vn是非终结符。用来表示语法成分的符号,类似上面的<名词短语>,也就是语法变量。
P是产生式。描述了终结符和非终结符组合成串的方法。表示形式是:α -> β, α至少要包含一个非终结符。
S是开始符号。是一个非终结符,是一个文法的最大的语法成分。就如同上面的<句子>
例如:
上面这张图中描述的是加法乘法表达式的文法。其中我们能够看出,终结符Vt = {id, + * (,)}这些都是最终的一个一个语法不能被替换的元素;非终结符是E,他表示表达式,它可以被替换成各种数字等等。产生式P包含四种,可以被替换成加法,乘法,括号以及单独的数字。S开始符号是E,因为只有这一个非终结符,自然就是最大的了。
一般来说,第一个产生式的左部那个非终结符就是开始符号。
-
编译原理——语法分析
2019-01-13 21:36:47使用龙书以及编译程序设计原理(第二版)金成植、金英编著 老师的PPT是英文的,我自己随便翻的,不一定对 文章目录语法分析parsing语法分析过程语法分析基础知识语法分析方法分类上下文无关文法什么是文法乔姆斯基...根据上课内容顺序写的博客,并不是按照书的目录来的
使用龙书以及编译程序设计原理(第二版)金成植、金英编著
老师的PPT是英文的,我自己随便翻的,不一定对
语法分析parsing
知识图谱
语法分析过程
语法分析基础知识
语法分析器的功能
输入:词法单元/词法单元序列
输出:语法结构的内在表达式
过程:
读取词法单元
生成语法结构——语法树,根据语法定义(上下文无关文法)
检查语法错误
语法结构
用来描述一个明确定义的程序的结构
- 程序
- 声明
常数声明
类型声明
变量声明
程序/函数声明 - 主体
- 声明(赋值,条件语句,循环,函数调用)
- 表达式(算数,逻辑,布尔)
语法错误
不同类型的语法错误:
- 后继单词错误
- 标识符或者常量错
- 关键字错
- 开始单词错
- 括号配对错
处理语法错误:
- 立即退出,不实际
- 错误恢复
- 错误修补
- 错误改正
- 没有完美的办法
语法分析方法分类
通用于任何语法的语法分析方法(低效)
Cocke-Younger-Kasami算法
Earley’s 算法
自顶向下语法分析方法(有限制,可预测的)
递归下降法 recursive descendent parsing
LL(K) – K=1
自底向上语法分析方法(有限制,归约)
SLR(k)
LR(k)
LALR(k)
简单优先关系法
上下文无关文法
什么是文法
文法是表示无穷字符串集的强有力的一种有限方式
文法G (VT, VN, S, P)
VT 是一个有限的终极符集合
VN是一个有限的非终极符集合
S是文法的开始符
P是产生式的集合
每个生成规则都有以下形式
乔姆斯基文法分类
文法的分类
- O型文法: 也称为短语文法,其产生式具有形式:
- α→β,其中α,β∈(VT∪VN)*,并且α至少含一个非终极符;
- 1型文法: 也称为上下文有关文法。其产生式形式为:
- αAβ→αuβ,A∈VN,u为非空串,它是0型文法的特例,即要求|α| ≤ |β|;
- 2型文法: 也称为上下文无关文法。
- 它是1型文法的特例,即要求产生式左部是一个非终极符: A→β
- 3型文法: 也称为正则文法。
- 它是2型文法的特例,即其产生式的右部至多有两个符号,而且具有下面形式之一:
- A →a ,A →a B, 其中A,B∈VN ,a∈VT
上下文无关文法与正则表达式
正则表达式(a|b)*abb
文法:A0 → aA0|bA0|aA1
A1 → bA2
A2 →bA3
A3→ ε
文法的分类
描述能力
0型文法 > 1型文法 > 2型文法 > 3型文法
对应自动机
0型文法:图灵机
1型文法:线性有界自动机
2型文法:下推自动机
3型文法:有限自动机上下文无关文法
上下文无关文法
Context Free Grammar(CFG)定义为四元组(VT,VN,S,P)
VT是有限的终极符集合
VN是有限的非终极符集合
S是开始符,S∈ VN
P是产生式的集合,且具有下面的形式:
A→X1X2…Xn
其中A∈VN,Xi∈ (VT∪VN) ,右部可空。
一些通常的符号变量
通常情况下
- {A,B,…,Z}用来表示非终极符
- {a,b,…,z}用来表示终极符
- {α,β,…}用来表示字符串
- ε用来表示空字符串
推导
如果有一个产生式A→β,我们得到αAγ=>αβγ =>代表用A→β一步推导
我们可以说αβγ 是αAγ推导的=>的含义是,使用一条规则,代替=>左边的某个符号,产生=>右端的符号串
扩展巴克斯范式
文法转换的一些算法
文法等价变化:L(G1)=L(G2)
增补文法(增光文法):开始符不能出现在产生式的右侧
Z→S
消除公共前缀
公共前缀 A→αβ1| … | αβn | γ1 | … | γm
提取公因子 A→αA’ | γ1 | … | γm A’ → β1 | … | βn
例子
例子1
VT={i, n, +, , (, )}
VN={E, T, F}
S=E
P:{ E→T E→E+T T→F T→TF F→(E) F→i F→n }
例子2
算术表达式
VT={id, num, (, ), +, -, *, /}
VN={Exp}
S=Exp
P:{ Exp→Exp+Exp Exp→Exp-Exp Exp→Exp * Exp Exp→Exp/Exp Exp→(Exp) Exp→id Exp→num }
例子3
程序
VT={VarDec, TypeDec, ConstDec, MainFun, FunDec}
VN={Program, Dec, Decs}
S=Program
P:{ Program→Dec MainFun Decs Dec→ε Dec→VarDec Dec→ConstDec Dec→FunDec Dec→TypeDec Decs→Dec Decs→Decs;Dec}
语法分析书和抽象语法树
问题:推导是从开始符构造一个句子的方法
许多推导来自同一个句子
不能唯一地代表句子的结构
语法书:表示一个句子的结构的方法依旧是上面的例子
语法树
一颗使用上下文无关文法的有标号树
根必须是开始符的标号
每一个节点都是一个与之相关联的符号
每个叶子必须是一个终极符的标签
对于每一个与非终极符A相关的节点,都有n个儿子,从左到右他们一起与符号B1,B2,…,Bn相关,必须有个产生式A→B1B2…Bn
二义性
二义性文法
对于一个文法G,如果存在一个句子有不止一颗语法树,G被称为二义性文法二义性文法是不可判定的
解决方案1:重写文法
解决方案2:制定一个语法分析树作为推荐的
简单语言的语法
C0程序的结构
-
编译原理 START 龙虎鲸书简介
2017-12-19 22:39:34什么是龙书虎书鲸书 龙书 英文名:《Compilers: Principles, Techniques, and Tools 》 中文名:《编译原理技术和工具》 作者 :Alfred V.Aho,Ravi Sethi,Jeffrey D.Ullman 下载地址:...编译原理START—龙书虎书鲸书
什么是龙书虎书鲸书
龙书
英文名:《Compilers: Principles, Techniques, and Tools 》
中文名:《编译原理技术和工具》
作者 :Alfred V.Aho,Ravi Sethi,Jeffrey D.Ullman
下载地址:https://download.csdn.net/download/diehuang3426/10283590
简介:此书全面、深入地探讨了编译器设计方面的重要主题,包括词法分析、语法分析、语法制导定义和语法制导翻译、运行时刻环境、目标代码生成、代码优化技术、并行性检测以及过程间分析技术,并在相关章节中给出大量的实例。与上一版相比,本书进行了全面的修订,涵盖了编译器开发方面的最新进展。每章中都提供了大量的系统及参考文献。因书封面初始为恐龙和骑士,故亦叫做龙书。
目录:https://book.douban.com/subject/3296317/
第一版
第二版中文版
虎书
英文名:Modern Compiler Implementation in C
作者:Andrew W.Appel,with Jens Palsberg
中文名:现代编译原理-C语言描述
简介:《现代编译原理:C语言描述》全面讲述了现代编译器的结构、编译算法和实现方法,是Andrew w.Apple的“虎书”——Modern Compiler Implementation——“红、蓝、绿”三序列之一。这三本书的内容基本相同。但是使用不同的语言来实现书中给出的一个编译器。本书使用的是更适合广大读者的c语言,而另外两本书分别采用ML语言和Java语言。本书的另一个特点是增加了一些其他编译原理教科书没有涉及的内容。前端增加了面向对象的程序设计语言、函数式程序设计语言等现代语言的编译实现方法,后端增加了针对现代计算机体系结构特征的一些比较成熟的优化方法。这部分内容展现了现代商业编译器需解决的一些关键问题,开拓了学生的视野,为学生未来进行更深入的研究奠定了基础。
《现代编译原理:C语言描述》全面讲述了现代编译器的各个组成部分,包括词法分析、语法分析、抽象语法、语义检查、中间代码表示、指令选择、数据流分析、寄存器分配以及运行时系统等。全书分成两部分,第一部分是编译的基础知识,适用于第一门编译原理课程(一个学期);第二部分是高级主题,包括面向对象语言和函数语言、垃圾收集、循环优化、ssA(静态单赋值)形式、循环调度、存储结构优化等,适合于后续课程或研究生教学。书中专门为学生提供了一个用C语言编写的实习项目,包括前端和后端设计,学生可以在一学期内创建一个功能完整的编译器
目录:https://book.douban.com/subject/1806974/
下载地址:https://download.csdn.net/download/diehuang3426/10283582
中文版鲸书
原名:Advanced Compiler Design andImplementation
作者:Steven S.Muchnick
中文名:高级编译器设计与实现
简介:此书是经典的编译器著作,与“龙书”齐名。书中针对现代语言和体系结构全面介绍了编译器设计与实现的高级论题,从编译器的基础领域中的高级问题开始,然后深入讨论了各种重要的代码优化。本书专为编译器专业人士和计算机专业本科生,研究生编写,在设计和实现高度优化的编译器以及确定优化的重要性和实现优化的最有效的方法等方面,为读者提供了非常有价值的指导。
目录:https://book.douban.com/subject/1128349/
下载地址:https://download.csdn.net/download/diehuang3426/10283594
中文版总结
龙书全,偏理论。
鲸书比龙书偏后端,也偏理论。
虎书也全,是龙书和鲸书结合之后的简化版,重实践。
粗略之写,现在在看编译原理,其他等以后读过了,有一定理解来补。 -
编译原理课堂笔记之第一章-引论
2021-02-22 11:44:37编译原理课堂笔记之第一章-引论 什么是编译程序 编译程序:先把源程序翻译成机器语言,然后再执行。 解释程序:每次读源程序的一句,边翻译边执行。 编译过程 编译过程:把英文翻译成中文(类比) 编译过程 : 五个... -
编译原理:第三节
2015-09-08 21:18:43形式语言与自动机原理 什么是语言? 我们知道世界上存在很多种语言:我们可以把他们分为自然语言(人们日常交流的工具)和程序设计语言。自然语言复杂且难以描述,程序设计语言结构规整,便于处理。 但两者又有... -
编译原理三大经典:龙书 虎书 鲸书
2017-11-24 18:42:00众所周知,在编译原理界有三本经典的书籍,它们分别被称为龙书、虎书、鲸书,但很多人不知道这三本书分别是什么,或者很多人只知道龙书而对其它两本书不了解,这里给出简单介绍并附上三本书PDF版本的下载链接。... -
侃一侃编译原理的“文法”
2017-10-06 15:23:00如果你敲累了代码,想喝喝咖啡,顺便看点儿可以当...是的,你可以看成和中文、英文等语言平等的存在。是语言就得有语言的解析规则,不懂得规则自然无法理解语言的意思。就跟看没字幕的美剧一样,真是痛苦。╮(╯﹏╰... -
斯坦福大学CS143编译原理课程笔记:2.编译器结构
2021-01-08 13:41:55这句话里共有四个单词,想要表达的意思是这是一个句子,用我们让的话一眼就能看清楚这个句子有几个单词,并且能够理解这些单词组合成句子是什么意思,This is a sentence翻译过来就是这是一个句子。 我们人在看这... -
编程语言原理英文版第10版
2019-03-14 14:36:53是英文原版教材,需要中文的请移步主页「编译原理中文版第10版」。 《编程语言原理(第10版)》从为什么学习程序设计语言入手,深入细致地讲解了命令式语言的主要结构及其设计与实现,内容涉及变量、数据类型、... -
转载 侃一侃编译原理的“文法” 作者 :博客网 my笔触
2019-02-23 18:08:00如果你敲累了代码,想喝喝咖啡,顺便看点儿可以当...是的,你可以看成和中文、英文等语言平等的存在。是语言就得有语言的解析规则,不懂得规则自然无法理解语言的意思。就跟看没字幕的美剧一样,真是痛苦。╮(╯﹏╰... -
python怎么被发明的英文_一门编程语言是如何被创造出来的?
2021-02-10 12:38:46不过作为背景,一般我们先要先掌握一点编程基础,学习一些程序语言理论和编译原理。这里假设题主有一定编程基础,然后出于实用或者学习的目的想设计一种简单的语言。首先要思考以下问题:语言的用途或者使用场景是... -
.Net 垃圾回收机制原理(一)
2015-03-15 21:13:24英文原文:Jeffrey Richter 编译:赵玉开 ...有了Microsoft.Net clr中的垃圾回收机制程序员不需要再关注什么时候释放内存,释放内存这件事儿完全由GC做了,对程序员来说是透明的。尽管如此,作为一个 -
现代浏览器的工作原理
2017-06-20 17:51:53浏览器可以被认为是使用最广泛的软件,本文将介绍浏览器的工 作原理,我们将看到,从你在地址栏输入google.com到你看到google主页过程中都发生了什么。 将讨论的浏览器 今天,有五种主流浏览器——IE、Firefox... -
浏览器的工作原理
2013-07-17 17:03:00http://blog.jobbole.com/12749/ 英文原文:Tali Garsiel,编译:zzzaquarius 简介 浏览器可以被认为是使用最广泛的软件,本文将介绍浏览器的工 作原理,我们将看到,从你在地址栏输入google.com到你看到google主页... -
Java 面试题问与答:编译时与运行时
2013-01-07 11:01:00英文原文:java-success 在开发和设计的时候,我们需要考虑编译时,运行时以及构建时这三个概念。理解这几个概念可以更好地帮助你去了解一些基本的原理。下面是初学者晋级中级水平需要知道的一些问题。 Q.下面的... -
好文:现代浏览器原理详解
2016-09-27 18:35:34浏览器可以被认为是使用最广泛的软件,本文将介绍浏览器的工 作原理,我们将看到,从你在地址栏输入google.com到你看到google主页过程中都发生了什么。 将讨论的浏览器 今天,有五种主流浏览器——IE、Firefox...
-
VS2019 getline()
-
基于python的dango框架购物商城毕业设计毕设源代码使用教程
-
做菜 : 玉米排骨汤
-
Jenkins软件开发持续集成及自动构建
-
FastDFS 分布式文件系统部署
-
linux基础入门和项目实战部署系列课程
-
通过新颖的二元君主蝶优化算法解决0-1背包问题
-
使用内置传感器的LED进行LED热阻和TIM评估的研究
-
沿RF锁相辅助的光纤环路链路上任意中间点的精确时延感测和工作台频率分配
-
ASHRAE 2012 IT Equipment Thermal Management and Controls_V1.0.pdf
-
Golang零基础-->高级编程
-
MySQL Router 实现高可用、负载均衡、读写分离
-
JavaWeb之JavaBean
-
APPKIT打造稳定、灵活、高效的运营配置平台
-
Glasterfs 分布式网络文件系统
-
JavaWeb之过滤器与监听器
-
虚幻4引擎基础
-
基于流形结构的图像地理信息标注方法
-
如何使用Smartproxy运行无限的运动鞋机器人任务
-
分布式存储系统中的异构感知数据再生