当前课程知识点:Compilers Techniques >  3 Syntax Analysis >  3.2 Writing a Grammar >  3.2.2 Left Factoring

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

3.2.2 Left Factoring在线视频

下一节:3.3 Languages and Grammars

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

3.2.2 Left Factoring课程教案、知识点、字幕

各位同学大家好

这一节我们继续来学习

语法分析中的提取左因子方法

接下来我们来学习

如何提取左因子

我们以if语句为例

我们先来看一下程序中

if语句的原始文法

S可以产生if E then S

或者if E then S else S 或者other

这个地方我们发现

红色的字体部分

if E then S

是包含左因子的

我们可以采取提取左因子的方法

来修改文法

我们看到由于左因子的存在

我们在进行if语句的处理的时候

难以判断使用哪一个产生式

来进行匹配

也就是说

这个地方存在左因子if E then S

我们可以提取左因子

来推迟进行这样的选择

我们看到当某一步的推导

如果存在左因子的时候

我们可以采取提取左因子的方法

来修改原有的文法

假设文法是

S可以产生aCb

C可以产生cd或者c

我们可以通过改写文法

将C改为 C产生cC'

C'产生d或者空串

这样我们就可以通过

提取左因子的方法

推迟我们做出的选择

从而可以知道

我们下一步来使用的产生是哪一个

我们接下来观察

一般的左因子提取方法

假设有一个左因子的文法

A产生αβ1 或者αβ2

我们观察到α是左因子

所以我们可以通过

改写这个文法来提取左因子

A产生αA'

我们使用A'来表示β1或者β2

我们仍然可以使用

提取左因子的方法

来解决if else语句的问题

我们看到针对悬空else的文法

我们可以将它提取左因子之后

将它改为

statements产生if expr then statement

后边跟着的是可选的else部分

或者其他

而可选的else这个部分

可以是else statement或者空串

接下来我们来学习

一般的提取左因子的方法

假设有一个产生式

A可以产生αb1或者αb2或者αbm

或者γ1 γ2到γp

我们可以将这个文法

进行改写

A产生αA'或者γ1 γ2一直到γp

而A'它用来表示

b1或者b2一直到bm这样

我们就可以使用

这种方法

将所有的左因子提取出来

从而使得文法不存在左因子

在自上而下的分析中

我们看到

我们的基本思想是

寻找输入串的最左推导

也就是采取最左推导

来进行自上而下的分析

我们试图根据输入单词

来决定

每一次使用哪一个产生式来进行最左推导

所以我们的基本过程就是

从产生式的开始符号S出发

构造输入串的最左推导

从根节点开始进行匹配

按照最左推导相应的顺序

自上而下构造输入串的语法分析树

我们来回顾一下

这个小节

我们所学习的内容

我们将上下文无关文法中的左因子

进行取出来

我们消除了左递归

在完成了这两步之后

我们就可以来进行自上而下的推导

那也就是使用最左推导

来构造我们需要的语法树

这一小节就到这

谢谢大家

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

3.2.2 Left Factoring笔记与讨论

也许你还感兴趣的课程:

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