当前课程知识点:Compilers Techniques > 3 Syntax Analysis > 3.3 Languages and Grammars > 3.3 Languages and Grammars
返回《Compilers Techniques》慕课在线视频课程列表
返回《Compilers Techniques》慕课在线视频列表
各位同学大家好
这节课
我们继续来学习
语法分析方法
在这节课我们主要来学习
语言和文法的相关内容
语言和文法的相关内容
是由乔姆斯基这位科学家
来总结和发展
我们先来看一个例子
L1这个语言我们将它表示为wcw
w是属于ab的一个串
我们观察到这个L1语言
其实是程序中一个语法现象的抽象
也就是一个标志符的声明应该先于它的引用
在c之前先进行声明
然后我们才可以在c之后引用w
接下来我们来看L2这个例子
L2我们将它表示为an bm cn dm
我们观察到a和c的个数是一致的
b和d的个数是一致的
那么L2也是程序中语法现象的一个抽象
它用来表示我们在写函数的时候
形参的个数和实参的个数应该是一致的
我们再来看L3这个例子
L3用来表示an bn cn
那么也就是说a、b、c的个数应该是一致的
它其实是我们在进行排版的时候
抽象出来的一个概念
也就是abc它的个数是一致的
我们观察到
L1、L2和L3都是非上下文无关文法
但是有一些和L1、L2、L3非常类似的这些语言
其实它是上下文无关的
我们来看这个例子L1'
我们将之前的L1稍加改写
把它变成wcwR wR是w的逆
我们看到L1'
其实可以用上下文无关文法表示出来
也就是我们将文法改写为
S产生aSa或者bSb或者c
它是一个以c为轴对称的这样的一个字符串
前后的a和b 是由c进行对称出现的
那么它可以表示为上下文无关文法的形式
所以L1'是上下文无关文法
另一个例子是我们在L2文法的基础上加以改写
将它改为an bm cn dm
我们观察到这个时候
c和d的个数跟之前有了变化
也就是b和c的个数是一致的
而a和d的个数是一致的
改写完成之后
我们仍然可以将L2'
使用上下文无关文法将它写出来
也就是S可以产生aSd或者aAb
而A可以写为bAc或者bc
在这种情况下
它仍然是一个前后的a和d、 c和d是对称出现的(文法)
由于可以将L2'改写为上下文无关文法
所以L2'是上下文无关的
我们接下来
继续将L2'来进行改写
将它写为an bn cm dm
在这种情况下a和b的个数是一样的
c和d的个数是一样的
仍然可以将它改写为上下文无关文法
S可以产生AB
A可以产生aAb或者ab
B可以产生cBd或者cd
我们观察到S是分为两部分的
前边的A部分保证a和b的个数一样的
后边的B部分保证c和d的个数是一样的
我们接下来看 L3'文法
我们将它改为an bn
我们发现a和b的个数是一致的
也就是它其实需要一次的计数
我们知道了a的个数
接下来要保证b的个数和a的个数是一致的
我们还是可以将它改写为上下文无关文法
S可以产生aSb或者ab
那么可以根据这个文法
保证a和b的个数是一致的
而L3'其实是一个特例
L3'是不能用正规式
来进行描述的
也就是它只能用上下文关文法以上的语言来进行描述
我们可以从数学上进行证明
假设我们存在着一个接受L3'对应的DFA
那么如果是DFA 它的状态数目是确定的
假设设为K个
在D读取空串之后
我们假设它到达的状态是S0
读取了一个a之后 到达的状态是S1
读取了两个a之后 到达状态S2
读取了K个a之后 到达的状态是sk
我们观察到
由于这时候状态是从S0一直到sk
也就是说一共有k+1个状态
而我们之前假设它的状态数目为k个
那么出现了k+1个状态
意味着至少有两个状态是相同的
假设是sj和si 它们俩状态数目是一样的
如果si和sj的状态数目是一样的
就意味着ajbi是属于我们当前的L3'的
而这个是不应该的
因为我们本身知道
ai bi是属于L3'的
也就是i和j 应该是一致的
这样就推导出了矛盾
也就是说L3'不能够用正规式描述
只能使用上下文无关文法
乔姆斯基将上述的文法来加以总结
它提出了形式语言的概念
我们看假设一个文法使用四元组来进行表示
也就是VT终结符的集合
VN非终结符的集合
S是产生式的开始符号
P是产生式的集合
那么他(乔姆斯基)把它定义了4种类型的文法
首先是0型文法
在0型文法当中
可以出现的产生式是α→β
α和β都是(属于)VN和VT并集的集合
也就是α和β是终结符合和非终结符混合的串
我们要求α的长度大于等于1
那么0型文法
实际上要求是很松散的
我们将它称为短语文法
接下来是1型文法
1型文法中
它的要求是α的长度要小于等于β
但是S产生空串是可以例外的
我们将1型文法称之为上下文有关文法
然后2型文法 在1型文法的基础上 加了更多的限制
也就是A可以产生β
而A属于非终结符的集合
β属于终结符合和非终结符的串
2型文法
就是咱们这一章所学的上下文无关文法
在2型文法的基础上
我们增加一个限制就是3型文法
A可以产生aB或者A产生α
A和B属于非终结符集合
α属于终结符集合
在这种情况下是3型文法
也就是我们在第2章所学的正规式文法
有了这4种文法之后
我们可以去对所有的语言加以总结
我们接下来看一下
非上下文无关文法的一个例子
假设我们有一个L3=an bn cn
这是一个上下文有关文法
我们要求abc的个数是一致的
我们首先可以将它的产生式写出来
我们看到产生是有如下的这几个
S可以产生aSBc S可以产生aBC
CB可以产生BC
我们观察到
这样的一条产生式在上下文无关文法中是不会出现的
所以这不是一个上下文无关文法
它是上下文有关文法
aB产生ab
bB可以产生bb
bC可以产生BC
最后cC可以产生cc
那么我们接下来
就可以将an bn cn的推导过程(写出来)
首先我们用S产生aSBC (n-1)次
我们就得到了S产生 (n-1)个a S (n-1)个BC
接下来我们使用S产生aBC
我们就得到了S产生an (BC)n
然后我们使用CB产生BC来交换相邻的CB
我们就得到了S产生an Bn Cn
接下来使用aB产生ab
我们就得到了S可以产生n个a b B(n-1)次 还有n个C
然后我们使用bB产生bb(n-1)次
我们就可以得到S产生 n个a n个b n个C
接下来使用bC产生bc一次
我们就可以得到an bn c C (n-1)次
然后最后我们使用cC产生cc (n-1)次
最终我们就可以将S推导为n个a n个b n个c
也就是我们的推导过程结束了
关于语言和文法
这一小节
我们就学习到这儿
谢谢大家
-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