编译原理_编译原理答案 - CSDN
编译原理 订阅
编译原理是计算机专业的一门重要专业课,旨在介绍编译程序构造的一般原理和基本方法。内容包括语言和文法、词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代码优化和目标代码生成。 编译原理是计算机专业设置的一门重要的专业课程。编译原理课程是计算机相关专业学生的必修课程和高等学校培养计算机专业人才的基础及核心课程,同时也是计算机专业课程中最难及最挑战学习能力的课程之一。编译原理课程内容主要是原理性质,高度抽象 [1]  。 展开全文
编译原理是计算机专业的一门重要专业课,旨在介绍编译程序构造的一般原理和基本方法。内容包括语言和文法、词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代码优化和目标代码生成。 编译原理是计算机专业设置的一门重要的专业课程。编译原理课程是计算机相关专业学生的必修课程和高等学校培养计算机专业人才的基础及核心课程,同时也是计算机专业课程中最难及最挑战学习能力的课程之一。编译原理课程内容主要是原理性质,高度抽象 [1]  。
信息
外文名
Compilers: Principles, Techniques, and Tools [1]
领    域
计算机专业的一门重要专业课 [1]
中文名
编译原理 [1]
编译原理基本概念
编译原理即是对高级程序语言进行翻译的一门科学技术, 我们都知道计算机程序由程序语言编写而成, 在早期计算机程序语言发展较为缓慢, 因为计算机存储的数据和执行的程序都是由0、1代码组合而成的, 那么在早期程序员编写计算机程序时必须十分了解计算机的底层指令代码通过将这些微程序指令组合排列从而完成一个特定功能的程序, 这就对程序员的要求非常高了。人们一直在研究如何如何高效的开发计算机程序, 使编程的门槛降低。 [2] 
收起全文
精华内容
参与话题
  • 编译原理知识汇总

    千次阅读 2019-07-31 16:04:59
    编译原理 第一章 引言 1.从面向机器的语言到面向人类的语言 汇编指令:用符号表示的指令被称为汇编指令 汇编语言:汇编指令的集合称为汇编语言 2.语言之间的翻译 转换(也被称为预处理):高级语言之间的翻译,...

    转自:https://www.jianshu.com/p/eb63d31ad638

     

    编译原理

    第一章 引言

    1.从面向机器的语言到面向人类的语言

    汇编指令:用符号表示的指令被称为汇编指令
    汇编语言:汇编指令的集合称为汇编语言

    2.语言之间的翻译

    转换(也被称为预处理):高级语言之间的翻译,如FORTRANADA的转换
    编译:高级语言可以直接翻译成机器语言,也可以翻译成汇编语言,这两个翻译过程称为编译
    汇编:从汇编语言到机器语言的翻译被称为汇编
    交叉汇编:将一个汇编语言程序汇编成为可在另一机器上运行的机器指令成为交叉汇编
    反汇编:把机器语言翻译成汇编语言
    反编译:把汇编语言翻译成高级语言

     
     

    3. 编译器与解释器

    (1)语言翻译的两种基本形态

     
     

    解释器与编译器的主要区别:运行目标程序时的控制权在解释器而不在目标程序.

    (2)各自特点

    • 编译器:工作效率高,即时间快、空间省;交互性与动态性差,可移植性差.
    • 解释器:工作效率低,,即时间慢、空间费;交互性与动态性好,可移植性好.

    共同点:均完成对源程序的翻译.
    差异:编译器采用先翻译后执行,解释器采用边翻译边执行.

    4. 编译器的工作原理与基本组成

    (0)通用程序设计语言的主要成份 声明+操作=完整定义

    (1)以过程为基本结构的程序设计语言的组成

    • 声明性语句:提供操作对象的性质,如数据类型、值、作用域等;
    • 操作性语句:确定操作的计算次序,完成实际操作。
    • 过程定义 = 过程头+过程体

    (2)以阶段划分编译器

     
     

    注:符号表管理器和出错处理贯穿编译器工作的各个阶段.

    (3)编译器各阶段工作

    1> 词法分析:词法分析的输入源程序,输出是识别出的记号流.目的识别单词. 至少分以下几类:关键字(保留字)、标识符、字面量、特殊符号

    2> 语法分析: 输入是词法分析器返回的记号流,输出语法树.目的是得到语言结构并以树的形式表示.对于声明性语句,进行符号表的查填,对于可执行语句,检查结构合理的表达式运算是否有意义.

    3> 语义分析:根据语义规则对语法树中的语法单元进行静态语义检查,如类型检查和转换等,目的在于保证语法正确的结构在语义分析上也是合法的.

    4> 中间代码生成(可选):生成一种既接近目标语言,又与具体机器无关的表示,便于代码优化与代码生成.

    (到目前为止,编译器与解释器可以一致)

    5> 中间代码优化(可选):局部优化、循环优化、全局优化等;优化实际上是一个等价变换,变换前后的指令序列完成同样的功能,但在占用的空间上和程序执行的时间上都更省、更有效

    6> 目标代码生成:不同形式的目标代码—汇编语言形式、可重定位二进制代码形式、内存形式(Load-and-Go)

    7> 符号表管理:合理组织符号,便于各阶段查找\填写等.

    8> 出错处理:

    动态错误:源程序中的逻辑错误,发生在程序运行的时候。也称为动态语义错误
    静态错误:静态错误分为语法错误和静态语义错误.  
    <1> 语法错误:有关语言结构上的错误,如单词拼写错误、表达式缺少操作数、begin和end不匹配
    <2> 静态语义错误:分析源程序时可以发现的语言意义上的错误,如加法的两个操作数一个是整形变量,另一个是数组名
    

    (4)编译器的分析\综合模式

     
     

    逻辑上把编译器分为分析(前端)部分综合(后端)部分.
    1> 分析(前端):语言结构和意义的分析; 从词法分析到中间代码生成各阶段的工作
    2> 综合(后端):语言意义处理;从中间代码生成到目标代码生成的各阶段的工作
    3> 编译器和解释器的区别往往是在形成中间代码之后开始的.

    5. 编译器扫描的遍数

    每个阶段将程序完整分析一遍的工作模式称为一遍扫描。
    (将源程序或源程序的某种形式的中间表示完整分析一遍,亦称作一遍扫描)

    第二章 词法分析

    1. 词法分析中的若干问题

    (1) 记号、模式与单词

    单词的分类:关键字(保留字)、标识符、字面量、特殊符号
    模式(pattern):产生/识别单词的规则
    记号(token):按照某个模式(或规则)识别出的元素(一组)
    单词(lexeme):被识别出的元素的值(字符串本身) ,也称为词值

    (2) 词法分析器的作用与工作方式

    词法分析器的作用:

    1> 识别记号并交给语法分析器(根据模式识别记号)
    2> 滤掉源程序中的无用成分,如注释、空格和回车等
    3> 处理与具体平台有关的输入(如文件结束符的不同表示等)
    4> 调用符号表管理器和出错处理器,进行相关处理

    工作方式:
    1.单独一遍扫描
    2.作为语法分析器的子程序
    3.并行方式

    2. 模式的形式化描述

    (1) 字符串与语言

    语言L是有限字母表∑上有限长度字符串的集合.
    定义中强调两个有限,因为计算机的表示能力有限 :
    1> 字母表是有限的,即字母表中元素是有限多个;
    2> 字符串的长度是有限的,即字符串中字符个数是有限多个。

    (字符串与字符串集合相关的概念与运算,如前缀、后缀、子串、子序列等,字符串的并、交、连接、差、闭包)

    (2) 正规式与正规集

    令Σ是一个有限字母表,则Σ上的 正规式 及其表示的集合递归定义如下:
        1. ε是正规式,它表示集合  L(ε) = {ε}
        2. 若a是Σ上的字符,则a是正规式,它表示集合L(a)={a}
        3. 若正规式r和s分别表示集合L(r)和L(s),则
           (a) r|s是正规式,表示集合L(r)∪L(s),
           (b) rs是正规式,表示集合L(r)L(s),
           (c) r*是正规式,表示集合(L(r))*,
           (d)(r)是正规式,表示的集合仍然是L(r)。                                   
           括弧用来改变运算的先后次序!
    

    可用正规式描述(其结构)的语言称为 正规语言 或 正规集

    若运算的优先级和结合性做下述约定:
        1. 三种运算均具有左结合性质;
        2. 优先级从高到低顺序排列为:闭包运算、连接运算、或运算。
    则正规式中不必要的括号可以被省略。
    

    若正规式P和Q表示了同一个正规集,则称P和Q是等价的,记为P=Q

     
     

    (3) 简化正规式描述(主要是简化书写上的复杂)

    (a) 正闭包 若r是表示L(r)的正规式,则r+是表示(L(r))+的正规式,且下述等式成立:r+ = rr* = rr,r = r+|ε;
              +与*具有相同的运算结合性和优先级
    (b) 可缺省  若r是正规式,则r?是表示L(r)∪{ε}的正规式,且下述等式成立:r? = r|ε
               ? 与 * 具有相同的运算结合性和优先级
    (c) 串    若r是若干字符进行连接运算构成的正规式,则:串“r” =  r ,且: ε= “”,   a = “a”(a是Σ的任一字符)
    (d) 字符组 若r是若干字符进行|运算构成的正规式,则可改写为  [r’],其中r’可以有如下两种书写形式:
                 枚举:      如  a|b|e|h,可写为 [abeh]:
                 分段:   如0|1|2|3|4|5|6|7|8|9|a|b|c|d|e , 可写为: [0-9a-e]
    (e) 非字符组 若[r]是一个字符组形式的正规式,则[^r]是表示∑- L([r])的正规式。 
    

    3. 记号的识别——有限自动机

    (1) 不确定的有限自动机(NondeterministicFinite Automaton, NFA)

    NFA是一个五元组(5-tuple):M =(S,∑,move,s0,F),其中
    (1) S是有限个状态(state)的集合;
    (2) ∑是有限个输入字符(包括ε)的集合;
    (3) move是一个状态转移函数,move(si,ch)=sj表示,当前状态si下若遇到输入字符ch,则转移到状态sj;
    (4) s0是唯一的初态(也称开始状态);
    (5) F是终态集(也称接受状态集),它是S的子集,包含了所有的终态。
    

    <1> 直观的表示方式

    ① 状态转换图:用一个有向图来直观表示NFA
    ② 状态转换矩阵:用一个矩阵来直观表示NFA (矩阵中,状态对应行,字符对应列)

    <2> NFA(识别记号)的特点
    NFA识别记号的最大特点是它的不确定性,即在当前状态下对同一字符有多于一个的下一状态转移。

    具体体现:
    定义: move函数是1对多的;
    状态转换图:从同一状态出发,可通过多于一条标记相同字符的边转移到不同的状态;
    状态转换矩阵: M[si,a]是一个状态的集合
    

    <3> NFA识别记号存在的问题

    1.只有尝试了全部可能的路径,才能确定一个输入序列不被接受,而这些路径的条数随着路径长度的增长成指数增长
    2.识别过程中需要进行大量回朔,时间复杂度升高且算法复杂

    (2) 确定的有限自动机(Deterministic Finite Automaton, DFA)

    定义: DFA是NFA的一个特例,其中: 
      (1)没有状态具有ε状态转移(ε-transition),即状态转换图中没有标记ε的边;
      (2)对每个状态s和每个字符a,最多有一个下一状态。
      
    特点:与NFA相比,DFA的特征:确定性
        定义:move(si, a)函数都是 1对1 的;
        转换图 从一个状态出发的任2条边上的标记均不同;
        转换矩阵:M[si,a]是一个状态   且字母表不包括ε。
    提示:正规式和有限自动机从两个侧面表示正规式。正规式是描述,自动机是识别。
    

    4. 从正规式到词法分析器

    构造词法分析器的一般方法和步骤:
    1. 用正规式描述模式(为记号设计正规式);
    2. 为每个正规式构造一个NFA,它识别正规式所表示的正规集;
    3. 将构造的NFA转换成等价的DFA,这一过程也被称为确定化;
    4. 优化DFA,使其状态数最少,这一过程也被称为最小化;
    5. 根据优化后的DFA构造词法分析器。
    

    (1) 从正规式到NFA

    Thompson 算法

     
     

    (2) 从NFA到DFA

    - smove(S, a):从状态集S出发,标记为a的下一状态全体。与move(s, a)的唯一区别:用状态集取代状态
    - ε-闭包(T):从状态集T出发,不经任何字符达到的状态全体
    - “子集法”构造DFA
    

    (3) 最小化DFA

    ​ ① 对于任何两个状态t和s,若从一状态出发接受输入字符串ω,而从另一状态出发不接受ω.

    或者,② 从t出发和从s出发到达不同的接受状态,则称ω对状态t和s是可区分的.

    ​ 不可区分的状态位于一个组内,可以合并成一个状态.

    主要步骤:
    ​ 1.初始划分:终态组 , 非终态组;
    ​ 2.利用可区分的概念,反复分裂划分中的组Gi,直到不可再分裂;
    ​ 3.由最终划分构造D',关键是选代表和修改状态转移;
    ​ 4.消除可能的死状态和不可达状态。

    5. 从DFA构造词法分析器

    分类:表驱动型的词法分析器;直接编码的词法分析器
    比较:

     表驱动直接编码
    分析器的速度
    程序与模式的关系 无关 有关
    适合的编写方法 工具生成 手工编写
    分析器的规模 较大 较小

    第三章 语法分析

    词法分析:记号的集合,字符串由字母组成,线性结构
    语法分析:句子的集合,句子由记号组成,非线性结构(树)

    语法分析的双重含义:

    • 语法规则:上下文无关文法(子集:LL文法或LR文法)
    • 语法分析:下推自动机(LL或LR分析器)、自上而下分析、自下而上分析

    1. 语法分析的若干问题

    许多编译器,特别是由自动生成工具构造的编译器,往往其前端的中心部件就是语法分析器

    (1)语法分析器的作用

    • 根据词法分析器提供的记号流,为语法正确的输入构造分析树(或语法树)
    • 检查输入中的语法(可能包括词法)错误,并调用出错处理器进行适
      当处理
     
     

    (2)语法错误的处理原则

    源程序中可能出现的错误

    语法(包括词法)错误和语义错误(静态语义错误和动态语义错误)

    注:跟第一章的分类角度不同,第一章是从静态错误(语法错误,静态语义错误)和动态错误(动态语义错误)分类的,但是殊途同归。

    词法错误:指非法字符或拼写错关键字、标识符等
    语法错误:指语法结构出错,如少分号、括号不匹配、begin/end不配对等
    静态语义错误:如类型不一致、参数不匹配等
    动态语义错误(逻辑错误):如死循环、变量为零时作除数等

    2. 上下文无关文法(CFG)

    (1)上下文无关文法(Context Free Grammar,CFG)

     CFG是一个四元组G =(N,T,P,S),其中
    (1) N是非终结符(Nonterminals)的有限集合;
    (2) T是终结符(Terminals)的有限集合,且N∩T=Φ;
    (3) P是产生式(Productions)的有限集合,A→α,其中A∈N(左部),α∈(N∪T)*(右部),若α=ε,则称A→ε为空产生式(也可以记为A →);
    (4) S是非终结符,称为文法的开始符号(Start symbol)
     注: S ∈ N , N可以出现在产生式左边和右边,T绝不出现在产生式左边.
    

    (2)CFG产生语言的基本方法-推导

    CFG(产生式)通过推导的方法产生语言,即(通俗地讲)从开始符号S开始,反复使用产生式:将产生式左部的非终结符替换为右部的文法符号序列(展开产生式,用=>表示),直到得到一个终结符序列。

    1> 直接推导:利用产生式产生句子的过程中,将用产生式A→γ的右部代替文法符号序列αAβ中的A得到αγβ的过程,称αAβ直接推导出αγβ,记作:αAβ=>αγβ

    2> 零步或多步推导:若对于任意文法符号序列α1,α2,...αn,有α1=>α2=>...=>αn,则称此过程为零步或多步推导,记为:α1 =*> αn,其中α1=αn的情况为零步推导。

    3> 至少一次推导:若α1≠αn,即推导过程中至少使用一次产生式,则称此过程为至少一步推导,记为:α1 =+> αn

    (推导具有自反性和传递性)

    4> 由 CFGG 所产生的语言L(G)被定义为: L(G) = { ω┃S ωand ω∈T* },
    ​ L(G)称为上下文无关语言(Context Free Language, CFL),ω称为句子。
    ​ 若S =* > α,α∈(N∪T)*,则称α为G的一个句型。句子一定是句型,反之不是。

    5> 在推导过程中,若每次直接推导均替换句型中最左边的非终结符,则称为最左推导,由最左推导产生的句型被称为左句型。 类似的可以定义最右推导与右句型,最右推导也被称为规范推导。

    (3)推导、分析树与语法树

    1、分析树既反映语言结构的实质,也反映推导过程。

    2、对CFGG的句型,分析树被定义为具有下述性质的一棵树。

    (1) 根由开始符号所标记;
    (2) 每个叶子由一个终结符、非终结符、或ε标记;
    (3) 每个内部结点由一个非终结符标记;
    (4) 若A是某内部节点的标记,且X1,X2,...,Xn是该节点从左到右所有孩子的标记,则A→X1X2...Xn是一个产生式。若A→ε,则标记为A的结点可以仅有一个标记为ε的孩子。

    注:分析树的叶子,从左到右构成G的一个句型。若叶子仅由终结符标记,则构成一个句子。

    3、对CFG G的句型,表达式的语法树被定义为具有下述性质的一棵树:

    (1) 根与内部节点由表达式中的操作符标记;
    (2) 叶子由表达式中的操作数标记;
    (3)用于改变运算优先级和结合性的括号,被隐含在语法树的结构中。

    • 语法树是表示表达式结构的最好形式

    (4)二义性与二义性的消除

    二义性:若文法G对 同 一句子产生不止一棵分析树,则称G是二义的.

    结论:
    1> 一个句子有多于一棵分析树,仅与文法和句子有关,与采用的推导方法无关;
    2> 造成文法二义的根本原因:文法中缺少对文法符号优先级和结合性的规定

    二义性消除的方法:
    ① 改写二义文法为非二义文法;
    ② 规定二义文法中符号的优先级和结合性,使仅产生一棵分析树。

    3. 语法与文法简介

    (1)正规式与上下文无关文法

    • 记号可以用正规式描述,正规式适合描述线性结构,如标识符、关键字、注释等.
    • 句子可以用CFG描述,CFG适合描述具有嵌套(层次)性质的非线性结构,如不同结构的句子if-then-else\while-do等

    正规式所描述的语言结构均可以用CFG描述,反之不一定.

    (2)上下文有关文法CSG

    典型的这类语言结构包含:计数问题的抽象、变量的声明与引用、过程调用时形参与实参的一致性检查等.描述它们的文法被称为上下文有关文法(Context Sensitive Grammar,CSG).这些语言结构无法用上下文无关文法CSG来描述.

    (3)形式语言与自动机简介

    ​ 若文法G=(N,T,P,S)的每个产生式α→β中,均有α∈(N∪T),且至少含有一个非终结符,β∈(N∪T),则称G为0型文法.

    ​ 对0型文法施加以下第i条限制,即得到i型文法。

    ​ 1> G的任何产生式α→β(S→ε除外)满足|α|≤|β|;
    ​ 2> G的任何产生式形如A→β,其中A∈N,β∈(N∪T)*;
    ​ 3> G的任何产生式形如A→a或者A→aB(或者A→Ba),其中A和B∈N,a∈T。

    文法语言自动机
    短语文法(0型) 短语结构语言 图灵机
    CSG(1型) CSL 线性界线自动机
    CFG(2型) CFL 下推自动机
    正规文法(3型) 正规集 有限自动机

    4. 自上而下语法分析

    分为:递归下降分析法、预测分析法

    基本思想:对任何一个输入序列ω,从S开始进行最左推导,直到得到一个合法的句子或发现一个非法结构。整个自上而下分析是一个试探的过程,是反复使用不同产生式谋求与输入序列匹配的过程。

    提前准备——重写文法:1.消除左递归,以避免陷入死循环; 2.提取左因子,以避免回溯.

    (1)消除左递归

    定义:若文法G中的非终结符A,对某个文法符号序列α存在推导A =+> Aα,则称G是左递归的。若G中有形如A→Aα的产生式,则称该产生式对A直接左递归。

    <1> 消除文法的直接左递归

    A→Aα|β     替换为     A →βA'
                        A'→αA'|ε
    

    首先,整理A产生式为如下形式:A→ Aα1|Aα2|...|Aαm|β1|β2|...|βn
    然后用下述产生式代替A产生式:A→ β1 A'|β2 A'| ...|βn A'
    ​ A'→ α1 A' | α2 A' | ... | αm A' |ε

    <2> 消除文法的左递归

    核心思想:将无直接左递归的非终结符展开到其他产生式,然后消除其他产生式中的直接左递归(如果有的话)

    若G产生句子的过程中出现A=+A的推导,则无法消除左递归(出现回路)

    (2)提取左因子

    <1> 提取文法的左因子

    左因子产生原因:公共前缀:A → αβ1|αβ2
    方法:将 A → αβ1|αβ2|γ
    ​ 替换为 A→αA'|γ A'→β1|β2

    (3)递归下降分析

    直接以程序代码(的方式)模拟产生式产生语言的过程:

    基本思想:每个非终结符对应一个子程序(函数),过程体中:

    • 产生式右部的非终结符:对应子程序调用,
    • 产生式右部的终结符: 与输入记号序列进行匹配。

    特点:
    1> 子程序是递归的(因为文法是递归的);
    2> 程序与文法相关;
    3> 它对文法的限制是不能有公共左因子和左递归;
    4> 它是一种非形式化的方法,只要能写出子程序,用什么样的方法和步骤均可。

    (4)预测分析器

    ☆ 预测分析器由一张预测分析表、一个符号栈和一个驱动器组成,数学模型是下推自动机。
    ☆ 对文法的限制是不能有公共左因子和左递归

     
     

    预测分析器的核心概念:
    1> 分析方法:格局与格局变换
    2> 分析表+驱动器(模拟算法)
    3> 预测分析表的构造
    4> LL(文法、语言、分析器)

    ☆ 开始格局的剩余输入是全部输入序列,而接收格局中剩余输入应该为空,任何其他格局或出错格局中的剩余输入应该是全部输入序列的一个后缀.

    ☆ 改变格局的动作:

    ① 匹配终结符: 若top=ip(但≠#),则pop且next(ip);
    ② 展开非终结符:若top^= X且M[X,ip^]=α(X→α),则pop且push(α);
    ③ 报告分析成功: 若top ^= ip^ = #,则分析成功并结束;
    ④ 报告出错:其它情况,调用错误恢复例程.

    ☆ 驱动器算法

    ☆ 构造预测分析表

    步骤:1. 构造文法符号X的FIRST集合和非终结符的FOLLOW集合;2. 根据两个集合构造预测分析表.

    通俗地讲,α的FIRST集合就是从α开始可以导出的文法符号序列中的开头终结符。而A的FOLLOW集合,就是从开始符号可以导出的所有含A的文法符号序列中紧跟A之后的终结符.

    <1> 计算X的FIRST集合 -----自下而上计算
    <2> 计算所有非终结符的FOLLOW集合 —— 自上而下计算
    <3> 构造预测分析表
    <4> LL(1)文法

    文法G被称为是LL(1)文法,当且仅当为它构造的预测分析表不含多重定义的条目。由此分析表所组成的分析器被称为LL(1)分析器,它所分析的语言被称为LL(1)语言

    ☆ 第一个L代表从左到右扫描输入序列,第二个L表示产生最左推导,1表示在确定分析器的每一步动作时向前看一个终结符.

    推论3.2 G是LL(1)的,当且仅当G的任何两个产生式A→α|β满足:
    1. 对任何终结符a,α和β不能同时推导出以a开始的串;即First(α) ∩ First(β) = ∅
    2. α和β最多有一个可以推导出ε;
    3. 若β =*> ε,则α不能导出以FOLLOW(A)中终结符开始的任何串. 即First(α) ∩ Follow(A) = ∅
    

    ☆ 无论是递归下降子程序法还是非递归的预测分析法,他们都只能处理LL(1)文法.

    5. 自下而上语法分析

    ☆ 自上而下分析采用的是推导;自下而上分析采用的是归约(规范归约—剪句柄—移进/归约分析—SLR(1)分析器).

    (1)自下而上分析的基本方法

    基本思想:最左归约.

    对于每个输入序列ω:从左到右扫描ω; 从ω开始,反复用产生式的左部替换产生式的右部(即当前句型中的句柄)、谋求对ω的匹配,最终得到文法的开始符号,或者发现一个错误。

    基本概念:

    a) > 设αβδ是文法G的一个句型,若存在S=*>αAδ,A=+>β, 则称β是句型αβδ相对于A的"短语".
       > 特别的,若 有A→β,则 称β是句型αβδ相对于产生式A→β的"直接短语".
       > 一个句型的最左直接短语被称为"句柄".
    
       特征:
        1.  短语:以非终结符为根子树中所有从左到右的叶子;
        2.  直接短语:只有父子关系的子树中所有从左到右排列的叶子(树高为2);
        3.  句柄:最左边父子关系树中所有从左到右排列的叶子(句柄是唯一的)
        
        
    b)最左归约:若 α是文法G的句子且满足下述条件,则称序列αn,αn-1,...,α0是α的一个最左归约。
       1) αn = α
       2) α0 = S(S是G 的开始符号)
       3) 对任何i(0<i<=n),αi-1是将αi中句柄替换为相应产生式左部非终结符得到的
       
     ☆ 最左归约的逆过程是一个最右推导,分别称最右推导和最左归约为规范推导和规范归约.
     
     c)移进-归约分析器
     1. 工作方式:格局与格局变换
     2. 分析表
     3. 驱动器(模拟算法)
     4. SLR分析表的构造
     5. LR(文法、语言、分析器)
    
    ☆ 改变格局的动作:
    1. 移进(shift):当前剩余输入的下一终结符进栈。
    2.归约(reduce):将栈顶句柄替换为对应非终结符(最左归约)
    3.接受(accept):宣告分析成功
    4. 报错(error):发现语法错误,调用错误恢复例程
    
     
     

    (2) LR分析

    a) LR分析与LR文法
    LR分析:允许左递归,但不能有二义

    定义3.15 若为文法G构造的移进-归约分析表中不含多重定义的条目,则称G为"LR(k)文法",分析器被称为是"LR(k)分析器",它所识别的语言被称为"LR(k)语言"。"L"表示从左到右扫描输入序列,"R"表示逆序的最右推导,"k"表示为确定下一动作向前看的终结符个数,一般情况下k<=1。当k=1时,简称"LR"。             
    

    构造SLR(1)分析器

    <1> 活前缀与LR(0)项目

     第1步第2~N步状态
    词法--DFA ε-closure(S) ε-closure(smove(S,a)) 状态集
    语法--DFA closure(I) closure(goto(I,x)) 项目集

    出现在移进-归约分析器栈中的右句型的前缀,被称为文法G的活前缀(viable prefix).
    LR(0)项目(简称项目)是这样一个产生式,在它右边的某个位置有一个点"."。对于A→ε,它仅有一个项目A→.。
    项目A→α.β显示了分析过程中看到(移进)了产生式的多少。
    β不为空的项目称为可移进项目,β为空的项目称为可归约项目.

    <2> 拓广文法与识别活前缀的DFA

    G' = G ∪ {S' → S}
    其中:S' → S是识别S的初态,S' → S. 是识别S的终态. 目的是使最终构造的DFA状态集中具有唯一的初态和终态. ① closure(I):从项目集I不经任何文法符号到达的项目全体;

    ② goto(I,x):所有从I经文法符号x能直接到达的项目全体。

    项目[S’→.S]和所有“.”不在产生式右部最左边的项目称为核心项目(kernel items),
    其它“.”在产生式右部最左边的项目(不包括[S’→.S])称为非核心项目(nonkernel items).
    
    核心项目:J=goto(I,X),S'→.S(作为项目集的代表)
    非核心项目:closure(J)-J(特点:可由J某中某项目算得) 
    
     
     

    <3> 识别活前缀

    定义3.21 若存在最右推导S’=*> αAω => αβ2ω,则称项目[A→β1.β2] 对活前缀αβ1有效。
    
    当一个项目集中同时存在:
        1. A→β1.β2和B→β.:既可移进又可归约,移进/归约冲突
        2.A→α.和B→β.:均可指导下一步分析,归约/归约冲突
    
    解决方法:简单向前看一个终结符:
        1. 移进/归约冲突:若FIRST(β2)∩FOLLOW(B)=Φ,冲突可解决
        2. 归约/归约冲突:若FOLLOW(A)∩FOLLOW(B)=Φ,冲突可解决
    
    若冲突可以解决,则称文法为SLR(1)文法,构造的分析表为SLR(1)分析表。
    SLR(1)文法:简单向前看一个终结符即可解决冲突
    ☆ 二义文法不是SLR(1)文法
    

    第四章 静态语义分析

    采用语法制导翻译生成中间代码

    1. 语法制导翻译简介

    (1)语法与语义的关系

    语法是指语言的结构、即语言的“样子”;
    语义是指附着于语言结构上的实际含意,即语言的“意义”.
    一个语法上正确的句子,它所代表的意义并不一定正确.

    语义分析的作用

    • 检查结构正确的句子所表示的意思是否合法;
    • 执行规定的语义动作,如:表达式求值、符号表的查询/填写、中间代码生成等

    ☆ 应用最广的语义分析方法是语法制导翻译,他的基本思想是将语言结构的语义以属性的形式赋予代表此结构的文法符号,而属性的计算以语义规则的形式赋予由文法符号组成的产生式.

    (2)属性/语义规则的定义

    定义4.1 对于产生式A→α,其中α是由文法符号X1X2...Xn组成的序列,它的语义规则可以表示为(4.1)所示关于属性的函数f:
              b := f(c1, c2, ..., ck)                  (4.1)
    语义规则中的属性存在下述性质与关系:
          (1)   称(4.1)中属性b依赖于属性c1, c2, ..., ck。
          (2) 若b是A的属性,c1, c2, ..., ck是α中文法符号的属性,或者A的其它属性,则称b是A的综合属性。
          (3) 若b是α中某文法符号Xi的属性,c1, c2, ..., ck是A的属性,或者是α中其它文法符号的属性,则称b是Xi的继承属性。
          (4) 若语义规则的形式如下述(4.2),则可将其想像为产生式左部文法符号A的一个虚拟属性。属性之间的依赖关系,在虚拟属性上依然存在。
              f(c1, c2, ..., ck)                (4.2)          ■
    

    ☆ 继承属性从前辈和兄弟的属性计算得到,综合属性从子孙和自身的其他属性计算得到.

    即,继承属性"自上而下,包括兄弟",综合属性"自下而上,包括自身".

    (3)语义规则的两种形式

    ☆ 语义规则的两种形式(忽略实现细节,二者作用等价)

    <1> 语法制导定义(Syntax Directed Definition)

    用抽象的属性和运算表示的语义规则;(公式,做什么)
    

    <2> 翻译方案(Translation Scheme)

    用具体的属性和运算表示的语义规则。(程序段,如何做)
    

    继承属性是自上而下计算的,综合属性是自下而上计算的.

    (4)LR分析翻译方案的设计

    ☆ LR分析中的语法制导翻译实质上是对LR语法分析的扩充:

    1. 扩充LR分析器的功能

    当执行归约产生式的动作时,也执行相应产生式对应的语义动作。由于是归约时执行语义动作,

    ​ 因此限制语义动作仅能放在产生式右部的最右边

    1. 扩充分析栈

    ​ 增加一个与分析栈并列的语义栈,用于存放分析栈中文法符号所对应的属性值

    ☆ 扩充后的LR分析最适合对综合属性的计算,而对于继承属性的计算还需要进行适当的处理.

    2. 中间代码简介

    ☆ 中间代码应具备的特性
    1)便于语法制导翻译
    2)既与机器指令的结构相近,又与具体机器无关.

    使用中间代码的好处:一是便于编译器程序的开发和移植,二是代码进行优化处理.

    ☆ 中间代码的主要形式:后缀式、树、三地址码等.最基本的中间代码形式是树?;最常用的中间代码形式是三地址码,它的实现形式常采用四元式形式。

    ☆ 符号表是帮助声明语句实现存储空间分配的重要数据结构。

    (1)后缀式

    操作数在前,操作符紧随其后,无需用括号限制运算的优先级和结合性;便于求值.

    (2)三地址码

    ① 三元式 形式: (i) (op, arg1, arg2)

    ​ 三地址码:(i):= arg1 op arg2

    序号的双重含义:既代表此三元式,又代表三元式存放的结果

    存放方式:数组结构,三元式在数组中的位置由下标决定

    弱点:给代码的优化带来困难

    ② 四元式 形式: ( i ) (op,arg1,arg2,result)

    ​ 所表示的计算: result:= arg1 op arg2

    1. 四元式与三元式的唯一区别:将由序号所表示的运算结果改为:用(临时)变量来表示。

    2. 此改变使得四元式的运算结果与其在四元式序列中的位置无关.为代码的优化提供了极大方便,因为这样可以删除或移动四元式而不会影响运算结果.

    ③ 树形表示

    1> 语法树真实反映句子结构,对语法树稍加修改(加入语义信息),即可以作为中间代码的一种形式(注释语法树)
    2> 树的优化表示-DAG
    3> 树与其他中间代码的关系

    树表示的中间代码后缀式三地址码之间有内在联系

    1. 树 → 后缀式

    ​ 方法:对树进行深度优先后序遍历,得到的线性序列就是后缀式,或者说后缀式是树的一个线性化序列;

    1. 树 → 三元式/四元式

    特点:树的每个非叶子节点和它的儿子对应一个三元式或四元式;

    方法:对树的非叶子节点进行深度优先后序遍历,即得到一个三元式或四元式序列。

    3. 符号表简介

    • 符号表的作用:连接声明与引用的桥梁,记住每个符号的相关信息,如作用域和类型等,帮助编译的各个阶段正确有效地工作。
    • 符号表的基本目标:有效记录信息、快速准确查找。
    • 符号表设计的基本要求:
      • 正确存储各类信息;
      • 适应不同阶段的需求;
      • 便于有效地进行查找、插入、删除和修改等操作;
      • 空间可以动态扩充.

    (1)构成名字的字符串

    构成名字的字符串的存储方式:直接存储---定长数据(直接将构成名字的字符串放在符号表条目中)和间接存储---变长数据(将构成名字的字符串统一存放在一个大的连续空间内,字符串与字符串之间采用特殊的分隔符隔开,符号表条目中仅存放指向该字符串首字符的指针).

    (2)名字的作用域

    ☆ 程序语言范围的划分可以有两种划分范围的方式:并列嵌套

    名字的作用域规则:规定一个名字在什么样的范围内应该表示什么意义.

    <1> 静态作用域规则(static-scope rule):编译时就可以确定名字的作用域,即仅从静态读程序就可确定名字的作用域
    <2> 最近嵌套规则(most closely nested):名字的声明在离其最近的内层起作用
    

    (3)线性表

    符号表以栈(线性表)的方式组织.

    线性表上的操作:查找、插入、删除、修改

    查找:从表头(栈顶)开始,遇到的第一个符合条件的名字;插入:先查找,再加入在表头(栈顶);

    关键字 = 名字+作用域;

    (4)散列表

    名字挂在两个链上(便于删除操作):

    1. 散列链(hash link): 链接所有具有相同hash值的元素,表头在表头数组中;
    2. 作用域链(scope link):链接所有在同一作用域中的元素,表头在作用域表中.

    ☆ 操作:查找、插入、删除

    4. 声明语句的翻译

    (1)变量的声明

    ☆ 一个变量的声明应该由两部分来完成:类型的定义变量的声明

    • 类型定义:为编译器提供存储空间大小的信息
    • 变量声明:为变量分配存储空间
    • 组合数据的类型定义和变量声明:定义与声明在一起,定义与声明分离.

    1> 简单数据类型的存储空间是预先确定的,如int可以占4个字节,double可以占8个字节,char可以占1个字节等

    2> 组合数据类型变量的存储空间,需要编译器根据程序员提供的信息计算而定.

    (2) 过程

    1.过程(procedure):过程头(做什么) +  过程体(怎么做);
       - 函数:  有返回值的过程
       - 主程序:  被操作系统调用的过程/函数
    
    2.过程的三种形式:过程定义、过程声明和过程调用。
       过程定义:过程头+过程体;
       过程声明:过程头;
    
    3. 左值与右值 
       1> 直观上,出现在赋值号左边和右边的量分别称为左值和右值;
       2> 实质上,左值必须具有存储空间,右值可以仅是一个值,而没有存储空间.
       3> 形象地讲,左值是容器,右值是内容.
       
    4. 参数传递
       1> 形参与实参
            - 声明时的参数称为形参(parameter或formal parameter)
            - 引用时的参数称为实参(argument或actual parameter)
       2> 常见的参数传递形式:(不同的语言提供不同的形式)
            - 值调用(call by value)---过程内部对参数的修改,不影响作为实参的变量原来的值.
            - 引用调用(call by reference)--- 过程内部对形参的修改,实质上是对实参的修改.
            - 复写-恢复(copy-in/copy-out)--- ① 过程内对参数的修改不直接影响实参,避免了副作用;
                                            ② 返回时将形参内容恢复给实参,实现参数值的返回.
            - 换名调用(call by name)--- 宏调换
       3> 参数传递方法的本质区别: 实参是代表左值、右值、还是实参本身的正文.
       
    5. 作用域信息的保存
    ☆ 能够画出嵌套过程的嵌套关系树(P191 4.33),根据语法制导翻译(P193 4.35)画出分析树,写出推导步骤,构造的符号表
    

    5. 简单算术表达式与赋值句

    P197 例4.36 主要是变量类型的转换

    6. 数组元素的引用

    (1)数组元素的地址计算

    • 注意是行主存储还是列主存储

    (2)☆数组元素引用的语法制导翻译(考试热点之一)

    • P201 例4.37

    7. 布尔表达式

    布尔表达式的计算有两种方法:数值表示的直接计算和逻辑表示的短路计算

    ☆ 布尔表达式短路计算的翻译:短路计算的控制流,真出口与假出口,真出口链与假出口链,拉链回填技术(P207 例4.41)(考试热点之一)

    8. 控制语句

    控制语句的分类:①无条件转移、②条件转移、③循环语句、④分支语句

    • 无条件转移(goto)\条件转移(if、while)
    • 条件转移的语法制导翻译:P213 例4.42
    多看课件PPT,多做题练手


    作者:舰长同学
    链接:https://www.jianshu.com/p/eb63d31ad638
    来源:简书
    简书著作权归作者所有,任何形式的转载都请联系作者获得授权并注明出处。

    转载于:https://www.cnblogs.com/jacksplwxy/p/10807180.html

    展开全文
  • 《计算机科学丛书:编译原理》全面、深入地探讨了编译器设计方面的重要主题,包括词法分析、语法分析、语法制导定义和语法制导翻译、运行时刻环境、目标代码生成、代码优化技术、并行性检测以及过程间分析技术,并在...
  • 编译原理入门笔记

    千次阅读 2018-05-24 20:24:37
    什么是编译原理? 编译原理这门课程本来是很多大学必修的一门课程,但是我的本科课程里面并没有安排这门课程,由于研究生需要研究这方面的基础,于是开始自学。相信很多人都知道这门课程是计算机基础课程中比较难...

    什么是编译原理?

        编译原理这门课程本来是很多大学必修的一门课程,但是我的本科课程里面并没有安排这门课程,由于研究生需要研究这方面的基础,于是开始自学。相信很多人都知道这门课程是计算机基础课程中比较难入门的课程,于是我在开始之前也有点方,于是开始参考各路大神的经验。

    知乎上有关于相关问题的回答

    最终我在慕课上参加了哈工大张陈鄞老师的课程,其实网上的课程基本都差不多,反正都比较枯燥,选择你喜欢的就好。(ps:我主要是看脸,哈哈哈哈~,大笑陈老师说话好温柔,听着舒服!!!!)

    下面就是我学习过程做的一些笔记,在这里记录一下。

    First:啥也不说了,这门课程开始一定要有一定的基础,不然真的看不下去。。。。。

    首先你必须学习:C语言程序设计,了解基本的C语言语法等,然后就是离散数学的集合和图论,数据结构也需要了解一点。就差不多了。

    看完上面的基础就可以开始上课了。其实只要跟着老师学还是可以听懂的。



    上图主要说明了编译器工作的一个过程-主要工作就是翻译的过程。把高级语言编写的源代码变成目标语言。


    编译器的主要流程如上图所示。

    词法分析:词法分析的主要任务从左向右逐行扫描源程序的字符,识别出各个单词,确定单词的类型。将识别出的单词转换成统一的机内表示——词法单元(token)形式


    比如:int a;这句代码输入,相应的token就是<INT,->;<IDC,a>,<,SEMI,->其中INT表示int关键字,IDC表示变量名,SEMI表示分号。ps:这里用的INT,IDC并不是标准统一的符号,这里只是为了举例子,方便理解,如果自己写编译器是可以自己定义的。

    语法分析:语法分析器(parser)从词法分析器输出的token序列中识别出各类短语,并构造语法分析树(parse tree)


    语义分析:收集标识符的属性信息——包括:存储位置、长度、值、作用域、参数和返回值信息等,同时在语义分析步骤过程,还需要进行语义检查——变量或过程未经声明就使用、变量或过程名重复声明、运算分量类型不匹配、操作符与操作数之间的类型不匹配、数组下标不是整数、对非数组变量使用数组访问操作符、对非过程名使用过程调用操作符、过程调用的参数类型或数目不匹配、函数返回类型有误。

    中间代码生成:类似把程序变成汇编指令的样子。

    比如,a=b+c;   中间代码就是<+,a,b,c>这样的四元式。

    学到这里我们对编译原理有了初步的了解,接下来详细介绍每一个步骤。


    展开全文
  • 编译原理:总结

    万次阅读 多人点赞 2019-01-08 11:33:57
    编译器概述 编译器的核心功能 编译器的核心功能是把源代码翻译成目标代码: 翻译!!!目标代码!!! 理解源代码:词法分析、语法...转化为等价的目标代码:中间代码生成、目标代码生成 ...语法分析器:单词流-&am

    编译器概述

    编译器的核心功能

    编译器的核心功能是把源代码翻译目标代码

    翻译!!!目标代码!!!

    • 理解源代码:词法分析、语法分析、语义分析
    • 转化为等价的目标代码:中间代码生成、目标代码生成
    • 更好:优化方法

    编译器的结构

    每个阶段将源程序从一种表示转换成另一种表示。
    随着编译器各个阶段的进展,源程序的内部表示不断地发生变化。

    • 词法分析器:字符流->单词流
    • 语法分析器:单词流->语法树
    • 语义分析器:
      • 收集标识符的属性信息:
        • 类型(Type)
        • 种属(Kind)
        • 存储位置、长度
        • 作用域
        • 参数和返回值信息
      • 语义检查:
        • 变量或过程未经声明就使用
        • 变量或过程名重复声明
        • 运算分量类型不匹配
        • 操作符与操作数之间的类型不匹配
    • 中间代码生成器:抽象语法树->中间表示(与平台无关的抽象程序):
      1. 易于产生
      2. 易于翻译成目标程序
      3. 三地址码:temp1=c*d;temp2=b+temp1;a=temp2
      4. 四元式:(op, arg1, arg2, result);(* , c , d , temp1);(+ , b, temp1 , temp2);(= , temp2 , - , a)
    • 代码优化器:试图改进中间代码,以产生执行速度较快的机器代码:
      • temp1=c*d;temp2=b+temp1;a=temp2
      • change to:temp1=c*d;a=b+temp1
    • 代码生成器:生成可重定位的机器代码或汇编代码:
      • temp1=c*d;a=b+temp1
      • change to:Mov R2,c;Mul R2, d;Mov R1, b;Add R2, R1;Mov a, R2
      • 一个重要任务是为程序中使用的变量合理分配寄存器
    • 符号管理表:
      • 基本功能是记录源程序中使用的标识符,
      • 并收集与每个标识符相关的各种属性信息,
      • 并将它们记载到符号表中。
    • 错误处理器:
      • 处理方式:报告错误,应继续编译
      • 大部分错误在语法分析、语义分析阶段检测出来
      • 词法分析:字符无法构成合法单词
      • 语法分析:单词流违反语法结构规则
      • 语义分析:语法结构正确,但无实际意义

    在这里插入图片描述


    程序设计语言及其文法

    字母表和串上的运算

    串:是字母表中符号的一个有穷序列。
    ∑ 是一个字母表,任意 x∈∑*,x 是 ∑ 上的一个串。

    语言的定义和运算、句子的定义

    设 ∑ 是一个字母表,任意L 属于 ∑*,L 称为字母表 ∑ 上的一个语言
    任意 x∈L,x 叫做 L 的一个句子

    文法的定义

    文法是用于描述语言的语法结构的形式规则。
    任何一种语言都有它自己的文法,不管它是机器语言还是自然语言。

    • 自然语言的文法:主 谓 宾
    • 机器语言也有描述它语言构成的特定文法

    文法可以定义为一个四元组(VT, VN, S, P)

    1. 一个终结符号集合VT
    2. 一个非终结符号集合VN
    3. 一个产生式集合P,定义语法范畴。产生式:A → α,产生式:描述了将终结符和非终结符组合成串的方法
    4. 一个特定的非终结符——开始符号S

    文法的四种类型

    • 0型文法:也称为短语文法
      • ∀α → β∈P,α中至少包含1个非终结符
      • 任何0型语言都是递归可枚举的;反之,递归可枚举集必定是一个0型语言。
    • 1型文法:上下文有关文法context-sensitive
      • ∀ α→β,都有|α| ≤ |β| ,仅 S→ε除外
      • 产生式的形式描述:α1Aα2 → α1βα2 (α1, α2,β∈(VN∪VT ) *,β≠ε,A∈ VN)
      • 即:A只有出现在α1, α2的上下文中,才允许用β替换。
    • 2型文法:上下文无关文法, context-free grammar. CFG
      • ∀ α→β,都有α∈VN,β∈(VN∪VT)*
      • 产生式的形式描述:A →β (A∈VN)
      • 即:β取代A时,与A所处的上下文无关。
    • 3型文法:regular grammar, RG,也称正则文法
      • 每个产生式均为 “A→aB”或“A→a” —— 右线性
      • 或 “A→Ba”或“A→a” —— 左线性
      • (A、B∈VN,a∈VT*)

    推导和归约

    推导:用产生式的右部替换产生式的左部

    句子、句型和语言的定义

    • 如果Sαα(VTVN)S →^* α,α∈(V_T∪V_N)^*,则称α是G的一个句型
    • 如果SwwVTS →^* w,w ∈V_T^*,则称w是G的一个句子
    • 由文法G的开始符号S推导出的所有句子构成的集合称为文法G生成的语言,记为L(G)。即L(G)={w|SwwVTS →^* w,w ∈V_T^*}

    语法生成树

    用图形的方式展示推导过程

    二义性:多个语法分析树生成同一个终结符号串

    程序语言定义

    任何语言实现的基础是语言定义
    语言的定义决定了该语言具有什么样的语言功能、 什么样的程序结构、以及具体的使用形式等细节问题。

    • 词法:是指单词符号的形成规则。(状态转换图、正则表达式和有穷自动机)
    • 语法:是指一组规则,用它可产生一个程序。(下推自动机理论和上下文无关文法是讨论语法分析的理论基础)
    • 规则:词法规则 + 语法规则
    • 语义:定义语言的单词符号和语法单位的意义。(属性方法和基于属性文法的语法制导翻译方法)
    • 形式语言:上述的定义是用文字来描述的,当设计编译程序时,就要把它用形式的方式描述出来,就要用到形式语言。

    参数传递方法:

    1. 传值调用
    2. 引用调用
    3. 复制恢复(传值结果)
    4. 传名调用

    词法分析

    词法分析器的作用

    • 识别源程序中的单词是否有误
    • 读入源程序字符流、组成词素,输出词法单元序列
    • 过滤空白、换行、制表符、注释等
    • 将词素添加到符号表中

    词法分析器的角色

    编译过程的分析部分:词法分析 + 语法分析

    • 简化编译器的设计:词法分析器可以首先完成一些简单的处理工作
    • 提高编译器的效率:相对于语法分析,词法分析过程简单,可高效实现增强编译器的可移植性(输入设备无关)

    输入缓冲

    三种实现方式

    1. 自动生成工具——Lex,生成工具提供读取输入和缓冲的函数
    2. 高级语言手工编码,利用高级语言提供的I/O函数
    3. 汇编语言编程,直接访问磁盘
    • 1 → 3,性能↗ ,实现难度↗
    • 唯一读取文件的阶段,值得优化
    • 方案:
      • 双缓冲方案
      • 哨兵标记

    词法单元的描述:正则表达式定义规则

    若 r, s为正则表达式,表示语言L(r)L(s)L(r)和L(s),则(从1到4优先级递增)

    1. (r)(s)L(r)L(s)(r) | (s)是正则表达式,表示语言L(r)∪L(s)
    2. (r)(s)L(r)L(s)(r)(s)是正则表达式,表示语言L(r)L(s)
    3. (r)(L(r))(r)*是正则表达式,表示语言(L(r))*
    4. (r)L(r)(r) 是正则表达式,表示语言L(r)

    正则表达式等价(equivalent):r = s → 表示的语言相同,L(r)=L(s)L(r) = L(s)

    • 能被5整除的10进制整数:[1-9][0-9]*(0|5)|0|5(!!!
    • C 语言标识符:[_a-zA-Z][_a-zA-Z0-9]*
    • C 语言无符号数的集合:
      • digit → [0-9]
      • digits → digit+
      • number → digits (.digits)? (E(+|-)? digits)?
    • 不包含连续的0的01串:((ε|0)1)*0?

    词法单元的识别

    状态转换图(注意初态和终态)

    不确定有限自动机

    数学模型,表示为五元组 M = {S,Σ,δ,s0,F},其中

    • S:有限状态集
    • Σ:有穷字母表,其元素为输入符号
    • δ:S×Σ到S的子集的映射,即 δ: S×(Σ∪{ε}) → 2S2^S,状态转换函数。
    • s0∈S 是唯一的初态
    • F⊆S 是一个终态集

    正则表达式(描述单词)
    NFA(定义语言):存在缺点,同一符号或ε和其它符号 → 多义性,难以实现
    DFA(适于计算机实现)

    NFA 和 DFA 都可识别正则表达式,时-空折衷
    词法分析器可用一组NFA来描述,每个NFA表示一个单词

    设计自动机(注意初态的 →start 和终态的双圈)

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    词法分析器的构造

    正则表达式 → 构造NFA(Thompson构造法)

    构造规则:注意开始的箭头和结束的双圈

    • N(ε)

    在这里插入图片描述

    • N(a)

    在这里插入图片描述

    • N(s|t)

    在这里插入图片描述

    • N(st)

    在这里插入图片描述

    • N(s*)

    在这里插入图片描述

    NFA → 转换DFA(子集构造法)

    在这里插入图片描述

    1. ε-closure(0)={0,1,2,4,7}=A
    2. ε-closure(δ(A,a)) = ε-closure(δ({0,1,2,4,7},a))
      = ε-closure({3,8})
      = {1,2,3,4,6,7,8} = B
      ∴ Dtran[A,a] = B
      ε-closure(δ(A,b)) = ε-closure(δ({0,1,2,4,7},b))
      = ε-closure({5}) = {1,2,4,5,6,7} = C
      ∴ Dtran[A,b] = C
    3. ε-closure(δ(B,a)) = ε-closure(δ({1,2,3,4,6,7,8},a))
      = ε-closure({3,8})
      = {1,2,3,4,6,7,8} = B
      ∴ Dtran[B,a] = B
      ε-closure(δ(B,b)) = ε-closure(δ({1,2,3,4,6,7,8},b))
      = ε-closure({5,9})
      = {1,2,4,5,6,7,9} = D
      ∴ Dtran[B,b] = D
    4. ε-closure(δ(C,a)) = ε-closure(δ({1,2,4,5,6,7},a))}
      = ε-closure({3,8})
      = {1,2,3,4,6,7,8} = B
      ∴ Dtran[C,a] = B
      ε-closure(δ(C,b)) = ε-closure(δ({1,2,4,5,6,7},b))
      = ε-closure({5})
      = {1,2,4,5,6,7} = C
      ∴ Dtran[C,b] = C
    5. ε-closure(δ(D,a)) = ε-closure(δ({1,2,4,5,6,7,9},a))}
      = {1,2,3,4,6,7,8} = B
      ∴ Dtran[D,a] = B
      ε-closure(δ(D,b)) = ε-closure(δ({1,2,4,5,6,7,9},b))}
      = {1,2,4,5,6,7,10} = E
      ∴ Dtran[D,b] = E
    6. ε-closure(δ(E,a)) = ε-closure(δ({1,2,4,5,6,7,10},a))}
      = {1,2,3,4,6,7,8} = B
      ∴ Dtran[E,a] = B
      ε-closure(δ(E,b)) = ε-closure(δ({1,2,4,5,6,7,10},b))}
      = {1,2,4,5,6,7} = C
      ∴ Dtran[E,b] = C
    7. 最终结果:

    在这里插入图片描述

    最小化DFA状态

    • 初始,两个组:终态与非终态
    • 划分方法,对于状态组A={s1,s2,…,sk}
      • 对符号a,得到其转换状态t1,t2,…,tk
      • 若t1,t2,…,tk属于不同状态组,则需将A对应划分为若干组

    在这里插入图片描述

    在这里插入图片描述


    语法分析

    语法分析器的类型

    在自顶向上的语法分析方法中,分析的关键是:选择候选式
    在自底向上的语法分析方法中,分析的关键是:寻找句柄

    自顶向下分析器:递归下降法,LL(1)
    自底向上分析器:LR()

    LL 和 LR 都不能表示所有 CFG。

    LR分析表种类:

    • LR(0):局限性大,但它是建立其它分析表的基础
    • SLR (1) :易实现,功能比LR(0)稍强些
    • LR(1) :分析能力最强,但实现代价高
    • LALR (1) :功能介于SLR(1)和LR(1)之间,适用于大多数程序设计语言的结构,并且可以比较有效地实现。同心集。

    语法分析器的作用

    • 利用语法检查单词流的语法结构
    • 构造语法分析树
    • 语法错误和修正
    • 识别正确语法
    • 报告错误

    语法错误处理

    不同层次的错误

    • 词法:拼写错误(then → them)
    • 语法:单词漏掉、顺序错误(花括号不配对)
    • 语义:类型错误(声明void f()和调用aa = f())
    • 逻辑:无限循环/递归调用( == → = )

    错误处理目标

    • 清楚、准确地检测、报告错误及其发生位置
    • 快速恢复,继续编译,以便发现后续错误
    • 不能对正确程序的编译速度造成很大影响

    LL,LR,可最快速度发现错误:可行前缀特性,viable-prefix property,当一个输入前缀不是语言中任何符号串前缀——发生错误。

    错误恢复策略

    1. 错误恢复策略
      • 丢弃单词,直到发现 “同步”单词,设计者指定同步单词集,{end, “;”, “}”, …}
      • 缺点:丢弃输入导致遗漏定义,造成更多错误;遗漏错误
      • 优点:简单 → 适合每个语句一个错误的情况
    2. 短语层次的恢复
      • 局部修正,继续分析,同样由设计者指定修正方法。e.g. “,” → “;”,删除“,”,插入“;”
      • 与恐慌模式相结合,避免丢弃过多单词
    3. 错误产生式
      • 理解、描述错误模式,文法添加生成错误语句的产生式,拓广文法 → 语法分析器程序。( 错误检测信息+自动修正)
      • e.g. 对C语言赋值语句,为“:=”添加规则 报告错误,但继续编译
    4. 全局纠正
      • 错误程序 → 正确程序,寻找最少修正步骤,插入、删除、替换
      • 过于复杂,时空效率低

    上下文无关文法

    推导:描述文法定义语言的过程,自顶向下构造语法分析树的精确描述。

    两个CFG生成相同语言,两个CFG等价。

    最左推导,最右推导。

    语法树:推导的图示,但不体现推导过程的顺序。

    一棵语法树对应多个推导,但是有唯一的最左推导和最右推导。

    二义性文法存在某个句子对应多个语法树,多个最左(右)推导。

    证明CFG G生成语言L:(数学归纳法)

    1. G生成的每个符号串都在L中
    2. L中每个符号串都可由G生成

    正则表达式可描述的语言CFG均可描述。
    RG 都可用 NFA 表示,CFG 都是 RG,所以 CFG 都可用 NFA 表示。

    为什么还需要正则表达式?

    • 词法规则很简单,正则表达式描述能力足够
    • 正则表达式更简洁、更容易理解
    • 能更自动构造更高效的词法分析器
    • 使编译器前端更模块化

    设计 CFG

    在这里插入图片描述

    CFG 的修改

    • 消除二义性
    • 消除左递归(间接左递归):见附录
    • 消除空产生式:利用产生式进行代入
    • 消除回路:保证每个产生式都加入终结符(开始符号的空产生式除外)
    • 提取左公因子:预测分析方法要求—— 向前搜索一个单词,即可确定产生式

    在这里插入图片描述

    在这里插入图片描述

    CFG 优点

    • 给出精确的,易于理解的语法说明
    • 自动产生高效的分析器
    • 可以给语言定义出层次结构
    • 以文法为基础的语言的实现便于语言的修改

    问题:CFG 文法只能描述编程语言的大部分语法。(无法表示标识符必须在使用前定义,函数形参和实参数目应匹配)

    递归下降分析法

    缺点

    • 不能处理左递归
    • 复杂的回溯技术
    • 回溯导致语义工作推倒重来
    • 难以报告出错的确切位置
    • 效率低

    产生回溯的原因:进行推导时,若产生式存在多个候选式,选择哪个候选式进行推导存在不确定性。
    消除回溯的基本原则:对文法的任何非终结符,若能根据当前读头下的符号,准确的选择一个候选式进行推导,那么回溯就可以消除。

    LL(1):构造预测分析表

    计算FIRST和FOLLOW函数

    • FIRST

    FIRST(X1 X2 … Xn ) = FIRST (X1) “+”
    FIRST(X2) if ε is in FIRST(X1) “+”
    FIRST(X3) if ε is in FIRST(X2) “+”

    FIRST(Xn) if ε is in FIRST(Xn-1)
    注意:仅当对所有i,e∈FIRST(Xi),才将e加入FIRST(X1 X2 … Xn)

    • FOLLOW

    $加入FOLLOW(S),S为开始符号,$为输入串结束标记
    若A → αBβ,则FIRST(β)中符号除ε外,均加入FOLLOW(B)
    若A → αB 或 A → αBβ 且 β →* ε,FOLLOW(A)中所有符号加入FOLLOW(B)

    在这里插入图片描述

    应用构造算法

    • 对所有的终结符a ∈ FIRST(α),将 A->α 加入M[A,a]
    • 若ε ∈ FIRST(α),对所有的终结符b ∈ FOLLOW(A),将 A->α 加入M[A,b]
    • 所有未定义的表项设置为错误

    在这里插入图片描述

    e.g. id+id*id

    在这里插入图片描述

    LL(1)文法

    若文法G的预测分析表M中不含有多重定义项,则称G为 LL(1)文法。且无二义性,无左递归。

    计算 First 和 Follow 习题

    在这里插入图片描述

    预测分析法的错误恢复

    恐慌模式恢复策略

    考虑非终结符的同步单词集

    • FOLLOW(A)——略过A
    • 将高层结构的开始符号作为低层结构的同步集
    • FIRST(A)——重新开始分析A

    在这里插入图片描述

    • Follow 集为 sync,弹出一个非终结符
    • 其他的空位则跳过输入符号

    在这里插入图片描述

    短语层次错误恢复

    预测分析表空位填入错误处理函数

    自顶向下分析:预测分析法

    预测分析法实现步骤

    • 构造文法
    • 改造文法:消除二义性、消除左递归、消除回溯
    • 求每个变量的FIRST集和FOLLOW集,构造预测分析表
    • 检查是不是LL(1) 文法
    • 对于递归的预测分析,为每一个非终结符编写一个过程;对于非递归的预测分析,实现表驱动的预测分析算法

    缺点:不是所有文法满足LL(1)要求

    自底向上分析方法

    自底向上语法分析,是从输入符号串出发,试图把它归约成识别符号。
    从图形上看,自底向上分析过程是以输入符号串作为末端结点符号串,向着根结点方向往上构造语法树,使识别符号正是该语法树的根结点。

    归约:某产生式体相匹配的特定子串被替换为该产生式头部的非终结符号

    自底向上分析是一个不断进行直接归约的过程。任何自底向上分析方法的关键是要找出这种句柄。

    符号串的句柄是与某个产生式右部匹配的子串,应该归约为产生式左部(最右推导的逆过程)。

    一个句型可有多个不同句柄,但是非多义性文法的最右句型有唯一句柄。

    基本操作:移进、归约、接受、错误。

    若B为非终结符,则 A→a · Bb 为待约项目。

    LR分析方法:当前最广义的无回溯的“移进- 归约”方法。

    优点:适用范围广;分析速度快;报错准确。

    从逻辑上说,一个LR分析器包括两部分:一个总控程序和一张分析表。

    构造 LR(0)分析表

    1. 写出给定文法G的增广文法G’并编号
    2. 构造识别可行前缀的DFA
    3. 根据DFA构造LR(0)分析表

    LR(0)示例

    • 示例文法

    在这里插入图片描述

    • 示例文法的分析表

    在这里插入图片描述

    构造 SLR(1)分析表

    解决同一项目集中的移进-归约冲突。

    对于冲突项目集 Ii ={A→β1·bβ2,B→β·,C→β·},如果集合FOLLOW(B)和FOLLOW(C)不相交,而且不包含b,那么,当状态Ii面临任何输入符号a时,可采用如下“移进—归约”的决策。

    ①当a=b时,则移进,置ACTION[i,a]=Sj
    ②当a∈FOLLOW(B)时,置ACTION [i,a]=rj
    ③当a∈FOLLOW(C)时,置ACTION [i,a]=rm
    ④当a不属于三种情况之一,置ACTION [i,a]=“ERROR”

    一般地,若一个项目集 Ii 含有多个移进项目和归约项目,例如
    Ii={A1→α·a1β1,A2→α·a2β2,…,Am→α·amβm,B1→α·,B2→α·,…,Bn→α·}
    如果集合{a1,a2,…,am},FOLLOW(B1),FOLLOW(B2),… FOLLOW(Bn)两两不相交时,可类似地根据不同的当前符号,对状态为i中的冲突动作进行区分。这种解决“移进—归约”冲突的方法称作SLR方法。

    SLR(1)文法:对于给定的文法G,若按上述方法构造的分析表不含多重定义的元素,则称文法G是SLR(1)文法。

    SLR(1)示例

    设有文法G
    E→E+T|T
    T→T*F|F
    F→(E)|id
    构造该文法SLR(1)分析表。

    ① 将文法G增广为G′,同时对每一产生式进行编号
    (0)S′→E
    (1)E→E+T
    (2)E→T
    (3)T→T*F
    (4)T→F
    (5)F→(E)
    (6)F→id
    ②对G′构造文法LR(0)项目集规范族如下:

    在这里插入图片描述

    ③ 取这些项目集作为各状态,并根据转换函数GO画出识别文法G′的有穷自动机,

    在这里插入图片描述

    ④ 用SLR方法解决“移进—归约”冲突。
    在十二个项目集中, I1、 I2 和 I9 都含有“移进—归约”冲突,其解决办法是:
    对于项目集 I1 ={S′→E·,E →E·+T},由于集合 FOLLOW(S′)={$}与集合{+}不相交,所以当状态为1时,面临着输入符号为+时便移进,而面临着输入符号为$时,则按产生式S′→E归约。对于项目集 I2 ={E→T·,T→T·*F},由于集合 FOLLOW(E)={+,),$}与集合{*}不相交,因此状态2面临输入符号为*时移进,而面临输入符号为+或)或$时,按产生式E→T归约。对于项目集I9 ={E →E+T·,T →T·*F},同样由于 FOLLOW(E) = { +, ), $ }与集合{*}不相交,因此状态9面临着输入符号为*时移进,面临着输入符号为+或)或$ 时,按产生式E→E+T归约。

    ⑤ 构造SLR(1)分析表

    在这里插入图片描述

    • 输入串为id+id*id为例,给出LR分析器的分析过程如下表:
    步骤 状态栈 符号栈 输入串 分析动作 下一状态
    1 0 id+id*id$ S5 5
    2 05 $id +id*id$ r6 GOTO[0,F]=3
    3 03 $F +id*id$ r4 GOTO[0,T]=2
    4 02 $T +id*id$ r2 GOTO[0,E]=1
    5 01 $E +id*id$ S6 6
    6 016 $E+ id*id$ S5 5
    7 0165 $E+id *id$ r6 GOTO[6,F]=3
    8 0163 $E+F *id$ r4 GOTO[6,T]=9
    9 0169 $E+T *id$ S7 7
    10 01697 $E+T* id$ S5 5
    11 016975 $E+T*id r6 GOTO[7,F]=10
    12 0169710 $E+T*F r3 GOTO[6,T]=9
    13 0169 $E+T r1 GOTO[0,E]=1
    14 01 $E acc

    LR(1)

    SLR(1)也存在不足,即如果冲突项目的非终结符FOLLOW集与有关集合相交时,就不能用SLR(1)方法解决。

    SLR(1)是 LR(1)的一种特例,即所有 SLR(1)文法都是 LR(1)文法。

    SLR只是简单地考察下一个输入符号b是否属于与归约项目A→α相关联的FOLLOW(A),但b∈FOLLOW(A)只是归约α的一个必要条件,而非充分条件。

    对于产生式A→α的归约,在不同的使用位置,A会要求不同的后继符号。在特定位置,A的后继符集合是FOLLOW(A)的子集。

    **任何二义性文法都不是LR(k)文法。 **

    LALR

    LALR分析法与SLR相类似,但功能比SLR(1)强,比LR(1)弱。

    首先构造LR(1)项目集,如果它不存在冲突,就把同心集合并在一起,若合并后项目集规范族不存在“归约—归约”冲突,就按照这个集族构造分析表。``

    一个LR(1)文法合并同心集后若不是LALR(1)文法,则可能存在归约/归约冲突,不可能存在移进/归约冲突。


    语法制导翻译

    语法制导翻译概述

    语法制导翻译使用CFG来引导对语言的翻译,是一种面向文法的翻译技术

    在这里插入图片描述

    语义分析器的任务:
    ① 检查各个语法结构的静态语义 (静态语义分析或静态检查 )
    ② 执行所规定的语义动作:如表达式的求值、符号表的填写、中间代码的生成
    将静态检查和中间代码生成结合到语法分析中进行的技术称为语法制导翻译

    语法制导的翻译:一种形式化的语义描述方法,包括两种具体形式:

    • 语法制导定义(Syntax-Directed Definitions, SDD):定义翻译所必须的语义属性和语义规则,一般不涉及计算顺序。
    • 翻译模式(translation schemes): 给出语义规则的计算顺序。

    语法制导定义(SDD)

    • 一个上下文无关文法。
    • 每个属性与文法的一个终结符或非终结符相关联
    • 每一个产生式和一个语义规则集合相关联。描述产生式中各文法符号的属性之间的依赖关系。通常用函数或程序语句的形式表示

    语法制导定义是一种接近形式化的语义描述方法。语法制导定义的表示分两部分:

    • 先针对语义为文法符号设置属性,
    • 然后为每个产生式设置语义规则,来描述各属性间的关系。

    继承属性和综合属性

    属性的特点:

    • 一个结点的综合属性的值通过分析树中它的子结点的属性值和自己的属性值计算的;
    • 继承属性的值由结点的父结点、兄弟结点来计算的;
    • 非终结符号即可有综合属性也可有继承属性,但文法开始符号没有继承属性;
    • 终结符号只有综合属性,由词法分析器提供,即记号的属性;
    • 每个文法符号的综合属性和继承属性的交集为空。

    判断一个属性是继承属性还是综合属性

    综合属性(synthesized attribute):

    • 在分析树结点 N 上的非终结符 A 的综合属性只能通过 N 的子结点N 本身的属性值来定义。
    • 终结符可以具有综合属性。终结符的综合属性值是由词法分析器提供的词法值,因此在SDD中没有计算终结符属性值的语义规则。

    继承属性(inherited attribute)

    • 在分析树结点 N 上的非终结符 A 的继承属性只能通过 N 的父结点、N 的兄弟结点或 N 本身的属性值来定义。
    • 终结符没有继承属性。终结符从词法分析器处获得 的属性值被归为综合属性值。

    继承属性和综合属性的计算在产生式中所在的位置

    • 将计算某个非终结符号A的继承属性的动作插入到产生式右部中紧靠在A的本次出现之前的位置上
    • 将计算一个产生式左部符号的综合属性的动作放置在这个产生式右部的最右端

    副作用

    副作用:一般属性值计算(基于属性值或常量进行的)之外的功能,如,打印出一个结果;将信息加入符号表。

    注释分析树

    注释分析树:将属性附着在分析树对应文法符号上(属性作为分析树的注释)。

    SDD的求值顺序

    • 对单词符号串进行语法分析,构造语法分析树
    • 根据需要构造属性依赖图;(综合属性在右,继承属性在左)
    • 遍历语法树,并在语法树各结点处按语义规则进行计算

    在这里插入图片描述

    S属性与L属性

    仅仅使用综合属性的 SDD 称为 S 属性的 SDD

    如果一个SDD是S属性的,可以按照语法分析树节点的任何自底向上顺序来计算它的各个属性值。

    L-属性定义的直观含义:在一个产生式所关联的各属性之间,依赖图的边可以从左到右,但不能从右到左。即 A->X1X2……Xn 中 Xi 的每个继承属性仅依赖于:

    • A 的继承属性
    • Xi 左边的符号X1,……Xi-1 的属性
    • Xi 本身的属性,但是不能在依赖图中形成环路。

    每个S-属性定义都是L-属性定义
    把L-属性定义变换成翻译模式,在构造翻译程序的过程中前进了一大步。

    语法制导的翻译方案

    示例1:实现桌上计算器的后缀 SDT

    val 为综合属性,计算其值都在产生式的末尾。

    L → En { print (E.val); }
    E → E1 + T { E.val = E1 .val + T.val;}
    E → T { E.val = T.val;}
    T → T1 * F { T.val = T1.val * F.val ;}
    T → F { T.val = F.val; }
    F → (E) { F.val = E.val; }
    F → digit { F.val = digit.lexval; }

    示例2:给出下列文法的 SDT

    为文法
    S → ( L ) | a
    L → L , S | S
    写一个翻译方案,它输出每个a的嵌套深度。例如,对于( a , ( a , a) ),输出的结果是1 2 2。

    depth 为继承属性,计算其值在紧靠非终结符出现之前。

    S’→ {S. depth = 0 } S
    S → {L. depth = S. depth + 1 } ( L )
    S → a {print (S. depth) }
    L → {L1. depth = L. depth }L1 , {S. depth = L. depth }S
    L → {S. depth = L. depth }S

    示例3:根据下列文法的 SDT

    有文法G及其语法制导翻译如下所示:(语义规则中的*和+为运算符乘号和加号)
    E → E1^T{E.val=E1.val * T.val}
    E → T{E.val= T.val}
    T → T1#n{T.val=T1.val +n.val}
    T → n{T.val= n.val}
    采用自底向下分析时,句子3∧3#4其值为:21

    示例4:给出下列文法的 SDT

    为文法
    S → ( L ) | a
    L → L , S | S
    写一个翻译方案,它打印出每个a在句子中是第几个字符。例如,当句子是( a , ( a , ( a , a ) , (a) ) )时,打印的结果是2 5 8 10 14。

    in 为继承属性,out 为综合属性。

    每个非终结符左侧计算其 in 属性,每个产生式最右侧计算其 out 属性。

    S’ → {S. in = 0 } S
    S → {L. in = S. in + 1 } ( L )
    {S. out = L. out + 1 }
    S → a {S. out = S. in + 1; print (S. out) }
    L → {L1. in = L. in }L1 ,
    {S. in = L1. out + 1 } S
    {L. out = S. out }
    L → {S. in = L. in }S {L. out = S. out }

    示例5:给出下列文法的 SDT

    为文法
    S → ( L ) | a
    L → L , S | S
    写一个翻译方案,它输出括号的对数。

    num 为综合属性。

    S’ → S {print (S. num)}
    S → ( L ) { S. num = L.num + 1}
    S → a {S. num = 0}
    L → L1 , S { L. num = L1. num + S. num}
    L → S { L. num = S.num }


    中间代码生成

    中间代码生成概述

    “中间代码生成”程序的任务是:把经过语法分析和语义分析而获得的源程序中间表示翻译为中间代码表示。

    方法:语法制导翻译。

    采用独立于机器的中间代码的好处:

    1. 便于编译系统建立和编译系统的移植;
    2. 便于进行独立于机器的代码优化工作。

    中间表示

    优点: 容易为不同目标机器开发不同后端
    缺点: 编译过程变慢 (因为中间步骤)

    中间表示:

    • 语法树:抽象语法树
      • 反映了抽象的语法结构,而分析树反映的是具体的语法结构。语法树是分析树的抽象形式或压缩形式。
      • 语法规则中包含的某些符号可能起标点符号作用,也可能起解释作用
    • 三地址代码表示
      • 四元式
      • 三元式
      • 间接三元式

    语法分析树,抽象语法树,有向无环图(DAG)

    抽象语法树(或者简称为语法树)反映了抽象的语法结构,而语法分析树(分析树)反映的是具体的语法结构。语法树是分析树的抽象形式或压缩形式。

    • ((a)+(b))的语法分析树和抽象语法树

    在这里插入图片描述

    • 有向无环图

    在这里插入图片描述

    三地址码的实现

    四元式 op, arg1, arg2, result

    在这里插入图片描述

    三元式 op, arg1, arg2

    三元式可以避免引入临时变量,使用获得变量值的位置来引用前面的运算结果。

    在这里插入图片描述

    间接三元式 间接码表+三元式表

    包含一个指向三元式的指针列表,而不是列出三元式序列本身。

    在这里插入图片描述

    类型和声明

    类型检查:利用一组逻辑规则来确定程序在运行时的行为,保证运算分量的类型和运算符的预期类型匹配。

    翻译时的应用:

    • 确定一个名字需要的存储空间
    • 计算一个数组元素引用的地址
    • 插入显式的类型转换
    • 选择算术运算符的正确版本

    类型构造符

    • 数组
    • 笛卡尔积
    • 记录
    • 指针
    • 函数

    类型表达式示例

    int[2][3] array(2,array(3,integer))
    int *f(char a, char b) (char×char) → pointer(integer)
    typedef struct person={
    char name[8];
    int sex;
    int age;
    }
    struct person table[50];
    person record( (name × array(8,char)) × (sex × integer) × (age × integer))
    table array(50,person)

    类型等价

    类型等价:结构等价 + 名等价
    结构等价:满足以下条件之一:(类型名被类型表达式所代替,if 替换所有名字后,两个类型表达式结构上等价即结构等价)

    • 相同的基本类型
    • 将相同类型构造算子应用于等价的类型而构建的
    • 一个类型是另一个类型表达式的名字
      名等价:满足前两个条件(将每个类型名看作是可区分的类型,名字完全相同即名等价)

    在这里插入图片描述

    计算类型及其宽度的语法制导翻译

    T → B { t = B.type; w = B.width;}
    C { T.type = C.type; T.width = C.width;}
    B → int { B.type = integer; B.width = 4;}
    B → float { B.type = float; B.width = 8;}
    C → ε { C.type = t; C.width = w;}
    C → [num] C1 { C.type = array( num.vale, C1.type);
    C.width = num.value × C1.width;}

    习题

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述


    运行存储分配

    运行存储分配概述

    运行时刻环境

    • 为源程序中命名的对象分配安排存储位置
    • 确定目标程序访问变量时使用的机制
    • 过程之间的连接
    • 参数传递

    主题

    • 存储管理:栈分配、堆管理、垃圾回收
    • 对变量、数据的访问

    静态和动态存储

    • 静态分配

      • 编译器在编译时刻就可以做出存储分配决定,不需要考虑程序运行时刻的情形
      • 全局变量
      • 静态分配给语言带来限制
        • 递归过程不被允许
        • 数据对象的长度和它在内存中位置的限制,必须是在编译时可以知道的
        • 数据结构不能动态建立
    • 动态分配

      • 栈式存储:和过程的调用/返回同步进行分配和回收,值的生命期和过程生命期相同
      • 堆存储:数据对象比创建它的过程调用更长寿

    堆空间:存储管理器

    堆空间,用于存放生命周期不确定、或生存到被明确删除为止的数据对象。

    存储管理器基本功能

    • 分配:为每个内存请求分配一段连续的、适当大小的堆空间。
      • 首先从空闲的堆空间分配;
      • 如果不行则从操作系统中获取内存、增加堆空间。
    • 回收:把被回收的空间返回空闲空间缓冲池,以满足其他内存需求。

    评价存储管理器的特性:

    • 空间效率:使程序需要的堆空间最小,即减小碎片
    • 程序效率:充分运用内存系统的层次,提高效率
    • 低开销:使分配/收回内存的操作尽可能高效

    两大问题:

    • 内存泄露:未能删除不可能再被引用的数据
    • 悬空指针引用:引用已被删除的数据

    其他问题

    • 空指针访问/数组越界访问

    代码生成

    代码生成器概述

    • 根据中间表示生成代码
    • 代码生成器之前可能有一个优化组件
    • 代码生成器的三个任务
      • 指令选择:选择适当的指令实现IR语句
      • 寄存器分配和指派:把哪个值放在哪个寄存器中
      • 指令排序:按照什么顺序安排指令执行

    静态/栈式数据区分配

    活动记录静态分配:每个过程静态地分配一个数据区域,开始位置用staticArea表示。

    活动记录栈式分配:

    • 寄存器SP指向栈顶
    • 第一个过程(main)初始化栈区
    • 过程调用指令序列
    • 返回指令序列

    基本块相关的代码生成

    中间代码的流图表示法

    • 中间代码划分成为基本块(basic block),其特点是单入口单出口,即:
      • 控制流只能从第一个指令进入
      • 除了基本块最后一个指令,控制流不会跳转/停机
    • 流图中结点是基本块,边指明了哪些基本块可以跟在一个基本块之后运行

    流图可作为优化的基础

    • 它指出了基本块之间的控制流
    • 可根据流图了解一个值是否会被使用等信息

    划分基本块的算法

    确定首指令(基本块的第一个指令)符合以下任一条:

    • 中间代码的第一个三地址指令
    • 任意一个条件或无条件转移指令的目标指令
    • 紧跟在一个条件/无条件转移指令之后的指令

    确定基本块

    • 每个首指令对应于一个基本块:从首指令(包含)开始到下一个首指令(不含)

    基本块划分示例

    在这里插入图片描述

    窥孔优化

    • 消除冗余指令
    • 消除不可达指令
    • 控制流优化
    • 代数化简/强度消减
    • 机器特有指令的使用

    简单的代码生成算法

    重要子函数:getReg(I)

    • 为三地址指令I选择寄存器;
    • 根据寄存器描述符和地址描述符、以及数据流信息来分配最佳的寄存器;
    • 得到的机器指令的质量依赖于getReg函数选取寄存器的算法

    代码生成时必须更新寄存器描述符和地址描述符。


    代码优化

    代码优化概述

    通过一些相对低层的语义等价转换来优化代码。

    • 公共子表达式消除
    • 复制传播
    • 死代码消除
    • 代码移动
    • 归纳变量和强度消减
    • 常量折叠

    附录

    作业一

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    作业二

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    展开全文
  • 编译原理是用来做什么的?从源语言提取需要的信息;把源语言翻译成目标语言;自动生成满足一定规范的文本...有个东西叫DSL(领域专用语言):从各种格式的数据中提取信息:XML/JSON/CSV/Excel;...各种格式文本的...
  • 编译原理

    千次阅读 2019-03-17 18:13:58
    编译过程的六个阶段:词法分析,语法分析,语义分析,中间代码生成, 代000码优化,目标代码生成 解释程序:把某种语言的源程序转换成等价的另一种语言程序——目标语言程序,然后再执行目标程序。解释方式是接受...

    第一章:

    编译过程的六个阶段:词法分析,语法分析,语义分析,中间代码生成,

    代000码优化,目标代码生成

    解释程序:把某种语言的源程序转换成等价的另一种语言程序——目标语言程序,然后再执行目标程序。解释方式是接受某高级语言的一个语句输入,进行解释并控制计算机执行,马上得到这句的执行结果,然后再接受下一句。

    编译程序:就是指这样一种程序,通过它能够将用高级语言编写的源程序转换成与之在逻辑上等价的低级语言形式的目标程序(机器语言程序或汇编语言程序)。

    解释程序和编译程序的根本区别:是否生成目标代码

    第三章:

    Chomsky对文法中的规则施加不同限制,将文法和语言分为四大类:

    0型文法(PSG à 0型语言或短语结构语言

    文法 G的每个产生式α→β中:若α∈V*VNV*,  β∈(VN∪VT)* ,

    则 G是0型文法,即短语结构文法。

    1型文法(CSG à 1型语言或上下文有关语言

    在0型文法的基础上:若产生式集合中所有|888 α|≤|β|,除S→ε(空串)外,

    则G是1型文法,即:上下文有关文法

    另一种定义:

    文法G的每一个产生式具有下列形式:αAδ→αβδ,其中α、δ∈V*,A∈VN,β∈V+;

    2型文法(CFG à 2型语言或上下文无关语言

    文法G的每个产生式A→α,若A∈VN ,α∈(VN∪VT)*,则G是2型法,即:上下文无关文法。

    3型文法(RG  à 3型语言或正则(正规)语言   

    若A、B∈VN,a∈VT或 e,

    右线性文法:若产生式为A→aB或A→a

    左线性文法:若产生式为 A→Ba或A→a

    都是3型文法(即:正规文法)

    最左(最右)推导

    在推导的任何一步αÞ β,其中α、β是句型,都是对α中的最左(右)非终结符

    进行替换

    规范推导:即最右推导。

    规范句型:由规范推导所得的句型。

    句子的二义性(这里的二义性是指语法结构上的。)

    文法G[S]的一个句子如果能找到两种不同的最左推导(或最右推导),或者存在两棵不同的语法树,则称这个句子是二义性的。

    文法的二义性

    一个文法如果包含二义性的句子,则这个文法是二义文法,否则是无二义文法。

    短语

    若SÞ* αAδ且  A Þ +β,则称β是句型αβδ相对于非终结符A的短语。

    简单短语(直接短语)

    若SÞ * αAδ且AÞβ,则称β是句型αβδ相对于非终结符A 的简单短语。

    句柄

    一个句型的最左简单短语。(产生式的右部)

     

    子树与短语的关系

      (1) 短语:子树的末端结点(即树叶)组成的符号串;

      (2) 直接短语:简单子树的末端结点组成的符号串; 

      (3) 句柄:最左简单子树的末端结点组成的符号串;

    左图所示的关于句型E+E*i的语法树来说:

      •                               它有3棵子树,即3个短语
      •                               分别为iE*iE+E*i
      •                               直接短语、句柄均为i   

     从语法树中可以看出,

    所有树叶的组合就是其相对应的父结点的短语。

                                            

     

     

     

    句型i+i*i的语法树

    8棵子树,短语和直接短语如下:

    直接短语:i1, i2 , i3

    短语:i1,i2,i3,i1*i2,i1*i2+i3

    句柄:i1

    注意:i2+i3不是短语不是某棵子树的结果

    第四章:

    单词符号的输出形式  二元组:(单词种别,单词自身的值)

    单词符号的分类

    关键字,标识符 ,常数,运算符,界符等(这种分类不是唯一的)

    【例4.2】 S={ab}S上的正规式和相应的正规集的例子有:

    正规式            正规集

    a       {a}

    a½b           {a, b}

    ab       {ab}

    (a½b)(a½b)       {aa, ab, ba, bb}

    a *       {e, a, aa, …任意个a的串}

    (a½b)*         {e,a,b,aa,ab …所有由a和b组成的串}

    (a½b)*(aa½bb)(a½b)*     {S*上所有至少含有两个相继的a或两个相继的b组成的串}

    DFA定义:一个确定的有穷自动机Md是一个五元组:Md=K,Σ, f, S, Z),其中:

    (1) K:有穷状态集;(2) Σ:有穷输入字母表;

    (3)  f :转换函数,K×Σ è K的单值映射;

         即 f (ki , a)=kj  ,其中 kikj∈Ka∈Σ

    (4) S : S∈K,惟一初态;

    (5) Z:ZÍK,是一个终态集,也称可接受状态或结束状态。

    【例】DFA M=({S,U,V,Q}{a,b}fS{Q})

     其中f定义为:fSa=UfVa=U

      fSb=VfVb=Q

      fUa=QfQa=Q

      fUb=VfQb=Q

     DFA的表示1)用转换函数;2)状态转换矩阵;3)状态转换图

    转换函数:DFA M=({0, 1, 2, 3}, {a, b }, f, 0, { 3 } )

    f:  f(0,a)=1 f(0,b)=2 f(1,a)3 f(1,b)2

    f(2,a)=1 f(2,b)=3 f(3,a)3 f(3,b)3

     转换矩阵                               状态转换图

     

     

     

     

     

     

    NFA M的定义:一个非确定有穷自动机Mn是一个五元组Mn=(K, Σ, f, S, Z ),其中:  

    (1)  K、Σ、Z的意义与DFA相同;

    (2)  f:从K×Σ* è K的子集映射;

    (3)  S Ì K,是一个非空初态集。 

    DFA的主要区别

    允许有多个初始状态。

    允许状态在其输出边上有相同的符号(多值映射)。

    允许输出边上有空串符号e 。

    特点:在给定状态和符号的情况下,不能唯一的确定下一个状态。

    NFA的确定化基本方法 基本方法:e边合并 ,符号合并   (NFA转化成的DFA不是唯一的) 

    【 例 】 NFA  M如右图所示,试将其确定化为DFA M'

    【解答】

    (1)用子集法将图所示的NFA M确定化为表1。

    (2)对表1中的所有子集重新命名

    得到表2的状态转换矩阵

     

     

     

     

     

     

     

     

     

     

     

     

     

     

    确定有穷自动机的化简:

     

     

     

    第五章:

    语法分析是编译程序的核心部分:在词法分析的基础上,识别单词符号序列是否是给定文法的正确句子(程序)。

    自上而下分析的前提:

    消除左递规和

    消除回溯。

    自顶向下分析法就是

    从文法的开始符号

    出发,试图推导出与

    输入的单词串完全

    匹配的句子。

    如果能够推导出,则该输入串是给定文法的句子。

    如果不能推导出,则该输入串不是给定文法的句子。

    自顶向下分析法分两种

    不确定性分析法:是带有回溯的分析方法,效率低,代 价高,极少使用。

    确定性分析法:对文法有一定的限制,但实现简单直观,便于手工或自动构造。

    LL(1)文法的定义

    一个上下文无关文法是LL(1)文法的充分必要条件是:对每个非终结符A的任两个不同产生式 A®a,A®β,满足:Select(A®a)∩Select(A®β)=Æ,其中:a、β不同时推导出e 

    注:对LL(1)文法进行语法分析时不会产生回溯。

    LL(1)的含义:(LL(1)文法是无二义的; LL(1)文法不含左递归)

    第1个L:从左到右扫描输入串        第2个L:生成的是最左推导

    1 :向右看1个输入符号便可决定选择哪个产生式

    某些非LL(1)文法到LL(1)文法的等价变换: 1. 提取公因子2. 消除左递归 

    1. 提取左公因子

    形如:  A→aβ1|aβ2|...|aβn|γ  提取左公因子: A →a(β1|β2|...|βn)|γ

    改写为: A →a A'|γ   A'→β1|β2|...|βn

    2. 消除左递归   (如果一个 文法是左递归时,则不能采用自顶向下分析法。)

    (1)左递归的定义  (含有左递归的文法绝对不是LL1)文法)

    一个文法含有下列形式的产生式时,

    • A®AbAÎVN, bÎV*   直接左递归

      ②A®BbB®AaA, BÎVN, a,bÎV*  间接左递归

    (2)直接左递归的消除  (改为右递归)

    形如:   A → A a|β(a非e,β不以A打头)

    改写为:A →βA¢    A¢ →aA¢ | e 

    形如:AAa1| Aa2| . . . | Aan | b1 | b2| . . . | bm  

    其中,每个a都不等于e,b1 , . . . , bm 均不以A开头。

    改写为: A →b1 A¢ | b2 A¢ | . . . | bmA¢   A¢ →a1 A¢ | a2 A¢ | . . . | anA¢ | e 

     

     

     

     

     

     

    预测分析法(又称LL(1)分析法,属于确定的自顶向下分析方法)

    基本思想 :从左到右扫描源程序,直接根据:

     (1) 当前(需推导)的语法变量; (2) 输入串的当前输入符号;

    确定进行分析所需的候选式:使其第一个符号与当前输入符号相同,或该候选式可推导出的第一个符号与当前符号相同。

    预测分析器构成:预测分析程序,先进后出栈,预测分析表——与文法有关

    第七章

    对输入串的分析过程(已知文法的分析表)

     

    LR分析法:是一种规范规约过程

    LR(k)含义

    L :从左到右扫描输入符号

    R :最右推导对应的最左归约(反序完成最右推导)

    k :超前读入k个符号,以便确定归约用的产生式

    LR(0)项目分类

    移进项目,形如A→a• ab,a是终结符,a,b ÎV* 以下同 【例】S→ • bBB

    待约项目,形如 A →a• Bb【例】 S→b • BB S→bB • B

    归约项目,形如 A →a• 【例】 S→bBB •

    接受项目,形如S’ →S •

    第八章:

    一个属性文法包含一个上下文无关文法和一系列语义规则,

    这些语义规则附在每个产生式上。

    文法符号的属性:单词的含义,即与文法符号相关的一些信息。如,类型、值、存储地址等。

    一个属性文法(attribute grammar)是一个三元组A=(G, V, F)

    G上下文无关文法。

    V属性的有穷集。每个属性与文法的一个终结符或非终结符相连。属性与变量一样,可以进行计算和传递。

    F关于属性的断言或谓词(一组属性的计算规则)的有穷集。断言或语义规则与一个产生式相联,只引用该产生式左端或右端的终结符或非终结符相联的属性。

     

    综合属性:若产生式左部的单非终结符A的属性值由右部各非终结符的属性值决定, 则A的属性称为综合属性。       

    继承属性:若产生式右部符号B的属性值是根据左部非终结符的属性值或者右部其它符号的属性值决定的,则B的属性为继承属性。

    在两种情况下,都说属性b依赖于属性c1,c2,…,ck

    (1)非终结符既可有综合属性也可有继承属性,但文法开始符
         号没有继承属性。

    (2) 终结符只有综合属性,没有继承属性,它们由词法程序提供。

    在计算时: 综合属性沿属性语法树向上传递;继承属性沿属性语法树向下传递。 

    语法制导翻译:是指在语法分析过程中,完成附加在所使用的产生式上的语义规则描述的动作。

    语法制导翻译实现:对单词符号串进行语法分析,构造语法分析树,然后根据需要构造属性依赖图,遍历语法树并在语法树的各结点处按语义规则进行计算。

    中间代码(中间语言)

    1、是复杂性介于源程序语言和机器语言的一种表示形式。/

    2、一般,快速编译程序直接生成目标代码。

    3、为了使编译程序结构在逻辑上更为简单明确,常采用中间代码,这样可以将与机器相关的某些实现细节置于代码生成阶段仔细处理,并且可以在中间代码一级进行优化工作,使得代码优化比较容易实现。

    何谓中间代码:源程序的一种内部表示,不依赖目标机的结构,易于代码的机械生成。

    为何要转换成中间代码

    逻辑结构清楚;利于不同目标机上实现同一种语言。

    便于移植,便于修改,便于进行与机器无关的优化。

    中间代码的几种形式:逆波兰记号 ,三元式和树形表示 ,四元式 

    逆波兰记号:把运算分量(操作数)写在前面,把运算符写在后面的表示法,又称后缀表示法。

    中缀表达式向逆波兰表达式转换

    postfix(x)=x postfix(c)=c

    postfix(E1op E2)= postfix(E1) postfix(E2) op

    postfix((E))= postfix(E)

    第九章:

    符号表的一般形式:一张符号表的的组成包括两项,即名字栏和信息栏。 

    信息栏包含许多子栏和标志位,用来记录相应名字和种种不同属性,名字栏也称主栏。主栏的内容称为关键字(key word)。

    符号表的功能:

    1)收集符号属性

    在分析语言程序中标识符说明部分时,编译程序根据说明信息收集有关标识符的属性,并在符号表中建立符号的相应属性信息。

    (2) 上下文语义的合法性检查的依据:检查标识符属性在上下文中的一致性和合法性。

    (3)作为目标代码生成阶段地址分配的依据

    符号的主要属性及作用:

    1. 符号名

    2. 符号的类型 (整型、实型、字符串型等))

    3. 符号的存储类别(公共、私有)

    4. 符号的作用域及可视性 (全局、局部) 

    5. 符号变量的存储分配信息 (静态存储区、动态存储区)

    6. 符号的其它属性

    数组内情向量(类型、维数、各维的上下界、首地址等)

    记录结构型的成员信息

    函数及过程的形参

    第十章:

    运行时的存储区

    为了使目标程序能够运行,编译程序要从操作系统中得到一块存储区,以使目标程序能够在其上运行。

    运行时的存储区划分

    目标区:存放目标代码。

    静态数据区:编译时能确定所占用空间的数据。

    栈区和堆区:可变数据及管理过程活动的控制信息。

    存储分配方案策略静态存储分配动态存储分配:栈式、堆式 

    静态存储分配

    1、基本策略

    在编译时就安排好目标程序运行时的全部数据空间,并能确定每个数据项的单元地址。

    2、适用的分配对象:子程序的目标代码段;全局数据目标(全局变量)

    3、静态存储分配的要求:不允许递归调用,不含有可变数组。

    FORTRAN程序是段结构,不允许递归,数据名大小、性质固定。 是典型的静态分配

    动态存储分配 

    1、如果一个程序设计语言允许递归过程、可变数组或允许用户自由申请和释放空间,那么,就需要采用动态存储管理技术。

    2、两种动态存储分配方式栈式,堆式

    栈式动态存储分配

    分配策略:将整个程序的数据空间设计为一个栈。

      【例】在具有递归结构的语言程序中,每当调用一个过程时,它所需的数据空间就分配在栈顶,每当过程工作结束时就释放这部分空间

    过程所需的数据空间包括两部分

    一部分是生存期在本过程这次活动中的数据对象。如局部变量、参数单元、临时变量等;

    另一部分则是用以管理过程活动的记录信息(连接数据)。

    活动记录(AR)

       一个过程的一次执行所需要的信息使用一个连续的存储区来管理,这个区 (块)叫做一个活动记录。

    构成

    1、临时工作单元;2、局部变量;3、机器状态信息;4、存取链;

    5、控制链;6、实参;7、返回地址

    第十一章:

    什么是代码优化

    所谓优化,就是对代码进行等价变换,使得变换后的代码运行结果与变换前代码运行结果相同,而运行速度加快或占用存储空间减少。

    优化原则:等价原则:经过优化后不应改变程序运行的结果。

    有效原则:使优化后所产生的目标代码运行时间较短,占用的存储空间较小。

    合算原则:以尽可能低的代价取得较好的优化效果。

    常见的优化技术

    (1) 删除多余运算(删除公共子表达式)   (2) 代码外提:是针对循环的

    (3)强度削弱; 把执行时间较长的运算替换为执行时间较短的运算

    (4)变换循环控制条件  (5)合并已知量与复写传播  (6)删除无用赋值

    基本块定义

    程序中只有一个入口和一个出口的一段顺序执行的语句序列,称为程序的一个基本块。

    对四元式序列,各个基本块的入口语句是:

    (1)代码序列的第一个语句。 (2)转移语句的目标语句。 (3)转移语句的下一条语句。

    例子:

    (1)      read (C)

    (2) A:= 0

    (3) B:= 1

    (4)   L1: A:=A + B

    (5) if B>= C goto L2

    (6) B:=B+1

    (7) goto L1

    (8)  L2: write (A)

    (9) halt

    必经结点

    在程序流图中,对任意结点m和n,如果从流图的首结点出发,到达n的任一通路都要经过m,则称m是n的必经结点,记为m DOM n。

    必经结点集:流图中结点n的所有必经结点的集合称为结点n的必经结点集,记为D(n)。

    回边:假设a→ b是流图中一条有向边,如果b DOM a,则称a→b是流图中的一条回边。

    循环(依据回边判断)

    1、给出一个回边 n®d,定义这个边的(自然)循环是d加上所有不经过d能到达n的结点;

    2、d是这个循环的首结点。 

    【 例 】  求出左图的所有回边。

    【解答】(1) 6→6,因为D(6)={1,2,4,6}

    所以6 DOM 6,故6→6是回边;

    (2) 7→4,因为D(7)={1,2,4,7}

    所以4 DOM 7,故7→4是回边;

    (3) 4→2,因为D(4)={1,2,4}

    所以2 DOM 4,故4→2是回边。

    容易看出,其它有向边都不是回边。

    例二:求回边和循环 

    回边4 → 33 DOM 4

    循环:{3,4,5,6,7,8,10}

    回边7 → 44 DOM 7

    循环:{4,5,6,7,8,10}

    回边10→7 7 DOM 10

    循环: {7810}

    回边8 → 3 3 DOM 8

    循环:{3,4,5,6,7,8,10} 

    展开全文
  • 编译原理流程简介

    千次阅读 2018-08-31 10:33:41
    词法分析是编译的第一步,主要任务是读入源程序的输入字符(将代码一个字符一个字符的读入),将其组成词素(一个字符序列),生成并输出一个词法单元序列。由于负责读取程序源码,它还有一些其他任务。如:过滤程序...
  • 编译原理学习(一)--编译以及编译过程

    万次阅读 多人点赞 2018-05-22 21:01:00
    【龙书】编译原理(第二版)学习与理解:1.也许我们这辈子都不会去实现一个编译器,但是我们至少要知道编译器是什么?为什么会需要编译器? ①编译器首先也是一种电脑程序。它会将用某种编程语言写成的源代码(原始...
  • 【C语言】浅析编译原理

    千次阅读 2019-04-13 13:17:36
    提到“编译原理”,大部分人的首要反应就是苦恼。确实,编译原理这一部分的内容在计算机学习中是比较难以理解的一部分。首次接触编译原理,我也感觉很复杂,难以理解。但是当看过几次之后,对于一些简单知识点的理解...
  • 编译原理第三版课后习题

    万次阅读 多人点赞 2018-12-22 11:12:47
    编译原理课后习题 都是编译原理老师上课布置的课后习题的整理 第二章 1.P34-4 证明G(E)是二义的。 E-&gt;EOE|(E)|v|d O-&gt;+|* 2.P34-8 上下文无关文法G[S] :S-&gt;SS*|SS+|a 答:(1)S=&gt;SS*=...
  • 编译原理书籍推荐

    千次阅读 2018-09-28 13:44:20
    大学课程为什么要开设编译原理呢?这门课程关注的是编译器方面的产生原理和技术问题,似乎和计算机的基础领域不沾边,可是编译原理却一直作为大学本科的必修课程,同时也成为了研究生入学考试的必考内容。编译原理及...
  • 编译原理实验:词法分析

    万次阅读 多人点赞 2020-07-06 09:44:07
    编译原理实验:词法分析1. 实验题目:词法分析实验目的实验内容实验要求输入输出2. 设计思想3.算法流程4. 源程序5. 调试数据 1. 实验题目:词法分析 实验目的 根据PL/0语言的文法规范,编写PL/0语言的词法分析...
  • 编译原理中:短语,直接短语,句柄

    万次阅读 多人点赞 2016-12-13 19:45:02
    这几天邻近期末,感觉上了快一学期的编译原理的许多方面还是难以理解,今天早上就突然遇到了一道题,求短语,直接短语和句柄的题,突然才发现自己连这些词的定义都不清楚,于是仔细查了以下,下面分享出来:短语书上...
  • 编译原理_第2版_张素琴

    热门讨论 2020-07-21 09:57:33
    编译原理_第2版_张素琴等_清华大学 由张素琴和吕映芝等编著的《编译原理》介绍编译系统的一般构造原 理、基本实现技术和一些自动构造工具。主要由语言基础知识、词法分析 、语法分析、中间代码生成、代码优化、目标...
  • 编译原理及交叉编译

    2018-04-20 17:27:19
    转载: https://blog.csdn.net/testmyieda22/article/details/51444804编译原理及交叉编译编译原理gcc/g++在执行编译的时候,只要分四个阶段 :1、预处理阶段,完成宏定义和include文件展开等工作;不生成文件 [预...
  • 编译原理编译原理简单介绍

    万次阅读 多人点赞 2017-05-07 13:27:20
    编译原理简单介绍编译原理简单介绍 什么叫编译程序 翻译程序 编译程序 翻译和编译的区别 编译的过程 词法分析 语法分析 语义分析和中间代码的产生 优化 目标代码生成 编译程序的结构 编译程序总框 表格与表格的管理 ...
  • 编译原理课程总结

    2018-06-09 20:42:18
    编译原理是计算机专业一门非常重要的课程,介绍高级语言编译程序的一般原理、基本设计方法、主要实现技术和一些自动构造工具。通过该课程的学习,我认识到计算机信息处理的实质并将综合运用所学的知识分析解决实际...
  • 编译原理之代码优化

    万次阅读 多人点赞 2017-12-18 10:43:49
    编译原理出于代码编译的模块化组装考虑,一般会在语义分析的阶段生成平台无关的中间代码,经过中间代码级的代码优化,而后作为输入进入代码生成阶段,产生最终运行机器平台上的目标代码,再经过一次目标代码级别的...
  • 对于编译原理的理解

    千次阅读 2018-09-27 14:38:05
    编译原理 今天组长教育了一下整个程序的编译过程,感觉自己对于这块了解还是很少,有许多知识之前知道,现在忘记了,还有很多规则只是知道,但并不知道它为什么要这样写,所以再次记录一下,有什么问题或者错误...
  • 深入浅出说编译原理(一)

    千次阅读 多人点赞 2012-05-09 14:33:40
    个人认为编译原理对于一个程序员来说很重要,可能你认为编程的时候用的都是C++、C#、Java等高级语言,至于编译原理懂与不懂并无大碍。其实不然,所谓万变不离其宗,所有高级语言的诞生都是基于最根本的编译原理的。...
1 2 3 4 5 ... 20
收藏数 436,165
精华内容 174,466
关键字:

编译原理