2.3句型的分析 定义24设GS是文法,a∈,若S→a,则称a是G的一个句型 句型的分析:构造一算法,用以判断所给的符号串是 否为某文法的句型 常见分析方法有自顶向下分析和自底向上分析两类; 自顶向下从开始符出发,试图推导出给定的符号串; 自底向上从已给的符号串出发,试图将其归约为开始 符。归约:是推导的逆过程,即将某一符号子串替换成 相应产生式的左部变量
1 2.3 句型的分析 • 句型的分析：构造一算法，用以判断所给的符号串是 否为某文法的句型 • 常见分析方法有自顶向下分析和自底向上分析两类； • 自顶向下 从开始符出发，试图推导出给定的符号串； • 自底向上 从已给的符号串出发，试图将其归约为开始 符。归约：是推导的逆过程, 即将某一符号子串替换成 相应产生式的左部变量。 2.4 [ ] , , , . * 定义 设G S 是文法 V * 若S 则称 是G的一个句型 G
23/规范推导和规范归约 问题:根据文法G2E,从E推导出计+i G2E]: 1)E→E+→E+T→T+T*→T+T E→>E+TT →F+T*→i+T*→i+F*→→i+i T→T*F|F (2)E→E+T→T+T→F+→iT→iT*F F→>(E)i →计F*F→计+F→计*最左推导 3)E→E+T→E+T*F→E+T*→E+Fi →E+i→Tii→Fi→计i最右推导 (4) 对于一文法而言,从开始符到某句型的推导过程可能 不唯
2 2.3.1 规范推导和规范归约 问题: 根据文法G2[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*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) … … • 对于一文法而言，从开始符到某句型的推导过程可能 不唯一。 最左推导 最右推导 G2[E]: E→E+T|T T→T*F|F F→(E)|i
规范推导 为了让计算机实现推导的自动进行,引入推导时非终 结符的替换顺序。 最左(右)推导:在推导序列的每一步直接推导中 被替换的总是当前句型中最左(右)的非终结符。 形式定义,设有从符号串到符号串β的推导序列 →x→x→B, 其中,xUy→xuy表示该推导序列中的任一直接推导 如果总有x∈V*,则该推导序列为最左推导;如果总 有y∈V,则该推导序列为最右推导,最右推导也称 为规范推导
3 规范推导 • 为了让计算机实现推导的自动进行，引入推导时非终 结符的替换顺序。 • 最左（右）推导：在推导序列的每一步直接推导中， 被替换的总是当前句型中最左（右）的非终结符。 • 形式定义，设有从符号串到符号串的推导序列 其中，xUy xuy表示该推导序列中的任一直接推导， 如果总有 xVT *，则该推导序列为最左推导；如果总 有yVT * ，则该推导序列为最右推导，最右推导也称 为规范推导。 , xUy xuy
规范句型 由最左推导推出的句型称为左句型;由最右推导或规 范推导推出的句型称为右句型或规范句型。 每个句子都有相应的最左和最右(规范)推导,因此, 句子即是左句型也是右句型(规范句型) 但并不是每个句型都有最左和最右推导。例如,句型 T*十T有唯一推导: E→E+T→T+T→1*F+T→T*i+T 上述推导既不是最左推导,也不是最右推导,因此 T*i+T既不是左句型,也不是右句型
4 规范句型 • 由最左推导推出的句型称为左句型；由最右推导或规 范推导推出的句型称为右句型或规范句型。 • 每个句子都有相应的最左和最右（规范）推导，因此， 句子即是左句型也是右句型（规范句型） • 但并不是每个句型都有最左和最右推导。例如，句型 T*i+T有唯一推导： E E+T T+T T*F+T T*i+T 上述推导既不是最左推导，也不是最右推导，因此 T*i+T既不是左句型，也不是右句型
自顶向下的语法分析 对于给定的符号串,采用自顶向下的分析来判断w是 否为L(GS的句子的方法是:建立从开始符S到和的 最左推导:S→w 每步推导时,对应于最左非终结符相应的产生式可能 会有多个,如U→a1|a2|…|an,此时就面临一个 如何选择候选式的问题。除非有办法预先知道哪个候 选式有用,否则只能一个一个地试探。因此,推导过 程可能是带回溯的。 带回溯的语法分析效率大大降低,为提高效率,就应 尽量避免回溯(不带回溯的LL分析方法)
5 自顶向下的语法分析 • 对于给定的符号串w，采用自顶向下的分析来判断w是 否为L(G[S])的句子的方法是：建立从开始符S到w的 最左推导: S* w • 每步推导时，对应于最左非终结符相应的产生式可能 会有多个，如 ，此时就面临一个 如何选择候选式的问题。除非有办法预先知道哪个候 选式有用，否则只能一个一个地试探。因此，推导过 程可能是带回溯的。 • 带回溯的语法分析效率大大降低，为提高效率，就应 尽量避免回溯（不带回溯的LL分析方法）。 U n | | | → 1 2
归约是推导的逆过程,是把当前的符号串Ba8中构成文 法某个产生式4→a右部的子串a替换成产生式的左部 符号A,得到一个新的符号串B4δ。这样的一步动作, 称为进行了一步归约。 例如,符号串F+中的F可按产生式T少F归约为T, 从而得到新的符号串T+ 若归约的每一步都归约的是当前符号串中最左边的某 产生式的右部,则称该归约是最左归约。 最左归约是最右推导(规范推导)的逆过程,因此最 左归约也称为规范归约
6 自底向上的语法分析——归约 • 归约是推导的逆过程，是把当前的符号串中构成文 法某个产生式A→右部的子串替换成产生式的左部 符号A，得到一个新的符号串A。这样的一步动作， 称为进行了一步归约。 • 例如，符号串F+i*i中的F可按产生式T→F归约为T， 从而得到新的符号串T+i*i。 • 若归约的每一步都归约的是当前符号串中最左边的某 产生式的右部，则称该归约是最左归约。 • 最左归约是最右推导（规范推导）的逆过程，因此最 左归约也称为规范归约
自底向上的语法分析:从已给的符号串w出发,试图以 相反的方向为w建立一个规范推导,最终得到文法的 开始符。 若从给定的符号串w出发,一步步地将其归约,最终 得到文法的开始符号,则归约成功,说明w是该文法 定义的一个句子;否则,w不是该文法定义的句子
7 自底向上的语法分析过程 • 自底向上的语法分析：从已给的符号串w出发，试图以 相反的方向为w建立一个规范推导，最终得到文法的 开始符。 • 若从给定的符号串w出发，一步步地将其归约，最终 得到文法的开始符号，则归约成功，说明w是该文法 定义的一个句子；否则，w不是该文法定义的句子
符号串计i的归约过程 步序 当前符号串w 所用的产生式 i+ii G2{E: F+i*i T→F E→>E+TT 2 +i*i E→T T→>TF|F E+ii F→i F→>(E)i E+Fxi T→F E+TMi F→i E+TMF 个→T*F 7 E+T E→E+T 8 E 由上表可以看出,该归约过程是最左归约,其逆过程 就是规范推导(式25)
8 符号串i+i*i的归约过程 步序 当前符号串 wi 所用的产生式 0 i+i*i F→i 1 F+i*i T→F 2 T+i*i E→T 3 E+i*i F→i 4 E+F*i T→F 5 E+T*i F→i 6 E+T*F T→T*F 7 E+T E→E+T 8 E 由上表可以看出，该归约过程是最左归约，其逆过程 就是规范推导（式2.5）。 G2[E]: E→E+T|T T→T*F|F F→(E)|i
关于归约的一点说明 对于前面例子中归约的第五步,当前的符号串为E+T 有,可以有以下几种规约 E+T归约为符号串E站,继续归约得EE, 无法继续进行归约 E+T归约为符号串E+E,继续归约得E+EE, 无法继续进行归约 E+T归约为符号串E+TF,这是唯一正确的归约, 也就是说,i是唯一可被归约的最左子串。 那么,对于规范归约的每一步,如何确定符号串中的当 前应被归约的最左子串呢?这个问题将在23.3小节进行 讨论
9 关于归约的一点说明 • 对于前面例子中归约的第五步，当前的符号串为E+T*i， 有，可以有以下几种规约： E+T*i 归约为符号串E*i ，继续归约得E*E， 无法继续进行归约 E+T*i 归约为符号串E+E*i ，继续归约得E+ E*E， 无法继续进行归约 E+T*i 归约为符号串E+T*F ，这是唯一正确的归约， 也就是说，i是唯一可被归约的最左子串。 • 那么，对于规范归约的每一步，如何确定符号串中的当 前应被归约的最左子串呢？这个问题将在2.3.3小节进行 讨论
见B0图视图 语法树是一有向树 1)有且仅有一个结点无父结点,称为根(S); 2)除根外,每个结点恰有一个父结点;无回路性 3)对于任一结点m,从根到m可达连通性 4)每个结点的子孙结点是有序的(从左到右)。 子树:某一结点及其全部子孙结点所构成的树。 直接子树:根结点只有孩子结点,没有更远的子孙结点 的子树
10 2.3.2 语法树和二义性 • 语法树是一有向树： 1）有且仅有一个结点无父结点，称为根（S）； 2）除根外，每个结点恰有一个父结点；无回路性 3）对于任一结点m，从根到m可达; 连通性 4）每个结点的子孙结点是有序的（从左到右）。 子树：某一结点及其全部子孙结点所构成的树。 直接子树：根结点只有孩子结点，没有更远的子孙结点 的子树