编译原理第4章4剖析.ppt

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 4.4.4 算符优先分析算法的设计 2. 识别句型最左素短语的方法 4.4.4 算符优先分析算法的设计 对算符优先文法G有如下定理： 4.4.4 算符优先分析算法的设计 4.4.4 算符优先分析算法的设计 4.4.4 算符优先分析算法的设计 下面给出算符优先分析算法。 4.4.4 算符优先分析算法的设计 例如，对表达式的文法 E → E + T | T T → T * F | F F → (E) | id 4.4.4 算符优先分析算法的设计 4.4.4 算符优先分析算法的设计 4.4.6 算符优先分析法的局限性 由于算符优先分析法跳过了所有单非产生式之间的归约，这样算符优先分析比规范归约要快得多，这既是优点也是缺点。由于忽略非终结符在归约过程中的作用，可能导致把本来不是句子的输入串误认为是文法句子。 4.4.6 算符优先分析法的局限性 设有算符优先文法 该文法对应的算符优先关系表如下表所示。 * 所谓句型的素短语是指这样一种短语，它至少包含一个终结符，并且除自身之外，不再包含其它的素短语。句型最左边的素短语称 最左素短语。 求该文法句型T + T * F + id的素短语和最左素短语。 由算符文法的定义可知，算符优先文法的任何句型都没有相邻的两个非终结符。 其句型总可以表示成： $ N1a1 N2a2 … Nnan Nn+1$ 其中每个Ni为非终结符或空, ai为终结符 （1≤i≤n） 一个算符优先文法G的任何句型的最左素短语是满足下列条件的最左子串: Ni ai Ni+1 ai+1 … aj Nj+1 ai-1 ai . ai ai+1, … , aj-1 aj = . = . aj aj+1 . 根据最左素短语的定理，最左素短语中的终结符号具有相同的优先关系，并且，由于最左素短语中的符号是当时最先要归约的串，其优先关系先于最左素短语之外的符号，所以我们使用一个用于存放文法符号的先进后出栈，并利用优先关系表，可以确定最左素短语是否已形成来决定分析器的动作。 3. 算符优先分析程序的设计 基本思想: $ t1 t3 tj+1 t2 ? ? tj ti+1 tn ? ? $ 符号栈 优先关系 ? ti 尾 头 最左素短语 3. 算符优先分析程序的设计 . = . . . . ai-1 ai . aj aj+1 ai ai … aj-1 aj = . = . 输入：输入符号串W和优先关系表。 输出：若W是正确的句子，则接收， 否则输出错误信息。 方法：执行下图算法。 栈置初值 K ?1, S[K] ? ‘$’ 当前输入符号读入a S[K]是终结符？ j ? K Y j ? K–1 N S[ j ]是终结符？ Q ? S[ j ] , j ? j-1 Y S[ j+1]······S[K]是最左素短语 K ?j+1 , S[K] ? N Y.. 结束 Y K=2 且 a =‘$’? N S[K] ? a K ? K+1 Y error N j ? j-1 N S[ j ] a ? . S[ j ] a ? 或 S[ j ] a ? N . = . Y S[ j ] Q? . N 说明:算法中K为符号栈S的指针，a用来存放当前输入符号，j是栈的查找指针，Q是工作单元。 对输入串id +id ＄的算符优先分析