4.4.4算符优先分析算法的设计.pptVIP

对于算符优先分析法，它虽然是一种自下而上的语法分析方法，但它并不是一种规范归约的分析方法。 4.4.4 算符优先分析算法的设计 4.4.4 算符优先分析算法的设计 这是因为在算符优先文法中，仅在终结符号之间定义优先关系而未对非终结符定义优先关系，从而无法使用优先关系表去识别由单个非终结符组成的可归约串，这也就是说，算符优先分析法不是用句柄来刻画可归约串，而是用最左素短语来刻画可归约串的。 4.4.4 算符优先分析算法的设计 1. 最左素短语 所谓句型的素短语是指这样一种短语，它至少包含一个终结符，并且除自身之外，不再包含其它的素短语。句型最左边的素短语称 最左素短语。 4.4.4 算符优先分析算法的设计 例如，有文法 G [E] E → E + T | T T → T * F | F F → (E) | id 求该文法句型T + T * F + id的素短语和最左素短语。 首先给出句型T+T *F + id的语法树,见 下图: 4.4.4 算符优先分析算法的设计 其短语有： T + T*F + id T+T*F T T*F id 由素短语定义可知T*F和id是素短语。 T*F为最左素短语。 注意：T是该句型的句柄，而不是素短语。 E E + T E + T F T T * F id 4.4.4 算符优先分析算法的设计 2. 识别句型最左素短语的方法 由算符文法的定义可知，算符优先文法的任何句型都没有相邻的两个非终结符。 其句型总可以表示成： $ N1a1 N2a2 … Nnan Nn+1$ 其中每个Ni为非终结符或空, ai为终结符 （1≤i≤n） 4.4.4 算符优先分析算法的设计 对算符优先文法G有如下定理： 一个算符优先文法G的任何句型的最左素短语是满足下列条件的最左子串: Ni ai Ni+1 ai+1 … aj Nj+1 ai-1 ai . ai ai+1, … , aj-1 aj = . = . aj aj+1 . 4.3.3 算符优先分析算法的设计 需要指出的是出现在ai左端的非终结符Ni和aj右端的非终结符Nj+1是属于素短语的。 这是由于算符文法的任何句型中终结符和非终结符相邻时含终结符的短语必含相邻非终结符。 + * id ( ) $ + * id ( ) $ . . . . . . . . . . . . . . . . . . . . . . . . = . . . . . = . 4.4.4 算符优先分析算法的设计 对上述句型 $ T+T*F+id $ 写成算符优先分析形式为： ai ai+1, … , aj-1 aj = . = . aj aj+1 . ai-1 ai . $ N1a1N2a2N3a3a4$ 因有 $ + * + $ . . . . 故由最左素短语定理有N2a2N3 即T*F 是 最左素短语。 根据最左素短语的定理，最左素短语中的终结符号具有相同的优先关系，并且，由于最左素短语中的符号是当时最先要归约的串，其优先关系先于最左素短语之外的符号，所以我们使用一个用于存放文法符号的先进后出栈，并利用优先关系表，可以确定最左素短语是否已形成来决定分析器的动作。 4.4.4 算符优先分析算法的设计 3. 算符优先分析程序的设计 4.4.4 算符优先分析算法的设计 基本思想: $ t1 t3 tj+1 t2 ? ? tj ti+1 tn ? ? $ 符号栈 优先关系 ? ti 尾 头 最左素短语 3. 算符优先分析程序的设计 . = . . . . ai-1 ai . aj aj+1 ai ai … aj-1 aj = . = . 返回图 4.4.4 算符优先分析算法的设计 下面给出算符优先分析算法。 输入：输入符号串W和优先关系表。 输出：若W是正确的句子，则接收，