编辑: You—灰機 2019-07-05

若y非空,则x是固有头.例:设z=abc,则z的固有头是ε, a, ab 则z的固有尾是 ε,c ,bc (3)符号串的连接: 设x,y是符号串,连接xy是y符号写在x符号之后.例:x=ab, y=MN 则xy=abMN显然:εx=xε=x(4)符号串的方幂:设x是符号串,则z=xx……xx,称z为x的方幂, 记z=xn. 因此 x0=ε, x1=x, x2=xx, x3=xxx 显然n>

0时, 有xn =x・x n-1= x n-1・x N个(5)符号串的集合:若集合A中的一切元素都是某字母表上的符号串,则称A为该字母表上的符号串集合.两个符号串集合A、B乘积定义:AB={xy| x∈A且y∈b} 例:A={a,b},B={c,d} 则AB= {ac,ad,bc,bd} (6)闭包(∑*) 字母表∑,用∑* 表示∑上所有有穷长的串集合,∑*称为∑的闭包.例:字母表∑={0,1}则∑*= {ε,0,1,00,01,10,11,000,001,010……}=∑0∪∑1 ∪ ∑2∪. …∪∑n 〈7〉正闭包(1 ∪ ∑2∪. …∪∑n ∑+称∑的正闭包.显然:∑*= ∑0∪ ?

三、文法和语言的形式定义(用以上术语对文法的概念进行形式化)

1、规则(重写规则、产生式、生成式) 形如?→ β 或? ::= β ? 是字母表V的正闭包V+的一个符号;

β是字母表V的闭包V*的一个符号;

? 称规则的左部,β称规则的右部.

2、文法的定义〈1〉文法G定义为四元组(VN,VT,P,S) 其中: VN ―― 非终结符号集 VT ―― 终结符号集 P ―― 产生式(规则)S ―― 开始符号或称作识别符号,它是一个非终结符,至少要在一条规则中作为左部出现.规定:(1)VN ,VT,P是有穷非空集合;

2)VN∩VT=? (不含公共元素) 例1 文法G =(VN ,VT ,P,S), 其中 VN={S},VT ={0,1}, P={S → 0S1,S → 01}. 非终结符集中只含一个元素S;

终结符集由两个元素0和1组成;

有两条产生式;

开始符号是S.想:从终结符可推出哪些符号串? 答案:S={01,0011,000111,00001111…} 例2 文法G =(VN ,VT,P,S)其中 VN ={标识符,字母,数字}VT= {a,b ,c,…,x,y,z,0,1,…,9} ?P = { →〈字母〉标识符>

→ → →a →b … →z →1 … →9 }S= 表示非终结符 文法G的第二种表示法: 上例1改为: G: S → 0S1 S →

01 文法G的第三种表示法: 上例1改为: G[S]: S → 0S1 S →

01 一般约定,第一条产生式的左部是识别符号;

用尖括号括起来的是非终结符号,不用尖括号括起来的是终结符号,或者用大写字母表示非终结符号,小写字母表示终结符号.

3、直接推导的定义 ? → ? 是文法G=(VN ,VT ,P,S)的规则,?和?是V*中的任意符号,若有符号串V,W满足:V= ? ? ?,W=? ?? 则说 V是直接产生W 或 W是V的直接推导 或 W直接规约到V 记作 V? W V=S,W=0S1W 是否V的直接推导V=0S1,W=00S11 W 是否V的直接推导 例3: 在例1中V=0S1,W=0011W 是否V的直接推导 G: S → 0S1 S →

01 V=S,W=0S1V是否W的直接推导直接推导:S ? 0S1V=0S1,W=00S11 V是否W的直接推导直接推导: 0S1?00S11 例3: 在例1中V=0S1,W=0011V是否W的直接推导直接推导:0S1 ?0011 使用规则:S →01?=0,?=1,?=S, ?=01 规则: S → 0S1 ? =? , ? = ??=S, ?=0S1 规则: S → 0S1 ? =0 , ? = 1?=S, ?=0S1 若有 V?W ,或V=W,则记作 V ?W 例子: 在例1中存在序列:V=0S1? 00S11? 000S111?

00001111 =W记作: 0S1?

00001111 0S1?

00001111 + + + * 若存在直接推导的序列: V=W0 ? W1 ? W2 ? … Wn =W (n>

0)则称V推导W (或W规约到V) ,记V ? W * 一样的

4、句型的定义: 设G[S]是文法,如果符号串x是从识别符号(开始符号)推导出来的(即S? x)则称x是文法G[S]的句型. 若x仅由终结符号组成(S?x,x?VT*)则称x为G[S]的句子. * * 例: S,0S1,000111都是文法G的句型,000111是G的句子.〖结论〗句子一定是句型,句型不一定是句子.

下载(注:源文件不在本站服务器,都将跳转到源网站下载)
备用下载
发帖评论
相关话题
发布一个新话题