当前课程知识点:Compilers Techniques >  8 Design and Implementation of a Simple Compiler >  8.2 Basic >  8.2.3 Parser-2ActionGoto

返回《Compilers Techniques》慕课在线视频课程列表

8.2.3 Parser-2ActionGoto在线视频

下一节:8.2.4 SA

返回《Compilers Techniques》慕课在线视频列表

8.2.3 Parser-2ActionGoto课程教案、知识点、字幕

各位同学

大家好

我们看一下

这里编译器设计的第二个部分

在这里我们将它称为句法分析器

在Parser句法分析器这部分

我们主要介绍5个方面的内容

第四,我们介绍一下如何来计算Action和Goto表

最后,我们介绍一下parser的部分

下面我们来讨论一下

Action和Goto

也就是我们需要生成自动机

并且生成Action和Goto表

首先我们来看一下

LR(1)项目集自动机的计算方法

第一

我们需要获取所有的输出边

也就是针对一个 Item Set

我们要找到这个点之后

所有的符号

第二

我们需要遍历所有的输出边

从而计算新项目的核心集

第三

我们需要求取当前项目集的闭包

比如说

针对当前的 Item Set 1

我们去求取它的闭包

当前这个项目集的闭包

和它的核心集是一样的

所以在这里并没有变化

第四

我们需要将这个 Item Set

加入到队列当中去

重复刚才的过程

得到 Item Set 2

继续重复刚才的过程

得到 Item Set 3

继续重复刚才的过程

得到 Item Set 4

在 Item Set 4当中

我们在进行闭包(计算)的时候

就会发现

这个项目的闭包

跟之前计算出来的是不一样的

扩大了很多

我们再回头看一下

Item Set 1、 Item Set 2

和 Item Set 3

它的核心集合和closure

也就是闭包计算之后是一样的

所以在进行闭包计算的时候

它们三个并没有发生变化

但 Item Set 4 进行了扩大

然后我们继续重复上面的过程

在计算 Item Set 0碰到T之后

获取到 Item Set 5

在 Item Set 0

进行输出边的计算之后

我们得到了 Item Set 1

到 Item Set 5

那么新生成的 Item Set

又会有新的输出边

我们需要继续搜寻出新的项目集来

在实现getActionGoto

这个函数的时候

我们首先需要进行

宽度优先搜索的初始化

我们来看一下

BFS宽度优先搜索的核心

在这里

我们需要注意三点

首先我们使用for语句

getNext()来获取输出边

其次

我们需要注意

计算闭包是很耗费时间的

而hash不太浪费时间

所以在这里

我们使用字典存储 Item Set核心

到其闭包的映射

这样可以大大加速我们的运算

第三

我们可以使用一个字典

将已经计算过的项目集

映射到对应的编号

这样可以同时判断

当前的项目集是否已经存在

在计算完成之后

我们需要将计算的结果

填入到Action和Goto表中

以供后继的计算

下面我们来看一下

Parser当中的parse方法

这是句法分析器的核心部分

句法分析器是用来做什么呢?

在这里

我们需要根据Action和Goto分析表

来分析输入token list

并且来构造对应的语法分析树

在这一部分

我们会从文法的开始符号开始

递归的使用这些产生式

从而生成语法分析树

比如针对产生式

E'→ (+TE')

这样的一个产生式

我们会生成E'对应的子树

那么E' 包括+TE'

这样的三个子结点

然后我们再针对每个子结点

生成对应的子树

在这里

加号就没有孩子结点了

而T和E'

还会继续有对应的子树

所以需要递归的去使用这些产生式

在paser()这个函数当中

我们使用for语句

来实现递归的调用

那么在for语句当中

我们使用了actionType

来标记是移进还是归约

当actionType=0的时候

意味着此时需要移进

在移进的时候

需要去创建结点

当actionType=1的时候

意味着需要归约

我们在归约之前

需要去创建父结点

然后将pop出来的结点

作为子结点

程序运行完成之后

我们就会得到这棵语法树

我们将它返回

我们还可以将产生的分析树

打印出来

这里给出一个例子

针对SQL语句

如果我们来编写对应的编译器

那么在产生的分析树这一步

打印输出的一个结果

如幻灯片上所示

我们再来看另外的一个例子

这是计算器对应的编译器

针对一段源程序

产生的语法分析树

我们看到

这个分析树是比较大的

这一讲就到这里

谢谢大家

Compilers Techniques课程列表:

1 Overview of Compilers Techniques

-1.1 Overview of Compilers Techniques

--Chapter 1 Overview of Compilers Techniques

--Overview of Compilers Techniques

2 Lexical Analysis

-2.1  Lexical Tokens, Strings and Language

--2.1  Lexical Tokens, Strings and Language

--2.1 Lexical Tokens, Strings and Language

-2.2  Regular form

--2.2 Regular form

--2.2 Regular form

-2.3  Finite automata

--2.3 Finite automata

--2.3 Finite automata

-2.4  DFA construction, Subset construction, Simpleset DFA

--2.4  DFA construction, Subset construction, Simpleset DFA

-2.5 Lex

--2.5 Lex

3 Syntax Analysis

-3.1 Context-free Grammars

--3.1.1 The Role of the Parser

--3.1.2 The Formal Definition of a Context-free Grammar

--3.1.3 Derivations

--3.1.4 Ambiguity

-3.2 Writing a Grammar

--3.2.1 Elimination of Left Recursion

--3.2.2 Left Factoring

--3.2 Top-Down Parsing

-3.3 Languages and Grammars

--3.3 Languages and Grammars

--3.3 Language and Grammars

-3.4 Top-Down Parsing

--3.4.1 First and Follow

--3.4.2 LL(1) Grammers

--3.4.3 Recursive Descent Analysis

--3.4.4 Nonrecursive Descent Analysis

-3.5 Bottom-up Parsing

--3.5.1 Reductions and Handle

--3.5.2 Shift- Reduce Parsing

--Bottom-up Parsing

-3.6 LR Parsing

--3.6.1 LR Parsing

--3.6.2 Viable Prefixes

--3.6.3 Simple LR

--3.6.4 LR(1)

--3.6.5 LALR

--3.6.6 Characteristics of LR Parsing

--3.6.7 Non Ambiguous and Not LR Context-Free Grammars

4 Syntax-Directed Translation

-4.1 Syntax-Directed Definitions

--4.1.1 Attribute Grammars

--4.1.2 Attribute Dependency Graphs and Ordering the Evaluation of Attributes

--Syntax-Directed Definitions

-4.2 Bottom-Up Calculation of S Attribute

--4.2.1 Bottom-Up Calculation of S-Attributed

--4.2.2 Stack Code

-4.3 L-Attributed Definitions

--4.3.1 L-Attributed Definitions

--4.3.2 Translation Schemes

--4.3.3 Design of Predictive Translator

--L-Attributed Definitions

-4.4 Bottom-Up Parsing of L-Attributed Translation

--4.4.1 Bottom-Up Parsing of L-Attributed Translation

--4.4.2 Simulate the Parsing of Inherited Properties

--Bottom-Up Parsing of L-Attributed Translation

5 Organization and Management of Run-Time Storage Space

-5.1 Overview

--5.1 Overview

--Overview

-5.2 Global Stack Storage

--5.2 Global Stack Storage

-5.3 Calling Sequences

--5.3 Calling Sequences

-5.4 Non Local Names

--5.4 Non Local Names and dynamic scope

--Non Local Name

6 Intermediate Code Generation

-6.1 Overview of Intermediate Code Generation

--6.1 Overview of Intermediate Code Generation

-6.2 Declaration Statements

--6.2 Declaration Statements

7 Code Generation

-7.1 Issues in the Design of Code Generator

--7.1 Issues in the Design of Code Generator

-7.2 Target Machine

--7.2 Target Machine

--Target Machine

-7.3 Basic Blocks and Flow Graphs

--7.3 Basic Blocks and Flow Graphs

-7.4 A Simple Code Generator

--7.4 A Simple Code Generator

8 Design and Implementation of a Simple Compiler

-8.1 Demonstration of Compiler Framework based on Python

--8.1 Demonstration of Compiler Framework based on Python

-8.2 Basic

--8.2.1 Scanner

--8.2.2 Parser -1LRItem

--8.2.3 Parser-2ActionGoto

--8.2.4 SA

-8.3 SimpleJava

--8.3 SimpleJava

8.2.3 Parser-2ActionGoto笔记与讨论

也许你还感兴趣的课程:

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