7 语法分析 语法树 二义性文法.ppt

第三章：语法分析  语法树 二义性文法 正则文法与自动机 内容介绍 语法树 文法的二义性 正则文法与自动机 1.1 语言树的定义 语法树：设G是给定的语法，称满足下列条件的树为G的一棵语法树： 1. 树的每个节点都标有G的一个语法符号，且根节点标有初始符S。 2. 如果一个非叶节点A按从左到右顺序有n个儿子节点B1、B2、…、Bn，则: A?B1B2…Bn 一定是G的一个产生式. 1.1 语言树的定义 例子：有文法 E ?E+T E ?T T ? T *F T ?F F ? ( E ) | i 1.2 语法树的作用 作用主要有两点： 语法树反映出我们推导的过程，每一步节点的生长过程都可以对应到我们的一步推导。 语法树反应出串的语法结构。 1.3 语法树和语法概念的关系 子树：某语法树T中的某一节点A和它所有分支组成的树T，则称T是T的一颗子树。 简单子树：某一节点A与其子节点（单层节点）组成的树。从严格意义上来说，A应该有且仅有一层子节点。 1.3 语法树和语法概念的关系 结论 语法树的所有叶节点（从左到右）组成的是一个句型 语法树的子树所有叶节点（从左到右）组成的是一个短语 简单子树所有叶节点（从左到右）构成一个简单短语 最左简单子树叶节点对应的是一个句柄 1.3 语法树和语法概念的关系 例子：(T+i)*F+i 2.1 文法的二义性 定义：设存在文法G，若G的某一个句子存在两棵不同的语法树，则称G为二义性文法。 例1：表达式文法E ?E+E|E*E|(E)|i 对于i+i*i有： 2.1 文法的二义性 例2，PASCAL语言中的条件语句： 正常 if (E) then S1 else S2 简写 if (E) then S1 二义性：if (E1) then S1 if (E2) then S2 else S3 2.2 文法二义性的判定和利用 文法二义性的判断 目前，不存在一个一般性的方法来判断一个现有文法是否为二义性文法。 常用的经验性判断: S?SS|a 可以推导出SSS串，必有二义性 S?S+S 可以推导出S+S+S，必有二义性 2.2 文法二义性的判定和利用 文法二义性的利用 对二义性文法进行修改，消除其二义性会导致文法的复杂程度和符号数目迅速升高。 可以利用二义性文法状态少，分析快的特点，使用二义性文法，对具体问题加入语义规则，约束其二义性即可。 3.1 正则文法和DFA间的关系 定理：正则文法（3型文法）与DFA等价 构造性证明：给定一个正则文法G(VN, VT, P, S) 构造一个等价的DFA A(?,S,S0,f, Z)，使得L(G)=L(A)。 3.2正则文法到DFA的转换 构造方法： 令S=VN∪{k}； ?=VT ； S0=Z; F={k}; 转换函数f 如果有X?aY 则构建f(X,a)=Y 如果有X?a 则构建f(X,a)=k 例子： Z?aZ|bB|c B?dB|b 3.3 DFA到正则文法的转换 构造方法 令Z={A|A∈Z，A没有输出边}; S=S0; VN=S-Z; VT=?; 规则P： 若有f(X,a)=Y，且Y?Z，则构建X?aY； 若有f(X,a)=Y，且Y∈Z ，则构建X?a； 若干历年考试题 构造一个文法G，使L(G)={anbmck|m=n+k,n≥1,m1,k≥1} G[S]: S?AB ???????? A?aAb| ab ???????? B?bBc| bc 若干历年考试题 ?已知文法G[Z]: Z?WV? W?aB?|?aW?|?a??? B?b?|?bB? V?bV?|?dD? D?d?|?dD 判断文法G[Z]是否为二义性文法，如果是请举例 句子abdd有两棵语法树。 若干历年考试题 设有一个文法G[S]: S-V V-T|ViT T-F|T+F F-V*|[ 句型F+Fi[的短语，简单短语和句柄分别为： 首F,F+F, F+Fi[, [ 首F,[； 首F。 * * 上一次课给大家介绍了形式语言的一些基础知识，提出了一些基础概念，同学们可以从两个角度来理解，1、我们从文法的开始符出发，推导出一个符号串，按照定义来说这个串是一个句子，这个句子映射到我们程序设计语言中就是用户写的一个程序，要验证这个程序有没有语法错误，就是从开始符出发一步一步推导看看能不能把这个程序推导出来，这里的定义就涉及到句型 句子 语言，2、从另外一个角度来看，我们要验证一个串是不是文法的句子可以反过