词法分析及词法分析程序.ppt

3.1 设计扫描器时应考虑的问题 源程序的输入和预处理 单词的分类(关键字,标识符,无符号数,运算符,界符等等) 识别约定和策略 单词的内部表示 * f与f^的区别 由f^的定义可知，f^(S,a) 与f(S,a) 不同，f^(S,a)是从S出发经过路径a所达的状态集（可走若干步）；而f(S,a)是从S出发经过矢线a所达的状态集（只走一步） 显然，f(S,a) 只走一步a矢线 ? ?-CLOSURE(f(S,a)) 多步，第一步必须走a矢线 ? f^(S,a) 路径a ：第一步可以是?矢线 ?-NFA的接受集： L(M)={w|f^(S0,w)?Z??} * f与f^的计算示例 例如，在右图的NFA中， f(0, ?)={1,2}; f(0,a)={0} ?是输入符号 f^(0, ?)= ?-CLOSURE(0)={0,1,2,3}; ? 是符号串 0 1 2 3 ? ? ? a b b c f^(0,a)= ?-CLOSURE(f(f^(0,?),a))= ?-CLOSURE(f({0,1,2,3},a)) = ?-CLOSURE(f(0,a)?…?f(3,a))= ?-CLOSURE({0})={0,1,2,3} f^(0,ac)= ?-CLOSURE(f(f^(0,a),c))= ?-CLOSURE(f({0,1,2,3},c)) = ?-CLOSURE(f(0,c)?…?f(3,c))= ?-CLOSURE({2})={2,3} * ?-NFA的用途：构造更复杂的FA 有了?-NFA，就可把识别各种不同单词的FA用?矢线（并连）连接起来，组成一个单一的NFA，经确定化后可得识别所有单词的DFA，由此可设计编译程序的词法分析器。 例如，某语言的单词有： 1.BEGIN 2.END 3.IF 4.THEN 5.ELSE 6.标识符 7.无符号整数 8. 9. = 10. = 11. 12. 13.= 可分别构造出识别各类单词的FA,然后将其合并为一个大FA,如书中P65图3-11所示。 * 3.3.5具有 ?动作的NFA的确定化 为具有?动作的NFA M=(K,?,f,S0,Z)构造相应的DFA M’=(K’,?,f’,q0,Z’) 基本思路：从M的初始状态S0出发，仅经过任意条矢线所能到达的状态集合作为M’的初态q0 ；然后从q0出发，将对输入符号a??进行状态转移所能到达的状态（包括转移后再经过?矢线所能到达的状态）所组成的集合作为M’的状态，如此反复，直到无新状态产生为止。 * 构造K’,f’和Z’的递归过程 1. 令 K’={[?-CLOSURE(S0)]}; f’=? ; 2. 对K’中尚未被标记的状态qi=[Si1,Si2,…,Sim]: (1)标记qi; (2)对于每个a??,令Ta=f({Si1,Si2,…,Sim},a); 对a转移 令 qj= [?-CLOSURE(Ta)]; 进行?矢线转移 (3)若qj?K’,则令K’=K’?{qj }; (4)令f’=f’ ?{f’(qi ,a)= qj }; 3. 重复2.,直到K’中无未标记的状态; 4. 令Z’={qj | qj ? Z??} (这里把qj 视为集合) * 确定化具有?动作的NFA的例子 例3.4 考虑右图具有?动作的NFA 1.q0 = [?-CLOSURE(0)] =[0,1,2,3]==K’; 2.q0未标记,故 (1)标记q0; 0 1 2 3 ? ? ? a b b c (2)f’(q0,a)=[?-CLOSURE(f({0,1,2,3},a))] =[?-CLOSURE({0})] = q0; f’(q0,b)=[?-CLOSURE(f({0,1,2,3},b))] =[?-CLOSURE({1,3})] = [1,3]= q1 ==K’; f’(q0,c)= [?-CLOSURE(f({0,1,2,3},c))] =[?-CLOSURE({2})] = [2,3]= q2 ==K’; * 确定化具有?动作的NFA的例子(续) 3. K’={q0,q1, q2},q1,q2 没有标记， (1) 标记q1; (2) f’(q1,a)=[?-CLOSURE(f({1,3},a