文法和语言09年9月

《文法和语言09年9月》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章文法和语言3.1文法的直观理解3.2字符串及其运算3.3文法的形式定义3.4文法的类型3.5递归规则与递归文法3.6规范推导与句柄3.7语法树和二义性3.8语言和文法构造讨论和小结3.9文法的实用限制和变换13.1文法的直观理解在C语言中的赋值语句：a=b+c*60;a+b=c*60;问：1、如何分析哪句是非法的？2、计算机不知道它们是赋值语句，如何确定使用哪一套句型？2语言的基本概念（1）语法——指一组规则，使用这组规则，可以产生一个合适的程序；包括：词法规则（字符组成单词）语法规则（单词组成语法单元）（2）语义——赋予程序意义

2、的规则例如：数据类型匹配、变量是否声明、变量作用域静态语义：合乎语法的程序要遵守的语义规则动态语义：表明程序要做什么3文法：即语言的表述方法把一门语言的句子描述清楚，就把这门语言表述出来了，这种表述方法就称为文法。两种方式：1、有穷语言只需列出句子2、无穷语言要给出有穷表示法4用一组规则表述语言的例子构成规则：<句>→<主><谓><主>→<代>

3、<名><代>→我

4、你

5、他<名>→王明

6、大学生

7、英语<谓>→<动><宾><动>→是

8、学习<宾>→<代>

9、<名>从上述规则产生句子“我是大学生”的例子：<句>＝＞<主><谓>＝＞<代>

10、<谓>＝＞我<谓>＝＞我<动><宾>＝＞我是<宾>＝＞我是<名>＝＞我是大学生“＝＞”表示：使用一条规则，代替左端的某个符号，产生右端的符号串5文法的直观表示文法由四部分组成：一组非终结符：<句>，<主>，<代>，……一组终结符：我，你，他，王明，……一个开始符号：<句>一组产生式：<句>→<主><谓>，……63.2字符串及其运算字母表：元素的非空有穷集合。例：∑＝{0，1}，Α＝{a，b，c}。V1={a,b,c,…,z}英语小写字母表V2={book,pencil,pen,paper}V2也是字母表（单词表）字母表中的元素称

11、为符号，字母表也称符号集。程序语言的字母表由字母数字和若干专用符号组成。7符号串：由字母表中的符号组成的任何有穷序列称为该字母表上的符号串。例：字母表∑＝{0，1}，Α＝{a，b，c}0，00，01，10，……等是∑上的符号串。a，b，c，ab，aaca，……是A上的符号串。不含任何符号的符号串称为空串，用ε表示。符号串长度表示符号串中含有符号的个数。例：

12、abc

13、＝3，

14、ε

15、＝03.2字符串及其运算8串的连接：符号串x和y的连接xy，是把y的符号写在x的符号之后得到的符号串。例如x＝ST，y＝abu，则xy＝STabu显然εx＝xε

16、＝x3.2字符串及其运算9设z=xy是符号串，则称x是z的头，y是z的尾。若y非空，则x是z的真（固有）头或真前缀。若x非空，则y是z的真（固有）尾或真后缀。例7:设z=abc,则z的头有ε,a,ab,abc,除了abc，其余都是固有头；10串的方幂：符号串x自身n次连接记作xn，称为串x的方幂。x0＝ε(n＝0)x1＝x(n＝1)x2＝xx(n＝2)…xn＝xxn-1＝xn-1x(n>0)例：x＝AB，x0＝ε，x1＝AB，x2＝ABAB…3.2字符串及其运算11串的集合：由某字母表上的符号串组成的集合称为该字母表上的符号串集

17、合，简称串集合。串集合的乘积：符号串集合A和B的乘积AB定义为：AB＝{xy

18、x∈A且y∈B}，即AB是由A中的串x和B中的串y连接而成的串xy组成的集合。例：设A＝{a，b}，B＝{c，d}，则AB＝{ac，ad，bc，bd}显然{ε}A＝A{ε}＝A3.2字符串及其运算12串集合的闭包：符号串集合A的闭包A*定义如下：A*＝A0∪A1∪A2∪A3∪……例：设字母表Σ={0，1},(字母表是串集合)则Σ*＝Σ0∪Σ1∪Σ2∪……＝{ε,0,1,00,01,10,11,……}即Σ*表示字母表Σ上符号的任意串的集合。3.2字符串及其运算Σ

19、+＝Σ1∪Σ2∪Σ3∪……称为A的正闭包。显然Σ*＝Σ0∪Σ+＝Σ+∪Σ0星闭包Σ+＝ΣΣ*＝Σ*Σ133.3文法的形式定义定义文法G定义为四元组（VN，VT，P，S）,其中：VN：非终结符集；VT：终结符集，并且VN∩VT＝φ；P：产生式集合；S：开始符号或识别符号；P中产生式形式为：α→β，其中：α∈V+且至少含一个非终结符，β∈V*，而V＝VN∪VT，V称为文法G的字母表。例：G＝（{S}，{0，1}，{S→0S1，S→01}，S）14文法的简化表示法通常不用将文法G的四元组显示表示，只写出产生式。约定：第一条产生式的左部是开始

20、符号或用G[S]表示S是开始符号；用大写字母(或用尖括号括起来)表示非终结符；用小写字母表示终结符。左部相同的产生式A→α，A→β可以记为：A→α

21、β，其中“

22、”是“或”的意思，α，β分别称为侯选式。3.3