第3章 文法和语法(4学时).ppt

《第3章 文法和语法(4学时).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第3章文法和语言学习要点：符号和符号串的相关概念文法和语言的形式定义文法的类型上下文无关文法及其语法树上下文无关文法的句型分析有关文法实用中的一些说明学习目的：掌握文法和语言的相关概念，为以后的词法分析、语法分析、语义分析等做出准备。3.1文法的直观概念语言：是由句子组成的集合，是一组记号所构成的集合。汉语——所有符合汉语语法的句子的全体英语——所有符合英语语法的句子的全体程序设计语言——所有该语言的程序的全体语言研究语言研究的三个方面：语法Syntax：表示构成语言句子的各个记号之间的组合规律。语义Semantics：表示按照各种表示方法所表示的各个记号的特定含义。（各个记号和记号所表示的

2、对象之间的关系）语用Pragmatics：表示在各个记号所出现的行为中，它们的来源、使用和影响。研究程序设计语言：每个程序构成的规律每个程序的含义每个程序和使用者的关系研究语言：每个句子构成的规律每个句子的含义每个句子和使用者的关系如果不考虑语义和语用，只从语法这一侧面来看语言，这种意义下的语言称作形式语言。形式语言抽象地定义为一个数学系统。“形式”是指：语言的所有规则只以什么符号串能出现的方式来陈述。形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。文法：描述词法、语法规则的工具。用一组规则严格定义句子的结构，即对含有“无穷句子”的语言进行“有穷的表示

3、”。形式语言与文法判断下列句子是否是该语言的句子？（用规则去推导句子）我是大学生我大学生是他学习英语英语学习他〈句子〉::=〈主语〉〈谓语〉〈主语〉::=〈代词〉

4、〈名词〉〈代词〉::=你

5、我

6、他〈名词〉::=王明

7、大学生

8、工人

9、英语〈谓语〉::=〈动词〉〈直接宾语〉〈动词〉::=是

10、学习〈直接宾语〉::=〈代词〉

11、〈名词〉文法举例：以自然语言为例，用EBNF描述语言3.2符号和符号串字母表：元素的非空有穷集合。（又称为符号集）符号：字母表中的元素。例如：汉语的字母表：包括汉字、数字及标点符号等。英文的字母表：{a,b,…z,A,B,…,Z}二进制的字母表：{0,1}标识符的字母表：{a…z

12、,A…Z,0…9,_}符号串：由字母表中的符号组成的任何有穷序列空符号串ε(没有符号的符号串)是上的符号串符号串不仅表示由哪些符号组成，还表示符号的顺序例如：Σ={0,1}ε,0,1,00,01,10,11,…,1011,…都是上的符号串01≠10相关概念(1)符号串的长度：符号串x中符号的个数，用

13、x

14、表示例如：x=aabc则

15、x

16、=4(2)空符号串：ε则

17、ε

18、=0(3)头、尾、固有头、固有尾z=xyx是z的头；y是z的尾若y非空，x是z的固有头；若x非空，y是z的固有尾。例如：符号串abc头：ε,a,ab,abc尾：ε,c,bc,abc固有头：ε,a,ab固有尾：ε,c,bc(4)符

19、号串的连接：x,y的连接即xy（把y的符号写在x符号后面）例如：x=01y=abc则xy=01abcyx=abc01注意：εx=xε=x相关概念(5)符号串的方幂：对符号串x，把它自身连接n次得到符号串z，z=xxx…x，记作：z=xn，x0=ε，x1=x，x2=xx，……例如：x=01，则x0=εx1=01x2=0101x3=010101(6)符号串集合：集合A中的一切元素都是某字母表上的符号串，则称A为该字母表上的符号串集合。例如：Σ={0,1}A={0,1,00,01,10…，10001,……}是B={10,11,101}是C={1a,11011,b11}不是(7)符号串集合的乘积：AB

20、={xy

21、x∈A且y∈B}例如：A={01,10}B={ab,cd}AB={01ab,10ab,01cd,10cd}注意：“ab01”不在AB中{ε}A=A{ε}=A相关概念(8)集合的闭包：指定字母表V之后，可用V*表示V上所有有穷长度的串的集合。V+为V的正闭包。V*=V0∪V1∪…∪Vn…V+=V1∪…∪Vn…则：V*=V0∪V+V+=VV*=V*VV+=V*-{ε}例如：设V={0，1}则V*={ε,0,1,00,01,10,11,000,001,…}V+={0,1,00,01,10,11,000,001,…}3.3文法和语言的形式定义规则（重写规则、产生式、生成式）是形如α→β或α∷

22、=β的（α，β）有序对。其中α∈V+，β∈V*α称为规则的左部β称为规则的右部举例：<程序><分程序>.<条件语句>IF<条件>THEN<语句>文法的定义文法G定义为四元组（VN,VT,P,S）VN：非终结符集VT：终结符集P：产生式集合（规则集合）S：开始符号（识别符号）其中，VN、VT和P是非空有穷集S∈VN，并且S至少在一条规则中作为左部出现VN∩VT=φV=VN∪VT，V称为文法G的字