资源描述：
《《文法和语言》ppt课件2》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第三章文法和语言程序设计语言程序设计语言语法：一种规则，用它可以形成和产生一个合适的程序。阐明语法的工具是文法。语义静态语义：一系列的限定规则，并确定哪些合乎语法的程序是合适的。动态语义：运行语义或执行语义，表明程序要做什么，要计算什么。8/27/20212文法和语言主要内容文法的直观概念符号和符号串文法和语言的形式定义文法的类型上下文无关文法及其语法树句型的分析有关文法实用中的一些说明8/27/20213文法和语言3.1文法的直观概念当我们表述一种语言时，就是要说明这种语言的句子。如果语言只含有有穷多个句子，则只需列出句子的有穷集。如果语言含有无穷多个
2、句子，存在着如何给出它的有穷表示的问题。这需要一种规则，用这些规则来描述语言的结构，可以把这些规则看成一种元语言，这些规则(或语言)就称为文法。8/27/20214文法和语言汉语文法举例<句子>::=<主语><谓语><主语>::=<代词>
3、<名词><代词>::=我
4、你
5、他<名词>::=王明
6、大学生
7、工人
8、英语<谓语>::=<动词><直接宾语><动词>::=是
9、学习<直接宾语>::=<代词>
10、<名词>8/27/20215文法和语言“我是大学生”的动作过程<句子><主语><谓语><代词><谓语>我<谓语>我<动词><直接宾语>我是<直接宾语>我是
11、<名词>我是大学生<句子>::=<主语><谓语><主语>::=<代词>
12、<名词><代词>::=我
13、你
14、他<名词>::=王明
15、大学生
16、工人
17、英语<谓语>::=<动词><直接宾语><动词>::=是
18、学习<直接宾语>::=<代词>
19、<名词>8/27/20216文法和语言3.2符号和符号串字母表：元素的非空集合，也称为符号集例：∑={0，1}A={a,b,c}符号：字母表中的元素例：0，1都是∑的符号，a、b、c是A的符号符号串：由字母表中的符号组成的任何有穷序列例：01、1001是∑的符号串a、b、c、abc、ab是A的符号串长度：如果某符号串x有m个符号，
20、称其长度为m，表示为
21、x
22、=m。如001110的长度为6空符号串：不包含任何符号的符号串，用
23、ε
24、=0表示8/27/20217文法和语言符号和符号串符号串的头尾，固有头和固有尾：如果z=xy是一符号串，那么x是z的头，y是z的尾。如果x是非空的，那么y是固有尾；若y非空，x是固有头。如：符号串abc头：ε,a,ab,abc尾：abc，bc,c,ε固有头：ε,a,ab固有尾：bc,c,ε8/27/20218文法和语言符号和符号串符号串的连接：设x和y是符号串，它们的连接xy是把y的符号写在x的符号之后得到的符号串如：x=ST，y=abu，xy=STabu符
25、号串的方幂：设x是符号串，把x自身连接n次得到符号串z，即z=xx…xx，成为符号串x的方幂，写作z=xn如：x=AB，x0=ε，x1=AB，x2=ABAB对于n>0，xn=xxn-1=xn-1x8/27/20219文法和语言符号和符号串符号串集合：若符号串集合A中的一切元素都是某字母表上的符号串，则称A为该字母表上的符号串集合。如{0，1，01，001，0001}是∑上的符号串的集合符号串集合的乘积：AB={xy
26、x∈A且y∈B}。即AB是满足x∈A，y∈B的所有符号串xy所组成的集合如：A={a,b}，B={c,d}，AB={ac,ad,bc,bd}
27、对于任意符号串，有εx=xε=x8/27/202110文法和语言符号和符号串集合的闭包：指定字母表Σ之后，用Σ*表示Σ上的所有有穷长的串的集合。Σ*称为集合Σ的闭包。Σ*=Σ0∪Σ1∪Σ2∪…∪Σn…如Σ={0，1}，Σ*={ε,0,1,00,01,10,11,000,001,010,…}集合的正闭包：Σ+=Σ1∪Σ2∪…∪Σn…称为Σ的正闭包。Σ*具有无穷数量的元素，如果x是Σ*中的元素，则表示为x∈Σ*，否则x∈Σ*。对于所有的Σ，有ε∈Σ*。8/27/202111文法和语言3.3文法和语言的形式定义规则（重写规则，产生式或生成式）的定义：形如α→β
28、或α∷=β的(α，β)有序对，α称为规则的左部，β称作规则的右部8/27/202112文法和语言文法的定义文法G定义为四元组(VN，VT，P，S)其中VN为非终结符号(或语法实体，或变量)集；VT为终结符号集；P为规则(α→β)的集合，α∈(VN∪VT)*且至少包含一个非终结符，β∈(VN∪VT）*；VN，VT和P是非空有穷集。S称作识别符号或开始符号，它是一个非终结符，至少要在一条产生式中作为左部出现。VN和VT不含公共的元素，即VN∩VT=φ用V表示VN∪VT，称为文法G的字母表或字汇表8/27/202113文法和语言文法定义举例1例1：文法G=（V
29、N，VT，P，S）VN={S},VT={0,1}P={S→0S1,S→01}S为
