编译原理(第二版)第3章 文法和语法

编译原理(第二版)第3章 文法和语法 课件

第3章

文法和语言

教学要求：本章是编译原理课程的理论基 础，要求理解文法、语言、规范推导、规 范归约和短语、简单短语、句柄的基本概 念；掌握语言的求解方法、文法的二义性 的判断方法及句型的分析方法。

教学重点：上下文无关文法，语言定义

编译原理(第二版)第3章 文法和语法 课件

一、语言 语言是由句子组成的集合，是由一组记号 所构成的集合。 汉语--所有符合汉语语法的句子的全体 英语--所有符合英语语法的句子的全体 程序设计语言--所有该语言的程序的全体

编译原理(第二版)第3章 文法和语法 课件

二、文法

一种语言描述工具，用来定义句子的结构， 用有限的规则把语言的全部句子描述出来， 是以有穷的集合刻划无穷的集合的工具。

〈句子〉::=〈主语〉〈谓语〉 〈主语〉::=〈代词〉|〈名词〉 〈代词〉::= 你 | 我 | 他 〈名词〉::= 王明 | 大学生 | 工人 | 英语 〈谓语〉::=〈动词〉〈直接宾语〉

〈动词〉::= 是 | 学习〈直接宾语〉::=〈代词〉|〈名词〉

“我是大学生”是否是该语言的句子？

编译原理(第二版)第3章 文法和语法 课件

〈句子〉::=〈主语〉〈谓语〉 〈主语〉::=〈代词〉|〈名词〉 〈代词〉::= 你 | 我 | 他 〈名词〉::= 王明 | 大学生 | 工人 | 英语 〈谓语〉::=〈动词〉〈直接宾语〉 〈动词〉::= 是 | 学习 〈直接宾语〉::=〈代词〉|〈名词〉 〈句子〉

〈主语〉〈谓语〉 〈代词〉〈谓语〉 我〈谓语〉 我〈动词〉〈直接宾语〉 我是〈直接宾语〉 我是〈名词〉 我是大学生

编译原理(第二版)第3章 文法和语法 课件

三、符号和符号串任何一种语言可看成是某个符号集上定义的，按 一定规则构成的一切基本符号串组成的集合。 字母表 :元素的非空有穷集合。(符号集) 符号：字母表中的元素。例如： 汉语的字母表中包括汉字、数字及标点符号等。 C语言的字母表是由字母、数字、若干专用符号及IF、 FOR之类的保留字组成。

编译原理(第二版)第3章 文法和语法 课件

符号串：由字母表 中的符号组成的任何有穷序列 称为该字母表上的符号串。形式定义: 1.空符号串ε(没有符号的符号串)是 上的符号串 2.若x是 上的符号串,a是 的元素,则xa是 上的符号 串 3.y是 上的符号串,当且仅当它可以由1和2导出。

例如： Σ={a,b} ε,a,b,aa,ab,aabba,…,都是 上的符号串 注意： 符号串中的符号排列是有顺序的。 常用大写字母表示符号串，如 x=aaca

编译原理(第二版)第3章 文法和语法 课件

如果 z = xy 是一符号串，那么： 1、x 是 z 的头，y 是 z 的尾；

2、如果 x 非空，那么 y 是固有尾；如果 y 非空，那么 x 是固有头。 例：设 z = abc, 那么 z 的头是： ε ,a ,ab , abc(除 abc 外都是固有头) z 的尾是： ε ,c ,bc , abc(除 abc 外都是固有尾)

编译原理(第二版)第3章 文法和语法 课件

4、符号串的运算符号串的长度：符号串中符号的个数.符号串s的长度 记为|s|。 ε的长度为0

符号串的连接：符号串x、y的连接,是把y的符号写在 x的符号之后得到的符号串xy 例 x=ST,y=abu 则 xy=STabu

|x|=2,|y|=3,|xy|=5εx = xε= x

编译原理(第二版)第3章 文法和语法 课件

方幂：符号串x自身连接n次得到的符号串 xx…xx(n个x)定义为 xn x0=ε , x1=x, x2=xx, x3=xxx x=AB, 则 x0=ε , x1=AB, x2=ABAB, x3=ABABAB 对于 n>0, xn = xxn-1 = xn-1x

编译原理(第二版)第3章 文法和语法 课件

5、符号串集合若集合A中一切元素都是某字母表 上的符号串， 则称A为字母表 上的符号串集合。 两个符号串集合A和B的乘积定义为 AB= xy|x A且y B

若集合A= a,b B= c,d 则 AB= ac,ad,bc,bd {ε}A=A{ε}=A(∵εx=xε=x) 使用 *表示 上的所有有穷长的串(包括ε)的集合。 Σ*称为Σ的闭包。

从 *中除去ε得到的集合记为 + 。 Σ+称为Σ的正 闭包。

编译原理(第二版)第3章 文法和语法 课件

Σ* = Σ0 ∪ Σ1 ∪ Σ2 … ∪ Σn …Σ+ = Σ1 ∪ Σ2 … ∪ Σn … Σ* = Σ0 ∪ Σ+ Σ+ = ΣΣ* = Σ*Σ Σ+ = Σ* -{ε} 例：设Σ={0,1},则 Σ* ={ε, 0, 1, 00, 01, 10, 11, 000, 001, 010,…} 例：设Σ ={a,b},则 Σ *={ε ,a,b,aa,ab,ba,bb,aaa,aab,…} Σ +={a,b,aa,ab,ba,bb,aaa,aab,…}

编译原理(第二版)第3章 文法和语法 课件

四、文法和语言的形式定义1、文法的形式定义 1)规则(重写规则、产生式或生成式):是 一个有序对(α,β)。记为α→β或 α∷=β,其中α∈V+,β∈V* 。 α称为规则的左部(或生成式的左部)。 β称为规则的右部(或生成式的右部)。

编译原理(第二版)第3章 文法和语法 课件

2)文法G[S]:文法为四元组(VN,VT,P,S)VN :非终结符集 VT :终结符集 P:产生式(规则)集合

S:开始符号(识别符号)VN、VT 和 P 是非空有穷集。S 至少在一条规则 中作为左部出现。 VN∩VT=φ, S∈VN V=VN∪VT,称为文法G的字母表(字汇表)

编译原理(第二版)第3章 文法和语法 课件

例3.1 文法G=(VN,VT,P,S) VN = { S }, VT ={ 0, 1 } P={ S→0S1, S→01 } S为开始符号

编译原理(第二版)第3章 文法和语法 课件

例3.2 文法G=(VN,VT,P,S) VN ={标识符，字母，数字} VT ={a,b,c,…x,y,z,0,1,…,9} P={<标识符>→<字母> <标识符>→<标识符><字母> <标识符>→<标识符><数字> <字母>→a,…, <字母>→z <数字>→0,…, <数字>→9} S=<标识符>

编译原理(第二版)第3章 文法和语法 课件

习惯上只将产生式写出。并有如下约定： –第一条产生式的左部是开始符号 –用尖括号括起的是非终结符，否则为终结 符。或者大写字母表示非终结符，小写字 母表示终结符 –G可写成G[S],其中S是开始符号

编译原理(第二版)第3章 文法和语法 课件

例3.1 文法G=(VN,VT,P,S) VN = { S }, VT ={ 0, 1 } P={ S→0S1, S→01 } S为开始符号 可写成： G:S→0S1 S→01 或写成： G[S]:S→0S1 S→01

编译原理(第二版)第3章 文法和语法 课件

Mini_C 介 绍Mini_C语言是在C语言的基础上定义的一种语言(C语言的子 集),它的文法定义如下：

1 <程序> ::= MAIN()<语句块> 2 <语句块> ::= {<变量声明列表><语句串>} | {语句串} 3 <变量声明列表> ::= <变量声明列表><变量声明>|<变量声明> 4 <变量声明> ::= <变量类型><ID>;

5 <变量类型> ::= i

nt | char | real6 <语句串> ::= <语句>;|<语句串><语句>; 7 <语句> ::= <赋值语句> | <条件语句> | <循环语句>

编译原理(第二版)第3章 文法和语法 课件

8 <赋值语句> ::= <ID>=<算术表达式>9 <条件语句> ::= if (<条件>)<语句块> | if (<条件>) <语句块>else<语句块>

10<循环语句> ::= <while语句> | <fo …… 此处隐藏：1877字，全部文档内容请下载后查看。喜欢就下载吧 ……