前后文无关文法及语言2.pptVIP

2.3 句型的分析 句型的分析：构造一算法，用以判断所给的符号串是否为某文法的句型（句子） 常见分析方法有自顶向下分析和自底向上分析两类； 自顶向下 从开始符出发试图推导出给定的符号串； 自底向上 推导的逆过程（称归约）：从已给的符号串出发，试图将其归约为开始符。 2.3.1 规范推导和规范归约 对于一文法而言，从开始符到某句型的推导过程可能不唯一。例如，文法G[E]中从 E 到 i+i*i 的推导有： (1)E? E+T? E+T*F? T+T*F? T+T*i? F+T*i? ?i+T*i? i+F*i?i+i*i (2)E? E+T? T+T? F+T? i+T? i+T*F? i+F*F? ?i+i*F ? i+i*F? i+i*i (3)E? E+T? E+T*F? E+T*i? E+F*i? E+i*i ? ?T+i*i? F+i*i? i+i*i (4) … … 规范推导 为了让计算机自动地进行推导，通常我们只考虑最左或最右推导。 最左（右）推导：在推导序列的每一步直接推导中，被替换的总是当前句型中最左（右）的非终结符。 例如，上页中的（2）、（3）分别是最左、最右推导。 形式上，从符号串?到符号串?的推导序列 ? ?* xUy ? xuy ?* ? 总有 x?VT* (y?VT*) 时，称为最左（右）推导 定义：最左（右）推导所得句型称为左（右）句型；最右推导称为规范推导；右句型称为规范句型。 句子、句型的推导方法 每个句子都有相应的最左和最右推导，因此，句子即是左句型也是右句型（规范句型） 并不是每个句型都有最左和最右推导 例如，E ?+ E+i*T即不是左句型，也不是右句型 对于给定的符号串w，采用自顶向下的分析来判断w是否为L(G[S])的句子的常见方法是：试图建立从开始符 S到w最左推导: S?* w 显然，每步推导时，对应于最左非终结符相应的产生式可能会有多个，若无特殊的办法，只能一个一个地试探。因此，推导过程可能是带回溯的。 为提高效率，就应尽量避免回溯 自底向上的语法分析 ~就是从已给的符号串w出发，试图以相反的方向为w建立一个规范推导，最终得到文法的开始符。 推导的逆过程称作归约，它是把当前的符号串???中的构成文法某个产生式A??右部的子串?替换成产生式的左部符号A，得到一个新的符号串?A? 。这样的一步动作，称为进行了一步归约。 例如，符号串F+i*i中的F可按产生式T?F归约为T，从而得到新的符号串T+i*i。 若从给定的符号串w出发，一步步地将其归约，最终得到文法的开始符号，则说明w是该文法定义的一个句子。归约成功，否则，归约失败。 若归约的每一步都归约的是当前符号串中最左边的某产生式的右部，则称该归约是规范归约（即最左归约）。 规范归约是规范推导的逆过程。 关于最左（右）归约、直接归约、归约等的形式定义不再赘述。 关于归约的一点说明 注意，前面例子中归约的第五步中，当前的符号串为 E+T*i，除了可将i归约成F外，还可将E+T或T归约成E，分别得到符号串E*i和E+E*i。但是，若真按这两个方案进行归约，则当我们把其归约成E*E或E+E*E时，就再也归约不下去了。这就告诉我们在第五步时，唯一正确的归约是将i归约为F，也就是说，i是唯一可被归约的最左子串。 那么，对于规范归约的每一步，如何确定符号串中的当前应被归约的最左子串呢？ 这里暂且按下不提，且听2.3.3小节分解。 2.3.2 语法树和二义性 语法树用于直接地描述一个句型右句子的语法结构 语法树是一有向树（连通的） 1）有且仅有一个无任何前驱的结点，称为根 （S）； 2）除根外，每个结点恰有一个直接前驱； 3）对于任一结点m，从根到m可达; 4) 每个结点的后继是有序的（从左到右） 设G=(VN,VT,P,S)是一文法，则满足下述条件的树称为语法树： 1）每个结点有一标记X， X?V； 2）根的标记为S（开始符）； 3）若结点X有后继，则X?VN； 4）A有k个后继，自左至右为X1, X2, …, Xk，则A? X1X2…Xk ?P 文法的二义性 存在这样的文法G，其某个句子w?L(G),可对应结构不同的语法树，即w对应了多个不同的最左（右）推导，这类文法称为二义性文法。 例如，G3[E]：E?E+E|E*E|(E)|i 的句型i+i*i及文法 C?if B then C|if B then C else C C ?S 的句型：if B1 then if B2 then S1 else S2 上面两个句型均有两个不同的语法推导树（见下页），所以，它们是二义性文法 关于二义性文法 应指出，二义性是一种常见的语法现象，然而，对于编译程序而言，二义性文法是有害的。 为解决二义性文法带来的不确定性问题，通