第二章是正式语言的理论.ppt

第二章 形式语言理论;形式语言;形式语言和编译理论中的 最基本概念 ——符号串和符号串集合;2.1字母表和符号串;符号串 定义:由字母表中的符号组成的任何有穷序列 例：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文法和语言;说明: 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步推导）;三种推导的比较;规范推导与规范规约;2.3 文法的分类;如果对于某文法G，P中每个规则具有下列形式： α→β 其中α∈V+ ， β ∈ V*，则该文法G为（Chomsky）0型文法或短语结构文法。相应的语言 称为0型语言或短语结构语言。 如文法G，其中VN={A,B,S} VT={0,1} P={ S→0AB 1B→0 B→SA|01 A1→SB1 A0→S0B } ;1型文法(上下文有关) 它是0型文法的特例, 对P中的任一产生式α→β，都有|β|≥|α| ≥ 1， 仅仅 S→ε除外,但S不得出现在任何产生式的右部。 例 文法G[S]： S→aSBE S→aBE EB→BE aB→ab bB→bb bE→be eE→ee 1型文法产生式的一般形式是 ?A?→???， ?,? ∈ V* ，A∈VN , β∈V＋ ，它表示当A的上文为?且下文为?时可把A替换成?，因此称1型文法为上下文有关文法。 ;2型文法（上下文无关文法） 它是1型文法的特例，对任一产生式α→β，都有 α∈VN ， β∈(VN∪VT)* 例 文法G[S]： S→AB A→BS|0 B→SA|1 2型