- 1、下载文档前请自行甄别文档内容的完整性,平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益,请联系客服反馈,我们会尽快为您处理(人工客服工作时间:9:00-18:30)。
符号串集合运算示例(续):
【例2.5】 设 A={a,b}, A* = ? ∵ A* = A0∪A1∪A2∪…∪An∪… A0 ={}; A1 = A ={a,b}; A2 = A.A={a,b}.{a,b}={aa,ab,ba,bb}; A3 = A.A2={a,b}.{aa,ab,ba,bb} ={aaa,aab,aba,abb,baa,bab,bba,bbb}; … ∴ A* = { x | x=(a|b)n ,n≥0 }
2.3
2.3.1
主要语法成分的定义
文法的运算问题
直接推导 算符
文法有两种基本运算:推导,归约。 设 x, y∈(VN+VT)*, A->∈P
Ⅰ.直接推导( => ): xAy => xy 即:指用产生式的右部符号串替换左部非终结符。 + ): + β 加推导( => => (当且仅当=>1=>2=>…=>β) 即:指一步或一步以上的直接推导运算。 * ): * β 星推导( => α => (当且仅当=β或=>1=>2=>…β) 即:指零步或零步以上的直接推导运算。 加推导 算符
根据 语言定义式〖2.1〗, 合法的算术表达式是指:
+ i*(i+i-i) 成立吗? E =>
∵ E =>T =>T*F =>T*(E) =>T*(E-T)
=>T*(E+T-T)=>F*(E+T-T)=>i*(E+T-T) =>… =>i*(i+i-i) 观察推导过程,可
∴
+ i*(i+i-i) E => 以看到:一旦产生式 选择错了,会导致失 败!
规则应用说明示例:
怎样利用上述文法规则表示语言L? 从开始符号出发,对符号串中的定义对象,采 用推导的方法(用其规则右部替换左部)产生新的 S -> aAc 符号串,如此进行,直到新符号串中不再出现定义 A -> bA | 的对象为止,则最终的符号串就是一个句子。 【句子产生过程】(=> 推导算符): 一个句子! 又一个句子!
【注】此文法定义了算术表达式的层次嵌套结构 : 项 因式 表达式 ( 表达式 )
+ * } L(G)={ x | Z x,x∈V => T ※ 算术表达式文法应用示例: 证明 i*(i+i-i) 是文法G(E)的一个句子 (即 合法的算术表达式):
G(E):
E->T |E+T |E-T T->F |T* F |T/F F->i |(E)
即:指零步或零步以上的直接归约运算。 这是相应的算符 ※ 实用中最常见的两种运算: + => 最左推导( ℓ )—每次推导皆最左非终结符优先; + )—每次归约皆最左可归约串优先。 最左归约( => . ℓ
文法运算示例:
【例2.8】 算数表达式文法:
G(E): E->T|E+T|E-T T->F|T*F|T/F F->i |( E )
【注】 ⑴ ⑵
2.1.1
符号串(集合)的运算
这是一种 泛指!
Ⅰ. 符号串的运算
设 , 为两个符号串,则:
1. 连接:• =
如
a•b=ab
2. 或: |= (或者 ) 3. 方幂: n = … = n-1 = n-1 n个 0 ※ = (空符号串)
第 2 章
形式语言基础
【内容提要】
2.1 2.2 2.3 2.4 2.5 2.6
形式语言是符号串集合 形式语言是由文法定义的 主要语法成分的定义 两类特性文法 文法变换方法 关于形式语言的分类问题
2.1
形式语言是符号串集合
【形式语言】是字母表上的符号,按一定的 规则组成的所有符号串集合。其中的每个符号串 称为句子。 【名词解释】:
2.3
2.3.2
主要语法成分的定义(续1)
三要素!
• 字母表 -- 元素(符号)的非空有限集合; • 符号串 -- 符号的有限序列; • 符号串集合 -- 有限个或者无限个符号串组成 的集合; • 规 则 -- 以某种形式表达的在一定范围内共 同遵守的章程和制度;这里,指符号串的组成 规则。
形式语言概念示例:
两个语言!
【例2.1】
L1={ 00,01,10,11 }; 字母表∑1= {0,1}, 句子有:00,01,10,11
推论:若 A为任一字母表,则 A* 就是该字母 表上的所有符号串(包括空串)的集合。
2.1.2
符号串集合的文法描述
长久以来,探讨符号串集合(即形式语言)的各种 描述方法,一直是语言计算机处理的重要任务之一。
【例2.5】
L ={ abnc | n≥0 }, 字母表:∑= {a,b,c}; 展开:L ={ac,abc,abbc,abbbc, … }
星推导 算符
Ⅱ.直接归约( => .
):
xy => . xAy
即:直接归约是直接推导的逆运算,用产生式的 左部非终结符替换右部符号串。 直接归约 + ): + β 加归约( => 算符 => . . (当且仅当 => . 1 => . 2 => . … => . β) 加归约 即:指一步或一步以上的直接归约运算。 算符 星归约( (当且仅当 星归约 * ): * β => => . . 算符 =β或 => . 1 => . 2 => . … => . β)
最左非终结符 给定一个符号串 i+i*i : 1. 最左推导(从开始符号出发)过程: E => E+T => T+T => F+T => i+T => i+T*F
=> i+F*F => i+i*F => i+i*i
+ => ∴ E ℓ i+i*i
最左可归约串
2. 最左归约(从符号串出发)过程: i+i*i => . F+i*i => . T+i*i => . E+i*i => . E+F*i => . E+T*i => E+T*F => . E+T => . E . + => ∴ i*i+i . ℓ E
① S => aAc => aεc = ac
② S => aAc => abAc => abεc = abc ③ S => aAc => abAc => abbAc => abbc …
+ abnc , n≥0 ∴ S =>
再一个句子!
2.2
形式语言是由文法定义的
什麽是文法 ?
2.2.1
【定义】 文法(grammar)是规则的有限集, 其中的上下文无关文法可定义为四元组: G(Z)=(VN, VT, Z, P) 每个元素
【例2.7】简单算术表达式文法
令
则
G(Z)= (VN, VT, Z, P)
VN ={ E(算术表达式),T(项),F(因式)}; VT ={ i(变量或常数),+,-,*,/,(,)}; Z = E ; P :
E -> T | E + T | E - T T -> F | T * F | T / F F -> i | ( E )
VN : VT : Z : P :
非终结符集(定义的对象集,如:语法成分等); 终结符集(字母表); 开始符号(研究范畴中,最大的定义对象); 规则集(又称产生式集); 每个规则
A -> 或者 A -> | 描述符号 : ->(定义为),|(或者是) 文法符号 : Z,A∈VN,,∈(VN+VT)*
【例2.2】
L2={ abmc,bn | m>0,n≥0 } 字母表∑2= {a,b,c}, 句型1: abmc , 有句子: abc, abbc, abbbc,… 句型2: bn ; 有句子: , b, bb, bbb,…
b0=(空符号串),b1=b,b2=bb,b3=bbb,… L1 为有限语言; L2 为无限语言。
A = ℓ A | d A |
※ 求解 I 值步骤:
正规方程式
① 先求解 A: A=(ℓ|d) A , A=(ℓ|d)2 A , … , A=(ℓ|d)n A
代入
A=
得: A= (ℓ|d)n , n≥0
代入 A= (ℓ|d)n , n≥0
② ∵ I=ℓ A | ℓ
得: I = ℓ (ℓ|d)n , n≥0 《标识符》:字母开头的字母、数字序列;
符号串集合运算示例:
【例2.3】 设 A={a,b},B={c,d} 则 A+B={a,b,c,d} 则 AB={xy|xA,yB}={ac,ad,bc,bd} 【例2.4】 设 A={a} 则 A* = A0∪A1∪A2∪…∪An∪… ={}+{a}+{aa}+{aaa}+… ={,a,aa,aaa,…} ={an|n≥0}
右图给出的表示 方法 --文法规则 ; 其中:
S -> aAc A -> bA |
⑴ S,A — 定义的对象(S 句子,最大的定义对象,又 称为开始符号; A为句型aAc的短语), ⑵ a,b,c -- 为字母表∑中的符号;ε- 空符号串。 ⑶ -> ,| -- 为描述符号( -> 定义为; | 或者是)