《第2章 文法和语言》由会员分享，可在线阅读，更多相关《第2章 文法和语言（63页珍藏版）》请在金锄头文库上搜索。
1、1第第2章章 文法和语言文法和语言2 构造编译程序，需针对构造编译程序，需针对特定的程序语言，故需对被特定的程序语言，故需对被编译的程序语言本身做精确编译的程序语言本身做精确地描述。地描述。 为语言的语法（文法）为语言的语法（文法）描述寻求工具。工具要对程描述寻求工具。工具要对程序设计语言给出精确无二义序设计语言给出精确无二义的语法描述。（严谨、简洁、的语法描述。（严谨、简洁、易读）。易读）。本章目的本章目的 对于程对于程序设计者而序设计者而言，文法给言，文法给出了语言的出了语言的精确的语法精确的语法规范说明。规范说明。3程序设计语言描述程序设计语言描述语法语法Syntax：对语言结构的定义。
2、：对语言结构的定义。语义语义Semantics：描述语言的含义。：描述语言的含义。语用语用Pragmatics：从使用者角度描述语言。：从使用者角度描述语言。如果不考虑语义和语用，即只从语法这如果不考虑语义和语用，即只从语法这一侧面来看语言，这种意义下的语言称作一侧面来看语言，这种意义下的语言称作形形式语言式语言。4形形式式语语言言抽抽象象地地定定义义为为一一个个数数学学系系统统。“形形式式”是是指指这这样样的的事事实实：语语言言的的所所有有规规则则只以符号串能出现的方式来陈述。只以符号串能出现的方式来陈述。形形式式语语言言理理论论是是对对符符号号串串集集合合的的表表示示法法、结结构构及及其其
3、特特性性的的研研究究。是是程程序序设设计计语语言言语语法法分析研究的基础。分析研究的基础。52.1字母表和符号串字母表和符号串2.2文法和语言的形式定义文法和语言的形式定义2.3语法树和文法的二义性语法树和文法的二义性2.4文法的类型文法的类型62.1字母表和符号串字母表和符号串7 每个程序设计语言都是一个每个程序设计语言都是一个“基本符基本符号号”串，设有一基本符号集，那么程序设串，设有一基本符号集，那么程序设计语言可看成是在这个基本符号集上定义计语言可看成是在这个基本符号集上定义的，按一定规则构成的一切基本符号串组的，按一定规则构成的一切基本符号串组成的集合。成的集合。 为了给出语言的形式
4、定义，首先学习为了给出语言的形式定义，首先学习一些基本概念和术语。一些基本概念和术语。8（1 1）空符号串）空符号串：没有没有符号的符号串符号的符号串 。 例如：例如： =a,b =a,b ,a,b,aa,ab,aabba,a,b,aa,ab,aabba都都是是 上的符号串上的符号串1. 1. 字母表字母表 ：符号（元素）的非空有穷集合。符号（元素）的非空有穷集合。字符（符号）：字符（符号）：可以相互区别的记号（元素）。可以相互区别的记号（元素）。2. 2. 符号串：符号串：由字母表由字母表 中的符号组成的任何有穷序中的符号组成的任何有穷序列称为该字母表上的符号串。列称为该字母表上的符号串。9
5、 （2 2）符号串）符号串s s的头（前缀）：的头（前缀）：移走符号串移走符号串s s尾部尾部的零个或多于零个符号得到的符号串。的零个或多于零个符号得到的符号串。 如：如：b b是符号串是符号串bananabanana的一个前缀。的一个前缀。 符号串符号串s s的尾（后缀）：的尾（后缀）：删去符号串删去符号串s s头部的零头部的零个或多于零个符号得到的符号串。个或多于零个符号得到的符号串。 如如:nana:nana是符号串是符号串bananabanana的一个后缀。的一个后缀。（3 3）符号串）符号串s s的子串：的子串：从从s s中删去一个前缀和中删去一个前缀和一个后缀得到的符号串。一个后缀
6、得到的符号串。 如如:ana:ana是符号串是符号串bananabanana的一个子串。的一个子串。10 对于每个符号串对于每个符号串s s， s s和和两者两者都都是符号是符号串串s s的前缀，后缀和子串。的前缀，后缀和子串。 （4 4）符号串）符号串s s的真前缀，真后缀，真子串的真前缀，真后缀，真子串 3.3.符号串的运算符号串的运算 (1)(1)符号串的长度：符号串的长度：符号串中符号的个数符号串中符号的个数. .符号符号串串s s的长度记为的长度记为|s|s|。 的长度为的长度为0 0。 (2)(2)连接：连接：符号串符号串x x、y y的连接的连接, ,是把是把y y的符号写在的符
7、号写在x x的符号之后得到的符号串的符号之后得到的符号串xyxy。 如如 x=ab,y=cd x=ab,y=cd 则则 xy=abcd xy=abcd 有有a = a= a a = a= a (3) (3)方幂：方幂：符号串自身连接符号串自身连接n n次得到的符号串次得到的符号串 a an n 定义为定义为 aaaaaa naa n个个a aa a1 1=a, a=a, a2 2=aa=aa则则a a0 0=11(4)(4)符号串集合：符号串集合：若集合若集合A A中所有元素都是某字母中所有元素都是某字母表表 上的符号串，则称上的符号串，则称A A为字母表为字母表 上的符号串集合。上的符号串集
8、合。 两个符号串集合两个符号串集合A A和和B B的乘积定义为：的乘积定义为： AB =AB = xy|xxy|x A A且且y y B B 若若 集合集合A=A= ab,cdeab,cde B = B = 0,10,1 ，则，则 AB=AB= ab1,ab0,cde0,cde1ab1,ab0,cde0,cde1 4.4.闭包：闭包：使用使用 * *表示表示 上的一切符号串（包括上的一切符号串（包括）组成的集合。组成的集合。* *称为称为的闭包。的闭包。 上的上的除除外的所有符号串组成的集合记为外的所有符号串组成的集合记为 + + 。 + +称为称为的正闭包。的正闭包。12例：例：=a,b*=
9、,a,b,aa,ab,ba,bb,aaa,aab,+=a,b,aa,ab,ba,bb,aaa,aab,13文法的直观概念文法的直观概念14 当我们表述一种语言时，无非是说明这种语当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，存在着如何给出它的子的语言来讲，存在着如何给出它的有穷表示有穷表示的的问题。问题。 以自然语言为例，人们无法列出全部句子，以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明
10、但是人们可以给出一些规则，用这些规则来说明( (或者定义或者定义) )句子的组成结构。句子的组成结构。 比如汉语句子可以是由主语后随谓语而成，比如汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语，以下是该句的构构成谓语的是动词和直接宾语，以下是该句的构成规则：成规则： 15“我是大学生。我是大学生。”是一个汉语句子是一个汉语句子句子句子 =主语主语谓语谓语主语主语 =代词代词名词名词代词代词 = 我我你你他他名词名词 = 王明王明大学生大学生工人工人英语英语谓语谓语 =动词动词直接宾语直接宾语动词动词 = 是是学习学习直接宾语直接宾语 =代词代词名词名词 16 有了一组规则以后，按
11、照如下方式用它们导出句子：开有了一组规则以后，按照如下方式用它们导出句子：开始去找始去找= =左端的带有左端的带有句子句子的规则并把它由的规则并把它由= =右端的符右端的符号串代替，这个动作表示成：号串代替，这个动作表示成：句子句子 主语主语谓语谓语， 然后在得到的串然后在得到的串主语主语谓语谓语中，选取中，选取主语主语或或谓语谓语，再用相应规则的，再用相应规则的= =右端代替之。右端代替之。 重复做下去，句子：重复做下去，句子：“我是大学生我是大学生”的全部动作过程是：的全部动作过程是：句子句子 主语主语谓语谓语 代词代词谓语谓语 我我谓语谓语 我我动词动词直接宾语直接宾语 我是我是直接宾语
12、直接宾语 我是我是名词名词 我是大学生我是大学生符号符号 的含义：的含义：使用一条规则，代使用一条规则，代替替左边的某个符左边的某个符号，产生号，产生右端的右端的符号串。符号串。17 “我是大学生我是大学生”的构成符合上述规则，的构成符合上述规则，而而“我大学生是我大学生是”不符合上述规则，那么不符合上述规则，那么它就不是句子。这些规则成为我们判别句它就不是句子。这些规则成为我们判别句子结构合法与否的依据。子结构合法与否的依据。 换句话说，这些规则看成是一种元语换句话说，这些规则看成是一种元语言，用它描述汉语结构。这种描述语言的言，用它描述汉语结构。这种描述语言的语法结构的形式规则称为文法。语
13、法结构的形式规则称为文法。18v王明是大学生。王明是大学生。v他学习英语。他学习英语。v你是工人。你是工人。 使用文法作为工具，不仅能使用文法作为工具，不仅能严格定义句子结构，也能用有限严格定义句子结构，也能用有限的规则把语言的全部句子描述出的规则把语言的全部句子描述出来。来。 所以，所以，文法是以有穷集合刻文法是以有穷集合刻划无穷集合的工具划无穷集合的工具。19上例中的局限性上例中的局限性v对对“我是大学生我是大学生”作扩充作扩充“我是计算机专我是计算机专业的大学生。业的大学生。”v该句子中多了定语，相应的对前面的该句子中多了定语，相应的对前面的7 7条规则条规则做相应修改。做相应修改。 因
14、此，用文法因此，用文法描述的一组规则只描述的一组规则只能描述一类句子，能描述一类句子，不同类的句子应使不同类的句子应使用不同的规则。用不同的规则。 同理，程序设计语同理，程序设计语言也不能只用一组规则言也不能只用一组规则就把程序都描述完整。就把程序都描述完整。202.2文法和语言的文法和语言的形式定义形式定义21一、文法一、文法二、推导二、推导 1. 1. 直接推导（一步推导）直接推导（一步推导） 2. 2. 推导序列（多步推导）推导序列（多步推导）三、句型，句子三、句型，句子四、语言四、语言 1. 1. 语言等价语言等价 2. 2. 文法与语言的关系文法与语言的关系22如何来描述一种语言？如
15、何来描述一种语言？ 如果语言是有穷的（只含有有穷多个句子），如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示。可以将句子逐一列出来表示。 如果语言是无穷的，找出语言的有穷表示。如果语言是无穷的，找出语言的有穷表示。语言的有穷表示有两个途经：语言的有穷表示有两个途经：生成方式生成方式 （文法）：（文法）：语言中的每个句子可以语言中的每个句子可以用严格定义的规则来构用严格定义的规则来构造。造。识别方式（自动机）：识别方式（自动机）：是是一个过程，当输入的一任一个过程，当输入的一任意串属于语言时，该过程意串属于语言时，该过程经有限次计算后就会停止经有限次计算后就会停止并回答并回答“是
16、是”，若不属于，若不属于，要么能停止并回答要么能停止并回答“不是不是”，（要么永远继续下去。，（要么永远继续下去。）23 文法是生成方式描述语言的：语言文法是生成方式描述语言的：语言中的每个句子可以用严格定义的规则来中的每个句子可以用严格定义的规则来构造。构造。 下面给出文法的四个组成部分，初下面给出文法的四个组成部分，初步对文法的形式定义有一个初步了解。步对文法的形式定义有一个初步了解。241. 1. 终结符：终结符：语言中不可再分的基本符号，通常是语言中不可再分的基本符号，通常是一个语言的字母表。一个语言的字母表。如程序设计语言中的基本字、如程序设计语言中的基本字、常数、运算符、分界符等。
17、常数、运算符、分界符等。2. 2. 非终结符：非终结符：它不像终结符代表了语法的最小元它不像终结符代表了语法的最小元素，是一种个体记号，它是一个类、一个集合。一个素，是一种个体记号，它是一个类、一个集合。一个非终结符代表了一定的语法概念。非终结符代表了一定的语法概念。程序设计语言中常程序设计语言中常见的语法单位有见的语法单位有“过程过程”、“赋值语句赋值语句”、“表达式表达式”等。等。3. 3. 开始符号：开始符号：是一个特殊的非终结符。是一个特殊的非终结符。4. 4. 产生式：产生式：构造某个语法时应满足的规则。构造某个语法时应满足的规则。25文法文法G定义为四元组定义为四元组(VN，VT，
18、P，S)其中：其中：VN为非终结符号为非终结符号(或语法实体，或变量或语法实体，或变量)集；集；VT为终结符号集；为终结符号集；S为开始符号，它是一个非终结符，至少要在一为开始符号，它是一个非终结符，至少要在一条产生式中作为左部出现。条产生式中作为左部出现。P为产生式为产生式(也称规则也称规则)的集合；的集合；VN，VT和和P是非空有穷集。是非空有穷集。VN和和VT不含公共的元素，即不含公共的元素，即VNVT=用用V表示表示VNVT，称为文法，称为文法G的字母表。的字母表。26文法的举例文法的举例例例:文法文法G=（VN，VT，P，S）VN=S,VT=0,1P=S0S1,S01S为开始符号为开
19、始符号27定义中的注意事项定义中的注意事项1.产生式形如产生式形如，“”读作读作“是是”或或“定义为定义为”。其中其中是字母表是字母表V的正闭包的正闭包V+中的一个符号，中的一个符号，是是V*中的一个符号。中的一个符号。称为规则的左部，称为规则的左部，称作规则的右部。称作规则的右部。2.若若1，2n，可简写为：，可简写为：1|2|n习惯表示习惯表示 小写字母：终结小写字母：终结符符 大写字母：非终结符大写字母：非终结符28例：例：文法文法G=（VN，VT，P，S）VN=标识符，字母，数字标识符，字母，数字VT=a,b,c,x,y,z,0,1,9P= a,z0,9S=29文法的几种等价写法文法的
20、几种等价写法GS：Aab|aAb|SaAbG：SaAbAabAaAbAGS：AabAaAbASaAb30直接推导直接推导“”是文法是文法G的产生式，若有的产生式，若有v,w满足：满足：v=,w=,其中其中V*,V*则称则称v直接直接推导推导到到w,记作记作vw。也称也称w直接直接归约归约到到v。例：例：G：S0S1，S010S100S11使用产生式使用产生式00S11000S111使用产生式使用产生式000S11100001111使用产生式使用产生式S0S1使用产生式使用产生式31推导序列推导序列1.若存在若存在vw0w1.wn=w,(n0)+则记为则记为v=w，称，称v推导出推导出w，或，或
21、w归约归约到到v。+*2.若有若有v=w，或，或v=w，则记为，则记为v=w32推导举例推导举例例：文法例：文法G：S0S1，S010S100S1100S11000S111000S11100001111S0S100S11000S11100001111+S=0000111133句型、句子的定义句型、句子的定义1.句型句型:有文法有文法G，若，若S=*x，则称，则称x是文法是文法G的的句型。句型。2.句子句子:有文法有文法G，若，若S=*x，且，且xVT*，则称，则称x是文法是文法G的句子。的句子。例：例：G：S0S1|01 S 0S1 00S11 000S111 00001111G的句型的句型:
22、S，0S1，00S11，000S111，00001111G的句子：的句子：00001111,0134推导句子推导句子a+a*a例：例：GE：EE+T|TTT*F|FF(E)|aEE+TT+TF+Ta+Ta+T*Fa+F*Fa+a*Fa+a*a句子：用符号句子：用符号a，+，*，(和和)构成的算术表达式构成的算术表达式35语言的定义语言的定义由文法由文法G生成的语言记为生成的语言记为L(G)，它是文，它是文法法G的一切句子的集合的一切句子的集合:例：例：G：S0S1，S01L(G)=0n1n|n1L(G)=x|S=*x，其中其中S为文法的开始符号，且为文法的开始符号，且xVT*36v语言是由句子
23、组成的集合，是由一组符语言是由句子组成的集合，是由一组符号所构成的集合。号所构成的集合。v换言之，字母表换言之，字母表 上上的一个语言是的一个语言是 上的上的一些符号串的集合一些符号串的集合 。v 字母表字母表 上上的每个语言是的每个语言是 *的一个子集。的一个子集。37 例如：字母表例如：字母表=a,b , *=,a,b,aa,ab,ba,bb,aaa,aab,集合集合ab,aabb,aaabbb,anbn,，或表示为或表示为w|w*且且w=anbn,n1，为字母表为字母表 上上的一个语言。的一个语言。集合集合a,aa,aaa,，或或表示为表示为w|w*且且w=an,n1，为字母表为字母表
24、上上的一个语言。的一个语言。 是一个语言。是一个语言。 即即 是一个语言。是一个语言。38语言的等价语言的等价若若L（G1）=L（G2），则称文法），则称文法G1和和G2是是等价的。等价的。G1A：A0RA01RA1G2S：S0S1S01等价等价39文法与语言的关系文法与语言的关系v给定一个文法，就能从结构上确定其语言，给定一个文法，就能从结构上确定其语言，且是唯一的。且是唯一的。GL(G)v给定一种语言，能确定其文法，但这种文给定一种语言，能确定其文法，但这种文法不是唯一的。法不是唯一的。LG1或或G2或或402.3语法树和语法树和文法的二义性文法的二义性41 上下文无关文法有足够的能力描述
25、程上下文无关文法有足够的能力描述程序设计语言的语法结构。序设计语言的语法结构。语法树语法树-句型推导句型推导的直观表示。的直观表示。42句型、推导句型、推导GE：EE+T|TTT*F|FF(E)|a最左推导最左推导EE+TT+TF+Ta+Ta+T*Fa+F*Fa+a*Fa+a*a最右推导最右推导EE+TE+T*FE+T*aE+F*aE+a*aT+a*aF+a*aa+a*a无规律无规律EE+TT+TT+T*FF+T*FF+F*Fa+F*Fa+F*aa+a*a43规范推导规范推导规范句型规范句型 最左（最右）推导：最左（最右）推导： 在推导的任何一步在推导的任何一步，其中，其中、是句型，都是对是句
26、型，都是对中的最左（右）中的最左（右）非终非终结符结符进行替换。进行替换。最右推导被称为规范推导。最右推导被称为规范推导。由规范推导所得的句型称为规范句型。由规范推导所得的句型称为规范句型。44语法树的构造过程语法树的构造过程以文法开始符号以文法开始符号S为根结点，随着推导为根结点，随着推导的逐步展开，对句型中某个非终结符的逐步展开，对句型中某个非终结符A用相用相应产生式应产生式A的右部替换时，为的右部替换时，为A的结点的结点生成其子结点依次为生成其子结点依次为的子树，直至推导结的子树，直至推导结束。束。45构造语法树构造语法树GE：EE+T|TTT*F|FF(E)|aEE+TT+TF+Ta+
27、Ta+T*Fa+F*Fa+a*Fa+a*a E EE + T E + T T E E + T T F46EE+TT+TF+Ta+Ta+T*Fa+F*Fa+a*Fa+a*aEE+TE+T*FE+T*aE+F*aE+a*aT+a*aF+a*aa+a*aEE+TT+TT+T*FF+T*FF+F*Fa+F*Fa+F*aa+a*a E E E + T E + T T T * F T T * F F F a F F a a a a a 看不出句型中的符号被看不出句型中的符号被替代的顺序替代的顺序47语法树中的几个概念语法树中的几个概念1.1.一棵语法树中没有后代的结点，称为端末结。一棵语法树中没有后代的结
28、点，称为端末结。2.2.一棵语法树生长的任何时刻，所有没有后代的端一棵语法树生长的任何时刻，所有没有后代的端末结自左至右排列起来就是一个句型。末结自左至右排列起来就是一个句型。3.3.在一棵语法树中，一个内部结点在一棵语法树中，一个内部结点A A连同它的所有连同它的所有后裔组成了一棵子树。后裔组成了一棵子树。只有单层分支的子树称为简单子树。（只有父子两只有单层分支的子树称为简单子树。（只有父子两代，没有第三代。）代，没有第三代。） 48语法树语法树-句型推导的直观表示句型推导的直观表示给定文法给定文法G=(VN,VT,P,S)，对于，对于G的任何的任何句型都能构造与之关联的语法树句型都能构造与
29、之关联的语法树(推导树推导树)。定理：定理：G为上下文无关文法，为上下文无关文法，对于对于，有，有S=*，当且仅当，当且仅当文法文法G有以有以为结果的一棵语法树为结果的一棵语法树(推导树推导树)49语法树要满足的条件语法树要满足的条件1.每个结点都有一个标记，此标记是每个结点都有一个标记，此标记是V的一个符的一个符号。号。2.根的标记是根的标记是S（开始符号）。（开始符号）。3.若一结点若一结点n至少有一个它自己除外的子孙，并至少有一个它自己除外的子孙，并且有标记且有标记A，则肯定，则肯定AVN。4.如果结点如果结点n有标记有标记A,其直接子结点从左到右的其直接子结点从左到右的次序是次序是n1
30、，n2，nk，其标记分别为，其标记分别为A1，A2，Ak，那么，那么AA1A2，Ak一定是一定是P中中的一个产生式。的一个产生式。50语法树的用处语法树的用处用于描述上下文无关文法用于描述上下文无关文法句型推导句型推导的直观方法。的直观方法。例例:GS:SaAS|aASbAASSAbaSaASSbAaaba句型句型aabbaa的语法树（推导树）的语法树（推导树）叶子结点：树中没有子孙的结点。叶子结点：树中没有子孙的结点。 从左到右读出推导树的叶子结点连接成的文法符号从左到右读出推导树的叶子结点连接成的文法符号串，为串，为GS的的句型。句型。51推导过程中施用产生式的顺序推导过程中施用产生式的顺
31、序SaASSbAaabaSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa例例:GS:SaAS|aASbAASSAba52 一棵语法树表示了一个句型的种种可能一棵语法树表示了一个句型的种种可能的的( (但未必是所有的但未必是所有的) )不同推导过程，包括最不同推导过程，包括最左左( (最右最右) )推导。推导。 但是，一个句型是否只对应唯一的一棵但是，一个句型是否只对应唯一的一棵语法树呢？一个句型是否只有唯一的一个最语法树呢？一个句型是否只有唯一的一个最左左( (最右最右) )推导呢推导呢? ?
32、53例：例：GE:EiEE+EEE*EE(E) E E E + E E + E E * E i E * E i i i i i E E E * E E * E i E + E i E + E i i i i句型句型 i*i+i 的两个不同的最左推导：的两个不同的最左推导：推导推导1：EE+EE*E+Ei*E+Ei*i+Ei*i+i推导推导2：EE*E i*E i*E+E i*i+Ei*i+i54文法的二义性文法的二义性 若一个文法存在某个句子对应两棵不同若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是的语法树，则称这个文法是二义二义的。的。 或者，若一个文法存在某个句子有两个或者，若
33、一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是不同的最左（右）推导，则称这个文法是二二义义的。的。 55文法的二义性与语言的二义性文法的二义性与语言的二义性文法的二义性和语言的二义性是两个不同的概念。文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法因为可能有两个不同的文法G和和G，其中，其中G是二义的，是二义的，但是却有但是却有L(G)=L(G)。这两个文法所产生的语言是相。这两个文法所产生的语言是相同的。同的。如果产生上下文无关语言的每一个文法都是二义如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。对于一个程序设计语的，则说此语言是先
34、天二义的。对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望对言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。它的每个语句的分析是唯一的。562.4文法的类型文法的类型57 通过对产生式施加不同的限制，将文法分为四种类型：通过对产生式施加不同的限制，将文法分为四种类型：0型文法型文法：对任一产生式：对任一产生式，都有，都有(VNVT)*且至少含有且至少含有一个非终结符，一个非终结符，(VNVT)*1型文法型文法：对任一产：对任一产生式生式，都有，都有|，仅仅仅仅S除除外。外。2型文法型文法：对任一产：对任一产生式生式，都有，都有VN，(VNVT)*3型文法
35、型文法(右线性文法右线性文法)：任一产生式：任一产生式的的形式都为形式都为AaB或或Aa，其中，其中AVN，BVN，aVT581型文法举例型文法举例例：例：1型（上下文有关）文法型（上下文有关）文法文法文法GS：SCDAbbACaCABaaBCbCBBbbBADaDCBDbDDAabD592型文法举例型文法举例例：例：2型（上下文无关）文法型（上下文无关）文法文法文法GS：SABABS|0BSA|1603 3型文法举例型文法举例GS：S0A|1B|0A0A|1B|0SB1B|1|061文法的类型文法的类型2 2型文法型文法1 1型文法型文法0 0型文法型文法四种文法之间的逐级四种文法之间的逐级
36、“包含包含”关系关系3 3型文法型文法62本章小结本章小结631.本章出现的概念较多，应该重点理解文本章出现的概念较多，应该重点理解文法、推导、句型、句子及语言的定义等法、推导、句型、句子及语言的定义等概念。语法分析有关内容在后面章节详概念。语法分析有关内容在后面章节详细讨论。细讨论。2.文法作为程序语言的语法的描述工具文法作为程序语言的语法的描述工具,它它用规则只能陈述的是用规则只能陈述的是:语言的所有句子以语言的所有句子以什么样的符号串出现。请记住文法和语什么样的符号串出现。请记住文法和语言的形式定义中的言的形式定义中的“形式形式”的含义的含义只只涉及语言的语法不涉及语言的语义。涉及语言的语法不涉及语言的语义。
