第二章 形式语言基础(1).ppt

编译原理编译原理如何让计算机如何让计算机认识、理解认识、理解和和执行执行高级程序设计语言高级程序设计语言? ? 2007 年2月【内容提要】第第2 2 章章形式语言基础形式语言基础 语言是符号串集合 文法是定义语言的规则集 怎样用文法定义语言 各种语法成分定义与求解…形式语言是真实语言(程序设计语言、自然语言…) 的一种数学模型;很适合于计算机处理。形式语言的基本观点是:语言是符号串之集合! 语言是符号串集合形式语言可定义为: 字母表上的符号,按一定的规则组成的所有符号串之集合;其中的每个符号串称为句子。【 】 L 1={ 00,01,10,11 } ; 【 】 L 2={ ab nc,b n| n ≥0 } ; ?句型 1 ab nc : 有句子: ac, abc , abbc , abbbc ,…?句型 2 b n: 有句子: ?, b, bb, bbb ,…【注】符号串的方幂运算: b 0=?(空符号串) ,b 1=b,b 2=bb,b 3=bbb ,…有限语言无限语言?仅有四个句子: 00,01,10,11 字母表字母表字母表是语言的基本符号集,是语言的第一要素;其内容随着语言的研究范畴不同而不同。【 】机器语言字符集: ∑ 1={ 0,1 } ; 【 】高级语言字符集: ∑ 2={ a,b, …,+,-, …,(,), …}; 【 】汉语字符集: ∑ 3={ 啊,…,吃…,饭,…,我,…}; 【 】汉语单词集: ∑ 4={ 毕业,…,吃…,打击,…,新华社,…}; …【注】字母表是符号的有限集;而由字母表中符号通过规则组成的句子的集合(语言),则可能是无限集。规则集是语言中句子的组成的规律和法则,它可以通过某种运算,把该语言中的句子产生出来;故而, 规则集又称为产生式集。⑴S,A —定义的对象(S 句子,最大的定义对象,又称为开始符号; A 为句型 aAc 的一个短语), ⑵a,b,c -- 为字母表∑中的符号;ε- 空符号串。⑶-> ,| -- 为描述符号( -> 定义为; | 或者是) 【 】 L ={ ab nc, b n | n ≥0 } , ?字母表:∑= {a,b,c} ; ?展开:L ={ ac,abc,abbc ,…; ?, b,bb, …} S -> aAc | A A -> bA | ?规则集: 其中: 规则集规则集①S=> aAc => a εc= ac ②S=> aAc => abAc => abεc= abc ③S=> aAc => abAc => abbAc => abbc …一个句子!又一个句子! ∴S ab nc ,n ≥0 => + 再一个句子! 句子的产生过程: 从开始符号出发,对符号串中的定义对象,用其规则右部替换之(称为推导);产生的新符号串仍如此进行,直到新符号串中不再出现定义的对象为止,则最终的符号串就是一个句子。用规则产生句子的过程: 同理 S b n,n≥0 => + 怎样利用怎样利用规则规则产生产生句子句子 S -> aAc | A A -> bA | ? G(S): A -> ?或者 A -> ?| ? 文法文法是定义语言的规则集是定义语言的规则集 文法的形式定义 V N : 非终结符集(定义的对象集,如:语法成分等); V T : 终结符集(字母表); Z : 开始符号(研究范畴中,最大的定义对象); P : 规则集(又称产生式集) : G(Z)=(V N, V T, Z, P) ※上下文无关文法可定义为四元组: 每一种形式语言,都能由相应的有限规则集来描述; 称为该语言的文法(grammar) 。【注】描述符号:->( 定义为),|(或者是) 文法符号:Z,A ∈V N,?,?∈(V N+V T) * 规则形式闭包-- 由V N+V T中符号组成的全部符号串集合。※※文法应用示例文法应用示例: : G(N): N -> d N | d 【 】无符号整数文法: 【无符号整数】由数字 0 — 9 组成的任意符号串。其中: d ( 泛指 0 — 9 的任意数字), 【标识符】指字母开头的字母、数字序列。 I -> ? A A -> ? A | d A | ?【 】标识符文法: 则则G(I): 其中: ?(泛指 a — z 的任一字母) d ( 泛指 0 —