高级语言及其语法描述-有限自动机理论

1、1形式化的方法 用一整套带有严格规定的符号体系来描述问题的方法。 Noan Chomsky 1956 形式语言理论 形式语言理论是编译的理论基础 编译理论中用到的有关形式语言理论的最基本概念 字母表和符号串 文法和语言的形式定义 语法树和文法的二义性 文法和语言的分类22.3 2.3 程序语言的语法描述程序语言的语法描述1. 1. 相关概念相关概念 考虑一个考虑一个有穷有穷 字母表字母表 字符集字符集 其中每一个元素称为一个其中每一个元素称为一个符号符号 上的上的符号串符号串 (也叫也叫字字) 是指由是指由中的中的符号符号所构成所构成的一个有穷序列的一个有穷序列空字，不包含任何符号的序列空字，

2、不包含任何符号的序列 * 上所有符号串的全体，包括上所有符号串的全体，包括例：若例：若 =a, b，则，则 *=, a, b, aa, ab, ba, bb, aaa, 3 ：空集，不包含任何元素的集合：空集，不包含任何元素的集合 * 的子集的子集U和和V的积定义为：的积定义为：(连接连接)UV= |U& V 注意，一般注意，一般UV VU, 但但(UV)W=U(VW) V自身的自身的n次次(连接连接)积积 Vn = VVVn V0 = 令令V* = V0V1 V2 V3 ，则令，则令V*是是V的闭包的闭包 V+ = VV* ，称，称V+是是V的正则闭包的正则闭包如如、分别表示符号串分

3、别表示符号串01和和110，则则表示符号串表示符号串01110，表示符表示符号串号串11001。空串是连接运算的恒等元素，空串是连接运算的恒等元素，s = s=s 4 例例 令令LA, B, , Z, a, b, , z，表示，表示L是由大、小写是由大、小写字母组成的字母表，字母组成的字母表，D0, 1, , 9，表示，表示D是由是由10个个数字组成的字母表。数字组成的字母表。L和和D可以分别看成是有穷的语言可以分别看成是有穷的语言集。用集合的运算作用于集。用集合的运算作用于L和和D所得到的所得到的6种新语言：种新语言： （1）LD是字母和数字的集合；是字母和数字的集合； （2）LD是所有一个

4、字母后随一个数字的符号串的集合；是所有一个字母后随一个数字的符号串的集合； （3）L6是由是由6个字母构成的符号串的集合；个字母构成的符号串的集合； （4）L*是所有字母串（包括是所有字母串（包括 ）的集合；）的集合； （5）L(LD )*是以字母开头的所有字母数字串的集合；是以字母开头的所有字母数字串的集合； （6）D+是不含空串的数字串的集合。是不含空串的数字串的集合。 从这个例子可以看出，从基本集合开始，利用集合上的从这个例子可以看出，从基本集合开始，利用集合上的运算，可以定义新的语言。运算，可以定义新的语言。52. 2. 上下文无关文法上下文无关文法文法：描述语言的语法结构的文法：描述

5、语言的语法结构的形式规则形式规则 (语法语法规则规则)。必须是必须是准确、易理解的，准确、易理解的，且应且应有强描述力有强描述力 应应有利于句子分析和翻有利于句子分析和翻译译 最好能够最好能够自动产生语法分析程序。自动产生语法分析程序。通常用符号通常用符号G表示表示(Grammar)。上下文无关文法：所定义的语法范畴是完全独上下文无关文法：所定义的语法范畴是完全独立于这种范畴可能出现的环境的，即是和立于这种范畴可能出现的环境的，即是和其上下文无关的，不同于自然语言。其上下文无关的，不同于自然语言。6例：英文例句分析例：英文例句分析 He gave me a book.设“” 为“由组成”或“定

6、义为”，则有语法规则： He me a gave book7推导He gave me a book 的语法的合法性。 He He He gave He gave He gave me He gave me He gave me a He gave me a book语法正确8得到语法分析树: Hegavemeabook9 上下文无关文法的定义：上下文无关文法的定义： 一个上下文无关文法一个上下文无关文法G是一个四元式是一个四元式 G=(VT，VN，S，P)，其中，其中VT：终结符集合：终结符集合(非空非空)VN：非终结符集合：非终结符集合(非空非空)，且，且VT VN=S：文法的开始符号：文法

7、的开始符号，S VNP：产生式集合：产生式集合(有限有限)，每个产生式形式为每个产生式形式为P， P VN， (VT VN)*开始符开始符S至少必须在某个产生式的左部出现至少必须在某个产生式的左部出现一次。一次。10上下文无关文法上下文无关文法G包括四个组成部分：包括四个组成部分：一组一组终结符号终结符号：组成语言的基本符号，不可再：组成语言的基本符号，不可再分，如基本字、标识符、常数等。分，如基本字、标识符、常数等。一组一组非终结符号非终结符号：规则中用尖括号括起来的符：规则中用尖括号括起来的符号，表示一些语法成分，可以推导出其他号，表示一些语法成分，可以推导出其他的语法成分的语法成分,表示

8、一定符号串的集合表示一定符号串的集合11一个一个开始符号开始符号：特殊的非终结符，程序语言中，：特殊的非终结符，程序语言中，最终感兴趣的是最终感兴趣的是“程序程序”。一组一组产生式产生式：定义语法范畴的书写规则，：定义语法范畴的书写规则，A，A是一个非终结符，称左部符号，是一个非终结符，称左部符号， 称为称为产生式的右部，是由终结符号或产生式的右部，是由终结符号或|与非终结与非终结符号组成的一个符号串。产生式符号组成的一个符号串。产生式A称为称为关于关于A的一条产生规则。的一条产生规则。这种表示法称这种表示法称巴科斯范式巴科斯范式，简称，简称BNF范式范式。有的书用。有的书用“:=”代替代替“

9、”。12对于一个语法范畴，有时需几个产生式，特对于一个语法范畴，有时需几个产生式，特别需含递归的产生式。别需含递归的产生式。 例，定义只含+，*的算术表达式的文法 G=， 其中，P由下列产生式组成：E iE E+EE E*EE (E)13 几点规定：几点规定： P 1 P 2 可缩写为可缩写为 P 1| 2| n P n 其中，其中，“|”读成读成“或或”，称为，称为P的一个候选式。的一个候选式。 表示一个文法时，通常只给出开始符号和产生式，表示一个文法时，通常只给出开始符号和产生式，如上例，可表示为：如上例，可表示为：G(E)： E i | E+E | E*E | (E)合并：E i | E

10、AE | (E)A +|14 上下文无关文法如何定义语言上下文无关文法如何定义语言: :从文法的开始符从文法的开始符号出发号出发, ,反复连续使用产生式反复连续使用产生式, ,对左边的非终结对左边的非终结符进行替换和展开符进行替换和展开 直接推导直接推导：又称一步推导：又称一步推导( (用用 符号符号=表示表示),),就是就是用某条规则的右部去替换该规则的左部用某条规则的右部去替换该规则的左部 连续使用某个产生式右部去替换左部某个非终连续使用某个产生式右部去替换左部某个非终结符的过程结符的过程, ,得到的连续序列称为推导得到的连续序列称为推导, ,从从 到我是大学生是一个到我是大学生是一个推导

11、推导. .15约约 定定大写字母大写字母A, B, C, 或汉语词组代表非终结符号；或汉语词组代表非终结符号；小写字母小写字母a, b, c, 代表终结符；代表终结符； , , 等代表由终结符和非终结符组成的符号串。等代表由终结符和非终结符组成的符号串。16 定义：称定义：称 A 直接推出直接推出，即，即 A 仅当仅当A 是一个产生式，是一个产生式， 且且 ， (VT VN)* 。例：例：S-01, 0S-01, 0S S0=00=001010(0(直接推导直接推导 , , ) ) v v直接推导直接推导出出w,w,也称也称w w直接归约直接归约到到v,v, 记作记作 v v w w 。直接推

12、导直接推导就是用产生式的右部替换产生式的左部就是用产生式的右部替换产生式的左部的过程的过程直接归约直接归约就是用产生式的左部替换产生式的右部就是用产生式的左部替换产生式的右部的过程的过程17 如果如果 1 2 n，则我们称这个序列，则我们称这个序列是从是从 1到到 n的一个的一个推导推导。若存在一个从。若存在一个从 1到到 n的推导，则称的推导，则称 1可以可以推导推导出出 n 。 例：对文法例：对文法G(E)： E i | E+E | E*E | (E)E (E) (E+E) (i+E) (i+i)18 1n，从，从 1出发，经一步或若干步，可出发，经一步或若干步，可推导出推导出 n， 1+

13、 1n，从，从 1出发，经出发，经0步或若干步，可推步或若干步，可推导出导出 n ， 0 故故 1n，相当于，相当于 = 或或 +19三种推导的比较 直接推导（直接推导（）的长度为）的长度为1 直接推导序列（直接推导序列（ +）的长度）的长度n1 广义推导（广义推导（ *）的长度）的长度020 例例 : G = (E, i, +, *, (, ) , P , E) (1.1) P： E E + E | E * E | ( E ) | i 表达式表达式(i)和和(i+i)*i的推导：的推导：E (E) (i)E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i

14、 + i)*i E E 0步推导步推导 E (i + i)*i 6步推导步推导 E (i + i)*i 6步推导步推导 E (E) 直接推导直接推导*21句型、句子、语言的定义q句型和句子句型和句子设有文法设有文法GSGS，若符号串，若符号串是从开始符推导是从开始符推导出来的出来的, ,即即 S S =* * ，则称，则称是文法是文法G G的的句型句型。 若若仅由终结符组成仅由终结符组成, ,即即 S S =* * ，且，且VVT T* *，则称则称是文法是文法G G的的句子句子。例例 文法文法GSGS： S0S1S0S1， S01S01因为因为S S 0 0S S1 1 00 00S S11

15、 11 000 000S S111 111 0000111100001111所以所以S,S,0S1 ,00S11 ,000S111,000011110S1 ,00S11 ,000S111,00001111都是都是G G的句型的句型0000111100001111是是G G的句子的句子22q语言的定义语言的定义由文法由文法G G生成的语言记为生成的语言记为L(G),L(G),它是文法它是文法G G的一切句的一切句子的集合子的集合, ,即即 L(G)=x|S L(G)=x|S =+ +x x，且，且 xVxVT T* * 例例 文法文法G G： S0S1S0S1， S01S01S0S1 00S11

16、 03S13 0n-1S1n-1 0n1nL(G)=0L(G)=0n n1 1n n|n1|n1q文法和语言的关系：文法和语言的关系：文法文法G G生成的每个串都在生成的每个串都在L(G)L(G)中中L(G)L(G)中的每个串确实能被中的每个串确实能被G G生成生成23根据文法，可以通过推导得到该文法相应的语言；根据文法，可以通过推导得到该文法相应的语言；例：例：GE E：EE+T|TEE+T|TTTTTF|FF|F F(E)|aF(E)|aE E E+T T+T F+T a+T a+TF a+FF a+aF a+aa表示一切能用符号表示一切能用符号a，+，(，)构成的算术表达式构成的算术表达

17、式有了语言的要求，也可以为该语言设计文法有了语言的要求，也可以为该语言设计文法例：若语言由例：若语言由0、1符号串组成，串中符号串组成，串中0和和1的个数相同，的个数相同，构造其文法为：构造其文法为：A 0B|1CB 1|1A|0BBC 0|0A|1CC24 例：文法例：文法(A,B,S,a,b,c,P,S) S-Ac|aB A-ab B-bc写出写出(G)的全部元素的全部元素 L(G) = abc25例例1：考虑文法：考虑文法G1：SbA AaA|a定义了一个什么语言定义了一个什么语言分析：分析：SbAbaSbAbaAbaaSbAbaA.baa.所以：所以：L(G1)=ban | n1l得到

18、一个语言，是通过利用所有的侯选式推导出所得到一个语言，是通过利用所有的侯选式推导出所有句子，构成一个集合。有句子，构成一个集合。L(G1) = 以以b开头后跟一个或多个开头后跟一个或多个a的串的串26推导例题2e.g. 文法产生的语言文法产生的语言L(G2)=ambn|m,n 1L(G3) = anbn|n 1G2: S A B A a A | a B b B | bG3: S a S b | ab27e.g. 文法产生的语言文法文法G2对句子对句子aaabb的推导：的推导：S = A B A B S A B = a A B a A B A a A = a a A B a a A B A a

19、A = a a a B a a a B A a = a a a b B a a a b B B b B = a a a b b a a a b b B bA= aB = abA= Ab = ab S A B A a A | a B b B | b28e.g. 文法产生的语言文法文法G3对句子对句子aaaabbbb的推导：的推导：S = a S b a S b S a S b = a a S b b a a S b b S a S b = a a a S b b b a a a S b b b S a S b = a a a a b b b b a a a a b b b b S a bS a

20、S b | ab29例例4：文法：文法G3(A)：A c|AbG3(A)的语言的语言?L(G3)=c，cb，cbb，以以c开头，后继若干个开头，后继若干个b30 从一个句型到另一个句型的推导往往不唯从一个句型到另一个句型的推导往往不唯一。一。 E+Ei+Ei+i E+EE+ii+i 最左推导最左推导：任何一步：任何一步 都是对都是对 中的最中的最左非终结符进行替换。左非终结符进行替换。 最右推导最右推导：任何一步：任何一步 都是对都是对 中的最中的最右非终结符进行替换。右非终结符进行替换。31举例 例例: 文法文法GS: SAB AA0|1B B0|S1 请给出句子请给出句子101001的最左

21、和最右推导。的最左和最右推导。 最左推导：最左推导： S AB 1B B10B 10S1 10AB1 101BB1 1010B1 101001 最右推导：最右推导： S AB AS1AAB1 AA01 A1B01 A1001 1B1001 101001323. 3. 语法分析树与二义性语法分析树与二义性语法树语法树(推导树推导树Parse Tree)作用作用:直观地描述上下文无关文法的句型直观地描述上下文无关文法的句型推导过程。给定文法推导过程。给定文法G=(VN,VT,P,S)，对，对于于G的任何句型都能构造与之关联的语法的任何句型都能构造与之关联的语法树树33语法树的相关概念 结点：每个树

22、的结点对应于一个符号。结点的名字就结点：每个树的结点对应于一个符号。结点的名字就是该符号。是该符号。 边：两个结点之间的连线。边：两个结点之间的连线。 根结点：没有边进入的结点。根结点：没有边进入的结点。 分支：某个结点向下射出的边和其结点称为分支。分支：某个结点向下射出的边和其结点称为分支。（父子结点，兄弟结点）（父子结点，兄弟结点） 子树：语法树的某个结点和它向下射出的部分子树：语法树的某个结点和它向下射出的部分 末端结点：没有向下射出的边的结点成为末端结点。末端结点：没有向下射出的边的结点成为末端结点。在相对于句型的语法树中，末端结点可能是非终结符在相对于句型的语法树中，末端结点可能是非

23、终结符号。号。34语法树的概念 定义：语法树的结点由符号组成。根结点对定义：语法树的结点由符号组成。根结点对应于识别符号。只有非终结符号对应的结点应于识别符号。只有非终结符号对应的结点有子结点。并且，一个结点和它的子结点分有子结点。并且，一个结点和它的子结点分别对应于文法中的一个规则的左部和右部。别对应于文法中的一个规则的左部和右部。 引入语法树的意义：作为识别句子的辅助工引入语法树的意义：作为识别句子的辅助工具，语法树可以表示句子的结构。这一点对具，语法树可以表示句子的结构。这一点对于其后的语义分析有非常重要的意义。于其后的语义分析有非常重要的意义。35语法树的特征 给定文法给定文法G，G=

24、(VN,VT,P,S)，对于，对于G的任何句型都能构造与之关的任何句型都能构造与之关联的语法树（推导树）。这棵树具有下列特征：联的语法树（推导树）。这棵树具有下列特征：1、根结点的标记是、根结点的标记是开始符号开始符号S；2、每个结点的标记都是、每个结点的标记都是V中的一个符号；中的一个符号；3、若一棵子树的根结点为、若一棵子树的根结点为A，且其所有直接子孙的标记从左向，且其所有直接子孙的标记从左向右的排列次序为右的排列次序为A1A2AR，那么，那么 A A1A2.AR一定是一定是P中的一中的一条规则；条规则；4、若一标记为、若一标记为A的结点至少有一个除它以外的子孙，则的结点至少有一个除它以

25、外的子孙，则AVN5、若树的所有叶结点上的标记从左到右排列为字符串、若树的所有叶结点上的标记从左到右排列为字符串w，则，则w是是文法文法G的的句型句型；若；若w中仅含中仅含终结符号终结符号，则，则w为文法为文法G所产生的所产生的句句子子。36从推导构造语法树 方法：把识别符号做方法：把识别符号做为根结点，对每一个为根结点，对每一个直接推导画一个分支，直接推导画一个分支，分支的名字是直接推分支的名字是直接推导中被替换的非终结导中被替换的非终结符号，直到再无分支符号，直到再无分支可画结束。可画结束。 例如：推导S AB AcBd Accdd abccddSBBdbaAcdc37语法树的构造过程S

26、AB AcBd Accdd abccddSSBASBB dAcSBB dAcdcSBB dbaAcdc（1）（2）（3）（5）（4）38从语法树构造推导 方法：从分支建立直接推导，然后从语法方法：从分支建立直接推导，然后从语法树中剪去之这个分支，直到无分支可剪。树中剪去之这个分支，直到无分支可剪。 语法树表明了在推导过程中使用了哪条规语法树表明了在推导过程中使用了哪条规则和使用在哪个非终结符号上，但它并没则和使用在哪个非终结符号上，但它并没有表明使用规则的顺序。有表明使用规则的顺序。 一棵语法树可能对应不止一种推导。一棵语法树可能对应不止一种推导。一棵语法树是不同推导过程的共性抽象。一棵语法树

27、是不同推导过程的共性抽象。39从语法树构造推导的过程 例如文法GS： S AB A aAb|ab B cBd|cd 存在下面的推导可能： S AB AcBd (4) (3) Accdd abccdd (2) (1) S AB abB abcBd abccdd（从后往前看）SBBdbaAcdc(1)(2)(3)(4)40文法G：EE+E|EE|（E）|i句子 ii+i 对应的语法树两个不同的最左推导：两个不同的最左推导：推导推导1：E E+E EE+E iE+E ii+E ii+i推导推导2：E EE iE iE+E ii+E ii+iiEE+EEEiiEEEiEE+ii文法的二义性文法的二义性

28、(Ambiguity)41定义定义 如果一个文法存在如果一个文法存在某个句子某个句子对应两棵不对应两棵不同的语法树，则说这个文法是二义的。同的语法树，则说这个文法是二义的。 二义性文法存在某个句子二义性文法存在某个句子, ,它它有两个不有两个不同的最左（右）推导同的最左（右）推导42 例例 设设if语句语句S的文法的文法G=(E，A，S，if，then，else，S，P)，其中，其中P为：为： Sif E then S （1） S if E then S else S （2） SA （3） 证明该文法是二义的。证明该文法是二义的。 由文法有推导：由文法有推导：S if E then S if

29、E then if E then S else S 同样也有推导：同样也有推导：S if E then S else S if E then if E then S else S 对于同一个句型对于同一个句型if E then if E then S else S，由于应用规则的顺序不同，得到了两个不同的推由于应用规则的顺序不同，得到了两个不同的推导，所以该文法是二义文法。导，所以该文法是二义文法。43为什么要避免文法产生二义性？ 二义性的文法将给编译程序的执行带来问二义性的文法将给编译程序的执行带来问题。当编译程序对二义性文法生成的句子题。当编译程序对二义性文法生成的句子结构进行语法分析时，

30、就会产生两种甚至结构进行语法分析时，就会产生两种甚至更多种不同的理解。语法结构上的不确定更多种不同的理解。语法结构上的不确定性，必将导致语义处理上的不确定性。因性，必将导致语义处理上的不确定性。因此，希望描述语言的文法是无二义性的。此，希望描述语言的文法是无二义性的。44如何消除文法的二义性？(1) 方法一：不改变文法中原有的语法规则，仅加进一方法一：不改变文法中原有的语法规则，仅加进一些语法的非形式规定。些语法的非形式规定。 如如1：对于文法对于文法 GE: E i E E+E E E*E E (E) 规定运算符优先顺序和结合律，即规定运算符优先顺序和结合律，即*优先于优先于+，+、*服从左

31、结合。服从左结合。 如如2：Pascal中二义性的消除是通过约定，如在符中二义性的消除是通过约定，如在符合合if 语句中，语句中，else子句总是属于最近的尚无子句总是属于最近的尚无else子句子句的那个的那个if语句。语句。45如何消除文法的二义性？(2) 方法二：构造一个等价的无二义性的文法，方法二：构造一个等价的无二义性的文法，即把排除二义性的规则合并到原有文法中，即把排除二义性的规则合并到原有文法中，改写原有的文法。改写原有的文法。 如文法如文法 G(E)： E i|E+E|E*E|(E) 将运算符的优先顺序和结合规则加到原有文将运算符的优先顺序和结合规则加到原有文法中，则可构造无二义

32、性的文法法中，则可构造无二义性的文法 46二义文法：G(E)： E i|E+E|E*E|(E)表达式表达式 项项|表达式表达式+项项项项 因子因子 | 项项*因子因子因子因子 (表达式表达式) | i无二义文法：无二义文法： G(E)：E T | E+T T F | T*F F (E) | i47)EEEFFTTTTi+*(EFiiE T F (E) (E+T) (T+T) (T*F+T) (F*F+T) (i*F+T) (i*i+T) (i*i+F) (i*i+i)考虑句子考虑句子(i*i+i)48上下文无关文法限制：上下文无关文法限制：(化简后化简后) 不存在任何形如不存在任何形如PP的产

33、生式的产生式(多余多余) 每个非终结符每个非终结符P必须都有用处必须都有用处b. 必须存在终结符串必须存在终结符串 ，使，使P，即，即P不不存在永不终结的回路。存在永不终结的回路。*TVa. 从从S出发，存在出发，存在SP *+49 文法G（S）: S Bd A Ad|d B Cd |Ae C Ce D e 文法G（S）: S Bd A Ad|d B Ae504.4.形式语言概述形式语言概述乔姆斯基将其分为四类，乔姆斯基将其分为四类，0, 1, 2, 3，与上下文无关，与上下文无关文法一样，它们都由四部分组成，差别在于对产生式施文法一样，它们都由四部分组成，差别在于对产生式施加不同的限制。加不

34、同的限制。v0型文法（型文法（PSG） 0型语言或短语结构语言型语言或短语结构语言v1型文法（型文法（CSG） 1型语言或上下文有关语言型语言或上下文有关语言v2型文法（型文法（CFG） 2型语言或上下文无关语言型语言或上下文无关语言v3型文法（型文法（RG）3型语言或正则（正规）语言型语言或正则（正规）语言510型文法型文法(短语文法，图灵机短语文法，图灵机) ：对文法对文法G，如果它的，如果它的每个产生式每个产生式 是这样的一种结构：是这样的一种结构：(VNVT)* 且至少含有一个非终结符且至少含有一个非终结符(VN VT)*0型文法相应的语言为型文法相应的语言为0型语言，或称递归可枚举型

35、语言，或称递归可枚举集，它的识别系统是图灵（集，它的识别系统是图灵（Turing）机。）机。如文法如文法G，其中，其中VN=A,B,S VT=0,1 P= S0AB 1B0 BSA|01 A1SB1 A0S0B 52q1型文法型文法(上下文有关上下文有关)：它是它是0型文法的特例，对型文法的特例，对P中的任一产生式中的任一产生式，都，都|， 仅仅仅仅 S除除外外,但但S不得出现在任何产生式的右部。不得出现在任何产生式的右部。q1型文法相应的语言称为型文法相应的语言称为1型语言或上下文有关型语言或上下文有关语言，它的识别系统是线性有界自动机。语言，它的识别系统是线性有界自动机。q例例 文法文法G

36、SGS： SaSBE SaSBE SaBESaBEEBBEEBBEaBab aBab bBbb bBbb bEbe bEbe eEeeeEee53 文法文法G的每一个产生式均为下列形式：的每一个产生式均为下列形式：A其中其中，V*，A Vn, V+ 它表示当它表示当A的上文为的上文为 且下文为且下文为时可把时可把A替替换成换成 ，因此称，因此称1型文法为上下文有关文法。型文法为上下文有关文法。 满足前页定义的长度限制，但它更明确地表满足前页定义的长度限制，但它更明确地表达了上下文有关的特性，即达了上下文有关的特性，即A必须在的上下必须在的上下文环境中才能被替换。文环境中才能被替换。54q2型文

37、法（上下文无关文法）型文法（上下文无关文法） ：它是：它是1型文法的特型文法的特例，对任一产生式例，对任一产生式，都有，都有VN N ， (VN NVT T)*q2型文法相应的语言称为型文法相应的语言称为2型语言或上下文无关语言。型语言或上下文无关语言。它的识别系统是下推自动机。它的识别系统是下推自动机。q例例 文法文法GS： SAB ABS|0 BSA|12型文法产生式的一般形式是型文法产生式的一般形式是: A ，它表示不管，它表示不管A的上下文如何都可把的上下文如何都可把A替换成替换成 ，因此被称为上，因此被称为上下文无关文法。下文无关文法。通常程序设计语言的文法，可用通常程序设计语言的文法，可用2型文法来描述，型文法来描述，因此我们重点研究因此我们重点研究2型文法。如型文法。如C，Pascal 55q3型文法型文法(正规文法正规文法)：它是它是2型文法的特例，型文法的特例，任一产生任一产生式式的形式都为的形式都为 AaB或或Aa，其中，其中A ，BVN N ，aVT Tq这种形式的这种形式的3型文法也叫型文法也叫右线性文法右线性文法。3型文法还有一种型文法还有一种形式，限定形式，限定P