当前课程知识点:Compilers Techniques > 3 Syntax Analysis > 3.1 Context-free Grammars > 3.1.3 Derivations
返回《Compilers Techniques》慕课在线视频课程列表
返回《Compilers Techniques》慕课在线视频列表
各位同学大家好
欢迎大家来学习语法分析这一课
接下来我们学习
上下文无关文法当中的推导的含义
推导是什么意思呢
是使我们从文法当中推出来
文法所描述的语言当中
所包含的合法串集合的动作
所以其实推导是一个动作
这个动作要做的功能是什么
是推导出来
所描述语言所包含的
合法串的集合
我们再看一下推导具体是什么
我们把产生式
看成是重写的规则
把符号串当中的非终结符
用产生式当中右部的串来进行代替
我们可以一直来进行这样的推导
一直到产生式的右部
推出来的串当中
只包含终结符
那就不能再进行推导
比如说
前面的产生式文法
我们把它进一步的简写
变成 E 可以产生 E+E | E×E | (E) | -E | id
那么我们可以用这个产生式来进行推导
推导
我们就写成两个横线这样的
双箭头
推导
我们就把它写成两个横线
这样的箭头
双箭头
E 可以推导 -E
然后 负号当中的 E
进一步可以推导成 (E)
所以最开始的 E
就推导成了 -(E)
进一步的括号当中的E
可以推导为 E+E
然后第一个 E 可以推导成id
第二个 E 也可以推导成id
最终原来的 E
就推导成了 -( id + id )
整个串当中
只有产生式右部的串
只有终结符
E 这一步推导就结束了
所以其实推导就是我们从文法的
开始符号 E 开始
推导出符合语法的句子来
那么什么是句子呢
如果我们推导出来的串当中
不包含任何的非终结符
也就是它都是终结符组成的串
它就是一个句子
那么句型是我们在推导的过程中
出现的这些串
我们把它叫做一个句型
上下文无关文法
描述的集合
我们就把它叫做
上下文无关文法对应的语言
我们还有一个概念
叫等价的文法
稍后来讲
我们再看一下
我们使用S推导*α
表示零步或者多步的推导
S可以推导+w
那么加号的推导表示的是
一步或多步的推导
我们看直接推导的
这个步骤的意思
A可以产生γ
是文法 G 的一个产生式
那么直接推导的意思就是
αAβ 在这一步
α 和 β 不变
而 A 推导成 γ
所以 αAβ
就可以推导成 αγβ
我们来看一下 文法G
S→ 0S1 S→01
那么0S1当中的S可以进行直接推导
推导为0S1
也就是0S1可以推导为00S11
那么类似的,00S11可以直接推导
得到000S111,剩下的类似
当然S也可以直接推导为0S1
下面我们看一下等价的文法的含义
文法1当中
S→aAb A→ab A→aAb A→ε
那么文法2和文法1
只是产生式顺序不同
在产生式集合当中
我们其实是不强调顺序
所以文法1和文法2是完全等价的文法
我们再看文法3
它只是把A产生式
给它用了简写的方法
E可以产生 ab | aAb | ε
那么它和文法1、文法2
仍然是等价的文法
这一页当中
这三个文法都是等价的文法
接下来我们再看一下
最左推导和最右推导的含义
比如说
我们在进行推导的时候
E推导成 -E
再推导成-(E)
然后其中的E
推导成 E+E
到这一步
我们是推导左边的 E
还是推导右边的 E
如果我们每一步的推导当中
都是从最左边的一个非终结符
开始推导
那么这个就被叫做最左推导
像我们这里边列出的例子
E在这一步
去推导左边的E
所以就可以推导成 -(id+E)
然后在最后得到 -(id+id) 结束
那么我们还可以选择
每一次推导的时候
推导最右边的那一个非终结符
这就被叫做最右推导
也被叫做规范推导
同样的步骤
我们在这一步
可以将它推导成
E可以推导 -(E+id)
然后再推导得到 -(id+id)
我们再观察一下
最左推导和最右推导
它们之间的分析树是不不一样的
大家看最左推导
就是左边的样子
到这个时候分析树
是最左边的 E 长出了叶子
而最右推导
是在这一步右边的E
长出了id这个叶子
当然最终得到的分析树是一样的
那么我们再看一下
文法推导
和分析树之间的关系
针对一个表达式
我们语法分析的目标是什么呢
我们给定一个句子
比如说id+id×id
我们怎么判断这个句子
是满足文法所描述的语法规则呢
也就是说
你给出一个句子
这个句子就相当于是
我们的源程序
经过词法分析
处理之后得到的句子
比如说id+id*id
这是经过词法分析处理之后
得到的这样的一个句子
怎么样判断句子
是不是我们这门语言所描述的语法规则
也就是它在语法上是符合我们程序要求的呢?
怎么判断呢?
我们的判断方法就是
判断一下
是不是存在着一个推导
使得我们可以从文法的开始符号
推导出来
给定的句子
如果能推导出来
就说明它是满足文法要求的
如果不能推导出来
就说明这个句子
不满足
这个文法
所描述的语法规则
就是有语法问题的
我们再来看一下推导过程
从E出发
如何得到id+id*id这样的一个串呢
首先从E出发
我们将它推导为E+E
我们用到了产生式E
可以产生E+E
然后我们将左边的 E
推导为id
我们用到了 E→id 这个产生式
接下来我们将右侧E
推导成E*E
我们用到了 E→E*E 这个产生式
假设我们采用最左推导
那么左边的E继续推导成id
我们又用到了 E→id 这个产生式
然后右边的
最右边的E
推导成id
我们再一次用到了 E→id
这个产生式
整个推导的过程就结束了
我们会观察到
其实推导的过程
是隐含着这样的一颗分析树的
那么从语法分析器
设计的角度来看
我们要保证文法能推导出来
所有正确的语法表示
并且只能是这些表示
也就是说
我们要保证我们的推导过程
可以推导出所有正确的表示
只要是正确的表示
它就能推导出来
但是只是这些表示
不会包含任何一个错误的表示
这是语法分析器里边要求的
这一讲就介绍到这
谢谢大家
-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