编译原理—第3章文法和语法分解.ppt

第3章 文法和语言;一、语言;“我是大学生”是否是该语言的句子？;〈句子〉 ?〈主语〉〈谓语〉 ?〈代词〉〈谓语〉 ? 我〈谓语〉 ? 我〈动词〉〈直接宾语〉 ? 我是〈直接宾语〉 ? 我是〈名词〉 ? 我是大学生;三、符号和符号串;2、符号串的运算 符号串的长度：符号串中符号的个数.符号串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 ;3、符号串集合 若集合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的字母表（字汇表）;例: 文法G=（VN，VT，P，S） VN = { S }, VT ={ 0, 1 } P={ S→0S1, S→01 } S为开始符号;例: 文法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是开始符号;例:文法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 语句 11while语句 ::= while (条件)语句块 12for 语句 ::= for (赋值语句 ; 条件 ; 算术表达式)语句块 13条件 ::= 算术表达式关系运算符算术表达式 14关系运算符 ::= |=||=|==|!= 15算术表达式 ::= 算术表达式+项|算术表达式 - 项|项 ;五、推导的定义;例 文法G=（VN，VT，P，S） VN ={标识符，字母，数字} VT ={a,b,c,…x,y,z,0,1,…,9} P={标识符→字母 标识符→标识符字母 标识符→标识符数字 字母→a,…, 字母→z 数字→0,…,数字→9} S=标识符;2）长度为n的推导（有限次推导） 若存在v =w0 ?w1 ?... ?wn