文章
26
标签
22
分类
17
Home
Archives
Tags
Categories
Link
About
List
目录
  1. 1. 12.30复习
  2. 2. 绪论
  3. 3. 高级语言
    1. 3.1. 一、程序设计语言的定义
    2. 3.2. 二、程序设计语言的内涵[语法、语义、语用]
    3. 3.3. 三、程序语言的功能
    4. 3.4. 四、高级语言的一般特性
  4. 4. 语法描述
    1. 4.1. 一、概述
    2. 4.2. 二、形式语言与自动机理论
    3. 4.3. 三、文法的形式定义 !!!
    4. 4.4. 四、符号的约定 !!!
    5. 4.5. 五、如何由文法产生句子
    6. 4.6. 六、Chomsky文法体系
    7. 4.7. 七、语法分析树和文法二义性
  5. 5. 词法分析
    1. 5.1. 一、对于词法分析器的要求
    2. 5.2. 二、词法分析器的设计
    3. 5.3. 三、正规表达式[正规式与正规集]
    4. 5.4. 四、有限⾃动机 (FA)
    5. 5.5. 五、确定有限⾃动机(DFA)
    6. 5.6. 六、⾮确定有限⾃动机(NFA)
    7. 5.7. 七、正规式与有限⾃动机的等价性
    8. 5.8. 八、确定有限⾃动机的化简
    9. 5.9. 九、词法分析器的⾃动⽣成
  6. 6. 语法分析[自上而下]
    1. 6.1. 一、  语法分析器的功能
    2. 6.2. 二、自上而下分析方法概述
    3. 6.3. 三、LL(1)分析法
    4. 6.4. 四、递归下降分析法
    5. 6.5. 五、预测分析法
    6. 6.6. 六、LL（1）分析中的错误处理
  7. 7. 语法分析[自下而上]
    1. 7.1. 一、自下而上分析基本问题
    2. 7.2. 二、规范规约
    3. 7.3. 三、算符优先分析方法
    4. 7.4. 四、LR分析方法
    5. 7.5. 语义分析和中间代码的生成
  8. 8. 目标代码的生成
编译原理PPT复习笔记
|编译原理
字数总计: 9.1k|阅读时长: 27 分钟|阅读量:

12.30复习

!! 难点

@ 考题

!!! 重点

!? 疑惑

绪论

  1. 解释、翻译

  2. 解释（执行结果）、编译（产生目标代码）

  3. 发展：自然语言结构、有穷自动机和形式语言

  4. 编译过程的五个基本阶段：词法分析、语法分析、语义分析中间代码生成、优化、目标代码生成

  5. 词法分析（扫描程序）：

    • 源程序中的字符流->内部形式属性字Token（识别出标识符、关键字、常量、界限符）

    • 工具：正规式和有限自动机

    • 方法：状态图、DFA、NFA

    • 词法分析示例；

  1. 语法分析（识别程序）：

    • 词法分析程序识别出并转换的符号->语法分析树或其它中间表示（识别出短语、子句、语句、程序段、程序）
    • 语法规则通常用上下文无关文法描述
    • 方法：递归子程序法、分析法、算符优先分析法
    • 语法分析示例

  2. 语义分析和中间代码生成

    • 语义分析：对语法分析树或其他内部中间表示进行静态语义检查，主要任务是进行==类型审查==

    • 语义分析示例

    • 中间代码生成：输入句子->输出中间代码序列（四元式、三元式和逆波兰式等）

    • 中间代码生成的方法：语义子程序、DAG图（有向无环图）、语法制导翻译

    • 四元式的结构：（算符，运算对象1，运算对象2，结果）

    • 例题：执行完103后没有跳出

  3. 优化

    • 加工中间代码->高效（时间和空间）代码
    • 依循的原则是程序的等价变换规则
    • 方法：公共子表达式的提取、循环优化、删除无用代码等。
    • 优化示例

  4. 目标代码生成

    • 中间代码->特定机器上的低级语言代码

  5. 编译程序的结构

  6. 表格与表格管理：各种表格，其中符号表最重要，记录标识符的名字、类型、作用域、分配存储等信息

  7. 出错处理：

    • 语法错误：词法分析和语法分析检测出，如保留字拼写错误、括号不配对
    • 语义错误：编译或运行时检测出，如
    • 出错处理最好：全、准、局部化

  8. 编译阶段的组合：前端（源语言，词分到优化）和后端（目标代码）

  9. 遍：每遍记录于外存，多遍编译

  10. 编译程序的生成

    • 编译程序实现语言:机器、汇编、高级
    • 生成技术：自编译、交叉编译、自动编译

  11. T形图!!

    • T形图

    • 示例1：用 L1语言编写另一种高级语言L2的==编译程序==

    • 示例2：@编译程序的移植，先用L语言写一个A机器上的B机器语言编译程序，然后用这个编译程序编译原来那个源程序，这样就能得到在B机器上运行的产生B机器语言的编译程序。

    • 自编译：某种高级语言书写==自己==的编译程序称为自编译。

    • 交叉编译：用x机器上的编译程序产生可在y机器上运行的目标代码

      称为交叉编译。

    • 自动编译：自动生成编译程序的软件工具，如和LEX和YACC

  12. 编译系统是一系统软件

高级语言

一、程序设计语言的定义

  1. 是否可直接执行：不可，需汇编，连接 高级：需编译/解释，连接

二、程序设计语言的内涵[语法、语义、语用]

  1. 语法

    • 语言的语法是指可以形成和产生程序的一组规则。包括==词法规则和语法规则==

    • 词法规则和语法规则的语法描述方式都可以用：自然语言、语法图、BNF(巴科斯范式)范式、或文法等描述。

  2. 语义：定义它的单词符号和语法单位的意义

    • 语义是指这样的一组规则，使用它可以定义一个程序的意义。
    • 采用的方法为：==基于属性文法的语法制导翻译==方法。

三、程序语言的功能

  1. 一个程序语言的基本功能是描述数据和对数据的运算，数据的处理过程

四、高级语言的一般特性

  1. 类型：强制式(过程式语言)、应用式(函数式语言)、基于规则(条件→动作)、面向对象(封装/继承/多态)

  2. 程序结构：单层、多层结构

  3. 数据类型与操作：初等类型（整型、浮点型、字符型）、复合类型（结构、数组）到抽象数据类型（类，信息隐蔽和数据封装，使用与实现相分离）

  4. 语句与控制结构：表达式、语句[简单语句（说明语句、赋值语句、控制语句、输入输出语句、过程调用语句），复合语句]

  5. 表达式的形成规则

  6. 语句

    • 赋值语句：对赋值号右边的B我们需要的是它的值；对于左边的A我们 需要的是它们的所代表的存储单元（的地址）；一个名字所代表 的那个存储单元（地址）称为该名字的左值；把一个名字的值称为该名字的右值。
    • 控制语句：无条件转移语句、条件语句、循环语句、过程调用语句、返回语句
    • 输入输出语句

语法描述

一、概述

  1. 编译原理=形式语言理论+编译技术，语言的语法定义是非常重要的
  2. 形式语言是某个字母表上的字符串的集合，有一定的描述范围。
  3. 由文法产生的符号串构成语言 = 由自动机识别的符号串构成语言

二、形式语言与自动机理论

  1. 文法和自动机分别从==生成和识别==的角度去表达语言， 而且证明了文法与自动机的等价性，形式语言真正诞生

三、文法的形式定义 !!!

$$
G = (V_T , V_N , P , S )
$$

  • G：表示文法，文法由==四元组==定义

  • 终结符集合和非终结符集合都是字母表

  • 终结符集合与非终结符集合是不相交的 -> $V_T∩V_N=Φ$

  • 终结符集合与非终结符集合的并集是文法符号集 -> $V_T∪V_N$：文法符号集

  • $V_T$：

  • $V_N$：因为从它们可以推出其他的语法成分，所以被称为非终结符

  • P：产生式集合，注意左部和右部的取值，左部是正闭包，右部是克林闭包

    例： P = <句子> → <名词短语><动词短语>, <名词短语> → <形容词><名词短语>

  • S：开始符号

    $S∈V_N$，开始符号(start symbol)表示的是==该文法中最大的语法成分==。属于==非终结符号==，至少在某个产生式的左部出现一次。例：S = <句子>

    例：

四、符号的约定 !!!

  • 终结符，非终结符和其他

  • 子符号串

  • 符号串的前缀与后缀

  • 符号串集合

  • 空符号串ε，{ε}

  • （连接）积，n次（连接）积，闭包，正闭包

  • 候选式

  • 文法简化的约定

五、如何由文法产生句子

  1. 基本思想：从识别符号开始，把当前产生的符号串中的非终结符号替换为相应产生式右部的符号串，直到最终全由终结符号组成。 这种替换过程称为推导或产生句子的过程， 每一步称为直接推导或直接产生。

  2. 归约是推导的逆过程

  3. 若在推导关系中，每次最先替换最左（右） 的非终结符，则称为最左（右）推导；

  4. 若在归约过程中，每次最先归约最左（右） 的非终结符，则称为最左（右）归约。

    例题@：

  5. 句型、句子和语言

    • 句型：假定G是一个文法，E是它的开始符号，如果E -> α，则称α是文法G的一个句型。

    • 句子：仅由==终结符==组成的句型称为句子

    • 语言：文法G所产生句子的全体

    • 写出某文法描述的语言

      image-20191231084450680

    • 写出某语言对应的文法

      image-20191231084705150
      • 同一句型可以有不同的推导序列

六、Chomsky文法体系

  1. 文法的==核心==是产生式的集合，它决定了语言中句子的产生。

  2. Chomsky文法体系分类：

    0型文法，无限制文法，短语结构文法

    • α中至少包含1个非终结符
    image-20191127221027086

    1型文法，上下文有关文法(CSG)

    • 产生式左部符号的个数不能多于右部

    • 不包含 $\varepsilon$ 产生式，即产生式右部是空串的产生式，因为左部至少包含一个非终结符，左部长度至少为1，如果右部是 $\varepsilon$ ，右部长度为1，与CGS定义不符合。

    image-20191127221328301

    2型文法，上下文无关文法(CFG)

    • 左边是一个非终结符，将其替换不需要考虑其上下文
    • 所举的例子即2型文法
    image-20191127221344869

    3型文法，正规文法，正则文法(RG)

    • 3型文法分为2种文法
    • 产生式右部最多只有一个非终结符，且只能在一侧
    • 例子中的两个文法都是指标识符，即一个字母或以字母开头的字母数字串
    • 程序语言中的多数单词都能用正则文法表示
    image-20191127222052426

    四种文法之间的关系

    image-20191127222635614

  3. 文法、形式语言和自动机的对应关系

    image-20191231090637721

  4. 自然语言是上下文有关的，上下文无关文法可以描述多数程序设计语言的语法结构（如算术表达式、语句）

  5. 基于正规文法讨论词法分析问题，基于上下文无关文法讨论语法分析问题，而其中上下文有关的问题，可通过==表格处理==解决

  6. 程序语言中,有些语言结构并不是总能用上下文无关文法描述的。

七、语法分析树和文法二义性

  1. 上下文无关文法的分析树

    程序语言中的多数单词都能用正则文法表示，但正则文法生成能力有限，句子构造则需要用上下文无关文法进行描述。

  2. 上下文无关文法分析树定义

    例：图中跟节点表示的是对第三个式子的应用

    树的叶结点符号所组成的符号串W就是所给句型；若w中仅含 终结符号，则w为文法G所产生的句子

    image-20191127222833264

  3. 分析树是推导的图形化表示

    推导过程中产生许多句型,最终推导出分析树的边缘

    image-20191127223759244

  4. 句型的短语

    给定一个句型，其分析树中的每一颗子树的边缘称为该句型的一个短语。

    如果子树只有父子两代节点，那么这课子树的边缘称为该句型的一个直接短语。

    ==直接短语==一定是==产生式的右部==，但产生式的右部不一定是给定句型的直接短语，但可能是其他句型的直接短语

    image-20191127224229562

    例：人民、生活、水平是该句子的直接短语，而高人、民生、活水虽然也是第5个产生式的右部，但是在这棵分析树中，它们不是直接短语。

    image-20191127225119891

  5. 一个句型是否只有唯一的一个最左(最右)推导呢?

    否！

    一个句型是否只对应唯一的一棵语法树呢?

    否！ ，因为不同的最右（左）推导对应不同的语法树。

    一个句型可以有不同的最左(最右)推导，对应的语法树也不同

  6. 二义性文法

    如果一个文法可以为某个句子生成多棵分析树，则称这个文法是二义性的。

    下面这个例子产生二义的原因是else可以跟第一个if条件语句和第二个if条件语句相配。

    消歧规则：每个else和最近的尚未匹配的if进行匹配，所以只有第一个分析树，可通过某些规定将二义文法改造为无二义文法

    image-20191127225609332

  7. 二义性文法的判定

    对于任意一个上下文无关文法，不存在一个算法，判断它是无二义性的，但能给出一组充分条件，满足这组充分条件的文法是无二义性的。

  • 满足，肯定无二义性
  • 不满足，也未必就是有二义性的

  1. 证明句子是二义性，找个句子然后画出多条语法分析树

    image-20191231114350430

词法分析

一、对于词法分析器的要求

  1. 字符串的源程序改造成为单词符号串

  2. 词法分析是编译的==基础==。执⾏词法分析的程序称为词法分析器。

  3. 词法分析顾名思义就是通过扫描源程序，识别出每一个单词，确定单词类型，然后转化为统一的机内表示——词法单元（token）形式

    token：< 种别码，属性值>

    例如if、else对应唯一的表示形式。具体的表示形式如下表所示：

    image-20191127170722792

    例如有一句代码为：

    while(value!=100){num++;}

    则经过词法分析后如下所示，其中每句后的<-,->表示每个单词的含义。

    while      < WHILE ,    -  >  // 关键词，一词一码
    (          <SLP    ,    -  >  // 界限符，一词一码
    value      <IDN    ,  value>  // 标识符，多词一码，< 种别码，属性值value>
    !=         <NE     ,    -  >  // 运算符，一词一码
    100        <CONST,100> 		  // 常 量，一型一码
    )          <SRP,->            // 界限符，一词一码
    {          <LP,->             // 界限符，一词一码
    num        <IDN,num>          // 标识符，多词一码，< 种别码，属性值value>
    ++         <INC,->            // 运算符，一词一码
    ;          <SEMI,->           // 界限符，一词一码
    }          <RP,->             // 界限符，一词一码

  1. 单词符号的属性值，标识符、常数：指针、内部字符串或⼆进制形式；关键字、运算符和界符是⼀符⼀种，不需给出其⾃身的值。

  2. 词法分析程序的实现⽅式：

    • 完全独⽴⽅式

      词法分析程序作为单独⼀遍来实现。 词法分析程序读⼊整个源程序，它的输出作为语法分析程序的输⼊。编译程序结构简洁、清晰和条理化

    • 相对独⽴⽅式

      把词法分析程序作为语法分析程序的 ⼀个独⽴⼦程序。语法分析程序需要新符号时调⽤这个⼦程序。优点：避免了中间⽂件⽣成，可以提⾼效率

二、词法分析器的设计

  1. 词法分析器的结构

    image-20191231120446214

  2. 单词符号的识别：超前搜索。C++语⾔中的“+ +”、“- -”，这种复合成的算符， 需要超前搜索。对于某些语⾔的常数的识别也需要使⽤超前搜索。

  3. 状态转换图

    • ⼤多数程序设计语⾔中单词符号的词法规则可以⽤==正规⽂法==描述
    • 利⽤这些规则==识别单词符号的过程==可⽤⼀张称为==状态转换图==的有限⽅向图来表示，⽽状态转换图识别单词符号的过程⼜可以⽅便地⽤程序实现。

  4. 对于某⼀符号串β，在状态转换图中，若存在⼀条路产 ⽣β，则称状态转换图接受（或识别）该符号串β，否 则称符号串β不能被接受。

  5. 能被状态转换图TG接受的符号串的集合记为 L(TG)，称它为==状态转换图所能识别的语⾔==。

  6. 状态转换图

    有穷自动机可以用转换图来表示。

    结点：有穷自动机 的状态

    • 初始状态（开始状态）：只有一个，由 start 箭头指向
    • 终止状态：可以由多个，用双圈表示（下例中的 3）

    带标记的有向边：如果对于输入 a ，存在一个从状态 p 到状态 q 的转换，就在 p、q 之间画一条有向边，并标记上 a。

    image-20191128002520110

    在这个图中，一共有4个状态，分别为状态0，状态1，状态2，状态3。状态0为初始状态，由start箭头指向，状态3为终止状态，用双圈表示。

三、正规表达式[正规式与正规集]

  1. 学习思路：词法规则 -> NFA ->正规式 DFA -> 词法分析器（Scanner）
  2. 空串是一个正则表达式，那么它所表达的语言也只包括空串。
  3. 字母表上的任何一个符号都是一个正则表达式，那么它所表示的语言只包含它本身。
  4. 假设 r 和 s 都是正则表达式，它们表示的语言分别是 $L(r)$ 和 $L(s)$ ，则:
    • $r|s$ （r 或 s）也是一个正则表达式，它表示的语言是 $L(r|s) = L(r) ∪ L(s)$
    • rs（r 和 s 的连接）也是一个正则表达式，它表示的语言是 $L(rs) = L(r)L(s)$
    • $r^$（r 的克林闭包）也是一个正则表达式，它表示的语言是也 $L(r^) = (L(r))^*$
    • $(r)$ 是一个正则表达式，它表示的语言就是 $L(r)$，即 $L((r))=L(r)$
image-20191127234942937

例：

假设符号表中有 a,b。则 a 是一个正则表达式，b 也是一个正则表达式。可以推导出以下的正则表达式：

image-20191127235851699

例：

描述 C 语言中无符号整数的正则表达式

  • 十进制整数的正则表达式：第一个符号是19中的一个数字，接下来连接若干个 09 的数字，或者连接符号 0。
  • 八进制整数的正则表达式：第一个符号是数字0，第二个符号是17中的一个数字，接下来连接若干个 07 中的数字。
  • 十六进制整数的正则表达式：第一个符号是0，第二个符号是 x，第三个符号是 1～f 中的符号，接下来连接若干个 0～f 中的符号。
image-20191128000002054
  1. 正则表达式的代数定律

正则语言：可以用正则表达式定义的语言叫做正则语言或正则集合。

正则表达式也遵循一些代数定律，如下图所示：

image-20191128000355664
  1. 正则文法与正则表达式等价：

  • 对于任何一个正则文法 G，存在定义同一语言的正则表达式 r。

  • 对任何正则表达式 r，存在生成同一语言的正则文法 G。

  • 总之，有 G 就有 r ，有 r 就有 G 。

四、有限⾃动机 (FA)

  1. 有穷自动机（FA）

有穷自动机（Finite Automata，FA）由两位神经物理学家Meculoch 和 Pitts 于 1948年提出，是对一类处理系统建立的数学模型。

  1. 重要的理论基础

这类系统具有一系列离散的输入输出信息和有穷数目的内部状态。

系统只需要根据当前所处的状态和当前面临的输入信息，就可以决定系统的后继行为。每当系统处理了当前的输入后，系统的内部状态也将发生改变。

  1. FA 的典型例子

电梯控制装置

  • 输入：顾客的乘梯需求（所要到达的层号）
  • 状态：电梯所处的层数+运动方向
  • 电梯控制装置并不需要记住先前全部的服务要求，只需要知道电梯当前所处的状态以及还没有满足的所有服务请求。
  1. FA 模型

FA模型由以下三部分组成：

  • 输入带：用来存放输入符号串

  • 读头：从左向右逐个读取输入符号，不能修改（只读），不能往返移动

  • 有穷控制器：具有有穷个状态数，根据当前的状态 + 当前输入符号控制转入下一状态。

image-20191128002151798

  1. 有限⾃动机=有限控制器+字符输⼊带

五、确定有限⾃动机(DFA)

  1. DFA定义为一个五元组
  2. 假设字母表中没有 $\varepsilon$
image-20191128003106533

例：

在这个有穷自动机DFA 中，

状态集S 包含4个状态。分别是：状态0， 状态1， 状态2， 状态3。

输入字母表Σ 中包含的元素是：符号a，符号b。

转换函数 δ ，我们用一个转换表来表示。

例：状态0 遇到符号 a 时，变成状态1，状态0 遇到 符号 b 时，依旧是状态 0。以此类推，完成状态转换图->转换表/转换矩阵(重点考点!!!)。

  • 3是终止态，用 * 标识。

DFA可以用状态图或转换表两种等价方式来表示。

image-20191128003129846

DFA 的算法实现

  • 输入：以文件结束符 eof 结尾的字符串 x，DFA 的开始状态为 s0，接受状态集 F，转换函数 move

  • 输出：如果 D 接受 x，则回答“yes”，否则回答“no”

  • 方法：将下述算法应用于输入串 x

    image-20191128173024112

s=s0;
c=nextChar();    //返回输入串x的下一个符号
while(c!=eof)
{
    s=move(s,c); //从状态s出发，沿着标记为c的边所能到达的状态
    c=nextChar();
}
if(s在F中)
    return "yes";
else
    return "no";

六、⾮确定有限⾃动机(NFA)

  1. DFA定义为一个五元组

  2. 同样假设字母表中没有 $\varepsilon$

  3. NFA 与 DFA 唯一的区别是：从状态 s 出发，能到达的状态可能有多个。（并不是唯一确定的）

    因此，转换函数在转换表里面写的是集合，而不是元素，没有则写空集

image-20191128011646974

例：

在这个例子中，在初始状态0，遇到符号 a 的时候，它进入的状态包含状态0和状态1 ，两个元素。在状态0 时，遇到符号 b 时，它进入的状态只有 状态 0，因此集合中只有状态 0 一个元素。

如果转换函数 没有给出对应于状态-输入对的信息，就把空集放入到相应的表项中。

例!!!

image-20191128011817554

带有 ε边的 NFA

在状态 a，不需要遇到任何符号，即可进入状态 b，在状态 b，不需要任何符号，即可进入状态 c。

一旦进入状态 b，就不再接受符号 0，同理，一旦进入状态 c，就不在接受符号 1。

这个带有 空边 的NFA 接受的语言是 由若干个 0 连接 若干个 1 再连接上 若干个 2。（r=0 * 1 * 2*）

image-20191128011907201

带有 ε边 和 不带有 ε边 的 NFA的等价性

  • 不带空边的状态 A：由若干个 0 构成
  • 不带空边的状态 B：由若干个 0 连接若干个 1 构成
  • 不带空边的状态 C：由若干个 0 连接 若干个 1 连接 若干个 2 构成

但是状态A,B,C 都可以概括为若干个 0 连接 若干个 1 再连接上 若干个 2 构成。

image-20191128012012232

DFA和NFA的等价性(重点考点)

对任何非确定的有穷自动机 NFA，存在定义同一语言的确定的有穷自动机 DFA。

对任何确定的有穷自动机 DFA，存在定义同一语言的非确定的有穷自动机 NFA。

DFA 和 NFA 可以识别相同的语言

这两个 DFA 和 NFA 都识别的是以 abb结尾 的 a,b 串。

image-20191128163557050

等价性(重点考点)

  1. (重点考点)：正则文法(即3型文法，a->b形式) = 正则表达式(大概是字符串，正则表达式是正则语言更紧凑的表达方式) = 有穷自动机

  2. 给定==正则文法==，可以构造等价的==有穷自动机==，给定有穷自动机，能够构造出相应的正则文法。

  3. (重点)：DFA和NFA都可以识别同一种语言，但就在表现形式而言，NFA比DFA更加直观，就计算机实现而言，NFA比DFA更难实现。

  4. 从正则表达式构造NFA比较简单，然后再将NFA转换成DFA

  5. 带有 ε边 和 不带有 ε边 的 NFA也具有等价性

  6. NFA转化为DFA!!!

    image-20200101083027023

  7. 习题

    image-20200101083053116

七、正规式与有限⾃动机的等价性

  1. 从 NFA 构造等价的正规式
（状态消去法）!!!

  2. 状态消去法例题

    image-20200101083313821

  3. 随堂练习：NFA->正规式

    image-20200101083406250

  4. 从正规式构造等价的NFA 
!!!

    image-20200101083525266

八、确定有限⾃动机的化简

  1. DFA的化简!!!

    image-20200101083630583

  2. 右线性正规⽂法⽣成NFA⽅法!!!

    image-20200101083739222

  3. DFA产⽣右线性正规⽂法⽅法!!!

    image-20200101083837581

九、词法分析器的⾃动⽣成

  1. 词法分析器的⾃动产⽣——LEX

  2. 正则定义：

    为了方便起见，我们可以给某些正则表达式命名，像使用字母表中的符号一样，使用这些名字来构造正则表达式。（这就是正则定义提出的定义和基本思想）

    正则定义就是给正则表达式命名，右侧是字母表与已定义的正则定义的并集

    image-20191128000623988

  3. 对每条识别规则Pi 构造⼀个相应的 NFA 引⼊⼀个新的初态X, 连接成 NFA，⽤⼦集法将其确定化为DFA并化简，将 DFA 转换为词法分析程序

  4. 匹配最⻓长⼦串(最⻓长匹配原则) && 多个最⻓长⼦串匹配Pi , 以前⾯的Pi 为准(优先匹配原则)

    最长子串匹配原则：当输入串的多个前缀与一个或多个模式匹配时，我们总是选择最长的前缀进行匹配。

    image-20191128003035729

    对于上图来说，当遇到 < 号时，转换到状态1，当遇到 < = 号时，转换到状态2。

    即：在到达某个终态之后，只要输入带上还有符号，DFA 就继续前进，以便找到尽可能长的匹配。

语法分析[自上而下]

一、  语法分析器的功能

  1. 作用：词法分析的单词符号串->能否构成语法分析树，属于该语言

  2. 自上而下：从文法的开始符号出发，反复使用各种产生式，寻找与输入符号匹配的最左推导

    • LL（1）分析法
    • 递归下降分析法
    • 预测分析法

    自下而上分析：从输入符号串开始，逐步进行归约（最右推导的逆过程），直至归约到文法的开始符号。

    • 算符优先分析法

    • LR分析法

  3. 举例：求符号串abcd的推导过程、规约过程

二、自上而下分析方法概述

  1. 从文法的开始符号出发，自上而下地为输入串建立一棵语法树，即为输入串寻找一个最左推导。

  2. 自顶向下的分析是指从分析树的顶部（根节点）向底部（叶节点）方向构造分析树，可以看做是从文法开始符号S推导出单词串w的过程，例如：

    通过语法分析树可以最终得到id+(id+id)，即将叶子节点连接起来就可以构成id+(id+id)。

    每次推导中都要作两个选择：

    • 替换哪一个非终结符
    • 用哪个候选式来替换非终结符

  3. 自上而下分析方法的问题

    • 含有左递归的文法将使自上而下的分析过程陷入无限循环
    • 回溯会引起时间和空间的大量消耗

三、LL(1)分析法

  1. 从左(Left)到右扫描输入串；构造最左(Leftmost) 推导；分析时每步向前看一个(1)字符。可以构造不带回溯的自上而下分析算法。

  2. 左递归的消除

    • 左递归文法：直接左递归、间接左递归
    • 消除直接左递归：
    • 消除间接左递归

  3. 消除回溯，提左因子

    • 对任非终结符A，用它匹配输入串时能够根据当前输入，准确地指派一个候选式
    • image-20200101182853448
    • 一般地，经过反复提取左因子可把每一个非终 结符的所有候选首符集变成两两不相交。

  4. FIRST集合，FOLLOW集合

    • FOLLOW集合，可能跟在非终结符后的终结符

  5. LL(1)分析条件

    • 文法已经消除了左递归

    • 对每个非终结符满足FIRST(αi )∩FIRST(αj ) = Φ

    • 对某个输入符号a，及待匹配的非终结符A （A→α 1 │α 2 │… │α n ），a不属于任何候选式的

    • 候选式不能都推导出空串

    • 可选集互不相交

      FIRST集合，即对任意α i ，a  FIRST (α i )

  6. LL(1)分析方法

    若A的候选首符集中包含ε，则

    FIRST (A)∩ FOLLOW (A) = Φ

  7. image-20200102082016321

四、递归下降分析法

  1. 一组递归过程  每个递归过程对应G的一个非终结符

  2. 从文法开始符号出发，在语法规则(文法产生式)的支配

    下进行语法分析。逐个扫描源程序中的字符(单词符号)， 根据文法和当前输入字符分析到下一个语法成分A时， 便调用识别和分析A的子程序(或其自身)，如此继续下 去。

  3.  LL(1)分析表（预测分析表）  符号栈（后进先出）  控制程序（表驱动程序）组成。

  4. image-20200102082952175

五、预测分析法

  1. 递归下降分析器的局限性

    需要具有能够实现递归过程的语言和编译系统

  2. 预测分析程序

    使用一个分析表和符号栈进行联合控制，是实 现LL(1)分析的另一种有效方法。

六、LL（1）分析中的错误处理

语法分析[自下而上]

  1. 自下而上分析法就是从输入串开始，逐步进行 “归约”，直至归约到文法的开始符号。

  2. 从语法树的末端，步步向上“归约”，直到根结。

一、自下而上分析基本问题

  1. 自顶向下的语法分析采用最左推导方式

    自底向上的语法分析采用最左归约方式（最右推导的逆过程，即规范规约）

  2. 自底向上语法分析的通用框架：移入-归约分析(Shift-Reduce Parsing)

    使用一个符号栈，把输入符号逐一移进栈，当 栈顶形成某个产生式右部时，则将栈顶的这一 部分替换（归约）为该产生式的左部符号。

  3. 每次归约的符号串称为“句柄”，保证最左规约

  4. 栈内符号串 + 剩余输入 =“规范句型”

  5. 句柄：句型的最左直接短语；直接短语是某个产生式的右部，但产生式的右部不一定是直接短语

  6. 子树、短语、直接短语、句柄

  7. 给定一个句型，其分析树中的每一颗子树的边缘称为该句型的一个短语。

    如果子树只有父子两代节点，那么这课子树的边缘称为该句型的一个直接短语。

    直接短语一定是产生式的右部，但产生式的右部不一定是给定句型的直接短语，但可能是其他句型的直接短语

  8. 每次规约的都是一个直接短语，而且是最左直接短语

  9. 二义性文法的句柄可能不唯一

二、规范规约

  1. 规范规约（最左规约）：将句柄替换成相应产生左部符号而得到的，最左归约方式（最右推导的逆过程，即规范规约），可规约串：句柄

  2. 移入-规约过程

    image-20200101211500840

三、算符优先分析方法

  1. 定义终结符的优先关系，按终结符的优先关系控制自下而上语法分析过程（寻找“可归约串”和进行归约）
  2. 不是规范归约，但分析速度快，适于表达式的语法分析
  3. 体现了相邻的两个终结符之间在归约上的的优先关系
  4. 算符文法：一个文法，如果它的任一产生式右部都不 含两个相继（并列）的非终结符，即不含 如下形式的产生式右部
  5. 算符间的优先关系定义，后面的优先级大
  6. 构造优先关系表方法：通过检查G的每个产生式的每个候选式，可找出 所有满足a = b的终结符对。确定满足关系 < 和 > 的所有终结符对[ FIRSTVT(P)和LASTVT(P) ]
  7. 空格子：不能进行算符优先比较
  8. 最左素短语—算符优先分析中的可归约串

四、LR分析方法

  1. LR文法(Knuth, 1963) 是最大的、可以构造出相应移入-归约语法分析器的文法类；k = 0 和 k = 1 这两种情况具有实践意义 当省略(k)时，表示k =1
  2. LR分析器基于这样一些状态来构造自动机进行句柄的识别（移进状态，待约状态，归约状态）
  3. LR分析法是严格的规范规约。
  4. LR分析法手工构造分析程序工作量相当大。YACC是一个语法分析程序的自动生成器。
  5. 所有的LR分析器相同，分析表: 是自动生成语法分析器的关键，LR分析器的核心是一张分析表
    • LR (0) 表：基础、有局限性
    • SLR表：简单LR表，实用
    • 规范LR表：能力强、代价大
    • LALR表：向前LR表，介于SLR和规范LR之间
  6. 增广文法：引入这个新的开始产生式的目的是使得文法开始符号仅出现 在一个产生式的左边，从而使得分析器只有一个接受状态
  7. 初始项目、接收项目、归约项目、后继项目
  8. 可以把等价的项目组成一个项目集( I ) ，称为项目集闭包 (Closure of Item Sets)，每个项目集闭包对应着自动机的一个状态
  9. 文法->LR(0)自动机，要构造closer()函数
  10. 如果LR(0)分析表中 没有语法分析动作冲 突，那么给定的文法 就称为LR(0)文法
  11. 不是所有上下文无关文法都能用LR(0)方法进行分析，也就是说，CFG不总是LR(0)文法
  12. 活前缀: 规范句型的一个前缀，前缀的尾符号最多包含到 句型的句柄，即这种前缀不含句柄之后的任何符号（可归 前缀）；在LR分析工作过程的任何时候，栈里的文法符号（自栈 底向上）应该构成活前缀。对于一个文法G，可以构造一个识别G的所有活前缀有限 自动机，并以此构造LR分析表。

LR（0）方法

  1. 方法一：识别活前缀的NFA方法

  2. 方法二： LR(0)项目集规范族

  3. 拓广文法会有一个仅含项目S ¢ →S·的状态，这就 是唯一的“接受”态。

  4. 项目集I的闭包CLOSURE(I)；状态转换函数GO(I，X)

  5. 重点题目!!!

    image-20200102015731915

  6. 例题：

    image-20200102020220264

  7. 例题：

    image-20200102021905163

语义分析和中间代码的生成

  1. 属性、语义规则、属性文法[ 每个文法符号联系于一组属性，且对每个产生式都给

    出其语义规则的文法称为属性文法 ]

  2. 属性的分类：综合属性、继承属性

  3. S -> 属性文法：仅仅使用综合属性的属性文法

  4. L属性文法，每个属性必须要么是一个综合属性要么是一个继承属性。，S属于L属性文法

  5. image-20200102034119895
  6. image-20200102055118642

目标代码的生成

  1. 代码⽣成是把语法分析后或优化后的中间代码 变换成⽬标代码。

    代码⽣成着重考虑的问题

    • 如何使⽣成的⽬标代码较短；

    • 如何充分利⽤计算机的寄存器，减少⽬标代码中 访问存贮单元的次数。

    • 如何充分利⽤计算机的指令系统的特点排序。

  2. 考虑问题：指令选择、寄存器分配、计算顺序选择

  3. ⽬标机器模型：具有多个通⽤寄存器，他们既可以作为累加器， 也可以作为变址器；运算必须在某个寄存器中进⾏；含有四种类型的指令形式

  4. image-20200102072110982

  5. ⼀个简单代码⽣成器

    四元式的中间代码变换成⽬标代码，并在⼀个基 本块的范围内考虑如何充分利⽤寄存器：

    • 尽可能留：在⽣成计算某变量值的⽬标代码 时，尽可能让该变量保留在寄存器中。

    • 尽可能⽤：后续的⽬标代码尽可能引⽤变量在 寄存器中的值，⽽不访问内存。

    • 及时腾空：在离开基本块时，把存在寄存器中 的现⾏的值放到主存中。

  6. 寄存器描述符RVALUE[R]={A,B}、寄存器描述符AVALUE[A]={R1, R2, A}

  7. image-20200102073255224

  8. 写出基本块对应的⽬标代码

image-20200102073530866
文章作者: 桔子邮差
文章链接: http://yoursite.com/2019/11/26/%E7%BC%96%E8%AF%91%E5%8E%9F%E7%90%86%E5%A4%8D%E4%B9%A0/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 微木斋！
编译原理PPT复习笔记
打赏
  • 微信
  • 支付寶
评论
繁