第二章形式语言理论.pptVIP

第二章 形式语言理论 形式语言 Chomsky于1956年提出了一种用来描述语言的数学系统。人们把用一组数学符号和规则来描述语言的方式称为形式描述，而把所用的数学符号和规则称为形式语言。 形式语言，只是从语法上研究语言。它是抽象的数学系统，用于模拟程序设计语言的语法，或者是并不很成功地模拟自然语言如英语的语法。 形式语言理论是编译理论的重要基础，它主要研究组成符号语言的符号串的集合及它们的表示法、结构与特性。 形式语言和编译理论中的 最基本概念 ——符号串和符号串集合 2.1字母表和符号串 字母表 定义:元素的非空有穷集合，记为∑。 例：∑={0?1} Α={a?b,c} 元素也称为符号，字母表也称符号集。 程序语言的字母表由字母数字和若干专用符号组成。 符号串 定义:由字母表中的符号组成的任何有穷序列 例：0,00,10是字母表∑={0?1}上的符号串 a,ab,aaca是Α={a?b,c}上的符号串 在符号串中，符号是有顺序的，顺序不同,代表不同的符号串，如:ab和ba不同 不含任何符号的符号串称为空串，用ε表示 注意:{ε}并不等于空集合{ } 符号串长度: 符号串中含有符号的个数 如: |abc|=3 | ε|=0 符号串的运算 符号串的连接：设x、y是符号串,它们的连接 是把y的符号写在 x的符号之后得到的符号串xy 例如 x=ST，y=abu ，则 xy=STabu 显然εx = xε=x 符号串的方幂：把符号串a自身连接n次得到的符号串an = aa…aa 例如 a1=a a2=aa a0=ε 符号串集合： 定义: 若集合A中所有元素都是某字母表?上的符号串，则称A为字母表?上的符号串集合。 符号串集合的乘积：符号串集合A和B的乘积定义为:AB ={xy|x∈A且y∈B}，即AB是由A中的串x和B中的串y连接而成的串xy组成的集合。 若集合A = ?ab,cde? B = ?0,1? 则 AB = ?ab0,ab1,cde0,cde1? 显然 {ε}A = A{ε} = A 符号串集合的方幂: 设A是符号串的集合，则称Ai为符号串集A的方幂，其中i是非负整数。具体定义如下: A0 ={ε} A1 = A , A2 = A A AK = AA......A(k个) 集合的闭包 闭包 集合Σ的闭包Σ *定义如下： Σ * = Σ 0∪ Σ1∪ Σ 2∪ Σ 3∪… 例：设有字母表Σ={0，1} 则Σ*=Σ0∪Σ1∪Σ2∪… ={ε,0,1,00,01,10,11,000,…} 即Σ*表示Σ上所有有穷长的串的集合。 正闭包 Σ+ = Σ1∪Σ2∪Σ3∪…称为Σ的正闭包。 ?+ 表示?上的除ε外的所有有穷长串的集合 自反闭包Σ* = Σ0∪Σ+ Σ+ = ΣΣ* = Σ* Σ 2.2文法和语言 1、文法定义: 文法G(Grammar)定义为四元组（VN，VT，P，S） VN (Nonternimal)：非终结符集 VT (Terminal)：终结符集 P (Production)：产生式（规则）集合 S：开始符号或识别符号 说明: V=VN∪VT，V称为文法G的字母表 P中产生式形如：α→β,其中α∈V+且至少含一个非终结符，β∈V* VN,VT和P是非空有穷集 VN∩VT=φ S是一个非终结符，且至少要在一条产生式的左部出现 非终结符代表一个语言中的语法成分，如赋值语句，它是构成程序的一个语法成分，这个符号本身不会在程序中出现，而终结符是组成程序的具体的符号。 2. 推导和规范推导： α→β是文法G的产生式，若有v，w满足： v=γαδ,w=γβδ, 其中γ,δ∈V* 则称v直接推导出w,也称w直接归约到v, 记作 v ? w 直接推导就是用产生式的右部替换产生式的左部的过程 直接归约就是用产生式的左部替换产生式的右部的过程 2、直接推导序列： 或 ? + 若存在v =u0 ?u1 ?... ?un=w, (n0) 则称v ? + w，v推导出w，或w归约到v（至少有1步推导），这个直接推导序列的长度为n。 3、广义推导： 或 ? * 若有v ? + w 或 v=w， 则记为v ? * w，v广义推导出w，w广义规约到v（可以包含0步推导） 三种推导的比较 直接推导（?）的长度为1 直接推导序列（? +）的长度n≥1 广义推导（? *）的长度≥0 规范推导与规范规约 考虑两种特殊推导：最左推导和最右推导，即 对于一个推导序列中的每一步直接推导，都是对最左（最右）非终结符进行替换。 最右推导也