编译原理第2章文法和语言.pptx

基本概念字母表、符号、符号串、闭包等文法的定义文法的分类Chromsky对文法的分类文法和语言推导、归约、句型、句子、语言语法分析树和二义性第二章文法和语言

2.1文法和语言的定义字母表，符号，符号串定义2.1字母表：字母表∑是符号元素的非空有限集合。定义2.2符号（字符）：字母表中的元素。定义2.3符号串（字符串）：字母表中的符号所组成的任何有穷序列。如字母表∑={a,b}，则a,b是字母表∑中的元素，a,b,aa,ab,…都是符号串。空符号串：不含任何符号的符号串，用ε表示。符号串，如int例句：inti=0;包含字母i,n,t,=,0,;,所有字母形成字母表；

例：|ab|=2,|aabb|=4,|ε|=0。定义2.5符号串的长度：指符号串中符号的个数。01例：若∑={a,b},x=ab,y=ba,则xy=abba,yx=baab。注意：（1）xy≠yx；εx=xε=x。字符串连接、字符串长度定义2.4符号串x和y的连接：指x和y的符号按先后顺序排列在一起组成的新的符号串，用xy表示。022.1文法和语言的定义

2.1文法和语言的定义定义2.6符号串的前缀和后缀：分别指符号串的左部和右部任意字符串。例：ab的前缀有ε、a、ab；后缀有ε、b、ab。定义2.7符号串集合的乘积：设A、B是字母表∑上的符号串集合，则定义A与B的乘积：AB={xy|x∈A，y∈B}。例：设∑={a，b，c，d}，令A={aa,bb}，B={cc,dd},则 AB={aacc,aadd,bbcc,bbdd}, BA={ccaa,ccbb,ddaa,ddbb}。显然AB≠BA定义空集合：Φ={ε}，有{ε}A=A{ε}=A。前缀、后缀、乘积

定义2.8符号串的方幂：设x是符号串，则：x0=ε,x1=x,x2=xx,…,xn=x…x(n个)定义2.9符号串集合A的方幂：A0={ε},A1=A,A2=AA,…,An=A…A(n个A)A的正闭包：A+=A1∪A2∪…A的闭包：A*=A0∪A1∪A2∪…显然：A*=A0∪A+,A+=AA*问题：A={0,1},则A+表示的集合意义？030201050406方幂、正闭包、闭包2.1文法和语言的定义

2.1文法和语言的定义什么是文法文法是定义或描述语法结构的一组形式规则，是规则的非空有穷集合规则又称为重写规则，产生式或生成式，每个产生式为α?β或α::=β，α是某字母表A的正闭包A+的一个符号称为规则的左部；β是A*中的一个符号，称为规则的右部。α与β的区别？文法

2.1文法和语言的定义什么是文法文法是定义或描述语法结构一组形式规则，是规则的非空又穷集合规则又称为重写规则，产生式或生成式，每个产生式为α?β或α::=β，α是某字母表A的正闭包A+的一个符号称为规则的左部；β是A*中的一个符号，称为规则的右部。α与β的区别？例句：Hegavemeabook.英语中的基本语法规则：句子?主语谓语间接宾语直接宾语主语?代词|名词谓语?动词间接宾语?代词直接宾语?冠词名词代词?He|me名词?book动词?gave冠词?a|an|the例句：Hegavemeabook.根据上述语法规则对例句进行分析，可推出该例句。句子=主语谓语间接宾语直接宾语=代词谓语间接宾语直接宾语=He谓语间接宾语直接宾语=He动词间接宾语直接宾语=Hegave间接宾语直接宾语=Hegave代词直接宾语=Hegaveme直接宾语=Hegaveme冠词名词=Hegavemea名词=Hegavemeabook文法

2.1文法和语言的定义inti=0;i=i+1;程序?{句子}+句子?声明语句|赋值语句|……声明语句?数据类型{变量[=常量]}+赋值语句?变量=表达式变量?(a|…|z|A|…|Z|_)(a|…|z|A|…|Z|_|0|…|9)数据类型?int|char|………文法包含的要素：终极字符集：如inti非终极字符集：如程序、句子产生式：如程序?{句子}+开始符号：程序文法

2.1文法和语言的定义定义2.10文法是一个四元组：G[S]=(VN,VT,P,S),其中：VN：非终极符集合（