第二章 形式语言基础(3).ppt

11南京邮电大学计算机学院蒋凌云******@:《编译技术原理及其实现方法》piler piler Principles22第二章第二章形式语言基础知识形式语言基础知识§ 语法分析初步一、、§ 语法分析初步一、、§§ 语法分析初步语法分析初步一、自顶向下语法分析(导出法)一、自顶向下语法分析(导出法),利用其中产生从文法的开始符号出发,利用其中产生式,逐步推导出要分析的符号串式,逐步推导出要分析的符号串。换言之,对于任何给定的。换言之,对于任何给定的输入串,试图用一切可能的办法,从文法开始符号出发,自输入串,试图用一切可能的办法,从文法开始符号出发,自上而下、从左到右地为输入串建立语法树。这种分析过程本上而下、从左到右地为输入串建立语法树。这种分析过程本质上是一个试探过程,是反复使用不同规则谋求匹配输入串质上是一个试探过程,是反复使用不同规则谋求匹配输入串的过程。的过程。55第二章第二章形式语言基础知识形式语言基础知识§ 语法分析初步一、、§ 语法分析初步一、自顶向下语法分析(导出法)2. 分析方法例如:设有文法G=(VN,VT,P,S),其中VN={S,A} VT={a,b,c,d} P: S∷=cAd A∷=ab|a试分析符号串x=?cAd?cad容易判断出x=cad是该文法的句子。若用画语法树的方法我们同样可以判断出cad是文法的句子。aa77(1)为了自上而下为符号串x建立语法树,首先将文法的开始符号S作为树的根结点,并设输入串指针i指向其第一个符号c,,其过程如下:若按自上而下语法分析程序的步骤进行分析判断,其过程如下:P: SP: S∷∷=cAd A=cAd A∷∷=ab|a=ab|SS??cAdcAdcadcadii88(2)此时该树最左边末结点c与x的第一个符号c相匹配,于是调整指针i使其指向输入串下一符号a。我们再试图让树的中间端末结点A去匹配a,显然,由于A是非终结符,它不可能直接与终结符a匹配,我们只得在文法中选择以A为左部的产生式,这里以A为左部的产生式有两个,我们试着用第一个选择来匹配输入串,并扩展语法树。若按自上而下语法分析程序的步骤进行分析判断,其过程如下:若按自上而下语法分析程序的步骤进行分析判断,其过程如下:P: SP: S∷∷=cAd A=cAd A∷∷=ab|a=ab|SS??cAdcAd??cabdcabdcadcadiiaabb99(3)此时子树A最左端末结点a与i所指的符号a匹配。于是再调整i使其指向下一输入符号d,并试图用A的最右端末结点b与之匹配。但它们不匹配,因此,子树A的匹配失败,这意味着选用A的第一个候选式对此时的情况不适合,不能构造出输入串x的语法树,在这种情况下,我们应该回头看看(回溯),其过程如下:若按自上而下语法分析程序的步骤进行分析判断,其过程如下:P: SP: S∷∷=cAd A=cAd A∷∷=ab|a=ab|SS??cAdcAd??cabdcabdcadcadiiaabbERROR!ERROR!1010(4)我们应把A的第一个候选式所扩展的子树剪掉,还应把指针i恢复到进入A时所指的输入符号a,,其过程如下:若按自上而下语法分析程序的步骤进行分析判断,其过程如下:P: SP: S∷∷=cAd A=cAd A∷∷=ab|a=ab|SS??cAdcAdcadcadii