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

第3章 文法和语言;一、语言;“我是大学生”是否是该语言的句子？;〈句子〉 ?〈主语〉〈谓语〉 ?〈代词〉〈谓语〉 ? 我〈谓语〉 ? 我〈动词〉〈直接宾语〉 ? 我是〈直接宾语〉 ? 我是〈名词〉 ? 我是大学生;三、符号和符号串;符号串：由字母表?中的符号组成的任何有穷序列称为该字母表上的符号串。 形式定义: 1.空符号串ε(没有符号的符号串)是?上的符号串 2.若x是?上的符号串,a是?的元素,则xa是?上的符号串 3.y是?上的符号串,当且仅当它可以由1和2导出。 例如： Σ={a,b} ε,a,b,aa,ab,aabba,…,都是?上的符号串 注意： 符号串中的符号排列是有顺序的。 常用大写字母表示符号串，如 x=aaca;如果 z = xy 是一符号串，那么： 1、x 是 z 的头，y 是 z 的尾； 2、如果 x 非空，那么 y 是固有尾；如果 y 非空，那么 x 是固有头。;4、符号串的运算 符号串的长度：符号串中符号的个数.符号串s的长度记为|s|。 ε的长度为0 符号串的连接：符号串x、y的连接,是把y的符号写在x的符号之后得到的符号串xy 例 x=ST,y=abu 则 xy=STabu |x|=2,|y|=3,|xy|=5 εx = xε= x;方幂：符号串x自身连接n次得到的符号串 xx…xx(n个x)定义为 xn x0=ε, x1=x, x2=xx, x3=xxx x=AB, 则 x0=ε, x1=AB, x2=ABAB, x3=ABABAB 对于 n0, xn = xxn-1 = xn-1x ;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) 使用?*表示?上的所有有穷长的串（包括ε）的集合。Σ*称为Σ的闭包。 从?*中除去ε得到的集合记为?+ 。 Σ+称为Σ的正闭包。;Σ* = Σ0 ∪ Σ1 ∪ Σ2 … ∪ Σn … Σ+ = Σ1 ∪ Σ2 … ∪ Σn … Σ* = Σ0 ∪ Σ+ Σ+ = ΣΣ* = Σ*Σ Σ+ = Σ* -{ε};四、文法和语言的形式定义;2）文法G[S]：文法为四元组（VN，VT，P，S） VN ：非终结符集 VT ：终结符集 P：产生式（规则）集合 S：开始符号（识别符号） VN、VT 和 P 是非空有穷集。S 至少在一条规则中作为左部出现。 VN∩VT=φ， S∈VN V=VN∪VT，称为文法G的字母表（字汇表）;例3.1 文法G=（VN，VT，P，S） VN = { S }, VT ={ 0, 1 } P={ S→0S1, S→01 } S为开始符号;例3.2 文法G=（VN，VT，P，S） VN ={标识符，字母，数字} VT ={a,b,c,…x,y,z,0,1,…,9} P={标识符→字母 标识符→标识符字母 标识符→标识符数字 字母→a,…, 字母→z 数字→0,…, 数字→9} S=标识符;习惯上只将产生式写出。并有如下约定： 第一条产生式的左部是开始符号 用尖括号括起的是非终结符，否则为终结符。或者大写字母表示非终结符，小写字母表示终结符 G可写成G[S]，其中S是开始符号;例3.1 文法G=（VN，VT，P，S） VN = { S }, VT ={ 0, 1 } P={ S→0S1, S→01 } S为开始符号; Mini_C 介 绍 Mini_C语言是在C语言的基础上定义的一种语言（C语言的子集），它的文法定义如下： 1 程序 ::= MAIN()语句块 2 语句块 ::= {变量声明列表语句串} | {语句串} 3 变量声明列表 ::= 变量声明列表变量声明|变量声明 4 变量声明 ::= 变量类型ID; 5 变量类型 ::= int | char | real 6 语句串 ::= 语句;|语句串语句; 7 语句 ::= 赋值语句 | 条件语句 | 循环语句 ; 8 赋值语句 ::= ID=算术表达式 9 条件语句 ::= if (条件)语句块 | if (条件) 语句块else语句块 10循环语句 ::= while语句 | for