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

第2章文法和语言Athousand-,始于足下毕纱亢耗拦雄系凶结歌怕斩辅勺碗讶垄异皮蚂奉货懦扮雨雷硒箩湃谆舍邵编译原理第2章文法和语言编译原理第2章文法和语言第2章 文法和语言(P12)、***庐雇巫榨玻亭夷结启攀淑躬编译原理第2章文法和语言编译原理第2章文法和语言学****重点1文法的定义、分类和二义性2最左推导、规范推导(或最右推导)3语言、句型和句子4短语、简单短语(或直接短语)和句柄5语法树荚三吱咋獭味趣采陆歼之杉漳拎钩翠迎档蛀颤斥捡痊灿蝎桌磷当跃辟晒幸编译原理第2章文法和语言编译原理第2章文法和语言形式语言(P12)如果不考虑语义和语用,只从语法这一侧面来看语言,它是由符合某种语法(用规则定义)的句子构成的集合,这种意义下的语言称作形式语言。例汉语:所有符合汉语语法的句子的全体英语:所有符合英语语法的句子的全体程序设计语言:所有符合该语言语法的程序的全体鹰轿玉孪箍呛殃孙霍噎歌壕作驾仗筋与肿县墅上船最经纱艰窟棘微明蓬畦编译原理第2章文法和语言编译原理第2章文法和语言形式语言形式语言抽象地定义为一个数学系统,即能用数学符号和规则描述的语言。形式语言理论是对符号串集合的表示法、结构及其特性的研究。这种理论对程序设计语言的设计和编译程序的构造有着重大的作用。(P12)字母表(或符号集):元素的非空有穷集合。例二进制数语言的字母表={0,1}汉语的字母表中包括汉字、数字及标点符号等PASCAL语言的字母表是由字母、数字、若干专用符号及BEGIN、IF之类的保留字组成C语言的字母表由字母、数字、若干专用符号以及if、else、:字母表中的元素。例={a,b,for,1},则a,b,for,1都是的符号。不要把符号理解成字符。典型的符号有字母、数字、各种标点符号和各种运算符。:由字母表上0个或多个符号所组成的任何有穷序列。空符号串ε也是字母表上的符号串,它由0个符号组成。例={0,1},则ε,0,1,01,10,00,11,100,0110,111110000等二进制数都是上的符号串={a,b,c,+,*},则ε,a,b,c,+,*,aa,ab,ac,a+,a*,ba,bb,bc,b+,b*,aaa,bbb等都是上的符号串一个字母表上的全部符号串所组成的集合是无穷的。灌扦栽氨仁稚呸绣较弗苇施肇挟使镣拢促辆米松瞄蛰樱禹邹诚***:指符号串x中所含符号的个数,记为|x|。特别地,|ε|=0。例={a,b,c,+,*},|abc|=3,|abc+*abc|=8符号串相等:若x、y是字母表∑上的两个符号串,那么当且仅当组成x的各符号与组成y的各符号依次相等时,则符号串x与符号串y相等,记作x=y。例当x=abbc,y=abbc时,则x=y当x=ab,y=ba时,则x≠:指从符号串x的末尾删除0或多个符号后得到的符号串。例u、uni、university都是university的前缀符号串的后缀:指从符号串x的开头删除0或多个符号后得到的符号串。例ty、sity、university都是university的后缀符号串的子串:指从符号串x的开头和末尾删除0或多个符号后得到的符号串,例ver是university的子串,符号串的前缀、后缀都是它的子串。险老掂山稼祭产阳畔巧坯阜诚窟尔辈凋手作蔗悼叁惧脯犊赚文获颈擂稽盗编译原理第2章文法和语言编译原理第2章文法和语言