第3章文法和语法4学时(576KB).ppt

上下文无关文法的语法树 用于描述上下文无关文法的句型推导的直观方法 例: G[S]: S→aAS A→SbA A→SS S→a A→ba S a A S S b A a a b a 句型aabbaa的语法树（推导树） 叶子结点：树中没有子孙的结点。 从左到右读出推导树的叶子标记，所得的句型为推导树的结果。也把该推导树称为该句型的语法树。 推导过程中施用产生式的顺序 例: G[S]: S→aAS A→SbA A→SS S→a A→ba S a A S S b A a a b a 句型aabbaa的语法树（推导树） S?aAS?aAa?aSbAa?aSbbaa?aabbaa S?aAS?aSbAS?aabAS?aabbaS?aabbaa S?aAS?aSbAS?aSbAa?aabAa?aabbaa 最右推导 最左推导 最右推导被称为规范推导 由规范推导所得的句型称为规范句型 问题：一个句型是否对应唯一的一棵语法树？ 例：G[E]: E → i E → E+E E → E*E E → (E) E E + E E * E i i i E E * E i E + E i 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 二义文法 若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的。 产生某上下文无关语言的每一个文法都是二义的，则称此语言是先天二义的。 注：程序设计语言的文法不要二义！ 改造二义文法 例：将二义文法改造为无二义文法 G[E]: E → i G[E]：E → T|E+T E → E+E T → F|T*F E → E*E F →（E）|i E → (E) 或规定优先顺序和结合律 证明文法二义：参见书P.46 例题1 3.6 句型的分析 句型分析 就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。 分析程序 在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序。 分析算法又称识别算法。 从左到右的分析算法 即总是从左到右地识别输入符号串。 首先识别符号串中的最左符号 进而依次识别右边的一个符号 分析算法分类 自上而下分析法 从文法的开始符号出发，反复使用各种产生式，寻找与输入符号匹配的推导。 自下而上分析法 从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。 两种方法反映了两种不同的语法树的构造过程 自上而下的分析 例20 文法G：S → cAd A → ab A → a识别输入串 cabd 是否该文法的句子。 S S S c A d c A d a b 推导过程：S ? cAd ? cabd 自下而上的分析 例21 文法G：S → cAd A → ab A → a识别输入串 cabd 是否该文法的句子 S A A c a b d c a b d c a b d 归约的过程：S ? cAd ? cabd 句型分析的有关问题 1）如何选择使用哪个产生式进行推导？ 假定要被代换的最左非终结符号是V，且有n条规则：V→A1|A2|…|An，那么如何确定用哪个右部去替代V？ 2）如何确定“可归约串”？ 在自下而上的分析方法中，在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”。如何确定“可归约串”？ 引出“句柄”的概念。