编译原理课件CHAPTER2(GrammarandLanguage)

Chapter2

GrammarandLanguage一．教学目的掌握文法、语法树、推导、归约、句子、语言、规范推导与归约、短语、简单短语、句柄、二义性定义，了解文法的分析过程、文法实用限制、语言分类等。二．教学重点和难点 重点掌握：1．串和语言的概念。 2．文法和语言的定义。 3．文法和语言的分类。 4．分析树与句型。 难点：1．文法和语言的分类。2．分析树与句型。11/18/20221Chapter2

GrammarandLanguage一Chapter2

GrammarandLanguage

三．教学内容串和语言（StringsandLanguages

）文法和语言的定义（DefinitionsofGrammarandLanguage）文法和语言的分类（Classification

ofGrammarandLanguage）分析树与句型（ParseTreeandSententialform）11/18/20222Chapter2

GrammarandLanguage2.1串和语言

字母表（alphabet）：字母表是符号（symbols）的非空有穷集合，用∑表示符号：可以相互区别的记号（元素）不同的语言有不同的字母表汉语——汉字英语——26个英文字母11/18/202232.1串和语言字母表（alphabet）：不同的语言有2.1串和语言符号串（String）：符号串是由字母表中的符号所组成的有穷序列在语言理论中，符号串又称为:句子（sentence）、字（word）例如：Σ={a,b} a,b,aa,ab,aabba…都是Σ上的符号串ε是任何Σ上的符号串11/18/202242.1串和语言符号串（String）：在语言理论中，符号2.1串和语言符号串的长度符号串中包含符号的个数符号串s的长度记为|s|例，对于字母表{a,b,c}，aab是其上的一个符号串，|aab|=3注意：空符号串ε，|ε|=011/18/202252.1串和语言符号串的长度例，对于字母表{a,b,c}，2.1串和语言符号串的前缀（prefix）、后缀（suffix）、子串（substring）后缀：删去符号串s头部的零个或多于零个符号得到的符号串例如：nana是符号串banana的一个后缀前缀：移走符号串s尾部的零个或多于零个符号得到的符号串例如：b是符号串banana的一个前缀11/18/202262.1串和语言符号串的前缀（prefix）、后缀（suf2.1串和语言符号串的真（proper）前缀、真后缀和真子串——非空子串：从s中删去一个前缀和一个后缀得到的符号串例如：ana是符号串banana的一个子串*对于每个符号串s，s和ε两者都是符号串s的前缀，后缀和子串11/18/202272.1串和语言符号串的真（proper）前缀、真后缀和真2.1串和语言

语言（Language）：某个字母表上的符号串的集合例:汉语——所有符合汉语语法的句子构成的集合PASCAL语言——所有合法的PASCAL程序构成的集合注意：空集{}、和{ε}的不同11/18/202282.1串和语言语言（Language）：例:注意：空集2.1串和语言符号串的运算：连接（concatenation）：符号串x、y的连接，是把y的符号写在x的符号之后得到的符号串xy如x=ab,y=cd则xy=abcd注：εα=αε=α方幂（exponentiation）：符号串自身连接n次得到的符号串αn定义为αα…ααn个αα1=α,α2=αα，注：α0=ε11/18/202292.1串和语言符号串的运算：如x=ab,y=2.1串和语言语言的运算（operationsonlanguages）：语言是符号串的集合，集合的运算有并、交、差等并运算—等同于集合的并运算11/18/2022102.1串和语言语言的运算（operationsonl2.1串和语言连接（乘积）两个符号串集合A和B的乘积定义为：AB={xy|xA且yB}例如：集合A={ab,cde}B={0,1} 则AB={ab1,ab0,cde0,cde1}{ε}L=L{ε}=LLL…L=LnL0={ε}11/18/2022112.1串和语言连接（乘积）例如：集合A={ab,cde}2.1串和语言*闭包（Kleeneclosure）L*=L0∪L1∪L2∪L3∪…

+闭包（Positiveclosure）L+=L1∪L2∪L3∪…L*=L+

∪ε11/18/2022122.1串和语言*闭包（Kleeneclosure）+2.1串和语言注:后面通常是考虑字母表∑的*闭包和+闭包例：Σ={a,b} Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}Σ+={a,b,aa,ab,ba,bb,aaa,aab,…}11/18/2022132.1串和语言注:后面通常是考虑字母表∑的*闭包和2.1串和语言综合性的例子：P93example3.2L={A,B,C,…,Z,a,b,c,…,z}D={0,1,…,9}把L和D两个字母表看作长度为1的符号串集合，即语言1.L∪D2.LD3.L44.L*

5.L(L∪D)*6.D+11/18/2022142.1串和语言综合性的例子：P93example32.2文法和语言的定义如何来描述一种语言？如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示如果语言是无穷的，找出语言的有穷表示。11/18/2022152.2文法和语言的定义如何来描述一种语言？如果语言是有穷2.2文法和语言的定义语言的有穷表示有两个途经：生成方式（文法）：语言中的每个句子可以用严格定义的规则来构造。识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，（要么永远继续下去。）文法即是以生成方式描述语言的：语言中的每个句子可以用严格定义的规则来构造.11/18/2022162.2文法和语言的定义语言的有穷表示有两个途经：识别方式2.2文法和语言的定义文法G定义为四元组（VT，VN，S，P）：VT：终结符（terminals）集，其中的元素一般用小写字母或数字表示（a,b,c…0,1..），代表语言中不可再分的基本符号，如汉语中的汉字、PASCAL语言中的基本字VN：非终结符（nonterminals）集，其中的元素一般用大写字母表示（A,B,C…），或者用尖括号括起，代表语法单位，如汉语中的语句、段落，PASCAL语言中的语句、表达式、子程序等11/18/2022172.2文法和语言的定义文法G定义为四元组（VT，VN2.2文法和语言的定义S是一个特殊的非终结符号，称为开始符号（startsymbol）S至少要在一条产生式中作为左部出现P是一个产生式（production）的集合产生式（重写规则、生成式），是形如α→β或α∷=β的（α，β）有序对，且α∈V+，β∈V*其中V=（VT∪VN）α称为产生式的左部，不能为空εβ称为产生式的右部，可以为空ε（如：A→ε）11/18/2022182.2文法和语言的定义S是一个特殊的非终结符号，称为开2.2文法和语言的定义例1：文法G=（VT，VN，S，P） VN={S}VT={0,1} P={S→0S1,S→01}可以只写出产生式，通过产生式可以得到文法的其它部分左部相同的产生式可以写在一起，如: S→0S1|0111/18/2022192.2文法和语言的定义例1：文法G=（VT，VN，2.2文法和语言的定义例2：文法G=（VT，VN，S，P） VN={<标识符>，<字母>，<数字>} VT={a,b,c,…x,y,z,0,1,…,9} P={ <标识符>→<字母> <标识符>→<标识符><字母> <标识符>→<标识符><数字> <字母>→a,…,<字母>→z <数字>→0,…,<数字>→9} S=<标识符>11/18/2022202.2文法和语言的定义例2：文法G=（VT，VN，2.2文法和语言的定义推导（derivation）与归约（reduction）：直接推导与直接归约如果A→γ是G的一条产生式，则称用αγβ代替αAβ为一步直接推导，记为αAβ=>αγβ；称用αAβ代替αγβ为一步直接归约，记为αγβ<=αAβ推导是用产生式的右部代替左部，归约是用产生式的左部代替右部，归约是推导的逆过程11/18/2022212.2文法和语言的定义推导（derivation）与归约2.2文法和语言的定义推导的长度直接推导的次数αβ，长度大于等于1的推导αβ，长度大于等于0的推导推导的例子： S=>0S1=>00S11=>000111，长度为3 记为：S000111SS11/18/2022222.2文法和语言的定义推导的长度推导的例子：11/11/2.2文法和语言的定义最左推导与最右推导α=>β是一步推导，α，β∈（VT∪VN）*最左推导(=lm>)—对α中的最左非终结符进行展开最右推导(=rm>)—对α中的最右非终结符进行展开11/18/2022232.2文法和语言的定义最左推导与最右推导11/11/202.2文法和语言的定义例子：表达式文法E→E+T E→T T→T*F T→F F→（E） F→a最左推导：E=lm>T=lm>T*F=lm>F*F=lm>a*F=lm>a*a**最右推导又称为规范推导最右推导：E=rm>T=rm>T*F=rm>T*a=rm>F*a=rm>a*a11/18/2022242.2文法和语言的定义例子：表达式文法E→E2.2文法和语言的定义最右归约与最左归约最左推导的逆过程是最右归约，即对最右边的可归约串进行归约

a*a<=a*F<=F*F<=T*F<=T<=E最右推导的逆过程是最左归约，即对最左边的可归约串进行归约

a*a<=F*a<=T*a<=T*F<=T<=E**最左归约称为规范归约11/18/2022252.2文法和语言的定义最右归约与最左归约最右推导的逆过程2.2文法和语言的定义句型（sententialform）与句子（sentence）：句型：从文法的开始符号出发进行零步或多于零步的推导得到的文法符号串 Sα句型可以既包含终结符号又包含非终结符号，只包含终结符号的句型称为句子句子是一种特殊的句型11/18/2022262.2文法和语言的定义句型（sententialfor2.2文法和语言的定义例：在推导 E=>T=>T*F=>F*F=>a*F=>a*a中，句型有：E、T、T*F、F*F、a*F、a*a句子是：a*a11/18/2022272.2文法和语言的定义例：在推导句型有：E、T、T*2.2文法和语言的定义语言的形式定义：文法G推导出的所有句子组成的集合，称为语言，记为L（G）L（G）={α|Sα，α∈VT*}11/18/2022282.2文法和语言的定义语言的形式定义：文法G推导出的2.2文法和语言的定义例子：G1：S→A A→0A1 A→01是由一个或多个0开头，后跟同样数目的1的符号串构成的集合（语言），可记为：L(G)={0n1n|n≥1}11/18/2022292.2文法和语言的定义例子：是由一个或多个2.2文法和语言的定义G2： E→id E→E+E E→E*E E→（E）产生的是表达式的集合11/18/2022302.2文法和语言的定义G2： E→id产生的是2.2文法和语言的定义G3：E→E+T E→T T→T*F T→F F→（E） F→id产生的也是表达式的集合11/18/2022312.2文法和语言的定义G3：E→E+T产生的也2.2文法和语言的定义一个文法对应一个语言，但一个语言可能有若干个文法产生它，这若干个文法是等价的，称为

等价（equivalent）文法例G2与G311/18/2022322.2文法和语言的定义一个文法对应一个语言，但一个语言可2.3文法和语言的分类乔姆斯基（Chomsky）在1956年提出形式语言理论，他将形式文法分为四类(0,1,2,3)，对应四类形式语言(0,1,2,3)分类的方法是对文法的产生式进行不同的限制11/18/2022332.3文法和语言的分类乔姆斯基（Chomsky）在1952.3文法和语言的分类0型文法—|α|≠0，即α≠ε（α→β）1型（上下文有关）文法—|α|≤|β|（α→β）2型（上下文无关）文法—A∈VN，β∈（VT∪VN）*（A→β）3型（正规）文法A→a或A→aB（右线性）A→a或A→Ba（左线性）11/18/2022342.3文法和语言的分类0型文法—|α|≠0，即2.3文法和语言的分类例：1型（上下文有关）文法文法G： S→CD Ab→bA C→aCA Ba→aB C→bCB Bb→bB AD→aD C→ε BD→bD D→ε Aa→bD

L(G)={ww|w∈{a,b}*}11/18/2022352.3文法和语言的分类例：1型（上下文有关）文法11/12.3文法和语言的分类例：2型（上下文无关）文法文法G1： S→aB|bA A→a|aS|bAA B→b|bS|aBB

文法G2： S→0A|1B|0 A→0A|1B|0S B→1B|1|0

11/18/2022362.3文法和语言的分类11/11/2022362.3文法和语言的分类例：3型（正规）文法

文法G： S→0A|1B|0 A→0A|1B|0S B→1B|1|011/18/2022372.3文法和语言的分类例：3型（正规）文法11/11/22.3文法和语言的分类0型文法产生的语言称为0型语言1型文法或上下文有关文法（CSG）产生的语言称为1型语言或上下文有关语言（CSL）2型文法或上下文无关文法（CFL）产生的语言称为2型语言或上下文无关语言（CFL）3型文法或正则（正规）文法（RG）产生的语言称为3型语言正则（正规）语言（RL）11/18/2022382.3文法和语言的分类0型文法产生的语言称为0型语言1型2.3文法和语言的分类四种文法（语言）之间的逐级“包含”关系2型文法（语言）1型文法（语言）0型文法（语言）3型文法（语言）11/18/2022392.3文法和语言的分类四种文法（语言）之间的逐级“包含”2.3文法和语言的分类识别各类语言的数学模型（自动机）图灵机（0型语言）有界图灵机、线性有界自动机（1型语言）下推自动机（2型语言）有限自动机（3型语言）11/18/2022402.3文法和语言的分类识别各类语言的数学模型（自动机）图2.3文法和语言的分类上下文无关文法能够描述现今程序设计语言的大部分语法结构算术表达式赋值语句条件语句等11/18/2022412.3文法和语言的分类上下文无关文法能够描述现今程序设计2.3文法和语言的分类表达式文法：G=({+,*,i,(,)},{E},E,P) P: E→id E→E+E E→E*E E→(E) E表示算术表达式，id表示程序的“变量”，该文法定义了由变量，+，*，(和)组成的算术表达式的语法结构，即：变量是算术表达式；若E1和E2是算术表达式，则E1+E2，E1*E2和(E1)也是算术表达式。11/18/2022422.3文法和语言的分类表达式文法：G=({+,*,2.3文法和语言的分类描述一种简单赋值语句的产生式：〈赋值语句〉→i∶=E描述条件语句的产生式：〈条件语句〉→if〈条件〉then〈语句〉｜if〈条件〉then〈语句〉else〈语句〉11/18/2022432.3文法和语言的分类描述一种简单赋值语句的产生式：描述2.4分析树与句型分析树是描述上下文无关文法句型推导的一种直观方法，也称为推导树11/18/2022442.4分析树与句型分析树是描述上下文无关文法句型推导的一2.4分析树与句型为句型推导构造分析树例子：E=>TE→E+TE→T T→T*F T→F F→（E） F→a=>T*F=>F*F=>a*FTT*FFaaE=>a*a11/18/2022452.4分析树与句型为句型推导构造分析树E=>TE→2.4分析树与句型分析树的特性：根标识为开始符号内部结点标识为非终结符号每一内部结点及其子结点对应一条产生式，该结点是产生式的左部，子结点从左至右排列构成产生式的右部叶结点从左至右排列构成句型TT*FFaaE11/18/2022462.4分析树与句型分析树的特性：根标识为开始符号内部结点2.4分析树与句型分析树与句型推导的关系一次推导（不是一个句型）对应一棵分析树一棵分析树可能对应若干个推导例如下面的推导对应的也是上面那棵分析树E=>T=>T*F=>T*a=>F*a=>a*aTT*FFaaE11/18/2022472.4分析树与句型分析树与句型推导的关系一次推导（不是一2.4分析树与句型说明分析树没有严格反映推导的顺序但是一棵分析树对应一个最左推导，也只能对应一个最右推导TT*FFaaE11/18/2022482.4分析树与句型说明分析树没有严格反映推导的顺序但是一2.4分析树与句型句型的短语、直接短语和句柄（handle）如果SαAδ和Aβ，则称β是关于A的，句型αβδ的一个短语（子树的叶子）SαAδβ11/18/2022492.4分析树与句型句型的短语、直接短语和句柄（handl2.4分析树与句型例：句型F*a的短语TT*FFaEF*a、F、a11/18/2022502.4分析树与句型例：句型F*a的短语TT*FFaE2.4分析树与句型如果SαAδ和A=>β，则称β是关于A的，句型αβδ的一个直接短语（只有父子两代的子树的叶子）SαAδβ11/18/2022512.4分析树与句型如果SαAδ和A=>β，2.4分析树与句型例：句型F*a的直接短语TT*FFaEF、a11/18/2022522.4分析树与句型例：句型F*a的直接短语TT*FF2.4分析树与句型最左直接短语称为句柄最左性体现在分析树和句型中SαAδβ11/18/2022532.4分析树与句型最左直接短语称为句柄SαAδβ11/12.4分析树与句型例：句型F*a的句柄TT*FFaEF11/18/2022542.4分析树与句型例：句型F*a的句柄TT*FFaE2.4分析树与句型句型的素短语、最左素短语1、β是关于A的，句型αβδ的一个短语2、β至少含有一个终结符3、β除自身外不含更小的带终结符的短语称β是关于A的，句型αβδ的一个素短语句型最左边的素短语称为最左素短语问题:素短语是否总是在直接短语中?(否.反例:T+T+F)11/18/2022552.4分析树与句型句型的素短语、最左素短语1、β是关于A2.4分析树与句型例：EE+TE+TFTT*Fa句型：T+T*F+a短语：T+T*F+a、T+T*F、 T*F、T（左边）、a直接短语：T、T*F、a句柄：T素短语：T*F、a最左素短语：T*F11/18/2022562.4分析树与句型例：EE+TE+TFTT*Fa句型：T2.4分析树与句型句子、文法和语言的二义性（Ambiguity）如果一个文法的句子有两棵或两棵以上的分析树，称此句子是二义的最左（右）推导与分析树一一对应，句子二义说明它有两个或以上最左（右）推导11/18/2022572.4分析树与句型句子、文法和语言的二义性（Ambigu2.4分析树与句型E=>E+E=>id+E=>id+E*E=>id+id*E=>id+id*idE=>E*E=>E+E*E=>id+E*E=>id+id*E=>id+id*idEE+Eid*EEididEE*Eid+EEidid例：E→id E→E+E E→E*E E→（E）11/18/2022582.4分析树与句型E=>E+E=>id+E=>id+2.4分析树与句型如果一个文法有一个句子是二义的，此文法称为二义文法E→id E→E+E E→E*E E→（E）11/18/2022592.4分析树与句型如果一个文法有一个句子是二义的，此文法2.4分析树与句型如果一个语言的所有文法都是二义的，称此语言是二义的希望文法是无二义的，因为希望对于每一个句子进行唯一确定的分析11/18/2022602.4分析树与句型如果一个语言的所有文法都是二义的，称此TheEnd!11/18/202261TheEnd!11/11/202261Chapter2

GrammarandLanguage一．教学目的掌握文法、语法树、推导、归约、句子、语言、规范推导与归约、短语、简单短语、句柄、二义性定义，了解文法的分析过程、文法实用限制、语言分类等。二．教学重点和难点 重点掌握：1．串和语言的概念。 2．文法和语言的定义。 3．文法和语言的分类。 4．分析树与句型。 难点：1．文法和语言的分类。2．分析树与句型。11/18/202262Chapter2

GrammarandLanguage一Chapter2

GrammarandLanguage

三．教学内容串和语言（StringsandLanguages

）文法和语言的定义（DefinitionsofGrammarandLanguage）文法和语言的分类（Classification

ofGrammarandLanguage）分析树与句型（ParseTreeandSententialform）11/18/202263Chapter2

GrammarandLanguage2.1串和语言

字母表（alphabet）：字母表是符号（symbols）的非空有穷集合，用∑表示符号：可以相互区别的记号（元素）不同的语言有不同的字母表汉语——汉字英语——26个英文字母11/18/2022642.1串和语言字母表（alphabet）：不同的语言有2.1串和语言符号串（String）：符号串是由字母表中的符号所组成的有穷序列在语言理论中，符号串又称为:句子（sentence）、字（word）例如：Σ={a,b} a,b,aa,ab,aabba…都是Σ上的符号串ε是任何Σ上的符号串11/18/2022652.1串和语言符号串（String）：在语言理论中，符号2.1串和语言符号串的长度符号串中包含符号的个数符号串s的长度记为|s|例，对于字母表{a,b,c}，aab是其上的一个符号串，|aab|=3注意：空符号串ε，|ε|=011/18/2022662.1串和语言符号串的长度例，对于字母表{a,b,c}，2.1串和语言符号串的前缀（prefix）、后缀（suffix）、子串（substring）后缀：删去符号串s头部的零个或多于零个符号得到的符号串例如：nana是符号串banana的一个后缀前缀：移走符号串s尾部的零个或多于零个符号得到的符号串例如：b是符号串banana的一个前缀11/18/2022672.1串和语言符号串的前缀（prefix）、后缀（suf2.1串和语言符号串的真（proper）前缀、真后缀和真子串——非空子串：从s中删去一个前缀和一个后缀得到的符号串例如：ana是符号串banana的一个子串*对于每个符号串s，s和ε两者都是符号串s的前缀，后缀和子串11/18/2022682.1串和语言符号串的真（proper）前缀、真后缀和真2.1串和语言

语言（Language）：某个字母表上的符号串的集合例:汉语——所有符合汉语语法的句子构成的集合PASCAL语言——所有合法的PASCAL程序构成的集合注意：空集{}、和{ε}的不同11/18/2022692.1串和语言语言（Language）：例:注意：空集2.1串和语言符号串的运算：连接（concatenation）：符号串x、y的连接，是把y的符号写在x的符号之后得到的符号串xy如x=ab,y=cd则xy=abcd注：εα=αε=α方幂（exponentiation）：符号串自身连接n次得到的符号串αn定义为αα…ααn个αα1=α,α2=αα，注：α0=ε11/18/2022702.1串和语言符号串的运算：如x=ab,y=2.1串和语言语言的运算（operationsonlanguages）：语言是符号串的集合，集合的运算有并、交、差等并运算—等同于集合的并运算11/18/2022712.1串和语言语言的运算（operationsonl2.1串和语言连接（乘积）两个符号串集合A和B的乘积定义为：AB={xy|xA且yB}例如：集合A={ab,cde}B={0,1} 则AB={ab1,ab0,cde0,cde1}{ε}L=L{ε}=LLL…L=LnL0={ε}11/18/2022722.1串和语言连接（乘积）例如：集合A={ab,cde}2.1串和语言*闭包（Kleeneclosure）L*=L0∪L1∪L2∪L3∪…

+闭包（Positiveclosure）L+=L1∪L2∪L3∪…L*=L+

∪ε11/18/2022732.1串和语言*闭包（Kleeneclosure）+2.1串和语言注:后面通常是考虑字母表∑的*闭包和+闭包例：Σ={a,b} Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}Σ+={a,b,aa,ab,ba,bb,aaa,aab,…}11/18/2022742.1串和语言注:后面通常是考虑字母表∑的*闭包和2.1串和语言综合性的例子：P93example3.2L={A,B,C,…,Z,a,b,c,…,z}D={0,1,…,9}把L和D两个字母表看作长度为1的符号串集合，即语言1.L∪D2.LD3.L44.L*

5.L(L∪D)*6.D+11/18/2022752.1串和语言综合性的例子：P93example32.2文法和语言的定义如何来描述一种语言？如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示如果语言是无穷的，找出语言的有穷表示。11/18/2022762.2文法和语言的定义如何来描述一种语言？如果语言是有穷2.2文法和语言的定义语言的有穷表示有两个途经：生成方式（文法）：语言中的每个句子可以用严格定义的规则来构造。识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，（要么永远继续下去。）文法即是以生成方式描述语言的：语言中的每个句子可以用严格定义的规则来构造.11/18/2022772.2文法和语言的定义语言的有穷表示有两个途经：识别方式2.2文法和语言的定义文法G定义为四元组（VT，VN，S，P）：VT：终结符（terminals）集，其中的元素一般用小写字母或数字表示（a,b,c…0,1..），代表语言中不可再分的基本符号，如汉语中的汉字、PASCAL语言中的基本字VN：非终结符（nonterminals）集，其中的元素一般用大写字母表示（A,B,C…），或者用尖括号括起，代表语法单位，如汉语中的语句、段落，PASCAL语言中的语句、表达式、子程序等11/18/2022782.2文法和语言的定义文法G定义为四元组（VT，VN2.2文法和语言的定义S是一个特殊的非终结符号，称为开始符号（startsymbol）S至少要在一条产生式中作为左部出现P是一个产生式（production）的集合产生式（重写规则、生成式），是形如α→β或α∷=β的（α，β）有序对，且α∈V+，β∈V*其中V=（VT∪VN）α称为产生式的左部，不能为空εβ称为产生式的右部，可以为空ε（如：A→ε）11/18/2022792.2文法和语言的定义S是一个特殊的非终结符号，称为开2.2文法和语言的定义例1：文法G=（VT，VN，S，P） VN={S}VT={0,1} P={S→0S1,S→01}可以只写出产生式，通过产生式可以得到文法的其它部分左部相同的产生式可以写在一起，如: S→0S1|0111/18/2022802.2文法和语言的定义例1：文法G=（VT，VN，2.2文法和语言的定义例2：文法G=（VT，VN，S，P） VN={<标识符>，<字母>，<数字>} VT={a,b,c,…x,y,z,0,1,…,9} P={ <标识符>→<字母> <标识符>→<标识符><字母> <标识符>→<标识符><数字> <字母>→a,…,<字母>→z <数字>→0,…,<数字>→9} S=<标识符>11/18/2022812.2文法和语言的定义例2：文法G=（VT，VN，2.2文法和语言的定义推导（derivation）与归约（reduction）：直接推导与直接归约如果A→γ是G的一条产生式，则称用αγβ代替αAβ为一步直接推导，记为αAβ=>αγβ；称用αAβ代替αγβ为一步直接归约，记为αγβ<=αAβ推导是用产生式的右部代替左部，归约是用产生式的左部代替右部，归约是推导的逆过程11/18/2022822.2文法和语言的定义推导（derivation）与归约2.2文法和语言的定义推导的长度直接推导的次数αβ，长度大于等于1的推导αβ，长度大于等于0的推导推导的例子： S=>0S1=>00S11=>000111，长度为3 记为：S000111SS11/18/2022832.2文法和语言的定义推导的长度推导的例子：11/11/2.2文法和语言的定义最左推导与最右推导α=>β是一步推导，α，β∈（VT∪VN）*最左推导(=lm>)—对α中的最左非终结符进行展开最右推导(=rm>)—对α中的最右非终结符进行展开11/18/2022842.2文法和语言的定义最左推导与最右推导11/11/202.2文法和语言的定义例子：表达式文法E→E+T E→T T→T*F T→F F→（E） F→a最左推导：E=lm>T=lm>T*F=lm>F*F=lm>a*F=lm>a*a**最右推导又称为规范推导最右推导：E=rm>T=rm>T*F=rm>T*a=rm>F*a=rm>a*a11/18/2022852.2文法和语言的定义例子：表达式文法E→E2.2文法和语言的定义最右归约与最左归约最左推导的逆过程是最右归约，即对最右边的可归约串进行归约

a*a<=a*F<=F*F<=T*F<=T<=E最右推导的逆过程是最左归约，即对最左边的可归约串进行归约

a*a<=F*a<=T*a<=T*F<=T<=E**最左归约称为规范归约11/18/2022862.2文法和语言的定义最右归约与最左归约最右推导的逆过程2.2文法和语言的定义句型（sententialform）与句子（sentence）：句型：从文法的开始符号出发进行零步或多于零步的推导得到的文法符号串 Sα句型可以既包含终结符号又包含非终结符号，只包含终结符号的句型称为句子句子是一种特殊的句型11/18/2022872.2文法和语言的定义句型（sententialfor2.2文法和语言的定义例：在推导 E=>T=>T*F=>F*F=>a*F=>a*a中，句型有：E、T、T*F、F*F、a*F、a*a句子是：a*a11/18/2022882.2文法和语言的定义例：在推导句型有：E、T、T*2.2文法和语言的定义语言的形式定义：文法G推导出的所有句子组成的集合，称为语言，记为L（G）L（G）={α|Sα，α∈VT*}11/18/2022892.2文法和语言的定义语言的形式定义：文法G推导出的2.2文法和语言的定义例子：G1：S→A A→0A1 A→01是由一个或多个0开头，后跟同样数目的1的符号串构成的集合（语言），可记为：L(G)={0n1n|n≥1}11/18/2022902.2文法和语言的定义例子：是由一个或多个2.2文法和语言的定义G2： E→id E→E+E E→E*E E→（E）产生的是表达式的集合11/18/2022912.2文法和语言的定义G2： E→id产生的是2.2文法和语言的定义G3：E→E+T E→T T→T*F T→F F→（E） F→id产生的也是表达式的集合11/18/2022922.2文法和语言的定义G3：E→E+T产生的也2.2文法和语言的定义一个文法对应一个语言，但一个语言可能有若干个文法产生它，这若干个文法是等价的，称为

等价（equivalent）文法例G2与G311/18/2022932.2文法和语言的定义一个文法对应一个语言，但一个语言可2.3文法和语言的分类乔姆斯基（Chomsky）在1956年提出形式语言理论，他将形式文法分为四类(0,1,2,3)，对应四类形式语言(0,1,2,3)分类的方法是对文法的产生式进行不同的限制11/18/2022942.3文法和语言的分类乔姆斯基（Chomsky）在1952.3文法和语言的分类0型文法—|α|≠0，即α≠ε（α→β）1型（上下文有关）文法—|α|≤|β|（α→β）2型（上下文无关）文法—A∈VN，β∈（VT∪VN）*（A→β）3型（正规）文法A→a或A→aB（右线性）A→a或A→Ba（左线性）11/18/2022952.3文法和语言的分类0型文法—|α|≠0，即2.3文法和语言的分类例：1型（上下文有关）文法文法G： S→CD Ab→bA C→aCA Ba→aB C→bCB Bb→bB AD→aD C→ε BD→bD D→ε Aa→bD

L(G)={ww|w∈{a,b}*}11/18/2022962.3文法和语言的分类例：1型（上下文有关）文法11/12.3文法和语言的分类例：2型（上下文无关）文法文法G1： S→aB|bA A→a|aS|bAA B→b|bS|aBB

文法G2： S→0A|1B|0 A→0A|1B|0S B→1B|1|0

11/18/2022972.3文法和语言的分类11/11/2022362.3文法和语言的分类例：3型（正规）文法

文法G： S→0A|1B|0 A→0A|1B|0S B→1B|1|011/18/2022982.3文法和语言的分类例：3型（正规）文法11/11/22.3文法和语言的分类0型文法产生的语言称为0型语言1型文法或上下文有关文法（CSG）产生的语言称为1型语言或上下文有关语言（CSL）2型文法或上下文无关文法（CFL）产生的语言称为2型语言或上下文无关语言（CFL）3型文法或正则（正规）文法（RG）产生的语言称为3型语言正则（正规）语言（RL）11/18/2022992.3文法和语言的分类0型文法产生的语言称为0型语言1型2.3文法和语言的分类四种文法（语言）之间的逐级“包含”关系2型文法（语言）1型文法（语言）0型文法（语言）3型文法（语言）11/18/20221002.3文法和语言的分类四种文法（语言）之间的逐级“包含”2.3文法和语言的分类识别各类语言的数学模型（自动机）图灵机（0型语言）有界图灵机、线性有界自动机（1型语言）下推自动机（2型语言）有限自动机（3型语言）11/18/20221012.3文法和语言的分类识别各类语言的数学模型（自动机）图2.3文法和语言的分类上下文无关文法能够描述现今程序设计语言的大部分语法结构算术表达式赋值语句条件语句等11/18/20221022.3文法和语言的分类上下文无关文法能够描述现今程序设计2.3文法和语言的分类表达式文法：G=({+,*,i,(,)},{E},E,P) P: E→id E→E+E E→E*E E→(E) E表示算术表达式，id表示程序的“变量”，该文法定义了由变量，+，*，(和)组成的算术表达式的语法结构，即：变量是算术表达式；若E1和E2是算术表达式，则E1+E2，E1*E2和(E1)也是算术表达式。11/18/20221032.3文法和语言的分类表达式文法：G=({+,*,2.3文法和语言的分类描述一种简单赋值语句的产生式：〈赋值语句〉→i∶=E描述条件语句的产生式：〈条件语句〉→if〈条件〉then〈语句〉｜if〈条件〉then〈语句〉else〈语句〉11/18/20221042.3文法和语言的分类描述一种简单赋值语句的产生式：描述2.4分析树与句型分析树是描述上下文无关文法句型推导的一种直观方法，也称为推导树11/18/20221052.4分析树与句型分析树是描述上下文无关文法句型推导的一2.4分析树与句型为句型推导构造分析树例子：E=>TE→E+TE→T T→T*F T→F F→（E） F→a=>T*F=>F*F=>a*FTT*FFaaE=>a*a11/18/20221062.4分析树与句型为句型推导构造分析树E=>TE→2.4分析树与句型分析树的特性：根标识为开