资源描述：
《第3章 文法和语法(lly)3》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第3章文法和语言考查重点基本概念：文法；推导/归约；句型；句子；语言；文法的二义性；文法递归；语法树；短语；直接短语；句柄；正规文法；上下文无关文法。基本方法构造句型的推导/归约，规范推导/规范归约画出指定句型的语法树判别文法的二义性给出句型的短语、直接短语、句柄。文法与语言的互求（较简单）1、语言语言是由句子组成的集合，是由一组记号所构成的集合。汉语--所有符合汉语语法的句子的全体英语--所有符合英语语法的句子的全体程序设计语言--所有该语言的程序的全体研究语言：每个句子构成的规律每个句子的含义每个句子和使用者的关系3
2、.1语言与文法的直观概念研究程序设计语言及研究的三个方面：每个程序构成的规律（语法Syntax）每个程序的含义（语义Semantics）每个程序和使用者的关系（语用Pragmatics）语言三个方面定义：语法--表示构成语言句子的各个记号之间的组合规律语义--表示按照各种表示方法所表示的各个记号的特定含义。（各个记号和记号所表示的对象之间的关系）语用--表示在各个记号所出现的行为中，它们的来源、使用和影响。以自然语言为例（用EBNF描述一种语言：）补讲：终端符与非终端符思考：“我是大学生”是否是该语言的句子？〈句子〉::
3、=〈主语〉〈谓语〉〈主语〉::=〈代词〉
4、〈名词〉〈代词〉::=你
5、我
6、他〈名词〉::=王明
7、大学生
8、工人
9、英语〈谓语〉::=〈动词〉〈直接宾语〉〈动词〉::=是
10、学习〈直接宾语〉::=〈代词〉
11、〈名词〉2、文法文法：仅仅涉及语言句子的结构描述。〈句子〉〈主语〉〈谓语〉〈代词〉〈谓语〉我〈谓语〉我〈动词〉〈直接宾语〉我是〈直接宾语〉我是〈名词〉我是大学生思考：“”的含义？“我大学生是”与“大学生是王明”是句子?〈句子〉::=〈主语〉〈谓语〉〈主语〉::=〈代词〉
12、〈名词〉〈代词〉::=你
13、我
14、他〈名词〉:
15、:=王明
16、大学生
17、工人
18、英语〈谓语〉::=〈动词〉〈直接宾语〉〈动词〉::=是
19、学习〈直接宾语〉::=〈代词〉
20、〈名词〉语法规则（文法）3、程序设计语言与文法关系：一个程序设计语言是一个记号系统，如自然语言一样，由语句组成，完整的定义应包含语法与语义两个方面。语法规定了语句形成的规则，（哪些符号序列是合法的，而与其含义无关）；语义不仅要限定语法规则（静态），而且要表明程序要做什么（动态）。文法是阐述语法规则的工具，是形式语言理论基础。为语言的语法描述寻求工具工具要对程序设计语言给出精确无二义的语法描述。（严谨、简洁、易读
21、）形式工具--形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述。字母表：元素的非空有穷集合。（符号集）符号：字母表中的元素。例如：汉语的字母表中包括汉字、数字及标点符号等。C语言字母表是由字母、数字、若干专用符号及保留字组成。3.2符号和符号串1、符号例如：Σ={0,1} ε,0,1,00,01,11,1001110等都是上的符号串.注意：符号串中的符号排列是有顺序的.可以用字母表示符号串，如x=aaca1）符号串：由字母表中的符号组成的任何有穷序列称为该字母
22、表上的符号串。空符号串ε(没有符号的符号串)是上的符号串若x是上符号串,a是的元素,则xa和ax是上符号串y是上的符号串,当且仅当它可以由1和2导出。2、符号串2）串的头与尾如果z=xy是一符号串，那么：x是z的头，y是z的尾；如果x非空，那么y是固有尾；如果y非空，那么x是固有头。例：设z=abc,那么z的头是：ε,a,ab,abc（固有头呢？）z的尾是：ε,c,bc,abc（固有尾呢？）3）串的几种表示法（x,z是符号串,t是符号）：z=x…x是符号串z的头z=…x…x在符号串z中某处出现z=t…符号t是符
23、号串z的第一个符号3、符号串的运算1）符号串的长度：符号串中符号的个数.符号串s的长度记为
24、s
25、。ε的长度为02）连接：符号串x、y的连接,是把y的符号写在x的符号之后得到的符号串xy例：x=ST,y=abu则xy=STabu
26、x
27、=2,
28、y
29、=3,
30、xy
31、=5εx=xε=x3）方幂：符号串x自身连接n次得到的符号串xx…xx(n个x)定义为xnx0=ε,x1=x,x2=xx,x3=xxxx=AB,则x0=ε,x1=AB,x2=ABAB,x3=ABABAB对于n>0,xn=xxn-1=xn-1x4）符号串集合：若集合A中
32、一切元素都是某字母表上的符号串，则称A为字母表上的符号串集合。Σ*=Σ0∪Σ1∪Σ2…∪Σn…Σ+=Σ1∪Σ2…∪Σn…Σ*=Σ0∪Σ+Σ+=ΣΣ*=Σ*ΣΣ+=Σ*-{ε}例：设Σ={a,b}，则Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}Σ+={a,b,aa,ab,ba,bb,aaa,aa
