编译原理第二讲

1、形式形式语言及其文法语言及其文法本节主要本节主要内容内容2.1 2.1 语言概述语言概述什么是语言？什么是语言？2.1 2.1 语言概述语言概述 自然语言自然语言( (Natural Language)Natural Language) 是人与人的通讯工具是人与人的通讯工具 是人类概念形成和进行思维的工具，是人之是人类概念形成和进行思维的工具，是人之所以为人的主要特征所以为人的主要特征 复杂，多歧义复杂，多歧义难以形式化难以形式化 计算机语言计算机语言( (Computer Language)Computer Language) 计算机系统间、人机间通讯工具计算机系统间、人机间通讯工具 严格的

2、语法严格的语法( (Grammar)Grammar)、语义语义、易于形式化易于形式化形式语言与自动机理论的关系形式语言与自动机理论的关系Noam Chomsky （1928）形式语言与自动机理论的关系形式语言与自动机理论的关系 语言学家语言学家ChomskyChomsky最初从产生语言的角度研究语言。最初从产生语言的角度研究语言。 19561956年，通过抽象，他将语言形式地定义为是由一个字母表年，通过抽象，他将语言形式地定义为是由一个字母表中的字母组成的一些串的集合。可以在字母表上按照一定的中的字母组成的一些串的集合。可以在字母表上按照一定的规则定义一个文法（规则定义一个文法（Grammar

3、Grammar），该文法所能产生的所有句），该文法所能产生的所有句子组成的集合就是该文法产生的语言。子组成的集合就是该文法产生的语言。 19591959年，年，ChomskyChomsky通过深入研究通过深入研究，不仅，不仅确定了文法和自动机分别确定了文法和自动机分别从生成和识别的角度去表达语言，而且证明了文法与自动机的从生成和识别的角度去表达语言，而且证明了文法与自动机的等价性等价性。 形式语言与自动机理论的关系形式语言与自动机理论的关系 2020世纪世纪5050年代，人们用巴科斯范式（年代，人们用巴科斯范式（Backus Nour Backus Nour Form Form 或或 Back

4、us Normal FormBackus Normal Form，简记为，简记为BNFBNF）成功地对）成功地对高级语言高级语言ALGOL-60ALGOL-60进行了描述。实际上，巴科斯范式进行了描述。实际上，巴科斯范式就是上下文无关文法（就是上下文无关文法（Context Free GrammarContext Free Grammar）的一）的一种表示形式。这一成功，使得形式语言在种表示形式。这一成功，使得形式语言在2020世纪世纪6060年年代得到了大力的发展。代得到了大力的发展。 2.12.1语言概述语言概述 形式语言的描述方法形式语言的描述方法 文法文法数学语言（符号）数学语言（符号

5、） 严格、准确、形式化严格、准确、形式化 高度的抽象，严格的理论基础和方便的计算机高度的抽象，严格的理论基础和方便的计算机表示。表示。2.1 2.1 语言概述语言概述 形式语言的组成要素形式语言的组成要素语言语言( (Language)Language)：满足一定条件的句子集合满足一定条件的句子集合句子句子( (Sentence)Sentence)：满足一定规则的单词序列满足一定规则的单词序列单词单词( (Token)Token)：满足一定规则的字符串满足一定规则的字符串2.1 2.1 语言概述语言概述 程序设计语言的组成要素程序设计语言的组成要素 程序设计语言程序设计语言( (Program

6、ming Language)Programming Language)：组成程序组成程序的所有语句的集合。的所有语句的集合。 程序程序( (Program)Program)：满足语法规则的语句序列。满足语法规则的语句序列。 语句语句( (Sentence) Sentence) ：满足语法规则的单词序列。满足语法规则的单词序列。 单词单词( (Token) Token) ：满足词法规则的字符串。满足词法规则的字符串。 例：变量例：变量:=:=表达式表达式 if if 条件条件 then then 语句语句 whilewhile条件条件 do do 语句语句2.2 2.2 基本定义基本定义 字母表

7、字母表（AlphabetAlphabet）是一个非空有穷集合，是一个非空有穷集合，字母表中的元素称为该字母表的一个字母字母表中的元素称为该字母表的一个字母（LetterLetter），），也叫字符（也叫字符（CharacterCharacter）。）。 例例 以下是不同的字母表：以下是不同的字母表： aa，b b，c c，dd a a，b b，c c，zz 0 0，11 (4) ASCII(4) ASCII字母表字母表2.2 2.2 基本定义基本定义 符号串符号串的定义的定义 由字母表中的符号所组成的任何有穷序列被由字母表中的符号所组成的任何有穷序列被称之为该字母表上的符号串称之为该字母表上的

8、符号串, ,也称作也称作 字字 。(1) (1) 是是上的一个符号串。上的一个符号串。(2) (2) 若若x x是是上的符号串，而上的符号串，而a a是是的元素的元素, , 则则xaxa是是上的符号串。上的符号串。(3) (3) y y是是上的符号串上的符号串, ,当且仅当它由当且仅当它由(1)(1)和和(2)(2)导出。导出。2.2 2.2 基本定义基本定义设设s s是是符号串，则符号串，则s s的的前缀前缀：移走：移走s s的尾部的零个或多于零个符号的尾部的零个或多于零个符号后缀后缀：删去：删去s s的头部的零个或多于零个符号的头部的零个或多于零个符号子串子串: : 从从s s中删去一个前

9、缀和一个后缀中删去一个前缀和一个后缀逆转逆转：将：将S S中的符号按相反次序写出而得到的符号串中的符号按相反次序写出而得到的符号串长度长度：是该符号串中的符号的数目。例如：是该符号串中的符号的数目。例如| |aab|=3,|=0aab|=3,|=0。2.2 2.2 基本定义基本定义符号串的连接和方幂符号串的连接和方幂1.1.连接：设连接：设x x和和y y是符号串，它们的连接是符号串，它们的连接xyxy是把是把y y的符号的符号写在写在x x的符号之后得到的符号串。例如，的符号之后得到的符号串。例如，x=ba,y=nana,xy=banana.x=ba,y=nana,xy=banana.2.2

10、.方幂：方幂：x x0 0= = ; ; x x1 1=x; x=x; x2 2=xx; =xx; ； x xn n=x=xn-1n-1x;x; 例如例如, , 设设x=ba, x=ba, 则则 x x1 1= ba, x= ba, x2 2=baba, x=baba, x3 3=bababa, =bababa, 2.2 2.2 基本定义基本定义 定义定义1 1 设设1 1、2 2是两个字母表，是两个字母表，1 1与与2 2 的的乘积乘积( (Product)Product)定义为定义为1 12 2=ab|a=ab|a1 1，bb2 2 例例:1 1=0,1, =0,1, 2 2=a,b, a

11、,b, 1 12 2 =0a,0b,1a,1b =0a,0b,1a,1b 定义定义2 2 设设是一个字母表，是一个字母表，的的n n次幂次幂( (Power)Power)递归递归地定义为：地定义为： 0 0= n n=n-1n-1 n1 n1 例：例： 1 13 3 =000,001,010,011,100,101,110,111 =000,001,010,011,100,101,110,1112.2 2.2 基本定义基本定义 定义定义3 3 设设是一个字母表，是一个字母表，的的正闭包正闭包定定义为：义为： + +=2 23 34 4 的的闭包闭包为：为： * *=0 0+ + = =0 02

12、 23 3 2.2 2.2 基本定义基本定义例例0,10,1+ + = = 00，1 1，0000，0101，10,10,1111，000000，001001，010010，011011，100100， 0,10,1* * = = ，0 0，1 1，0000，0101，10,1110,11，000000，001001，010010，011011，100100， 2.2 2.2 基本定义基本定义定义定义5 5 设设是一个字母表，是一个字母表， L L * *，L L称为字称为字母表母表上的上的语言语言（LanguageLanguage），），xLxL，x x叫做叫做L L的一个的一个句子句子。例

13、：例： 字母表字母表00，11上的语言上的语言00，110000，111100，1 1，0000，111100，1 1，0000，1111，0101，10100000，1111* *0101，1010* *2.3 2.3 文法文法如何实现语言结构的形式化描述？如何实现语言结构的形式化描述？考虑一个句子考虑一个句子文法要素的提取文法要素的提取分析分析：The grey wolf will eat the goat谓语谓语主语主语形容词形容词名词名词动词动词直接宾语直接宾语情态情态动动词词句子句子动原动原冠词冠词名词名词The grey wolf will eat the goat冠词冠词 句子句

14、子 主语主语 谓语谓语 （1 1） 主语主语 冠词冠词 形容词形容词 名词名词 （2 2） 冠词冠词 thethe （3 3） 形容词形容词 greygrey （4 4） 谓语谓语 动词动词 直接宾语直接宾语 （5 5） 动词动词 情态动词情态动词 动词原动词原形形 （6 6） 情态动词情态动词 willwill （7 7） 动词原动词原形形 eateat （8 8） 直接宾语直接宾语 冠词冠词 名词名词 （9 9） 名词名词 wolfwolf （1010） 名词名词 goatgoat （1111）句子的组成规则句子的组成规则问题：如何用符号来描问题：如何用符号来描述？即如何形式化？述？即如何

15、形式化？终结符号集终结符号集V VT T = = thethe，grey, wolf,will, eat, goatgrey, wolf,will, eat, goat非终结符号集非终结符号集V VN N = = 句子句子 ， 主语主语 ， 谓语谓语 ， 冠词冠词 ， 形容词形容词 ， 名词名词 ， 动词动词 ， 直接宾语直接宾语 ， 助动词助动词 ， 动词原动词原形形 语法规则集语法规则集P P = = 句子句子 主语主语 谓语谓语 ， 开始符号开始符号S S = = 句子句子 定义句子的规则的语法定义句子的规则的语法组成组成问题：有了定义句子的规则，问题：有了定义句子的规则，如何如何推导出

16、推导出语语言言？ 句子句子 主语主语 谓语谓语 冠词冠词 形容词形容词 名词名词 谓语谓语 thethe 形容词形容词 名词名词 谓语谓语 the the greygrey 名词名词 谓语谓语 the grey the grey wolfwolf 谓语谓语 the grey wolf the grey wolf 动词动词 直接宾语直接宾语 . the grey wolf the grey wolf will eat the goatwill eat the goat句子的推导句子的推导 句子句子 the grey wolf will eat the goat the grey wolf wil

17、l eat the wolf the grey goat will eat the wolf the grey goat will eat the grey符合语法且符合语义的句子仅是：符合语法且符合语义的句子仅是： the grey wolf will eat the goat句子句子的的语义语义约束约束文法文法G G 的形式定义的形式定义文法文法G G为一个四元组为一个四元组: : = ( = (T T，N N，) ) T T：终结符终结符( (Terminal)Terminal)集集 N N：非终结符非终结符( (Variable)Variable)集，集，T TN N= 语法成分语法成

18、分代表某个语言的各种子结构代表某个语言的各种子结构 ：开始符号：开始符号( (Start Symbol)Start Symbol)，SSN N 代表文法所定义的语言，至少在产生式左侧出现一次代表文法所定义的语言，至少在产生式左侧出现一次文法文法G G 的形式定义的形式定义：产生式：产生式( (Product)Product)集合集合，被称为产生式（定义式），读作：被称为产生式（定义式），读作：定义为定义为。其中其中(T TN N) )+ +，且且中至少有中至少有N N中元素中元素的一个出现。的一个出现。(T TN N) )* *。称为产生式称为产生式的的左部左部( (Left Part)Lef

19、t Part)，称为产生式称为产生式的的右部右部( (Right Part)Right Part)。产生式定义各个语法成分的结构（组成规则）产生式定义各个语法成分的结构（组成规则） 产生式的简写产生式的简写对一组有相同左部的产生式对一组有相同左部的产生式1 1，2 2，n n可以简单地记为：可以简单地记为：1 1|2 2| |n n读作：读作：定义为或者定义为或者1 1，或者或者2 2，或者或者n n。并且称它们为并且称它们为产生式。产生式。1 1，2 2，n n称为称为候选式候选式( (Candidate)Candidate)。 例例2-1 2-1 算术表达式的文法算术表达式的文法 考虑简单

20、算术表达式组成的语言考虑简单算术表达式组成的语言 G =(idG =(id，+ +，* *，( (，)，EE，P P，E)E)P: EE + E P: EE + E EE EE * * E E E( E ) E( E ) Eid Eid 简写简写 E E + E | E E E + E | E * * E | ( E ) | id E | ( E ) | id 推导举例推导举例E E E + E E + E （1 1） 串中含有变量串中含有变量 id + E id + E （4 4） 串中含有变量串中含有变量 id + E id + E * * E E （2 2） 串中含有变量串中含有变量 i

21、d + id id + id * * E E（4 4） 串中含有变量串中含有变量 id + id id + id * * id id（4 4） 串中没有变量串中没有变量 到此串中已经没有（语法）变量了，不能再推导了到此串中已经没有（语法）变量了，不能再推导了最左推导与最右推导最左推导与最右推导最左推导最左推导( (Left-most Derivation)Left-most Derivation)每次推导都施加在句型的最左边的语法每次推导都施加在句型的最左边的语法变量上。变量上。最右推导最右推导( (Right-most Derivation)Right-most Derivation)每次推

22、导都施加在句型的最右边的语法每次推导都施加在句型的最右边的语法变量上。变量上。id+idid+id* *idid的不同推导的不同推导P: EP: EE+E|EE+E|E* *E|(E)|idE|(E)|id直接推导直接推导 设有文法设有文法G G 是文法的一个产生式，是文法的一个产生式， 且且、（T TN N）* *， 且且有有v,v, ,满足满足v=v=, , = =, , 则则是是v v的直接推导，记做的直接推导，记做v=v= （多步）推导（多步）推导 0 01 12 2 n n记为记为 0 0n n n n ( (恰用恰用n n步步) ) 0 0+ + n n （至少一步）至少一步） 0

23、 0* * n n （若干步若干步: :零步或多步）零步或多步）递归递归 设有文法设有文法G G A A是文法的一个产生式，是文法的一个产生式， 若若具有具有v vA A的形式，其中的形式，其中v,v,不同时为空，则不同时为空，则A A是直接递归的是直接递归的 若存在推导若存在推导A A * * vAvA, ,则则A A是递归的是递归的 特别的，当特别的，当v v为空，为空，不为空时，分别称上述两种不为空时，分别称上述两种情况的产生式为直接左递归和左递归情况的产生式为直接左递归和左递归 若文法中至少含有一个递归的产生式，则称为递若文法中至少含有一个递归的产生式，则称为递归文法归文法句型与句子句

24、型与句子 句型句型: :如果如果S S* *，(T TN N) )* *则称则称是是G G产生的一个产生的一个句型句型( (Sentential Form)Sentential Form) E E E + E E + E E E + E + E * * E E E E 4 4 id + id id + id * * E E 句子句子: :如果如果S S * * x x，且且xxT T* * ，则称则称x x是是G G产生的一个产生的一个句子句子( (SentenceSentence) )E E id + id id + id * * id id文法文法G G产生的语言产生的语言定义定义 ( (

25、) ) x x* * x and xx and xT T* * 文法文法G G的作用的作用语言的有穷描述语言的有穷描述 以有限的规则描述无限的语言现象以有限的规则描述无限的语言现象有限：有限： 产生式集合、终结符集合、非终结符集合产生式集合、终结符集合、非终结符集合无限：无限： 可以导出无穷多个句子（可以导出无穷多个句子（L L也可是有穷）也可是有穷）2.2. 文法的分类文法的分类( (ChomskyChomsky体系体系) ) 根据语言结构的复杂程度（形式语言）根据语言结构的复杂程度（形式语言） 涉及文法的复杂程度、分析方法的选择涉及文法的复杂程度、分析方法的选择 反映文法描述语言的能力反映

26、文法描述语言的能力 如果如果G G满足文法定义的要求，则是型文满足文法定义的要求，则是型文法（短语结构文法法（短语结构文法PSG: Phrase Structure PSG: Phrase Structure Grammar Grammar ）。）。 L(G)L(G)为为PSLPSL。 上下文有关文法上下文有关文法( (CSG)CSG) 若产生式集合中所有若产生式集合中所有， 除除 外，则是型文法外，则是型文法 即：上下文有关文法（即：上下文有关文法（CSGCSGContext Context Sensitive GrammarSensitive Grammar） L(G)L(G)为为1 1型

27、型/ /上下文有关上下文有关/ /敏感语言敏感语言( (CSL)CSL)上下文无关文法上下文无关文法( (CFG)CFG) 若若 N N，(N NT T) )* *，则则 是型文法是型文法 即：上下文无关文法即：上下文无关文法( (CFG: Context Free CFG: Context Free Grammar)Grammar) L(G)L(G)为为2 2型型/ /上下文无关语言（上下文无关语言（CFLCFL） CFGCFG能描述程序设计语言的多数语法成分能描述程序设计语言的多数语法成分例例2-3 2-3 标识符的文法标识符的文法2 2 S L|LTS L|LTT L|N|TL|TN T

28、 L|N|TL|TN L a|b|c|dL a|b|c|dN 0|1|2|3|4|5N 0|1|2|3|4|5正则文法正则文法( (RG)RG) 设、设、N N，T T或为或为 右线性右线性( (Right Linear)Right Linear)文法：文法：或或 左线性左线性( (Left Linear)Left Linear)文法：文法：或或 都是型文法都是型文法( (正规文法正规文法 Regular Grammar -RG)Regular Grammar -RG) L(G)L(G)为为3 3型型/ /正规集正规集/ /正则集正则集/ /正则语言（正则语言（RLRL）能描述程序设计语言的多

29、数单词能描述程序设计语言的多数单词左、右线性文法不可混用左、右线性文法不可混用例例 非非CFLCFL的文法的文法L=aL=an nb bn nc cn n|n0|n0的文法的文法S SaBC|aSBCaBC|aSBCCBCBBCBCaBaBababbBbBbbbbbCbCbc bc 在我们使用的程序设计语言中在我们使用的程序设计语言中, ,有些语言结有些语言结构不能用上下文无关文法来描述。构不能用上下文无关文法来描述。 例例2.2.4 L4 L1 1=wcw|wa,b=wcw|wa,b+ + 。例例, ,aabcaabaabcaab就就是是L L1 1的一个句子。这个语言是检查程序中标的一个句

30、子。这个语言是检查程序中标识符的声明应先于引用的抽象。识符的声明应先于引用的抽象。 例例2.2.5 L5 L2 2=a=an nb bm mc cn nd dm m|n,m0|n,m0，它是检查过，它是检查过程声明的形参个数和过程引用的参数个数是程声明的形参个数和过程引用的参数个数是否一致问题的抽象。否一致问题的抽象。非上下文无关的语言结构非上下文无关的语言结构ChomskyChomsky体系体系总结总结 = ( = (T T，N N，) )是一个文法是一个文法, , P P* * G G是是0 0型文法，型文法，L(G)L(G)是是0 0型语言；型语言； -其能力相当于图灵机其能力相当于图灵

31、机* * | |:G|:G是是1 1型文法，型文法，L(G)L(G)是是1 1型语言型语言( (除除);); -其识别系统是线性界限自动机其识别系统是线性界限自动机* * N N : G : G是是2 2型文法，型文法，L(G)L(G)是是2 2型语言型语言; ; -其识别系统是不确定的下推自动机其识别系统是不确定的下推自动机* * AaBAaB或或Aa: Aa: G G是右线性文法，是右线性文法，L(G)L(G)是是3 3型语言型语言ABaABa或或AA: : G G是左线性文法，是左线性文法，L(G)L(G)是是3 3型语言型语言 -其识别系统是有穷自动机其识别系统是有穷自动机文法的类型文

32、法的类型四种文法之间的关系是将产生式作进一步限制而定义的。四种文法之间的关系是将产生式作进一步限制而定义的。四种文法之间的逐级四种文法之间的逐级“包含包含”关系如下：关系如下：2型文法型文法1型文法型文法0型文法型文法3型文法型文法范式范式Backus-Naur FormBackus-Naur FormBackus-Normal FormBackus-Normal Form 表示为表示为 非终结符用非终结符用“ ”括起来括起来 终结符：基本符号集终结符：基本符号集 其他其他 (1 1|2 2|n n)1 1|2 2|n n | | 范式范式Backus Normal FormBackus No

33、rmal Form 例例 简单算术表达式简单算术表达式( (只写产生式只写产生式) ) + * * () idid 即： +| * * |(|()|)|idid 哪些是终结符？哪些是变量？哪些是终结符？哪些是变量？例例2-2-6 6 句子结构的表示句子结构的表示 ( (文法文法EE+E|EEE+E|E* *E|(E)|idE|(E)|id ）2.5 2.5 CFGCFG的分析树的分析树Parse TreeParse Tree 用树的形式表示句型的生成用树的形式表示句型的生成 树根：树根： 开始符号开始符号 中间结点：中间结点： 非终结符非终结符 叶结点：叶结点： 终结符或者非终结符终结符或者非

34、终结符 每个推导对应一个中间结点及其儿子每个推导对应一个中间结点及其儿子一个二级子树一个二级子树- -直接短语直接短语 又称为语法分析树又称为语法分析树EE+TT+TF+T a1+T a1+T*F a1+F * F a1+a2 *FE+T T,T+T F,F+T a1, a1+T a1, T*F, a1+T*Fa1, F,F*F, a1+F*F a1, a2,a1+ a2 *F, a2 *F a1, a2, a3, a2 * a3 a1+ a2 *a3EE+TTFa1T*FFa2a3a1+a2 *a3短语短语 二义性文法与先天二义性语言二义性文法与先天二义性语言 对同一句子存在两棵语法分析树对

35、同一句子存在两棵语法分析树 在理论上不可判定在理论上不可判定 1. 描述一个句子的文法不是唯一的；描述一个句子的文法不是唯一的； 2. 对于一个句子的分析应是唯一的。对于一个句子的分析应是唯一的。考虑表达式下面的文法考虑表达式下面的文法 GE,其产生式如下：其产生式如下： EE+E E*E (E) a 对于句子对于句子a+a*a, 有如下两个最左推导：有如下两个最左推导： EE+E a+E a+E*E a+a*E a+a*a E E*E E+E*E a+E*E a+a*E a+a*a文法的二义性文法的二义性 EE+E a+E a+E*E a+a*E a+a*a E E*EE+E*E a+E*E

36、a+a*E a+a*aEE+EE*EaaaEE*E+EEaaa最左推导最左推导 EE+E E+E*E E+E*a E+a*a a+a*a E E*EE*a E+E*aE+a*a a+a*aEE+EE*EaaaEE*E+EEaaa最右推导最右推导如果一个文法的句子存在两棵分析树如果一个文法的句子存在两棵分析树,那么那么,该句子该句子是二义性的。如果一个文法包含二义性的句子是二义性的。如果一个文法包含二义性的句子,则则称这个文法是二义性的称这个文法是二义性的; 否则，该否则，该文法是无二义性文法是无二义性的。几点说明：的。几点说明：1 . 一般来说，程序语言存在无二义性文法，一般来说，程序语言存在

37、无二义性文法， 对于对于表达式来说，文法（表达式来说，文法（2 .1）是二义性的。对于条件）是二义性的。对于条件语句，经常使用二义性文法描述它：语句，经常使用二义性文法描述它：S if expr then S if expr then S else S other二义性的句子二义性的句子: if e1 then if e2 then s1 else s2 二义性（歧义性，二义性（歧义性，ambiquity)ambiquity)的定义的定义 下面是下面是 Smatched_s unmatched_s matched_s if expr then matched_s else matched_s other unmatched