【7A文】上下文无关文法及其语法树.ppt

《【7A文】上下文无关文法及其语法树.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、软件教研室　徐慧英　吕振洪来自www.3722.cn中国最大的资料库下载上下文无关文法及其语法树文法和语言一、语法树（推导树）直观定义：用图表示上下文无关文法句型的推导的直观方法。语法树有助于理解一个句子的语法层结构的层次，语法树通常表示成一棵倒立的树，根在上，枝叶在下。2.形式定义对文法G=(VN,VT,P,S)相关联的语法树满足以下4个条件：（1）根结点由开始符号S所标记；（2）每个结点都有一个标记，此标记是V(即VN∪VT)的一个符号；（3）非终结符VN中的结点至少有一个除它自己以外的子孙结点；（4）对产生式A

2、→A1A2…Ak，结点A1,A2,…,Ak是结点A的直接子孙，顺序与产生式相同。软件教研室　徐慧英　吕振洪来自www.3722.cn中国最大的资料库下载从根结点S开始推导，当非终结符被它的某个候选式所替换时，这个非终结符的相应结就产生出下一代新结，候选式中自左向右的每个符号对应一个新结，并用这些符号标记其相应的新结。每个新结与其父结点间都有一条连线。在一棵语法树生长过程中的任何时刻，所有那些没有后代的端末结自左向右排列起来就是一个句型。语法树构造的过程例1文法G=({E},{+,*,i,(,)},P,E)，其中P为：

3、E→E+E

4、E*E

5、(E)

6、i对该文法关于(i*i+i)的推导的语法树如下所示：文法和语言软件教研室　徐慧英　吕振洪来自www.3722.cn中国最大的资料库下载接语法树构造举例文法和语言E(根)（E）E++EE*Eiii代次12345软件教研室　徐慧英　吕振洪来自www.3722.cn中国最大的资料库下载文法和语言语法树的问题分析（1）允许产生同名结点（反映递归性）；（2）没有后代的结点为端末结；（3）语法树不能反映生养后代的先后；（4）一棵语法树表示了一个句型种种可能的（但未必是所有的）不同推导过程。软件教研室　

7、徐慧英　吕振洪来自www.3722.cn中国最大的资料库下载文法和语言最左推导/最右推导/规范句型最左推导是指：任何一步α=>β都是对α中的最左非终结符进行替换。同样，可定义最右推导（又称规范推导）：任何一步α=>β都是对α中的最右非终结符进行替换。由规范推导所得到的句型称为规范句型。注意：从一个句型到另一个句型的推导过程往往是不唯一的。例如E+E(i+i)：（a）E+E=>E+i=>i+i——最右推导（b）E+E=>i+E=>i+i——最左推导软件教研室　徐慧英　吕振洪来自www.3722.cn中国最大的资料库下载

8、语法树的特点文法和语言一棵语法树是这些不同推导过程的共性抽象，是它们的代表。一棵语法树完全等价于一个最左（右）推导，这种等价性包括树的步步生长和推导的步步展开是完全一致的。例:推导(i*i+i)最左推导：E=>(E)=>(E+E)=>(E*E+E)=>(i*E+E)=>(i*i+E)=>(i*i+i)最右推导：E=>(E)=>(E+E)=>(E+i)=>(E*E+i)=>(E*i+i)=>(i*i+i)但两种推导的语法树相同。软件教研室　徐慧英　吕振洪来自www.3722.cn中国最大的资料库下载文法和语言一个句型是

9、否只对应唯一的一棵语法树？例如对于文法G[E]：E→E+E

10、E*E

11、(E)

12、i，关于(i*i+i)存在一个与前面不同的最左推导：E(E)(E*E)(i*E)(i*E+E)(i*i+E)(i*i+i)它所对应的语法树如右图：E(根)（E）E*EE+Eiii软件教研室　徐慧英　吕振洪来自www.3722.cn中国最大的资料库下载文法和语言1.定义：一个文法的某个句子对应两棵不同的语法树，则这个文法是二义的。或一个文法的某个句子有两个不同的最左（右）推导，则这个文法是二义的。二、二义性(1/2)2.区别文法的二义性：存在两

13、个不同文法G(二义)、G’(无二义)，却有L(G)=L(G’)，即产生语言相同。语言的二义性软件教研室　徐慧英　吕振洪来自www.3722.cn中国最大的资料库下载二义性其它问题文法和语言人们已证明，二义性问题是不可判定的，即不存在一个算法，它能在有限步骤内，确切地判断一个文法是否是二义的。我们所能做的就是为无二义性寻找一些充分条件，例如对文法G[E]：E→E+E

14、E*E

15、(E)

16、i修改，规定运算符“+”与“*”的优先关系和结合规则，设“*”的优先性高于“+”，且服从左结合。G’:E→T

17、E+TT→F

18、T*FF→(E

19、)

20、i软件教研室　徐慧英　吕振洪来自www.3722.cn中国最大的资料库下载文法和语言3.6句型的分析句型分析的任务就是按文法的产生式，识别输入的符号是否是该文法的句型。语法树——是句型推导过程的几何表示，可以十分直观的显示某句型的结构。因此在句型时，对输入符号串构造语法树，以此识别它是否是该文法的一个句型（或句子）。因此，语法树又可称为语法