第二章-形式语言理论.pptVIP

语法树的相关概念 结点：每个树的结点对应于一个符号。结点的名字就是该符号。 边：两个结点之间的连线。 根结点：没有边进入的结点。 分支：某个结点向下射出的边和其结点称为分支。 末端结点：没有向下射出的边的结点成为末端结点。在相对于句型的语法树中，末端结点可能是非终结符号。 语法树的特征 给定文法G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的语法树。这棵树具有下列特征： 根结点的标记是开始符号S； 每个结点的标记都是V中的一个符号； 若一棵子树的根结点为A，且其所有直接子孙的标记从左向右的排列次序为A1A2…AR，那么 A → A1A2..AR一定是P中的一条规则； 若一标记为A的结点至少有一个除它以外的子孙，则A∈VN。 构造语法树 方法：把开始符号做为根结点，对每一步直接推导画一个分支，分支的名字是所用产生式右部的符号（按左右顺序依次出现），分支的个数是产生式右部符号串的长度。以此往下，直到再无分支可画结束。 例如：文法G[S]: S→AB, B→cBd, A→ab, B→cd 符号串abccdd的推导过程如下： S?AB?AcBd?Accdd?abccdd S B B d b a A c d c S （1） S B A （2） S B B d A c （3） S B B d b a A c d c （5） S B B d A c d c （4） S?AB?AcBd?Accdd?abccdd 例4：已知文法G：E→E+T|T，T→T×F|F，F→（E）|i 求句型T+T×F的推导过程与语法树。 E E T + T F T × E=E+T =T+T=T+T×F E E T + T F T × E=E+T =E+T×F =T+T×F 从语法树中看不出句型中的符号被替代的顺序。 2.5 文法和语言的一些特性 无用非终结符：某个非终结符不出现在文法的任何一个句型中，并且不能从它推出终结符号串。含有该非终结符的规则即不可终止。 不可达文法符号：如果一个非终结符（开始符号除外）不出现在该文法的任何其他的产生式的右部。该非终结符为不可达文法符号，含有该非终结符的规则即不可达规则。 有害规则：U→U ，无用且引起文法的二义。 可空非终结符： 2型文法允许以下产生式 S→ε，该产生式称为空产生式，S称为可空非终结符。在消除左递归方法中用到空产生式。 例如：文法G[S]： （1）S→Be （2） B→Af （3） A→Ae （4） A→e （5） C→Cf （6） D→f 多余规则为：（5）不可终止 （6）不可到达 最左推导、最右推导和规范推导 最左推导：是指对于一个推导序列中的每一步直接推导 α=β，都对 α 中的最左非终结符进行替换。 最右推导：是指对于一个推导序列中的每一步直接推导 α=β，都对 α 中的最右非终结符进行替换。 最右推导也称为规范推导，用规范推导推导出的句型称为规范句型。 例5：已知文法G[S]：S→AB，A→A0|1B，B→0|S1 求句子101001的最右、最左推导。 S右=AB=AS1=AAB1=AA01 =A1B01=A1001=1B1001=101001 S左=AB=1BB=10B=10S1=10AB1 =101BB1=1010B1=101001 例如：文法G：E→E+E|E×E|（E）|i 句子 i×i+i 对应的语法树 最左推导1：E?E+E?E×E+E?i×E+E?i×i+E?i×i+i 最左推导2：E?E×E?i×E?i×E+E?i×i+E?i×i+i i E E + E E E × i i E E E × i E E + i i 文法的二义性(Ambiguity) 如果一个文法存在某个句子对应两棵或者两棵以上不同的语法树，则说这个文法是二义的。二义性文法存在某个句子,它有两个不同的最左（右）推导。 二义性的文法将给编译程序的执行带来问题。当编译程序对二义性文法生成的句子结构进行语法分析时，就会产生两种甚至更多种不同的理解。语法结构上的不确定性，必将导致语义处理上的不确定性。因此，希望描述语言的文法是无二义性的。 消除文法的二义性 方法一：不改变文法中原有的语法规则，仅加进一些语法的非形式规定。 方法二：构造一个等价的无二义性的文法，即把排除二义性的规则合并到原有文法中，改写原有的文法。 2.6 分析方法简介 对于2型文法，如何识别一个符号串是否为某文法的句型或句子，有两种分析方法： 自顶向下分析法 (