当前课程知识点:编译原理 >  第4章 自顶向下的语法分析 >  4.5 LL(1)分析器工作原理 >  LL(1)分析器工作原理

返回《编译原理》慕课在线视频课程列表

LL(1)分析器工作原理在线视频

下一节:LL(1)分析器工作原理

返回《编译原理》慕课在线视频列表

LL(1)分析器工作原理课程教案、知识点、字幕

同学们

在我们前面讨论了确定的

自顶向下的分析过程当中的

我们发现了一种理想的文法

就是LL(1)文法

这节课呢我们基于LL(1)文法

和大家分享另一种

确定的自顶向下的分析法

就是LL(1)分析法

这里第一个L表示自左向右

顺序扫描输入的符号串

第二个L表示的是分析过程当中

产生的每一个句子

都是最左推导

LL(1)表示的是向前扫描一个输入符号

就能够唯一的确定产生式

LL(k)表示的是向前扫描k个输入符号

才能唯一确定产生式

接下来我们来看一下LL(1)

分析器它的构造

LL(1)分析器呢是由一个总控程序一张分析表

和一个分析栈

还有输入缓冲区构成的

它可以根据当前栈顶的符号X

以及当前的输入符号a

来决定分析器的动作

其中输入缓冲区存放的是

要分析的输入符号串

串的末尾呢放置了一个特殊的符号#

表示的是结束

要注意#不是终结符号

分析栈存放的是一系列的文法符号

分析开始的时候

先将#入栈

然后再将文法的开始符号入栈

LL(1)总控程序可以根据栈顶符号

以及读头读取的当前输入符号

按照分析表的指示来完成分析过程

预测分析表呢是一个二维表

它概括了文法的全部信息

指出了分析器应该采取什么样的动作

输出则是文法过程当中

使用的产生式序列

由此可见

分析器在分析过程当中

扮演着非常重要的角色

它指出了分析器应该采用哪种动作

我们来看一下分析表它的庐山真面目

我们所看到的这个

分析表呢是表达式文法它的分析表

分析表当中的每一行

是文法当中的

非终结符号还有终结符号和#

分析表当中的每一列呢

是文法当中的一个终结符或者是#

而表边的内容

是分析器应该采用的动作

首先POP是一个过程

它的功能呢是将栈的顶元素从栈内弹出

PUSH(α)是一个过程

它的功能呢是将字符串α压栈

α是产生式右部的逆序排列

NEXTSYM是读符号的过程

将我这个读头呢指向下一个输入符号

ACCEPT表示的是分析成功

输入的符号串语法是正确的

下面我们来看一下

LL(1)控制程序是怎么工作的

分析的最开始

首先将符号#和文法的开始符号S

依次置于分析栈的底部

并且把各个指针调整到初始的位置

现在呢栈顶的指针指向S

而输入串的读头读取到的是a1

假设分析进行到了某一步

分析栈及余留的符号串是这样子的

我们可以看到栈顶的符号是Xm

正在扫描到的这个符号是ai

如果栈顶的符号Xm是非终结符的话

我们继续查分析表

Xm所在的那一行和ai所在的那一列

假设这一项是POP

PUSH(WVU)

那么就把Xm出栈

将WVU入栈

这意味着我们使用的规则是Xm→UVW

也就是说我们需要用UVW来替换栈顶的符号Xm

但是要注意的是

我们入栈的是UVW的逆序

如果说M[Xm,ai]为POP

那么就把Xm出栈

这意味着我们使用的规则是Xm→ε

如果说M[Xm,ai]是空或者是ERROR的话

那么表示的是我们这个句子出现错误了

如果栈顶Xm是非#的终结符ai

表示的是栈顶和我这个输入串

指针所指向的这个符号匹配

我们去查表

ai这一行ai这一列

为POP NEXTSYM

表示的是栈顶的符号Xm出栈

输入指针指向下一个符号

如果说栈顶的符号Xm

和读头下面读取的符号ai相同

都是#结束符的话

表示的是输入串完全匹配

分析成功

接下来看一个具体的分析过程

根据刚才我们给出的表达式文法LL(1)分析表

对符号串i+i*i来进行分析

分析之初呢分析栈的情况是这样的

#在栈底栈顶是E

当前正在扫描到的这个单词符号呢是i

我们就去查分析表POP

e行i列

那么查到的结果是POP PUSH(E’T)

则将栈顶的符号E出栈

E’T入栈

现在栈顶的符号是T

去查找分析表的T行i列的元素

这一项是POP,PUSH(T’F)

将栈顶的符号T出栈

T’F入栈

现在的栈顶的符号就变成了F

去查找分析表F行i列

那么这一项是POP,PUSH(i)

也就是说将栈顶的符号F出栈 i入栈

现在栈顶的符号是i

去查询分析表i行i列

这一项是POP NEXTSYM 那么i出栈

栈顶的符号就变成了T’

单词指针后移扫描到的是+

查分析表T’行+

这一项呢是POP

那么T’出栈

现在的栈顶呢就变成了E’

去查询分析表E’行+列

这一项呢是POP PUSH(E’T+)

将栈顶的符号E’出栈 E’T+入栈

栈顶的符号又一次发生了变化

现在是+

去查询分析表的+行+列

这一项是POP NEXTSYM

那么+出栈

栈顶的符号就变成了T

单词指针后移扫描到了i

查询找分析表的T行i列的元素

这一项是POP PUSH(T’F)

将栈顶的符号T出栈

T’F入栈

栈顶的符号现在变成了F

接下来去查分析表的F行i列

查到的这个结果呢是

POP PUSH(i)

将栈顶的符号F出栈 i入栈

现在栈顶的符号是i

去查分析表i行i列

得到的这一项是POP NEXTSYM

那么i出栈

栈顶的符号变成了T’

单词指针后移扫描到了*

查询分析表的T’行*列的元素

是POP PUSH(T’F*)

将栈顶的符号T’出栈

T’F*入栈

栈顶的符号就变成了*

那么查询分析表*行*列

这一项是POP NEXTSYM

那么*出栈

栈顶的符号就变成了F

单词指针后移扫描到了i

接下来去查询F行i列

查询的结果呢是POP PUSH(i)

将栈顶的符号F出栈 i入栈

现在栈顶的符号是i

查分析表的i行i列

这一项呢是POP NEXTSYM

那么i出栈

栈顶的符号变成了T’

单词指针后移扫描到了#结束符

查询分析表T’行#列

这一项呢是POP

T’出栈

栈顶的符号变成了E’

查询分析表E’行#列

这一项是POP

E’出栈

栈顶的符号就是#

查询#行#列

分析表的内容是ACCEPT

表示的是分析工作结束

i+i*i是一个正确的表达式

这一节我们讨论了LL(1)分析器它的结构

并且结合表达式文法

展示了LL(1)分析器

它的总控程序分析句子的过程

这一节课呢就到这里

谢谢大家

编译原理课程列表:

第1章 编译原理概述

-1.1 什么是编译原理

--什么是编译原理

--什么是编译程序

--讨论:翻译程序、汇编程序、编译程序、解释程序的区别和联系。

--练习1

-1.2 编译的基本过程

--编译的基本过程

--编译的基本过程

--讨论:表格管理和出错处理

--练习2

-1.3 编译程序的组织

--编译程序的组织

--编译程序的组织

--练习3

-编译原理概述

第2章 编译理论基础

-2.1 文法与语言

--文法与语言

--文法与语言

-2.2 文法和语言的形式定义

--文法和语言的形式化定义

--文法和语言的形式化定义

--讨论:高级语言的一般特点

--练习1

-2.3 文法的类型

--文法的类型

--文法的类型

--练习2

-2.4 上下文无关文法及语法树

--上下文无关文法及语法树

--上下文无关文法及语法树

--练习3

-2.5 上下文无关文法的句型分析

--上下文无关文法的句型分析

--上下文无关文法的句型分析

--练习4

-编译理论基础作业

-讨论:识别不同文法的实验方法

第3章 词法分析

-3.1 词法分析概述

--词法分析概述

--词法分析概述

--练习1

-3.2 正规文法和状态转换图

--正规文法和状态转换图

--正规文法和状态转换图

--练习2

-3.3 有限状态自动机

--有限状态自动机

--有限状态自动机

--讨论:有限状态自动机的应用

--练习3

-3.4 NFA与DFA的等价性

--NFA与DFA的等价性(上)

--NFA与DFA的等价性(下)

--NFA与DFA的等价性

--练习4

-3.5 正规表达式与正规集

--正规表达式与正规集

--正规表达式与正规集

--讨论:正规式的应用

--练习5

-3.6 正规文法与正规式

--正规文法与正规式

--正规文法与正规式

--练习6

-3.7 正规式与FA

--正规式与FA

--正规式与FA

--练习7

-词法分析作业

-讨论:如何实现词法分析器

第4章 自顶向下的语法分析

-4.1 自顶向下语法分析及其面临的问题

-- 自顶向下语法分析及其面临的问题

--自顶向下语法分析及其面临的问题

--自上而下语法分析中面临的问题

--练习1

-4.2 文法的等价转化

--文法的等价转化

--文法的等价转化

--讨论:什么样的文法才是等价的?

--练习2

-4.3 LL(1)文法与递归下降分析法

--LL(1)文法与递归下降分析法

--LL(1)文法与递归下降分析法

--LL(1)分析法和递归下降法的异同

--练习3

-4.4 构建FIRST集合FOLLOW集合

--构建FIRST集合FOLLOW集合

--构建FIRST集合FOLLOW集合

--讨论:FIRST集合FOLLOW集合的关系

--练习4

-4.5 LL(1)分析器工作原理

-- LL(1)分析器工作原理

--LL(1)分析器工作原理

-4.6 LL(1)分析表构造算法

--LL(1)分析表构造算法

--LL(1)分析表构造算法

--练习5

-讨论:自顶向下语法分析算法的实现方式

第5章 自底向上的语法分析

-5.1 自底向上的语法分析及优先分析

--自底向上的语法分析及优先分析

--自底向上的语法分析及优先分析

--练习1

-5.2 LR分析器

--LR分析器

--LR分析器

--练习2

-5.3 活前缀和LR(0)项目

-- 活前缀和LR(0)项目

--活前缀和LR(0)项目

--练习3

-5.4 构造识别活前缀的FA

--构造识别活前缀的FA

--构造识别活前缀的FA

--练习4

-5.5 LR(0)分析表构造算法

--LR(0)分析表构造算法

--LR(0)分析表构造算法

--练习5

-5.6 SLR(1)分析法

--SLR(1)分析法

--SLR(1)分析法

--练习6

-5.7 LR(1)分析法与LALR分析法

--LR(1)分析法与LALR分析法(上)

--LR(1)分析法与LALR分析法(下)

--LR(1)分析法与LALR分析法

--练习7

-讨论:比较四种LR分析法

第6章 语法制导翻译和中间代码生成

-6.1 语义分析和语法制导翻译概述

--语义分析和语法制导翻译概述

--语义分析和语法制导翻译概述

--练习1

-6.2 常见中间语言简介

--常见中间语言简介

--常见中间语言简介

--讨论:为什么要引入中间代码

--练习2

-6.3 简单算术表达式和赋值语句翻译

--简单算术表达式和赋值语句翻译

--简单算术表达式和赋值语句翻译

--练习3

-6.4 布尔表达式和复制语句翻译

--布尔表达式和复制语句翻译

--布尔表达式和复制语句翻译

-6.5 拉链和回填

--拉链与回填

--拉链与回填

--练习4

-6.6 程序控制语句翻译

--程序控制语句翻译

--程序控制语句翻译举例

--程序控制语句翻译

--练习5

-6.7 for循环语句的翻译

--for循环语句的翻译

--for循环语句的翻译

-6.8 GOTO语句和情况语句的翻译

--GOTO语句和情况语句的翻译

--GOTO语句和情况语句的翻译

--练习6

-6.9 含数组元素的算术表达式的翻译

--含数组元素的算术表达式的翻译

--含数组元素的算术表达式的翻译

--练习7

-6.10 数组元素赋值语句的翻译

--数组元素赋值语句的翻译

--数组元素赋值语句的翻译

--练习8

-讨论:三元式和四元式

第7章 符号表

-7.1 符号表概述

--符号表概述

--符号表概述

--练习1

-7.2 符号表的建立

--符号表的建立

-- 符号表的建立

--练习2

-讨论:符号表

第8章 运行时存储空间组织

-8.1 运行时存储空间组织概述

--运行时存储空间组织概述

--运行时存储空间组织概述

-8.2 运行时分配策略

--运行时分配策略

--运行时分配策略

--练习

第9章 中间代码优化

-9.1 线性窥孔优化

--线性窥孔优化

--线性窥孔优化

-9.2 基本块及其优化方法

--基本块及其优化方法

--基本块及其优化方法

-9.3 循环概念

--循环概念

--循环概念

-9.4 循环优化

--循环优化

--循环优化

-代码优化作业

-讨论:代码优化

LL(1)分析器工作原理笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。