《编译原理(第二版)第3课时文法和语法.docx》由会员分享，可在线阅读，更多相关《编译原理(第二版)第3课时文法和语法.docx（4页珍藏版）》请在课桌文档上搜索。
1、编译原理（第二版）第3章文法和语法编译原理（第二版）第3章文法和语法课件第3章文法和语言教学要求：本章是编译原理课程的理论基础，要求理解文法、语言、规范推导、规范归约和短语、简单短语、句柄的基本概念；掌握语言的求解方法、文法的二义性的判断方法及句型的分析方法。教学重点：上下文无关文法，语言定义编译原理（第二版）第3章文法和语法课件一、语言语言是由句子组成的集合，是由一组记号所构成的集合。汉语一所有符合汉语语法的句子的全体英语一所有符合英语语法的句子的全体程序设计语言一所有该语言的程序的全体编译原理（第二版）第3章文法和语法课件二、文法一种语言描述工具，用来定义句子的结构，用有限的规则把语言的全
2、部句子描述出来，是以有穷的集合刻划无穷的集合的工具。徇子：:主语谓语主语：:代词I名词代词：:你我I他名词：:王明I大学生;工人I英语谓语：:动词直接宾语动词：=是I学习直接宾语：=（代词I名词“我是大学生”是否是该语言的句子？编译原理（第二版）第3章文法和语法课件徇子）：=主语谓语主语：=代词I名词代词：=你我I他名词：=王明I大学生工人I英语谓语：=动词直接宾语动词）：=是I学习直接宾语：=代词名词句子）主语谓语代词谓语我谓语我动词直接宾语我是直接宾语我是名词我是大学生三、符号和符号串任何一种语言可看成是某个符号集上定义的，按一定规则构成的一切基本符号串组成的集合。字母表：元素的非空有穷集
3、合。（符号集）符号：字母表中的元素。例如：汉语的字母表中包括汉字、数字及标点符号等。C语言的字母表是由字母、数字、若干专用符号及IF、FOR之类的保留字组成。编译原理（第二版）第3章文法和语法课件符号串：由字母表中的符号组成的任何有穷序列称为该字母表上的符号串。形式定义：1.空符号串（没有符号的符号串）是上的符号串2.若X是上的符号串,a是的元素,则Xa是上的符号串3.y是上的符号串，当且仅当它可以由1和2导出。例如：=（a,b,a,b,aa,ab,aabba，都是上的符号串注意：符号串中的符号排列是有顺序的。常用大写字母表示符号串，如x=aaca编译原理（第二版）第3章文法和语法课件如果z=
4、xy是一符号串，那么：1、X是Z的头，y是Z的尾；2、如果X非空，那么y是固有尾；如果y非空，那么X是固有头。例：设Z=abc,那么z的头是：,a,ab,abc（除abc外都是固有头）Z的尾是：,c,be,abc（除abc外都是固有尾）编译原理（第二版）第3章文法和语法课件4、符号串的运算符号串的长度：符号串中符号的个数.符号串S的长度记为Is。的长度为0符号串的连接：符号串x、y的连接,是把y的符号写在X的符号之后得到的符号串Xy例x=ST,y=abu则Xy=STabux=2,y=3,xy=5X=X=X编译原理（第二版）第3章文法和语法课件方幕：符号串X自身连接n次得到的符号串_（n个x）定
5、义为Xnx=,xl=,x2=_,x3=_x=AB,则x=,xl=AB,x2=ABAB,x3=ABABAB对于n,xn=_n-l=x11-lx编译原理（第二版）第3章文法和语法课件5、符号串集合若集合A中一切元素都是某字母表上的符号串，则称A为字母表上的符号串集合。两个符号串集合A和B的乘积定义为AB=xyxA且yB若集合A=a,bB=c,d则AB=ac,ad,be,bdA=A=A（V=）使用*表示上的所有有穷长的串（包括）的集合。2*称为的闭包。从*中除去得到的集合记为+。+称为的正闭包。编译原理（第二版）第3章文法和语法课件*=0U1U2OUnO+=1U2oUno*=0U+=*=*+=*-例
6、：设E=0,1,则*=,0,1,00,01,10,11,000,001,010,O例：设Z=a,b,则*=,a,b,aa,ab,ba,bb,aaa,aab,+=a,b,aa,ab,ba,bb,aaa,aab,。编译原理（第二版）第3章文法和语法课件四、文法和语言的形式定义1、文法的形式定义1）规则（重写规则、产生式或生成式）：是一个有序对（,）o记为-B或：=B,其中V+,V*oa称为规则的左部（或生成式的左部）。称为规则的右部（或生成式的右部）。编译原理（第二版）第3章文法和语法课件2）文法GS:文法为四元组（VN,VT,P,S）VN:非终结符集VT:终结符集P:产生式（规则）集合S：开始符
7、号（识别符号）VN、VT和P是非空有穷集。S至少在一条规则中作为左部出现。VNVT=,SVNV=VNUVT,称为文法G的字母表（字汇表）编译原理（第二版）第3章文法和语法课件例3.1文法G=（VN,VT,P,S）VN=S,VT=0,1P=S-OSl,S01S为开始符号编译原理（第二版）第3章文法和语法课件例3.2文法G=（VN,VT,P,S）VN=标识符,字母，数字VT=a,b,c,ox,y,z,0,1,o,9P=标识符一字母标识符一标识符字母标识符一标识符数字字母一a,。，字母一Z数字-*0,o,数字-9S二标识符编译原理（第二版）第3章文法和语法课件习惯上只将产生式写出。并有如下约定：C第
8、一条产生式的左部是开始符号C用尖括号括起的是非终结符，否则为终结符。或者大写字母表示非终结符，小写字母表示终结符CG可写成GS,其中S是开始符号编译原理（第二版）第3章文法和语法课件例3.1文法G=（VN,VT,P,S）VN=S,VT=0,1P=S-OS1,S-01S为开始符号可写成：G:S-OS1S-01或写成：GS:SfOSlSfOlMini_C介绍Mini_C语言是在C语言的基础上定义的一种语言（C语言的子集），它的文法定义如下：1程序：=MAN（）语句块2语句块：=变量声明列表语句串I语句串3变量声明列表：=变量声明列表变量声明变量声明4变量声明：=变量类型ID5变量类型：=intIcharreal6语句串：=语句;语句串语句7语句：=赋值语句|条件语句循环语句编译原理（第二版）第3章文法和语法课件8赋值语句：=H）:算术表达式9条件语句：=if（条件）语句块Iif（条件）语句块else语句块10循环语句：=WhiIe语句for语句IIWhilC语句：=while（条件）语句块12for语句：=for（赋值语句条件算术表达式）语句块13条件：=算术表达式关系运算符算术表达式14关系运算符：=I=Il=I=I!=15算术表达式：=算术表达式+项I算术表达式一项I项
