【编译原理】图灵机、词法分析和语法分析

小灰灰 2023-09-24 17:49 23阅读 0赞

### 图灵机、词法分析和语法分析 ###

*  图灵机
 *  词法分析
 *   *  LA (scanner)的作用
     *  编辑器的作用
     *  汇编程序和编译器
     *  分析模块
     *  Tokens的分类
 *  语法分析（syntactic analysis）
 *   *  回顾：解析树
     *  两种解析策略
     *  语法分析的目的
     *  回顾：the Scanner
     *  语法分析器：The Parser
     *  语法分析的两种语法分析策略
     *  语法分析的概念
     *   *  自上而下分析（Top-down parsing）
         *  自下而上分析（Bottom-up parsing）
     *  解析策略的标准
     *   *  Power
         *  Back-tracking
         *  Lookingahead
         *  Efficiency
         *  Small Size
     *  两种解析策略

# 图灵机 #

**是功能强大且通用的计算机模型**

图灵机接受的字符串集合是TM识别的语言

如果某些TM识别出一种语言，那么它就是**图灵可识别**的语言

# 词法分析 #

编辑器的过程  
![在这里插入图片描述][cbfb4515663d43d1981437d37860f28c.png]

## LA (scanner)的作用 ##

**分析任务**：

1.  从左到右读取源代码，生成“token”
2.  输入源代码输出“token”

**词法分析器**：

1.  也称为’Scanner‘
2.  执行词法分析的程序

## 编辑器的作用 ##

1.  获取以源语言编写的源程序
2.  将其翻译成目标语言的等效目标程序
3.  提供错误消息  
    ![在这里插入图片描述][82b1ea63419b42e0a18564e34a3e9845.png]

## 汇编程序和编译器 ##

汇编程序比编译器要简单得多

它们确实有共同的特点，因为它们都必须从源代码“翻译”到目标代码

## 分析模块 ##

词法分析器（lexical analyser）或扫描器 (scanner)  
语法分析器（syntax analyser）或解析器 (parser)  
一些语义分析  
我们生成某种形式的中间表示和符号表  
![在这里插入图片描述][bc9ff79ffb1c4fb2aeaf458e7a07db3a.png]

## Tokens的分类 ##

1.  保留词（关键字）Reserved words（key words）  
    ![在这里插入图片描述][f209c730f85842a5a0cba2e93660f389.png]
2.  标识符（Identifiers）  
    变量名称、枚举类型值、方法、类……
3.  文字常量（Literal constants）  
    数字、字符、字符串…

空白和注释，语法分析阶段将忽略所有这些。

# 语法分析（syntactic analysis） #

## 回顾：解析树 ##

![在这里插入图片描述][6508bcc3f6ec43b4b22ad4f1163e571e.png]

## 两种解析策略 ##

搜索问题–给定根和叶，在它们之间找到适当的标记分支点。

**自顶向下解析策略**  
从顶部开始搜索，从< program >开始，尝试向下搜索填充在树中的树叶。

**自下而上解析策略**  
从词汇分析阶段的叶子序列开始，在我们朝着＜program＞的方向前进时，尝试构建树的一部分。  
![在这里插入图片描述][9cf0e56dd73a4b7c9ec813d5b8bba612.png]

## 语法分析的目的 ##

语法分析阶段的任务本质上是构建一个解析树

1.  根：区别符号，“< program >”或其他
2.  叶子：词汇分析阶段的标记（token）序列
3.  树中的每个分支点都由语法规则认可

可能同时执行语义检查

这个阶段可以一次一位地生成一系列机器代码指令或程序的其他中间形式

如果程序的语法无效，请尽可能多地给出有用的错误消息

识别比单词更大的单位

1.  表示语法结构的单位
2.  表达式、函数、声明

## 回顾：the Scanner ##

词法分析器（Lexical analyser）：它将字符序列收集成有意义的单位，称为令牌。

## 语法分析器：The Parser ##

语法分析器（Syntactic analyser）：它决定程序的结构。

语法分析的结果是解析树或语法树。

解析树：  
![在这里插入图片描述][a61cccef23ba4be98ef0b99d343daba8.png]

## 语法分析的两种语法分析策略 ##

1.  自上而下分析（Top-down parsing）  
    LL(1) /\*\* k = 1 \*\*/
2.  自下而上分析 （Bottom-up parsing）  
    LR(0) /\*\* k = 0 \*\*/

## 语法分析的概念 ##

形式上，对于指定的字符串α，识别它是否是指定语法G（Z）的句子。  
![在这里插入图片描述][3620065d5ce64f158b06bfcd3640df58.png]

### 自上而下分析（Top-down parsing） ###

1.  Recursive-decent parsing
2.  LL(1)
3.  从起始符号开始，使用递归算法构造解析树
4.  Left most  
    ![在这里插入图片描述][5fb72f552cac45f088db14b854267966.png]

### 自下而上分析（Bottom-up parsing） ###

1.  LR(0)
2.  Reductions
3.  Left most  
    ![在这里插入图片描述][d3f09f4b70194d08b7add0ca81fea9af.png]

## 解析策略的标准 ##

### Power ###

必须足够强大，以便分析语言

### Back-tracking ###

一些解析策略涉及反向跟踪

### Lookingahead ###

当解析器需要做出决定时，它会查看输入流中接下来的几个标记，以帮助做出正确的决定

### Efficiency ###

需要与程序长度成比例的时间

### Small Size ###

如果解析器也可以很小，那就太好了，但现在问题不大了，因为存储非常便宜

## 两种解析策略 ##

两组主要的解析策略，称为LL（k）和LR（k）

**第一个L表示从左到右处理token的输入流**  
k是允许的前瞻符号（令牌）的数量；结果通常是0或1  
![在这里插入图片描述][38918b6420204e4d8fbb4a70febfbc17.png]  
**第二个字母指定解析器生成的派生类型**  
LL（k）解析器生成最左边的派生，并且是自顶向下的解析器  
LR（k）解析器生成最右边的派生，是一种自下而上的方法  
![在这里插入图片描述][4e3110a4635e4ab29910279285397688.png]

***Thanks to Dr. John: Some contents are from their slides.***

[cbfb4515663d43d1981437d37860f28c.png]: https://img-blog.csdnimg.cn/cbfb4515663d43d1981437d37860f28c.png
[82b1ea63419b42e0a18564e34a3e9845.png]: https://img-blog.csdnimg.cn/82b1ea63419b42e0a18564e34a3e9845.png
[bc9ff79ffb1c4fb2aeaf458e7a07db3a.png]: https://img-blog.csdnimg.cn/bc9ff79ffb1c4fb2aeaf458e7a07db3a.png
[f209c730f85842a5a0cba2e93660f389.png]: https://img-blog.csdnimg.cn/f209c730f85842a5a0cba2e93660f389.png
[6508bcc3f6ec43b4b22ad4f1163e571e.png]: https://img-blog.csdnimg.cn/6508bcc3f6ec43b4b22ad4f1163e571e.png
[9cf0e56dd73a4b7c9ec813d5b8bba612.png]: https://img-blog.csdnimg.cn/9cf0e56dd73a4b7c9ec813d5b8bba612.png
[a61cccef23ba4be98ef0b99d343daba8.png]: https://img-blog.csdnimg.cn/a61cccef23ba4be98ef0b99d343daba8.png
[3620065d5ce64f158b06bfcd3640df58.png]: https://img-blog.csdnimg.cn/3620065d5ce64f158b06bfcd3640df58.png
[5fb72f552cac45f088db14b854267966.png]: https://img-blog.csdnimg.cn/5fb72f552cac45f088db14b854267966.png
[d3f09f4b70194d08b7add0ca81fea9af.png]: https://img-blog.csdnimg.cn/d3f09f4b70194d08b7add0ca81fea9af.png
[38918b6420204e4d8fbb4a70febfbc17.png]: https://img-blog.csdnimg.cn/38918b6420204e4d8fbb4a70febfbc17.png
[4e3110a4635e4ab29910279285397688.png]: https://img-blog.csdnimg.cn/4e3110a4635e4ab29910279285397688.png