资源描述：
《编译原理第03章文法和语言》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、1编译原理 文法和语言华东交通大学软件学院网络工程教研室万仲保Tel:704682113907097766E-mail:zbwan@tom.com2第三章文法和语言本章目的为语言的语法描述寻求工具工具要对程序设计语言给出精确无二义的语法描述。（严谨、简洁、易读）形式工具--形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述。33.1文法的直观概念3.2符号和符号串3.3文法和语言的形式定义3.4文法的类型3.5上下文无关文法及其语法树3.6句型分析3.7实用说明第三章文法和语言
2、4文法的直观概念一个程序设计语言是一个记号系统，如同自然语言一样，它的完整的定义应包括语法和语义两个方面。所谓一个语言的语法是指一组规则，用它可以形成和产生一个合适的程序。目前广泛使用的手段是上下文无关文法，即用上下文无关文法作为程序设计语言语法的描述工具。语法只是定义什么样的符号序列是合法的，与这些符号的含义毫无关系阐明语法的一个工具是文法，这是形式语言理论的基本概念之一。示例：汉语句子的描述语言概述5汉语句子的描述语法规则定义字符串的判断6语法规则定义〈句子〉∷=〈主语〉〈谓语〉〈主语〉∷=〈代词〉｜〈名词〉〈代词〉∷=我｜你
3、｜他〈名词〉∷=王明｜大学生｜工人｜英语〈谓语〉∷=〈动词〉〈直接宾语〉〈动词〉∷=是｜学习〈直接宾语〉∷=〈代词〉｜〈名词〉7字符串的判断有了一组规则以后，按照如下方式用它们导出句子：开始去找∷=左端的带有〈句子〉的规则并把它由∷=右端的符号串代替，这个动作表示成：〈句子〉〈主语〉〈谓语〉，然后在得到的串〈主语〉〈谓语〉中，选取〈主语〉或〈谓语〉，再用相应规则的∷=右端代替之。比如，选取了〈主语〉，并采用规则〈主语〉∷=〈代词〉，那么得到：〈主语〉〈谓语〉〈代词〉〈谓语〉，重复做下去。句子：“我是大学生”的全部动作过程是：〈
4、句子〉〈主语〉〈谓语〉〈代词〉〈谓语〉我〈谓语〉我〈动词〉〈直接宾语〉我是〈直接宾语〉我是〈名词〉我是大学生8字符串的判断“我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据，换句话说，这些规则看成是一种元语言，用它描述汉语。这里仅仅涉及汉语句子的结构描述。其中一种描述元语言称为文法。9符号和符号串定义：符号：可以相互区别的记号（元素）。字母表（）：符号（元素）的非空有穷集合。符号串：由字母表中的符号组成的任何有穷序列称为该字母表上的符号串
5、。1.空符号串ε(没有符号的符号串)是上的符号串2.若x是上的符号串,a是的元素,则xa是上的符号串3.y是上的符号串,当且仅当它可以由1和2导出。例如：Σ={a,b}ε,a,b,aa,ab,aabba…都是上的符号串符号串的运算10符号串的运算既然将语言定义为一个集合，那么有关集合的运算也适合语言。即：设L是（∑上的）一个语言,M是（∑上的）一个语言，则语言L和M的并，交，差，补是一个语言。符号串的头、尾、子串符号串的长度符号串的连接符号串的方幂符号串的集合11符号串的头、尾、子串符号串s的头（前缀）：移走符号串s尾
6、部的零个或多于零个符号得到的符号串。如：b是符号串banana的一个前缀.符号串s的尾（后缀）：删去符号串s头部的零个或多于零个符号得到的符号串。如:nana是符号串banana的一个后缀.符号串s的子串：从s中删去一个前缀和一个后缀得到的符号串。如:ana是符号串banana的一个子串.对于每个符号串s，s和ε两者都是符号串s的前缀，后缀和子串。符号串s的真前缀，真后缀，真子串：任何非空符号串x,相应地，是s的前缀，后缀或子串，并且sx。12符号串中符号的个数。符号串s的长度记为
7、s
8、。ε的长度为0符号串的长度13符号串的连接
9、设x、y是符号串，则x、y的连接是把y的符号写在x的符号之后得到的符号串xy如x=ab,y=cd则xy=abcd有εa=aε14符号串的方幂方幂：设x是符号串，把x自身连接n次得到的符号串z，即z=aa…aa称为符号串x的方幂。写作z=an示例：a1=a,a2=aaa0=ε15符号串集合若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。两个符号串集合A和B的乘积定义为：AB=xy
10、xA且yB若集合A=ab,cdeB=0,1，则AB=ab1,ab0,cde0,cde1使用*表示上的所
11、有有穷长符号串（包括ε）组成的集合。Σ*称为Σ的闭包。上的除ε外的所有符号串组成的集合记为+。Σ+称为Σ的正闭包。Σ*=Σ0∪Σ1∪Σ2∪⋯∪Σn⋯Σ+=Σ1∪Σ2∪⋯∪Σn⋯Σ*={ε}∪Σ+Σ+=ΣΣ*=Σ*Σ16文法和语言的形式定义文法和
