当前课程知识点:Compilers Techniques >  8 Design and Implementation of a Simple Compiler >  8.2 Basic >  8.2.2 Parser -1LRItem

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

8.2.2 Parser -1LRItem在线视频

下一节:8.2.3 Parser-2ActionGoto

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

8.2.2 Parser -1LRItem课程教案、知识点、字幕

各位同学

大家好

我们在学习完编译器

基本的知识之后

我们是不是可以自己来编写一个

编译器

从这节课开始

我们就来学习一下

基于Python的简易编译器实现

我们可以从头到尾

来学习一下

如何自己来编写一个编译器

我们看一下

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

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

句法分析器Parser作用是什么呢?

它的作用就是将词法分析器

获取的结果token list

变成语法树

使得文法分析

可以进行上下文有关分析

我们来看一个例子

假设我们针对一个SQL语言

来编写对应的SQL编译器

那么如果输入是上面所示的这一行

$ select * from grade, student

where dept='info' and student.age <100 and skernel>90

如果我们要针对这样的一条SQL语句

进行句法分析

也就是语法分析

那么我们需要在这一步

去构造这条SQL语句

对应的语法分析树

也就是下面的这棵树

在Parser句法分析器这部分

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

首先,是上下文无关文法CFG

第二,介绍LRIten项目的计算

第三,介绍LRItemSet项目集的计算

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

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

我们先来看一下

上下文无关文法这一部分

上下文无关文法

用来描述程序语言的文法

在这里

我们假设规定

使用空格来分割符号

使用竖线来分割多个产生式

我们假设输入的上下无关文法

如右侧所示

在规定了上下文无关文法的格式之后

我们就可以来进行上下文无关文法的定义

也就是针对一个具体的实现

我们给出它的上下文无关文法

在这里

我们是以计算器为例

给出对应的上下文无关文法

我们还可以给出更为复杂的

上下文无关文法的例子

比如这里

我们针对一门小的语言

给出它的上下文无关文法

包括一般的声明、简单的计算、

类型的定义、函数等等

上下文无关文法的实现

放入到cfg.py这个函数当中

在图中用圆圈圈起来的代码当中

我们用来记录非终结符、终结符、起始符号

并且在程序中

我们将产生式映射成编号

在图中这部分代码当中

我们执行打开文件的操作

然后将输入切分为对应的元组

并且我们将产生式映射成对应的编号

下面我们来看一下

LR(1)Item这一部分

也就是LR(1)项目

LR(1)项目组成的部分

包括如下两个部分

前边是产生式的部分

后边是前向搜索符集合

那么产生式的部分

我们观察到

包括产生式的左部、

箭头、以及产生式的右部

那么在产生式的右部当中

包括一个点

然后产生式结束之后

使用逗号来进行分割

逗号的后面就是前向搜索符的集合

在这部分实现的时候

我们采用产生式编号

来替代元组

这样可以减少内存的占用

在这里

前向搜索符的集合

可以直接存起来引用

这样可以避免

我们去声明不必要的对象

不过需要注意的是

不要从外部进行更改

在这里还需要记一下hash值

避免重复计算

下一步

我们来学习一下LR(1)项目集

顾名思义

LR(1)项目集就是一个装满了LR(1)项目的集合

也就是它是一个集合的对象

那么LR(1)项目集是用来做什么呢?

LR(1)项目集是用来

进行计算LR(1)项目集的自动机

我们来看一个LR(1)项目集自动机计算的例子

比如说

我们有一个文法

在这里我们已经计算出

它对应的LR(0)项目集

写在了左边的方框当中

黑色的方块

然后我们通过LR(0)项目集

开始进行计算

找到 LR(1)初始的项目集

然后在 item set 0 的基础上

找到这个项目集 碰到E

获取的 Item set 1 集合

也就是看到 E 之后

获取的LR(1)项目集

然后,我们再找到Item Set 0

碰到F之后找到的集合

也就是Item Set 2 这样的一个集合

剩下的就依次进行循环

直到找到所有的Item Set集合

为了能够方便的去计算

LR(1)项目集合

那么我们需要有对应的方法

其中有三个是最重要的

第一个是get这个方法

也就是

我们在计算一个Item Set之后

我们需要将这个Item Set

对应的所有点之后的符号

取出来

我们使用get这个函数将它取出

第二

我们在得到一个

Item Set集合之后

我们获取了点之后的符号

每一次碰到一个点之后的符号

需要去进行一个转移的计算

也就是需要设计goto这个函数

第三

我们在获取了一个Item Set之后

我们需要针对每个Item Set

来进行求取闭包

在这里我们看到

我们在求取闭包的时候

可能使得前向搜索符发生了扩展

我们再来看一下get方法

Get方法用来获取

所有跟再加点向后的符号

所组成的集合

比如说

这个例子当中Item Set 0之后

包括E、T、左括号、int_const

E是重复的

F、T这样几个符号

而我们可以通过get这个函数

将它取出

在实现的过程中

我们可以将step

和产生式的映射关系存起来

这样可以加速我们的计算

goto方法

用来返回

按照step走一步之后

所能获取得到的新的LRItemSet

比如这里Item Set 0当中

在碰见E之后

使用goto函数

可以得到Item1这样的一个转移函数的结果

在实现的过程中

我们在goto这个函数中

利用getNext中算好的映射

可以加速生成新的LRItemSet

calClosure方法

用来计算一个项目集核心的闭包

在这里

比如说我们有Item 4 Core

也就是核心项目集

那么针对这个核心项目

我们可以使用

计算闭包这个方法

得到它所有的项目集

那么 LR(1)项目集闭包的计算方法

是什么样呢?

假设对于如下的一个LRItem来说

也就是一个产生式

S→α0 α1 ... αn • T β0 ... βm

前向搜索符为γ0一直到γv

针对这个 LRItem

我们可以添加下面的 LRItem

对于任意的i来说

T可以产生前面的那些符号 逗号

然后 first(β0到βmγi)

那么在这里first函数

就可以理解为

我们输入的产生式

可能产生的第一个终结符的集合

也就是

我们在语法分析器当中

学过的first集合

在这里

既然展望符是

当前LRItem后面可能跟着的符号

那么

对于T后面的产生式

来求first集合

就相当于是求展望符

也就是前向搜索符了

在Parser部分

我们针对first这个函数

需要分类来进行讨论

也就是针对终结符、

非终结符和空串分类进行分析即可

有了上面的基础

我们就可以来实现

LR(1)项目集闭包的计算

在进行闭包的计算过程中

我们可以利用宽度优先搜索

去掉那些不需要的搜索

使用元素映射到对应的

前向搜索符集合

此外

我们还可以提前计算

每个新产生式的first集合

这样避免重复计算

第四

我们还可以利用一个字典

存储新的产生式

和它的first集合的映射关系

从而避免重复计算

最后我们还可以通过枚举

下一个可能的产生式

并且剪枝

剪枝之后加入到队列当中

去等待进一步的宽度优先搜索

这一讲就到这里

谢谢大家

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.2 Parser -1LRItem笔记与讨论

也许你还感兴趣的课程:

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