• /  81
  • 下载费用: 14.90积分  

短语、直接短语和句柄

'短语、直接短语和句柄'
2.4 短语、直接短语和句柄短语 令G是一个文法,S是文法的开始符号,假定αβδ是文法G的一个句型,如果有 + S??* αAδ 且 A?β 则称 β是相对于非终结符A的, 句型αβδ的短语。 2.4 短语、直接短语和句柄直接短语 令G是一个文法,S是文法的开始符号,假定αβδ是文法G的一个句型,如果有 S??* αAδ 且 A?β 则称β是直接短语。 2.4 短语、直接短语和句柄 注意:短语和直接短语的区别在于第二个条件, 直接短语中的第二个条件表示有文法规则 A?β ,因此,每个直接短语都是某规则右部。 2.4 短语、直接短语和句柄句柄 一个句型的最左直接短语称为该句型的句柄。句柄特征: (1) 它是直接短语,即某规则右部。 (2) 它具有最左性。 2.4 短语、直接短语和句柄 注意: 短语、直接短语和句柄都是针对某一句型的,都是指句型中的哪些符号串能构成短语和直接短语,离开具体的句型αβδ来谈短语、直接短语和句柄是无意义的。 2.4 短语、直接短语和句柄 例如 设有文法G[S]=({S,A,B},{a,b},P,S) 其中P为: S?AB A?Aa | bB B?a | Sb求句型 baSb的全部短语、直接短语和句柄。 2.4 短语、直接短语和句柄 分析 根据短语定义,可以从句型的推导过程 中找出其全部短语、直接短语和句柄。 对文法,首先建立该句型的推导过程: 最左推导: S?ABS??AB? bBB? baB?baSb A?Aa | bB ?最右推导: B a | Sb 句型 baSbS??AB ?ASb ?bBSb?baSb 2.4 短语、直接短语和句柄根据最左推导: S??* αAδ A ?+ β S??AB ?bBB?baB ?baSb(1) S??* S 句型本身是(相对于非终结符S) S +?baSb 句型baSb的短语。 (2) S??* baB 句型baSb中的子串Sb,是(相对 于非终结符 句型 的短语, B ?Sb B) baSb 且为直接短语。 2.4 短语、直接短语和句柄根据最右推导: S??* αAδ +S??AB ?ASb ?bBSb ?baSb A ? β (3) S??* bBSb 句型baSb中的子串a,是(相对 于非终结符 句型 的短语, B ?a B) baSb 且为直接短语、句柄。 (4) S??* ASb 句型baSb中的子串ba,是(相对 A ?+ba 于非终结符A)句型baSb的短语。 2.5 语法树与文法的二义性 推导和语法树 1. 语法树 对句型的推导过程给出一种图形 表示, 这种表示称为语法树,也称推 导树。 2.5.1 推导和语法树例如 设有文法G[E]: E?E+T | E–T | T T?T*F | T/F | F F?(E) | i构造句型i*i+i的语法树。首先给出句型的推导过程 (最左推导) :E?E+T?T+T?T*F+T?F*F+T?i*F+T ?i*i+T?i*i+F?i*i+i 2.5.1 推导和语法树根据推导过程构造句型i*i+i的语法树如下:E?E+T E ? T+T + ?T*F+T E T ?F*F+T T F ?i*F+T * ?i*i+T T F i ?i*i+F F i ?i*i+i i 2.5.1 推导和语法树 由例可知,语法树的构造过程是从文法的开始符号出发,构造一个推导的过程。 因为文法的每一个句型 (句子) 都存在一 个推导,所以文法的每个句型(句子) 都存在一棵对应的语法树。 2.5.1 推导和语法树 对句型i*i+i,还可给出最右推导: E?E+T E ?E+F E + T ?E+i ?T+i T F ?T*F+i T * F i ?T*i+i ?F*i+i F i * ?i i+i i2.5.1 推导和语法树 这也就是说,一棵语法树表示了一个句型的种种可能的(但未必是所有的)不同推导过程, 包括最左(最右)推导。 3.5.1 推导和语法树 2. 子树 E 语法树的子 E + T树是由某一结点 T F连同所有分枝组 T *成的部分。 F i F i i 3.5.1 推导和语法树 E 3. 简单子树 E + T 语法树的简单子树是指 T F只有单层分枝 T * F i的子树。 F i i 2.5.1 推导和语法树 句型的短语、直接短语和句柄的直观解释是: 短语:子树的末端结点形成的符号串是 相对于子树根的短语。 直接短语:简单子树的末端结点形成的 符号串是相对于简单子树根的直接短语。 句柄:最左简单子树的末端结点形成的 符号串是句柄。 2.5.1 推导和语法树短语: Eni*i+i E + Tni*in第一个i T Fn第二个i T * F in第三个in三个i都是直接短语 F in第一个i是句柄 i注意:i+i不是句型的短语 句子 i*i+i 2.5.1 推导和语法树 前例 对文法G[S]=({S,A,B},{a,b},P,S)其中P为: S?AB A?Aa | bB B?a | Sb 可用语法树非常直观地求出句型baSb的全部短语,直接短语和句柄。 2.5.1 推导和语法树 分析 首先根据句型baSb的推导过程画出对 应的语法树如下: SS?AB?bBB?baB?baSbS?AB?ASb?bBSb?baSb A B由语法树可知 b B S bbaSb 为句型的相对于S的短语 ba 为句型的相对于A的短语 a a 句型的相对于B的短语、直接短语和句柄 Sb 为句型的相对于B的短语、直接短语 2.5.2 文法的二义性 从前面的讨论可以看出,对于文法G中 任一句型的推导序列, 我们总能为它构造 一棵语法树,现在我们提出一个问题: 文法的某个句型是否只对应唯一的一棵语法树呢?也就是,它是否只有唯一的一个最左(最右)推导呢? 2.5.2 文法的二义性 例如 设有文法G[E]: E ? E+E | E*E | (E) | i 句子 i*i+i 有两个不同的最左推导,对应两棵不同的语法树。 2.5.2 文法的二义性 最左推导1 最左推导2 E?E+E?E*E+E E?E*E?i*E ?i*E+E?i*i+E ?i*E+E?i*i+E ?i*i+i ?i*i+i E E E + E E * E +E * E E E i ii i i i 2.5.2 文法的二义性 如果一个文法存在某个句子对应两棵不同的语法树,则说这个文法是二义性的。 或者说,若一个文法中存在某个句子,它有两个不同的最左 (最右) 推导,则这个文法是二义性的。 E ? E+E | E*E | (E) | i 2.5.3 文法二义性的消除 1. 不改变文法中原有的语法规则, 仅加进一些非形式的语法规定。 E E + E E * E i i i 2.5.3 文法二义性的消除 2. 构造一个等价的无二义性文法。即 把排除二义性的规则合并到原有文法中, 改写原有的文法。 例如,对于上例文法G[E],将运算符的 优先顺序和结合规则:*优先于+; +、*左结合加到原有文法中, 可构造出无二义 性文法如下 : 2.5.3 文法二义性的消除 E?E+T | T E T?T*F | F E + T F?(E) | i T F则句子i*i+i只有 * T F i唯一一棵语法树: F i i 2.5.3 文法二义性的消除 例2 定义某程序语言条件语句的文法G为: S?if b S | if b S else S | A (其它语句)试证明该文法是二义性的并消除之。 分析 该文法的句子 if b if b A else A 对应下面两棵不同的语法树: 2.5.3 文法二义性的消除 S?if b S | if b S else S | A 句子 if b if b A else A S Sif b S else S if b S if b S A if b S else S A A A 所以该文法是二义的。 2.5.3 文法二义性的消除 消除文法的二义性可采用下面两种方法: 1. 不改变已有规则,仅加进一非形式的语法规 S定: 与前面最接近 else if b S的不带else的 if 相对。文法G的句子 if b S else S if b if b A else A A A只对应唯一的一棵语法树,消除了二义性。 2.5.3 文法二义性的消除 2. 改写文法G为G'G: S?if b S | if b S else S | A (其它语句)G': S? S1 | S2 S1? if b S1 else S1 | A S2? if b S | if b S1 else S2 2.5.3 文法二义性的消除 这是因为通过分析,得知引起二义性的原因是: if—else 语句的 if 后可以是if型,因此改写文法时规定:if — else之间只能是if—else语句或其他语句。 2.5.3 文法二义性的消除 ?S S1 | S2 S S1? if b S1 else S1 | A S2 S ? if b S | if b S else S 2 1 2 if b S对改写后的文法,句子 S1 if b if b A else A 只对应唯一的一棵语法 if b S1else S1树。 A A 2.5.3 文法二义性的消除 应该指出的是文法的二义性和语言的二义性是两个不同的概念。 通常我们只说文法的二义性, 而不说语言的二义性, 这是因为可能有两个不同的文法G和G' ,而且其中一个是二义性的,另一个是无二义性的, 但却有L(G)=L(G'), 即这两个文法所产生的语言是相同的。 2.5.3 文法二义性的消除 将一个语言说成是二义性的,是指对它不存在无二义性的文法,这样的语言称为先天二义性的语言。 例如 L={ ai bj ck | i=j 或 j=k 且 i, j, k≥1}便是这种语言。 2.6 文法和语言的分类 著名的语言学家乔姆斯基(Chomsky) 将文法和语言分为四大类,即0型、1型、 2型、3型。划分的依据是对文法中的规则施加不同的限制。 2.6 文法和语言的分类 型文法描述的语言是Ø00型文法(无限制文法) 0型语言。若文法G=(VN,VT, P, S)中的每条规则 是这样一种结构: α?β 0型语言由 + * α?(VN∪VT) , β?(VN∪图V灵T)机识别。而且α中至少含一个非终结符, 则称G 是0型文法。0型文法没有加任何限制条件,又称为 无限制性文法,相应的语言称为无限制 性语言。 2.6 文法和语言的分类 例如,有0型文法G=(VN,VT, P, S) 其中:VN={A,B,S} , VT={0,1} P: S ? 0AB 1B ? 0 B ? SA | 01 A1 ? SB1 A0 ? S0B STOP其描述的 0 型语言为 L0(G[S])={ } 2.6 文法和语言的分类 Ø 型文法(上下文有关文法) 1 1型文法描述 的 若文法 中的每一条规则的 G=(VN,VT, P, S) 语言是1型语言。 形式为 αAβ ?αμβ , 其中: * +A?VN , α, β?(VN∪VT) , μ?(VN∪VT) 则称G是1型文法。 1型语言由线性界 1型文法也称为上下文限有自关动文机法识,别 。相应 的语言又称为上下文有关语言。 2.6 文法和语言的分类 例如,有1型文法G=(VN,VT, P, S) 其中:VN={S,A,B} , VT={a,b,c} P: S? aSAB | abB BA ? BA' BA' ? AA' AA' ? AB bA ? bb bB ? bc cB ? cc n n n 其描述的1型语言为L1(G[S])={a b c | n≥1} 2.6 文法和语言的分类 Ø2型文法(上2型下文文法无描述关的文语法) 言是2型语言。 若文法G=(VN,VT, P, S)中的每一条规则的 形式为 A ?β , 其中: 2型语言由下推 * A?VN , β?(VN∪自V动T机) 识别。则称G是2型文法。 2型文法又称上下文无关文法,其产生的语言又称为上下文无关的语言。 2.6 文法和语言的分类 例如前面描述算术表达式的文法G[E]: E?E+E | E*E | (E) | i 2.6 文法和语言的分类 例如,有2型文法G=(VN,VT, P, S) 其中:VN={S, A, B} , VT={a, b} P={ S? aB | bA A? a | aS | bAA B? b | bS | aBB } 其描述的语言为 + L2(G[S])={x | x ? {a, b} 且x中a和b的个数相同} 2.6 文法和语言的分类 Ø3型文法(正规文法) 若文法G=(VN,VT, P, S)中的每一条规则的形式 为A ?aB 或 A ?a , 其中:3 型文法描述的语言 * A , B?VN, a ?VT , 则称G是是3右型线语性言文。法。 若文法G=(VN,VT, P, S)中的每一条规则的形式 为A ?Ba 或 A ?a , 其中: * 型语言由有穷 A , B?VN , a ?VT , 则称G3是左线性文法。 右线性文法和左线性文法都称自为动3机型识文别法。。 3型文法也称正规文法。正规文法产生的语言 称为正规语言。 2.6 文法和语言的分类 例如,用左线性正规文法和右线性正规文法定义标识符 用I代表标识符; l代表任意一个字母; d代表任意一个数字; 则定义标识符的文法为: 左线性文法: 右线性文法: P: I→ l | Il | Id P: I→ l | lT T→l | d | lT| dT 2.6 文法和语言的分类 例如,用左线性正规文法和右线性正规文法定义无符号整数 用N代表无符号整数; d代表任意一个数字;则定义的无符号整数文法为: 左线性文法: 右线性文法: P: N→ Nd | d P: N→ dN | d 2.6 文法和语言的分类 由上述四类文法的定义可知, 从0型文法到3型文法, 是逐渐增加对规则的限制条件而得到的,因此每一种正规文法都是上下文无关的文法,每一种上下文无关的文法都是上下文有关的文法,而每一种上下文有关的文法都是0型文法, 而由它们所定义的语言类是依次缩小的,有 L0 ? L1 ? L2 ? L3 。 2.7 有关文法的实用限制和变换 文法是用来描述程序设计语言的,在 实际应用中需要对文法加一些限制条件。 对文法的实用限制有以下两点: 1. 文法中不能含有形如A →A 的规则。这种规则我们称之为有害规则。 2.7 有关文法的实用限制和变换 2. 文法中不能有多余规则。所谓多余规则是指文法中出现以下两种规则: (1) 某条规则 A ?α 的左部符号A不在所属文法的任何其他规则右部出现,即在推导文法的所有句子中始终都不可能用到的规则。 (2) 对文法中的某个非终结符A,无法从它推出任何终结符号串来。 2.7 有关文法的实用限制和变换 例如 设有文法G[S]: 删除多余规则后的 文法变换为: P: S? Bd A? Ad | d P: S? Bd B? Cd | Ae B? Ae ? C? Ce A Ad | d D? e 2.7 有关文法的实用限制和变换 若程序设计语言的文法含有多余规则, 其中必定有错误存在,因此检查文法中是否含有多余规则对我们来说是很重要的。 作业 P26 2.1 2.2(2) 2.3 L1,L2 ,L3 2.7 2.8 2.9 2.11 2.12 本章小结 本小结花时45分钟2004/2/28 本章重点介绍了语言的语法结构的形式描 述、语法树以及文法的二义性, 主要内容有: 1. 设计一个文法定义一个已知的语言 (1) 文法是一个四元组 G=(VN,VT, P, S), 文法四大要素中,关键是一组规则, 它定义(或描述)了一个语言的结构。 从文法定义可知, 文法对于程序设计者来 说,文法给出了语言的精确定义和描述。 本章小结 (2) 分析已知语言句子的结构特征, 设计出相应的一组规则,但不唯一。(3) 设计的文法必须能定义已知的语言, 不能超出或缩小所定义语言的范围。 (4) 若语言是无穷集合, 设计该语言的文 法一定是递归的。 本章小结 n m 例1. 给出语言 L2={a b | m≥n≥1} 的文法 分析 根据语言句子的结构特征,设计出相 应规则 L2={ab,abb,abbb, …aabb,aabbb,aabbbb, … aaabbb, aabbbb,…} P2: S→AB A→aAb | ab B→bB |ε 本章小结 2n+1 例2. 给出语言 L1={a |n≥0} 的文法 分析 根据语言句子的结构特征,设计出相 应规则 L1={a, aaa, aaaaa, aaaaaaa, aaaaaaaaa,…} : P1 A→aAa | a 或 P1': A→aB | a B→aa | aBa 本章小结 n m k 例3. 给出语言L3={a b c | n,m,k≥0}的文法 分析 根据语言句子的结构特征,设计出相应规则 L3={ε,a,aa,aaa…,b,bb,bbb…,c,cc,ccc, …, ab,abb, …,bc,bcc,…}P3: A→aA | bB | cC |ε P3': A→aA | B B→bB | cC |ε 或 B→bB | C C→cC |ε C→cC |ε 本章小结 例4. 写一个 文法,使其语言是正偶数的集合,每个偶数不以0开头。 分析 不以0开头的偶数集合中串的结构特征: L4={0 ,2,4,6,8,10,12,14,16,18,20,22,24,26,…} P ': P4: N→E | AE 或 4 A→D | AD′ N→0 | 2 | 4 | 6 | 8 |BN D→1 | 2 | 3 | …| 9 B→1 | 2 | 3 | …| 9 |B0 D'→0 | 1 | 2 | 3 |…| 9 E→0 | 2 | 4 | 6 | 8 本章小结例5. 给出语言L={1n0m1m0n | n,m≥0}的 文法。分析 根据语言句子的结构特征, 设计 出相应规则 L={ε,01,0011,…,10,1100,…,1010,100110, 110100,11001100…} P : S → 1S0 | 0A1 | ε A → 0A1 | ε 本章小结 例6. 给出语言L={WaWt | W∈{0|1}*,Wt 表示W的逆的文法。 分析 根据语言句子的结构特征,设计 出相应规则W={ε,0, 1 ,01, 10, 00, 11, 101, 110, 100, 111, …}L={a, 0a0, 1a1, 01a10, 10a01, 00a00, 11a11, 101a101, 110a011, 100a001, …} P : S → a | 0S0 | 1S1 本章小结2. 已知一个文法,确定该文法所定义的 语言。 (1) 文法所定义的语言 * L(G[S])={x|S ?x且x∈VT*} (2) 给定一个文法,可根据语言和推导定 义推导出文法的句子,从而确定出该文法 所定义的语言。 本章小结(3) 语言可用 ①自然语言描述。 例如, L={x|x∈{a,b}+且x中a,b个数相同}②式子描述。例如 L={a2nbb | n≥0}。③正规式描述。 本章小结 例1 文法G[A]=({A},{a,b},{A→bA | a}, A) 所生成的语言是什么? 分析 ∵ A?bA?bbA?bbbA?…?bnA?bna ∴ L(G[A])={ bna | n≥0 } 本章小结例2 文法G[N]为: N →ND | D D →0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 (1) G[N]所生成的语言是什么? (2) 给出句子0127的最左、最右推导。 本章小结 N →ND | D D →0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 L(G[N])={α | α∈{0,1,2, …9}+} ={α | α为可带前导0的正整数} ={α | α为数字串}最左推导: N?ND?NDD?NDDD?DDDD ?0DDD?01DD?012D?0127最右推导: N?ND?N7?ND7?N27?ND2 7 ? N127?D127?0127 本章小结 例3. 已知文法G[S]=( {A,B},{a,b,c,d}, P, S ) , 其中 P 为: S → AB A → aAb | ab B → cBd | cd 该文法 所生成的语言是什么? 分析 ∵ S?AB?aAbB?a2Ab2B?… ?an-1Abn-1B?anbnB?anbncBd ? anbnc2Bd2 ? … ? anbncm-1Bdm-1?anbncmdm ∴ L(G[S])={anbncmdm | n ,m≥1 } 本章小结3. 求句型的短语、直接短语和句柄 (1) 短语、直接短语和句柄是对某句 型而言的。 (2) 短语总是句型的某个子串,它对应 子树未端结点形成的符号串。 (3) 直接短语是某条规则右部,它对应 简单子树未端结点形成的符号串。 (4) 最左边的直接短语是句柄。 本章小结 2.9相似 例1 已知文法G[E]:E→E+T | E-T | T T→T*F | T/F | T T→(E) | i 证明 E+T*F是它的一个句型,指出这个句型的短语﹑直接短语和句柄。∵ E?E+T?E+T*F 画出该句型的语∴ E+T*F是它的一个句型。法树: E 短语: E+T*F、T*F直接短语: T*F E + T句柄: T*F T * F 本章小结 2.11 例2 已知文法G[S]: S→(AS) | (b) A→(SaA) | (a) 试找出符号串(a)和(A((SaA)(b)))的短语﹑ 直接短语和句柄(如果有的话)。分析 ∵ S?(AS)?((a)S)?/ (a)) ∴ 符号串(a))不是文法的句型,因此它没有短语﹑直接短语和句柄。 本章小结 S→(AS) | (b) A→(SaA) | (a) ∵S?(AS)?(A(AS))?(A(A(b))) ?(A((SaA)(b)))∴符号串(A((SaA)(b)))是文法的句型,画出该句型的语法树如下图: 本章小结 S→(AS) | (b) S A→(SaA) | (a) ( A S )对于句型(A((SaA)(b))) ( 从句型的语法树求 A S ) 短语: ( S a A ) ( b ) (A((SaA)(b))) 直接短语:(SaA)、(b) ((SaA)(b)) 句柄: (SaA) (SaA) (b) 本章小结4.文法二义性的判断 一个文法存在某个句子对应两棵不同的语法树或对应两个不同的最左(最右)推导,则该文法是二义性的。 本章小结例1 设有文法G[S]: S→iSeS| iS | i 试证明文法G[S]有二义性。 分析 因为对文法的句子 iiiei 有如下两 棵不同的语法树与之对应,所以该文法 是二义的 本章小结 S→iSeS| iS | i句子 iiiei 对应下面两颗语法树: S S i S e S i S i S i i S e S i i i 本章小结 例2 设有文法G[N]: N→SE | E S→SD | D E→0 | 2 | 4 | 6 | 8 | 10 D→0| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 1. 试证明文法G[N]有二义性。 2. 此文法所描述的语言是什么? 3. 试写出另一文法G'使L(G')=L(G)且 G'是无二义性的。 本章小结N→SE | ES→SD | DE→0 | 2 | 4 | 6 | 8 | 10D→0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 N分析 因为对文法的 N句子10有两棵不同的
关 键 词:
短语、直接短语和句柄 ppt、pptx格式 免费阅读 下载 天天文库
 天天文库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
关于本文
本文标题:短语、直接短语和句柄
链接地址: https://www.wenku365.com/p-39767895.html
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服点击这里,给天天文库发消息,QQ:1290478887 - 联系我们

本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有【成交的100%(原创)】。本站是网络服务平台方,若您的权利被侵害,侵权客服QQ:1290478887 欢迎举报。

1290478887@qq.com 2017-2027 https://www.wenku365.com 网站版权所有

粤ICP备19057495号 

收起
展开