1.最左素短语定义 (1)素短语：设有算符优先文法G(⑤)，其句型的素短语是一个短语，它至少含有一个终结 符，并且除它自身之外不再含任何更小的素短语。 2)最左素短语：处于句型最左边的那个素短语， 例：文法5. ()向型P却+ (2)句型T 、P、i、P却+i是PP+i的短语 ,T+T+i是T+TF+ 的茶面pP哪、i是P+的表 T*F.i是T+T*F+i的素短语 P(Ei P却是P却+i的最左素短语 T却是T+T*F+i的最左素短语 2.句型的一般形式： #N1a2…Nn,Nn1# (5.4) 即任何两个终结符之间项多只有一个非终结符。这是任何算符文法的句型都具有的形式。 优先文法G的任何句型(54)的最左素短语是满足如下条件的最左子串最左素短 语是满足如下条件的最左子串 Na…Na+1, (Ni-a-NjaNmaN-a-NaNma) 4-144 马工+1，…，-工 a>ai. 即a4-14,x1,…，1x4,>+1 算符优先分析算法根据上述定理构造出来的， 个存放输入串的敷组R,算法大意为： ①将榆人串RR?R依次逐个移人符号栈S中，直至符号栈顶元素S与下 一个待输人的符号Rk有关系S>R为止， ②最左素短语尾符号S已在符号栈S的栈顶，由此往前（左）在栈中找最 左素短语的头符号$，直至找到第一个(S,区Q)为止 已 重复上 ,调用语义子程序对它进行加工 直至j=2且RI 分析算法描述 为止 设单元a中存放当前输入符，S为一个符号栈，则： ()将当前输入符存放到a中，将#入符号栈。 2)将找而第 个终结符b与a比较。如果b二a,而b一#且栈中只剩一个非终结符时 则成功：否则a入栈：如果b中a则a入栈：如果b+a,在栈顶寻找最左素短语，并将最左素 短语归约为一个非终结符：如果文法中找不到相应规则，则出错： (3)重复(2)至成功或失败。 算法中，每次都取终结符号进行比较，当符号栈S的某个符号不是终结符号时，便取 其左邻符号（这时 定是终结符)。算法中的为 工作单元，用于存放待比较的终结符号 说明：k代表符号栈$的使用深度 在算法中，若出现减1后小于等于0时，则输入串有错：符号我S应呈现：# #表示正确，输入串是该文法的句子。 算法中并没有指出应把所找到的最左素短语归约到哪一个非终结符号N” N是产生式的左部符号，此产生式的右部和S0+Sk构成如下 一对应关系1．最左素短语定义 （1）素短语：设有算符优先文法 G(S),其句型的素短语是一个短语，它至少含有一个终结 符，并且除它自身之外不再含任何更小的素短语。 （2）最左素短语：处于句型最左边的那个素短语。 例：文法 5.3 E→E+T|T (1)句型 P*P+i (2)句型 T+T*F+i T→T*F|F P、P*P、i、P*P＋i 是 P*P＋i 的短语 T,T*F,T+T*F,i,T+T*F+i 是 T+T*F+i 的素短语 F→P↑F|P P*P、i 是 P*P＋i 的素短语 T*F,i 是 T+T*F+i 的素短语 P→(E)|i P*P 是 P*P＋i 的最左素短语 T*F 是 T+T*F+i 的最左素短语 2.句型的一般形式： 即任何两个终结符之间顶多只有一个非终结符。这是任何算符文法的句型都具有的形式。 3．定理 一个算符优先文法 G 的任何句型（5.4）的最左素短语是满足如下条件的最左子串最左素短 语是满足如下条件的最左子串 (Nj-1aj-1NjajNj+1aj+1…Ni-1ai-1NiaiNi+1ai+1) 即 4. 算符优先分析算法(根据上述定理构造出来的) 设一个符号栈 S 和一个存放输入串的数组 R，算法大意为： 重复上述过程，直至 j＝2 且 R[k]=#为止。 分析算法描述 设单元 a 中存放当前输入符，S 为一个符号栈，则： (1) 将当前输入符存放到 a 中，将#入符号栈。 (2) 将栈顶第一个终结符 b 与 a 比较。如果 b≡a ，而 b== #且栈中只剩一个非终结符时， 则成功；否则 a 入栈；如果 b≮a,则 a 入栈；如果 b≯a,在栈顶寻找最左素短语，并将最左素 短语归约为一个非终结符；如果文法中找不到相应规则，则出错； (3) 重复(2) 至成功或失败。 算法中，每次都取终结符号进行比较，当符号栈 S 的某个符号不是终结符号时，便取 其左邻符号（这时一定是终结符）。算法中的 Q 为一工作单元，用于存放待比较的终结符号。 说明：k 代表符号栈 S 的使用深度。 在算法中，若出现 j 减 1 后小于等于 0 时，则输入串有错；符号栈 S 应呈现：＃N ＃表示正确，输入串是该文法的句子。 算法中并没有指出应把所找到的最左素短语归约到哪一个非终结符号‘N’。 N 是产生式的左部符号，此产生式的右部和 S[j＋l]...S[k]构成如下一一对应关系：