3.4.2 LL(1) Grammers慕课视频播放-Compilers Techniques-MOOC慕课视频教程-柠檬大学

各位同学大家好

今天我们继续来学习语法分析

这节课我们来学习

语法分析中的LL1文法

LL1文法是在first集和follow集定义的基础上

加了两个条件

我们来看一下这两个条件

假设有两个产生式

A可以产生α或者β

对于LL1文法

它的要求有两点

first(α)和first(β)相交等于空

或者如果在β可以推导为空串的情况下

我们要求first(α)和follow(A)相交等于空

满足了这两点

我们可以知道

在进行自上而下推导的时候

可以顺利的决定

每一步是把A推导为α

还是把A推导为β

当然我们其实也可以观察到

LL1文法自然的它包含一些明显的性质

比如说不包含公共左因子

它不是二义性的

肯定也不含有左递归

比如说

对于我们之前看到的这个例子

我们来判断一下

它到底是不是LL1文法

对于E产生式TE'

T产生式FT'

对于这两条产生式来说

它其实不涉及到LL1中

这两个条件的判定

所以我们重点需要判定的是

E'产生+TE'或者空串

T'产生 *FT'或者空串

对于F产生(E)或者id

很明显的

我们可以在任何一个情况知道

是将F推导为带左括号的产生式

还是将它推导为id

所以我们只需要判断这两个产生式

我们根据之前求出的

First集和follow集

可以看到

对于产生式 E产生+TE'

或者空串来说

由于E'可以推导为空串

所以我们其实需要判定

first(+TE')和follow(E')

相交是不是为空

那么first(+TE') 它的集合等于+

而follow(E')

我们之前求得的结果

等于右括号 ) 和$

所以它们俩相交是为空的

对于T'产生*FT'或者空串来说

我们仍然需要去判定

First(*FT')和follow(T')相交是不是为空

根据之前的结果

First(*FT')等于 *号

follow(T')

等于加+ ) $

所以它们相交为空

根据这两个产生式

我们可以判断出来

这个文法是LL1文法

接下来我们可以看到

如果我们再求出一个文法的

First集和follow集之后

假设它满足我们的要求

是LL1文法

那么我们就可以来进行

自上而下的预测分析

我们通过构造非递归的预测分析表

可以来进行构造语法树

分析一个串

是不是属于文法

我们看在进行自上而下分析的时候

其实是有两种分析方法

一种是递归下降的预测分析方法

一种是非递归的预测分析方法

稍后我们会学习

非递归的预测分析方法

我们需要去构造

非递归的预测分析表

然后再来进行非递归的预测分析

关于LL1文法的部分

我们就学习到

这一小节结束

谢谢大家

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.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 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

3.4.2 LL(1) Grammers在线视频

3.4.2 LL(1) Grammers课程教案、知识点、字幕