当前课程知识点:Compilers Techniques > 8 Design and Implementation of a Simple Compiler > 8.2 Basic > 8.2.3 Parser-2ActionGoto
返回《Compilers Techniques》慕课在线视频课程列表
返回《Compilers Techniques》慕课在线视频列表
各位同学
大家好
我们看一下
这里编译器设计的第二个部分
在这里我们将它称为句法分析器
在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语句
如果我们来编写对应的编译器
那么在产生的分析树这一步
打印输出的一个结果
如幻灯片上所示
我们再来看另外的一个例子
这是计算器对应的编译器
针对一段源程序
产生的语法分析树
我们看到
这个分析树是比较大的
这一讲就到这里
谢谢大家
-1.1 Overview of Compilers Techniques
--Chapter 1 Overview of Compilers Techniques
--Overview of Compilers Techniques
-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.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.1 Context-free Grammars
--3.1.1 The Role of the Parser
--3.1.2 The Formal Definition of a Context-free Grammar
-3.2 Writing a Grammar
--3.2.1 Elimination of Left Recursion
--3.2 Top-Down Parsing
-3.3 Languages and Grammars
--3.3 Language and Grammars
-3.4 Top-Down Parsing
--3.4.3 Recursive Descent Analysis
--3.4.4 Nonrecursive Descent Analysis
-3.5 Bottom-up Parsing
--Bottom-up Parsing
-3.6 LR Parsing
--3.6.6 Characteristics of LR Parsing
--3.6.7 Non Ambiguous and Not LR Context-Free Grammars
-4.1 Syntax-Directed Definitions
--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.3 L-Attributed Definitions
--4.3.1 L-Attributed Definitions
--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.1 Overview
--Overview
-5.2 Global Stack Storage
-5.3 Calling Sequences
-5.4 Non Local Names
--5.4 Non Local Names and dynamic scope
--Non Local Name
-6.1 Overview of Intermediate Code Generation
--6.1 Overview of Intermediate Code Generation
-6.2 Declaration Statements
-7.1 Issues in the Design of Code Generator
--7.1 Issues in the Design of Code Generator
-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
-8.1 Demonstration of Compiler Framework based on Python
--8.1 Demonstration of Compiler Framework based on Python
-8.2 Basic
--8.2.4 SA
-8.3 SimpleJava