2.3句型的分析 句型的分析：构造一算法，用以判断所给 的符号串是否为某文法的句型（句子） 常见分析方法有自顶向下分析和自底向上 分析两类； 自顶向下从开始符出发试图推导出给定的 符号串； 自底向上推导的逆过程（称归约)：从已 给的符号串出发，试图将其归约为开始符
2.3 句型的分析 • 句型的分析：构造一算法，用以判断所给 的符号串是否为某文法的句型（句子） • 常见分析方法有自顶向下分析和自底向上 分析两类； • 自顶向下 从开始符出发试图推导出给定的 符号串； • 自底向上 推导的逆过程（称归约）：从已 给的符号串出发，试图将其归约为开始符
2.3.1规范推导和规范归约 ·对于一文法而言，从开始符到某句型的推导过程可能不唯 一。例如，文法G[E]中从E到+*的推导有： (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*℉→E+T*i→E+E*i→E+i*i→→I+i*i→ F+i*i→i+i*i (4)..… 心
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*ii+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)分别是最左、最右推导。 形式上，从符号串o到符号串β的推导序列 a→*xUy→xuy→*B总有x∈V,*(y∈V) 时，称为最左（右）推导 定义：最左（右）推导所得句型称为左（右）句型；最右 推导称为规范推导；右句型称为规范句型
规范推导 • 为了让计算机自动地进行推导，通常我们只考虑最左或最 右推导。 • 最左（右）推导：在推导序列的每一步直接推导中，被替 换的总是当前句型中最左（右）的非终结符。 • 例如，上页中的（2）、（3）分别是最左、最右推导。 • 形式上，从符号串到符号串的推导序列 * xUy xuy * 总有 xVT * (yVT *) 时，称为最左（右）推导 • 定义：最左（右）推导所得句型称为左（右）句型；最右 推导称为规范推导；右句型称为规范句型
句子、句型的推导方法 每个句子都有相应的最左和最右推导，因此，句子即是左句型 也是右句型（规范句型） ·并不是每个句型都有最左和最右推导 ·例如，E→+E+i*T即不是左句型，也不是右句型 ·对于给定的符号串w,采用自顶向下的分析来判断w是否为 L(G[S)的句子的常见方法是：试图建立从开始符S到w最左推 导：S→w ·显然，每步推导时，对应于最左非终结符相应的产生式可能会 有多个，若无特殊的办法，只能一个一个地试探。因此，推导 过程可能是带回湖的。 ·为提高效率，就应尽量避免回溯
句子、句型的推导方法 • 每个句子都有相应的最左和最右推导，因此，句子即是左句型 也是右句型（规范句型） • 并不是每个句型都有最左和最右推导 • 例如，E + E+i*T即不是左句型，也不是右句型 • 对于给定的符号串w，采用自顶向下的分析来判断w是否为 L(G[S])的句子的常见方法是：试图建立从开始符 S到w最左推 导: S * w • 显然，每步推导时，对应于最左非终结符相应的产生式可能会 有多个，若无特殊的办法，只能一个一个地试探。因此，推导 过程可能是带回溯的。 • 为提高效率，就应尽量避免回溯
自底向上的语法分析 ~就是从已给的符号串w出发，试图以相反的方向为W建立一个规 范推导，最终得到文法的开始符。 推导的逆过程称作归约，它是把当前的符号串Baδ冲的构成文法 某个产生式A→a右部的子串a替换成产生式的左部符号A,得到 一个新的符号串A6。这样的一步动作，称为进行了一步归约。 · 例如，符号串F+*中的F可按产生式T→F归约为T,从而得到新 的符号串T+*i。 若从给定的符号串出发，一步步地将其归约，最终得到文法的 开始符号，则说明是该文法定义的一个句子。归约成功，否则， 归约失败。 若归约的每一步都归约的是当前符号串中最左边的某产生式的右 部，则称该归约是规范归约（即最左归约）。 规范归约是规范推导的逆过程。 关于最左（右）归约、直接归约、归约等的形式定义不再赘述
自底向上的语法分析 • ~就是从已给的符号串w出发，试图以相反的方向为w建立一个规 范推导，最终得到文法的开始符。 • 推导的逆过程称作归约，它是把当前的符号串中的构成文法 某个产生式A→右部的子串替换成产生式的左部符号A，得到 一个新的符号串A 。这样的一步动作，称为进行了一步归约。 • 例如，符号串F+i*i中的F可按产生式T→F归约为T，从而得到新 的符号串T+i*i。 • 若从给定的符号串w出发，一步步地将其归约，最终得到文法的 开始符号，则说明w是该文法定义的一个句子。归约成功，否则， 归约失败。 • 若归约的每一步都归约的是当前符号串中最左边的某产生式的右 部，则称该归约是规范归约（即最左归约）。 • 规范归约是规范推导的逆过程。 • 关于最左（右）归约、直接归约、归约等的形式定义不再赘述