3.1.2 The Formal Definition of a Context-free Grammar慕课视频播放-Compilers Techniques-MOOC慕课视频教程-柠檬大学

各位同学大家好

欢迎大家来学习语法分析这一课

我们就正式进入到

上下文无关文法的学习

上下无关文法当中

我们重点学习三个方面的内容

首先是它的定义

我们来看一下正规式

它可以来定一些简单的语言

可以表示给定结构的

固定次数的重复

或者你没有指定次数的重复

正规式也是可以完成的

比如说在这里边

a(ba) 5次幂（表示：）

以 a 开头

后边跟着5个 ba 这样一个串

或者 a 开头

后边跟着零个或者 n 个 ba 这样的串

正规式都可以来进行描述

但是，正规式不能用来描述配对的

或者嵌套的结构

我们在程序当中

有非常多的配对的结构

比如说

我们在程序中

常常会写的

括号的串

那么你像下面这里边表示的wcw

w它用来表示 a、b 的串

而 c 前后的 w 是一致的

w它要配对

但是正规式

就没有办法去描述

这个 w 是一个什么样的 w

没有办法把 c 的前后 w 是一致的

这就是我们为什么要学习上下文无关文法

我们来看一下上下文无关文法的定义

上下文无关文法是一个4元组

我们把它写成 (VT, VN, S, P) 这样的形式

那么这是从数学上去定义它

VT表示的是终结符的集合

终结符就是那些记号名

记号的集合

非空有限集合

VN是非终结符的集合

当然VN也是一个非空的有限集合

非终结符的集合

和终结符的集合相交等于空

也就是说一个符号

要么是终结符

要么是非终结符

如果一个符号是终结符

它就肯定不是非终结符

然后S用来表示开始符号

P用来表示产生式的集合

产生式的形式

我们把它写成 A → α

这个箭头 → 可以读作产生

也就是A产生α

A是属于VN

也就是A是一个非终结符的集合

产生式的左部是非终结符

而 α 是属于VN和VT的并集括起来的闭包

也就是 α 是一个串

是一个终结符和非终结符混合的

这样的一个串

我们来看一个具体的例子

一个上下文无关文法

具体的例子是什么样呢

我们写成上面的形式

仍然是包括4个部分

前面首先

是终结符的集合 { id, +, *, -, (, ) } 结束

然后是非终结符的集合

包括 expr (expression) op (operator)

op是操作符

然后它的开始符号是expr

产生式的集合

我们记成 P

那么P是什么呢

P就是下面写的这6条产生式

我们来看一下这6条产生式

第一条产生式 expr → expr op expr

第二条产生式 expr → (expr)

第三条产生式 expr → - expr

第4条产生式 expr → id

第5条产生式 op → +

第6条产生式 op → *

那么在这里

我们会观察到

expr这个符号

可以在多个产生式当中去出现

这些产生式之间

是没有强制的顺序关系的

这和正规式是不一样的

正规式是有顺序关系的

接下来是只在产生

右部不出现的这些符号

( ) - id + *

这几个符号我们观察到

它们只在产生式的右部出现

那么我们就把它们叫做终结符

也就是说终结符

只在产生式的右部出现

我们观察一下

产生时的左部出现的是非终结符

刚才写的

大家看起来

就觉得很麻烦了

所以我们提供一下

上下文无关文法的一些简化的表示

写起来会更简单一些

首先是终结符的简化表示

在终结符当中

字母表前面的那些小写字母

比如说a b c

你就可以直接用了

用它去表示终结符

第二个黑体的串

比如说 id 或者 while

它是来表示终结符的

因为 id 或者 while 一般是指关键字这些

是终结符

第3个数字0、1、2、3一直到9

这些是终结符

第4个标点符号

比如说 , ( ) 这些都是终结符

第5个运算符号+ - * 除

这些也通常是终结符

我们再来看一下非终结符

针对非终结符

我们使用字母表当中

前面的那些大写字母去表示

比如说 A, B, C, D

还有一个特殊的

就是字母表当中的S

通常我们用它来表示开始符号

第三个

小写字母的名字

比如说 expr 或者 stmt (statement)

这些我们通常也用来表示非终结符

那么还有一些常用的

其他的简化表示

比如说

首先字母表当中

后面的那些大写字母

X, Y, Z等等

可以用来表示非终结符

或者是终结符

第二字母表当中

后边的那些小写字母

u, v, w, z 这些一般用来表示终结符对应的串

第三

小写的希腊字母

通常代表文法的符号串

那么

第四

如果 A → a1

A → a2

我们就会简写

记作 A → a1 | a2

这是没有先后顺序的

我们再看一下

前面刚刚学过的上下无关文法

如果我们使用简化的表示

它会是什么样呢

简化表示之后

就非常的简单了

expr 我们用 E 去表示

op 我们用 A 表示

就变成了下边这个样子

E → E A E | (E) | -E | id

而 A 用来表示 + 或者 *

有了简化表示

我们就会发现

上下文无关文法

还是蛮简单的

我们再把上下无关文法和正规式

做个简单的比较

左边是我们刚刚学过的上下无关文法

右边是正规式的定义

你会观察到对于正规式来说

虽然也是用箭头来表示

但是这个箭头的左边

是正规式的名字

而针对上下无关文法

箭头的左边是它的非终结符

它可以进一步来进行扩展

进行了产生更多的符号

这一讲就介绍到这

谢谢大家

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.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 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.1.2 The Formal Definition of a Context-free Grammar在线视频

3.1.2 The Formal Definition of a Context-free Grammar课程教案、知识点、字幕