当前课程知识点:Compilers Techniques > 3 Syntax Analysis > 3.2 Writing a Grammar > 3.2.2 Left Factoring
返回《Compilers Techniques》慕课在线视频课程列表
返回《Compilers Techniques》慕课在线视频列表
各位同学大家好
这一节我们继续来学习
语法分析中的提取左因子方法
接下来我们来学习
如何提取左因子
我们以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出发
构造输入串的最左推导
从根节点开始进行匹配
按照最左推导相应的顺序
自上而下构造输入串的语法分析树
我们来回顾一下
这个小节
我们所学习的内容
我们将上下文无关文法中的左因子
进行取出来
我们消除了左递归
在完成了这两步之后
我们就可以来进行自上而下的推导
那也就是使用最左推导
来构造我们需要的语法树
这一小节就到这
谢谢大家
-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