当前课程知识点：Compilers Techniques >  3 Syntax Analysis >  3.3 Languages and Grammars >  3.3 Languages and Grammars

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

3.3 Languages and Grammars在线视频

下一节:3.4.1 First and Follow

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

3.3 Languages and Grammars课程教案、知识点、字幕

各位同学大家好

这节课

我们继续来学习

语法分析方法

在这节课我们主要来学习

语言和文法的相关内容

语言和文法的相关内容

是由乔姆斯基这位科学家

来总结和发展

我们先来看一个例子

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

也就是我们的推导过程结束了

关于语言和文法

这一小节

我们就学习到这儿

谢谢大家

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.3 Languages and Grammars笔记与讨论

也许你还感兴趣的课程:


  1. Vernacular Landscapes(Round 1)

  2. 台词训练-寻找属于你自己的自然之声(2021秋)

  3. 商务俄语（四）(2021秋)

  4. 火工品设计原理(2021秋)

  5. Inorganic Chemistry(2021秋)

  6. English Course on Chinese Culture(Round 2)

  7. 税务会计实务(2021秋)

  8. Advance of Infection and Immunity(Round 2)

  9. 学术写作(2021秋)

  10. 核电厂系统与设备(2021秋)

  11. Compilers Techniques(Round 2)

  12. 细胞生物学和医学遗传学(2021秋)

  13. 商行天下——技术与运营(2021秋)

  14. 中国美术史新解(2021秋)

  15. 生态学实践——森林群落结构与土壤生境篇(2021秋)

  16. 护理教育理论与实践(2021秋)

  17. 2021年中国互联网大会(自主学习)

  18. Практика международной торговли（国际贸易实务）(Round 2)

  19. 面向对象程序设计(2021秋)

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