编译原理第06章 自底向上优先分析法

编译原理之优先分析法 华东交通大学软件学院万仲保 第06章自底向上优先分析法 自底向上优先分析概述简单优先分析法算符优先分析法 自底向上分析方法概述 自底向上分析方法 也称移进 归约分析法 实现思想是对输入符号串自左向右进行扫描 并将输入符逐个移入一个后进先出栈中 边移入边分析 一旦栈顶符号串形成某个句型的句柄时 就用该产生式的左部非终结符代替相应右部的文法符号串 这称为一步归约 重复这一过程直到归约到栈中只剩文法的开始符号时则为分析成功 也就确认输入串是文法的句子 示例 a b b c d e 步骤 符号栈 输入符号串 动作 1 abbcde 移进 2 abbcde 移进 4 aAbcde 移进 6 aAcde 移进 7 aAcde 移进 9 aAcBe 移进 11 S 接受 分析符号串abbcde是否G S 的句子 对输入串abbcde 的移进 规约分析过程 最右推导 示例 文法G S 1 S aAcBe 2 A b 3 A Ab 4 B d 简单优先分析法 按照文法符号 包括终结符和非终结符 的优先关系确定句柄 定义优先关系简单优先文法优先关系矩阵 表示文法符号之间关系的矩阵 算法示例 优先关系X Y 表示X Y的优先关系相同 当且仅当文法G中存在产生式A XY X Y 表示X的优先性比Y的要低 当且仅当文法G中存在产生式A XB 且BY X Y 表示X的优先性比Y的要高 当且仅当文法G中存在产生式A BD 且B X DY 优先关系的定义 简单优先文法的定义 满足以下条件的文法是简单优先文法 1 在文法符号集V中 任意两个符号之间最多只有一种优先关系成立 2 在文法中任意两个产生式没有相同的右部 简单优先分析法 算法 根据已知优先文法构造相应优先关系矩阵 并将文法的产生式保存 设置符号栈S 算法步骤如下 将输入符号串a1a2a3 an 依次逐个存入符号栈S中 直到遇到栈顶符号ai的优先性 下一个待输入符号aj时为止 栈顶当前符号ai为句柄尾 由此向左在栈中找句柄的头符号ak 即找到ak 1 ak为止 由句柄ak ai在文法的产生式中查找右部为ak ai的产生式 若找到则用相应左部代替句柄 若找不到则为出错 这时可断定输入串不是该文法的句子 重复上述三步 直到归约完输入符号串 栈中只剩文法的开始符号为止 简单优先文法分析示例 文法G S 1 S bAb 2 A B a 3 B Aa 1 确定文法符号之间的关系2 求出文法的简单优先关系矩阵3 对输入串进行分析 输入串b aa b 确定文法符号之间的关系 1 求 关系 由 1 b AA b由 2 B由 3 A aa 2 求 关系 由 1 2 b b a由 2 3 A a3 求 关系 由 1 B ba b b由 3 B aa a a 求出文法的简单优先关系矩阵 用来表示语句括号 其优先关系低于所有与其有相邻关系的文法符号 对输入串进行分析 输入串b aa b 文法G S 1 S bAb 2 A B a 3 B Aa 算符优先分析法 某些文法具有 算符 特性表达式运算符 优先级 结合性 人为地规定其算符的优先顺序 即给出优先级别和同一级别的结合性 只考虑算符之间的优先关系来确定句柄 定义算符文法算符优先关系算法优先文法最左素短语算符优先关系表的构造算符优先分析法概述算符优先文法的性质算符优先分析算法优先函数算符优先分析法的局限性 算符文法的定义 如果不含空产生式的上下文无关文法G中没有形如U BC 的产生式 其中B C VN 则称G为算符文法 OperaterGrammar OG 性质1 在算符文法中任何句型都不包含两个相邻的非终结符 归纳法 2 如Vx或xV出现在算符文法的句型 中 其中V VN x VT 则 中任何含x的短语必含有V 反证法 用归纳法 设 是句型 即S S 0 1 n 1 n 推导长度为n 归纳起点n 1时 S 0 1 即S 必存在产生式S 而由算符文法的定义 文法的产生式中无相邻的非终结符 显然满足性质1 假设n 1 n 1满足性质1 若 n 1 A A为非终结符 由假设知 的尾符号和 的首符号都不可能是非终结符 否则与假设矛盾 又若A 是文法的产生式 则有 n 1 n 而A 是文法的原产生式 不含两个相邻的非终结符 所以 也不含两个相邻的非终结符 满足性质1 证毕 反证法 因为由算符文法的性质1知可有 S bA 若存在B b 这时b和A不同时归约 则必有S BA 这样在句型BA 中存在相邻的非终结符B和A 所以与性质1矛盾 证毕 注意 含b的短语必含A 含A的短语不一定含b 算符优先关系的定义 设G是不含 产生式的文法 a b是任意两个终结符 A B C是非终结符 算符优先关系的定义如下 a b当且仅当G中有形如A ab 或A aBb 的产生式 a b当且仅当G中有形如A aB 的产生式 且B b 或B Cb a b当且仅当G中有形如A Bb 的产生式 且B a或B aC注意 算符优先关系中不存在递推关系 即a bb c a c或a bb c a c或a bb c a c优先关系的语法树表示方式 优先关系的语法树表示方式 算符优先文法的定义 设G是不含 产生式的算符文法 如果对任意两个终结符对a b之间至多只有一种算符优先关系存在 则称G为算符优先文法 结论算符优先文法是无二义的 算符优先关系表的构造 集合的定义 FIRSTVT B b B b 或B Cb 对于非终结符B 其往下推导所可能出现的首个算符 终结符 LASTVT B a B a或B aC 对于非终结符B 其往下推导所可能出现的最后一个算符 终结符 构造方式 由定义直接构造由关系图法构造构造算法 由定义计算算符优先关系 直接计算算法计算关系图计算 直接计算算符优先关系 关系直接看产生式的右部 若出现了A ab 或A aBb 则a b 关系求出每个非终结符B的FIRSTVT B 若A aB 则 b FIRSTVT B a b 关系求出每个非终结符B的LASTVT B 若A Bb 则 a LASTVT B a b示例 直接计算示例 文法G E 0 E E 1 E E T 2 E T 3 T T F 4 T F 5 F P F P 6 P E 7 P i FIRSTVT E FIRSTVT E i FIRSTVT T i FIRSTVT F i FIRSTVT P i LASTVT E LASTVT E i LASTVT T i LASTVT F i LASTVT P i 1 关系由产生式 0 和 6 得 3 关系找形如 A Bb 的产生式E 则LASTVT E E 则LASTVT E T 则LASTVT T P 则LASTVT P E 则LASTVT E 2 关系找形如 A aB 的产生式 E 则 FIRSTVT E T 则 FIRSTVT T F 则 FIRSTVT F F 则 FIRSTVT F E 则 FIRSTVT E 算法计算算符优先关系 算法规则 1 若有产生式A a 或A Ba 则a FIRSTVT A 其中A B为非终结符 a为终结符 2 若a FIRSTVT B 且有产生式A Bb 则有a FIRSTVT A 算法 文本描述按规则1对每个数组元素F A a 赋初值 并对数组元素F A a 初值为真的符号对 A a 都放入栈中 然后对栈做如下运算 当栈不空时 就将栈顶项弹出 并记为 B a 再用规则2 若F A a 为假 则使其变为真 且将 A a 推进栈 如此重复直到栈折空为止 程序描述示例 程序描述 将置为真的操作 PROCEDUREINSERT A a IFNOTF A a THENBEGINF A a TRUNPUSH A a 0NT0STRACKEND 主程序 BEGIN MAIN FOR每一个非终结符A和终结符a DOF A a FALSE FOR每个形如A a 或A Ba 的产生式DOINSERT A a WHILESTACK非空DOBEGIN把STACK的顶项记为 B a 托出去FOR每个形如A B 的产生式DoINSERT A a ENDEND 算法计算示例 文法G E 0 E E 1 E E T 2 E T 3 T T F 4 T F 5 F P F P 6 P E 7 P i 首次扫描STRACK的初值 6 P i 5 P 4 F 3 T 2 E 1 E 栈顶 6 的改变 F P F i T F T i E T E i 由于无右部以E开始的产生式 所以 E i 弹出后无进栈项 此时当前的栈顶为 P 栈顶 5 的改变 F P F T F T E T E E 弹出后无进栈项 此时当前的栈顶为 F 栈顶 4 的改变 T F T E T E E 弹出后无进栈项 此时当前的栈顶为 T 栈顶 3 的改变 E T E 以下逐次弹出栈顶元素后 都再无进栈项 直至栈空 FIRSTVT E FIRSTVT E i FIRSTVT T i FIRSTVT F i FIRSTVT P i 关系图计算算符优先关系 关系图的构造方法图中的结点为非终结符的FIRSTVT A 和终结符 对每一个形如A a 或A Ba 的产生式 则构造由FIRSTVT A 结点到终结符结点 a 用箭弧连接的图形 对每一个形如A B 的产生式 则对应图中由FIRSTVT A 结点到FIRSTVT B 结点用箭弧连接 对每一非终结符的FIRSTVT A 经箭弧有路径能到达的终结符结点 a 则有a FIRSTVT A 示例 关系图计算示例 FIRSTVT E FIRSTVT E FIRSTVT T FIRSTVT F FIRSTVT P 文法G E 0 E E 1 E E T 2 E T 3 T T F 4 T F 5 F P F P 6 P E 7 P i 由关系图法计算算符优先关系 文法符号的关系定义优先关系与符号关系之间的联系算符关系构造规则 的关系构造规则 的关系构造规则示例文法符号之间的关系文法终结符之间的 关系图文法终结符之间的 关系图 文法符号的关系定义 6 4 设G VN VT P S 是一个上下文无关文法 则 AFIRSTB当且仅当存在形如A B 的产生式 ALASTB当且仅当存在形如A B的产生式 BFIRSTTERMb当且仅当存在形如B b 或B Cb 的产生式 BLASTTERMa当且仅当存在形如B a或B aC的产生式 XFOLLOWEDBYY当且仅当存在形如A XY 的产生式 中必须是一个为终结符 另一个为非终结符 AFIRST B当且仅当存在形如A B或存在A X1 X1 X2 Xn 1 Xn Xn B 的产生式序列 ALAST B当且仅当存在形如B A或存在A X1 X1 X2 Xn 1 Xn Xn B的产生式序列 优先关系与符号关系之间的联系 a b aFOLLOWEDBYBBFIRST PPFIRSTTERMba b 存在形如A aB 的产生式 其中B b 或B Cb 而B b 可写成B P b B Cb 可写成B P Cb 所以B b 或B Cb BFIRST PPFIRSTTERMba b BLAST PPLASTTERMa TBFOLLOWEDBYba b 存在形如A Bb 的产生式 其中B a 或B aC 而B a可写成B P aB aC可写成B P aC所以B a或B aC BLAST PPLASTTERMa 的关系构造规则 凡有终结符在前非终结符在后相邻关系的 则由终结符结点到非终结符结点画一箭弧 对有FIRSTTERM关系的非终结符和终结符对 则从非终结符结点到终结符点画一箭弧 对非终结符对之间存在FIRST关系的 从左边的非终结符结点到右边的非终结符结点画一箭弧 对每个终结符结点a凡有路径能到达另一终结符结点b的 则有a b关系存在 的关系构造规则 对非终结符和终结符相邻关系的 由非终结符结点到终结符结点画一箭弧 对有LASTTERM关系的 由终结符结点到非终结符结点画一箭弧 对LAST关系的非终结符对 由后面的非终结符结点到前面的非终结符结点画一箭弧 对每个终结符结点a凡有路径能到达另一终结符结点b的 则有a b的关系成立 文法符号之间的关系 ELASTTTLASTFFLASTFFLASTP FIRST关系有EFIRSTEEFIRSTTTFIRSTTTFIRSTFFFIRSTP FIRSTTBRM关系有EFIRSTTBRM TFIRSTTBRM FFIRSTTBRM PFIRSTTBRM PFIRSTTBRMi 终结符在前非终结符在后的相邻关系有 FOLLOWEDBYE FOLLOWEDBYE FOLLOWEDBYT FOLLOWEDBYF FOLLOWEDBYF ELASTTERM TLASTTERM FLASTTERM PLASTTERM PLASTTERMi EFOLLOWEDBY EFOLLOWEDBY EFOLLOWEDBY TFOLLOWEDBY PFOLLOWEDBY 文法G E 0 E E 1 E E T 2 E T 3 T T F 4 T F 5 F P F P 6 P E 7 P i 文法终结符之间的 关系图 文法终结符之间的 关系图 P i E T F 构造文法的优先关系算法 for 每个产生式A X1X2 Xn for i 1 i n 1 i if Xi和Xi 1均为终结符 置Xi Xi 1 if i n 2且Xi和Xi 2均为终结符 但Xi 1为非终结符 置Xi Xi 1 if Xi为终结符 Xi 1为非终结符 for FIRSTVT Xi 1 中的每个b 置Xi b if Xi为非终结符 Xi 1为终结符 for LASTVT Xi 中的每个a 置a Xi 1 最左素短语 文法G S 句型的素短语是这样一个短语 它至少包含一个终结符号 并且 除它自身之外 不再包含其他素短语 最左素短语是指处于句型最左边的那个素短语 算符优先文法句型的最左素短语是唯一的 示例查找最左素短语的方法 在句型中加入优先关系 例如 i i i ii ii ii 1 找最左素短语的右端 从左至右扫描符号串直至遇到第一个 为止 2 找最左素短语的左端 然后向回扫描 向左 越过任何 直至一个 被发现 3 归约 可归约串包括在第1步所遇到的 的左边和第2步所遇到的 的右边的所有终结符号 包括插入在中间的或环绕在两旁的非终结符号 文法G E 1 E E T 2 E T 3 T T F 4 T F 5 F P F P 6 P E 7 P i 句型 T T F i 其短语有 T T F iT T FTT Fi 最左素短语为 T F 素短语 T F i E E T E T F F T T i 句型T T F i的语法树 最左素短语示例 算符优先分析法概述 1 算符优先分析法是一种特别有利于表达式分析 宜于手工实现的语法分析方法 2 算符优先分析过程是自下而上的归约过程 但未必是严格的最左归约 因此 它不是一种规范归约法 3 所谓算符优先分析法就是仿效算术表达式的运算过程而设计的一种语法分析方法 这种方法的关键在于规定算符 终结符 的优先顺序和结合性质 示例 算符优先分析法示例 文法G E 1 E E T 2 E T 3 T T F 4 T F 5 F E 7 F i对输入串i i 的规约过程 规范规约算符优先规约 规范规约示例 算符优先规约示例 算符优先文法的性质 对于算符优先文法 如果aNb 或ab 出现在句型r中 则之间有且仅有一种优先关系 即 若a b 则在r中必含有b而不含a的短语存在 若a b 则在r中必含有a而不含b的短语存在 若a b 则在r中含有a的短语必含有b 反之亦然 算符文法的任一句型有如下形式 N1a1N2a2 NnanNn 1 若Niai NjajNj 1为句柄 则Ni Nj 1在句柄中 且该句柄中终结符之间的关系为 ai 1 aiai ai 1 aj 1 ajaj ai 1 算符优先分析算法 算符优先分析归约的关键是寻找最左素短语 开始 当前输入符读入a 置初值k 1 S k S k VT S j a S j a j k j k 1 Q S j S j 1 VT j j 1 j j 2 S j Q S j 1 S k 归约为Nk j 1S k N K k 1S k a S j a S j 出错 检查是否正常结束 结束 Y N N Y Y Y N N Y Y Y Y Y N N N 优先函数 定义构造方法由定义进行构造由关系图进行构造示例通过定义计算优先函数关系通过关系图计算优先函数关系优先函数分析的特点 优先函数定义 定义两个函数f g 满足如下条件 当a b 则令f a g b 当a b 则令f a g b 当a b 则令f a g b 对f g可称它为优先函数 优先函数的值可以用整数表示 对优先函数每个元素的值都增加同一个常数 优先关系不变 所以对同一个文法的优先关系矩阵对应的优先函数不唯一 有一些优先关系矩阵中的优先关系是唯一的 却不存在优先函数 示例 由定义构造优先函数 若已知文法G终结符之间的优先关系 可按如下步骤构造其优先函数f g a 对每个终结符a VT 包括 在内 令f a g a 1 也可是其它整数 b 如果a b 而f a g b 则令f a g b 1c 如果a b而f a g b 则令g b f a 1d 如果a b 而f a g b 则令min f a g b max f a g b e 重复b d 直到过程收敛 如果重复过程中有一个值大于2n 则表明该算符优先文法不存在算符优先函数 由关系图构造优先函数 a对所有终结符a 包括 用有下脚标的fa gb为结点名 画出2n个结点 b若ai aj 或ai aj 则从fai到gaj画一条箭弧 c若ai aj 或ai aj 则从gaj到fai画一条箭弧 d给每个结点赋一个数 此数等于从该结点出发所能到达的结点 包括该结点自身在内