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