第六章 上下文无关文法

《第六章 上下文无关文法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第六章上下文无关文法第6章习题：题1，题3，题11，题12，题13，题14，题16第六章上下文无关文法上下文无关文法相关概念2标识符、整数、实数上下文无关文法等符号串的词法规则问题提出：1、正则语言描述模型能力有限，无法描述高级程序设计语言表达式中“良嵌套”的括号对、(begin…end)以及HTML中标记对…等配对符号序列的语法规则。例如，描述L（G）={(n1)n1(n2)n2…(nk)nk}的文法G：S→S（S）

2、ε2、高级程序设计语言语法结构绝大多数都用上下文无关文(CFG)描述。上下文无关文法定义6-

3、1：对于所有产生式A→β，均有

4、β

5、≥

6、A

7、，并且，A∈V,β∈(V∪T)∗，文法G=（V，T，P，S）被称为上下文无关文法。特点：对于所有A∈V，如果A→β∈P，则无论A出现在句型的什么位置，都可以用β替换A，无需考虑A的上下文。例如，设文法G=S→AB，A→aA

8、a，B→bB

9、b；对于任意n≠m，有anbm∈L(G)，A产生a的个数不受B产生b的个数的限制。上下文无关文法L(G1)={w∈{0,1}*

10、w=wT}。例：构造上下文无关文法G，使L(G)={wwT

11、w∈{0,1}*}。句子结构特征-字符串及其逆：按递归定义定

12、义文法：1、句子从中间分为两个部分：由基础语句：W=a1a2…an,WT=an…a2a1S→εWWT=a1a2…anan…a2a1由归纳语句：2、递归定义语言：S→0S0

13、1S1a)∀a∈{ε},a∈L;b)如果x∈L,则∀a∈{0,1},故有,G=({S},{0,1},P,S)axa∈L；P：S→0S0

14、1S1

15、εc)所有满足a)b)的字符串属于L。上下文无关文法定义6-2：设有CFGG=（V,T,P,S），G的派生树是满足如下条件的有序树：1、树的每个节点都有一个标记X，X∈V∪T∪ε。2、树的根节点的标记为S。3、如果

16、X是一个非叶节点的标记，则有X∈V。4、如果一个非叶节点v的标记为A，v的子节点从左到右依此为v1,v2,…,vn,并且，它们分别标记为X1,X2,…,Xn，则有A→X1,X2,…,Xn∈P。5、如果一个节点v标记为ε，则v是该树的叶节点，并且，v是其父节点的唯一子节点。上下文无关文法定理6-1：∗设CFGG=（V,T,P,S），S⇒α的充分必要条件为G有一棵结果为α的派生树。α是从派生树根节点S开始推导、由树的叶节点构成的一个句型。相关概念多种派生方式文法的化简规则文法的规范形式多种派生方式定义6-3：设CFGG=（V,T

17、,P,S），α是G的一个句型。如果在α的派生过程中，每一步都是对当前句型的最左变量进行替换，则该派生为最左派生，每一步所得到的句型叫做左句型。如果在α的派生过程中，每一步都是对当前句型的最右变量进行替换，则该派生为最右派生，每一步所得到的句型叫做右句型。最左派生被视为规范派生，常被计算机系统用来处理输入字符串。多种派生方式例：算术表达式的派生文法：多种派生方式按不同方式派生算术表达式x+x/y↑2：最左派生最右派生非左、非右派生文法的歧义性：同一表达式“x+x/y↑2”可对应多种不同的派生树：相关概念多种派生方式文法的化简规

18、则文法的规范形式文法的化简规则问题提出：根据语言的结构特征构造文法时，由于使用的符号及定义的产生式不恰当，可能会引入一些多余或者错误的符号。文法的化简规则例：设语言L={0x

19、x∈{0,1}*}∪{0x_y

20、x∈{0,1}*,y∈{0,1}+}构造语言描述文法G1：1、G1中的无用符号：i)终极符2不应出现，相关产生式无用ii)派生句型过程不会涉及变元D，相关产生式无用；iii)变元E一旦出现，则永远不会消失，其不能构成句子，相关产生式无用；例：设语言L={0x

21、x∈{0,1}*}∪{0x_y

22、x∈{0,1}*,y∈{0,1

23、}+}iiii）对于ε∈L(G1),产生式A→ε无用v）A→B为单一产生式，产生式无用2、删除无用符号及其相关产生式；3、删除单一和ε-产生式时，需保证原有文法的语义不变。文法的化简规则删除无用符号删除ε-产生式删除单一产生式文法的化简规则-删除无用符号定义6-4：设CFGG=(V,T,P,S)。对于任意X∈V∪T，如果存在w∈L(G)，X在派生w的过程中出现，即，存在α,β∈(V∪T)*，使得**S⇒αXβ⇒w则称X是有用的；否则，称X是无用符号。利用定义6-4中公式：w∈T*，使得X⇒*w，逆向地寻找有用语法变元以及与其

24、相关的产生式。算法6-1输入：CFGG=(V,T,P,S)；输出：CFGG’=(V’,T,P’,S)，其中，V’不包括不能推出终极符号串w的变量且L(G’)=L(G)V’包含所有有用语法变元；从P中挑选与V’、T中变元A终极符号a相关的产生式，构成P’。利用定义6-4中公式：α,β∈(V∪