编译原理——二到五章例题整理.ppt

一个上下文无关文法是如何定义一个语言呢?;例题 证明 i+5 是一个算术表达式;例题2.2;例题2.3;例题2.4 ;例题2.5 ;2.3.3 形式语言鸟瞰（4）;第三章： 思考题：写出下面正规式 ;确定的有限自动机;状态转换矩阵;状态转换矩阵 状态转换图;非确定的有限自动机;例如：正规式(a|b)*(aa|bb)(a|b)*;利用子集法求状态转换表：;继续求新的子集： I、Ia、Ib，得出下表：;对所有的状态子集重新命名，由此而得：;例题1;(3)用子集法求状态转换矩阵; (4) 重新命名得 DFA;例题2;例题3;例题4;例题5;例3.4(1);例3.4(2);例3.4(3);例题6;例题7 写出下面 NFA 对应的正规式;例题8;例题9将DFA 最小化;例题3.6;例题3.6;补充题;§4.3 LL(1) 分析法;例4.2 已知文法如下，消除左递归：;1.直接左递归消除的一般方法：;2. 间接左递归消除的一般方法;例4.3 已知文法如下，消除左递归：;例4.3 已知文法如下，消除左递归：;例4.3 已知文法如下，消除左递归：; 消除回溯，提左因子;终结首符集FIRST;例1 已知文法：;在不得回溯的前提下，对文法有何要求？; 如何将一个文法改造成任何非终结符的所有候选首符集都两两不相交？ 提取公共左因子。;例2 已知文法：;4.3.3 LL（1）分析条件;例3 已知文法：;例4.4 已知文法如下:;无回溯的自上而下分析方法;元语言符号;1）使用花括号{?}表示符号串 ? 的出现可 0 次或多次，即?* 。 {?} 表示?可重复0次至n次。 2）使用方括号[?]表示符号串 ? 的出现可有可无，表示可供选择的符号串。 3）使用圆括号可在规则中提取因子。A→x?1|x?2…|x?m 写成 A→x(?1|?2…|?m);？为何LL(1)文法要求： ? A ∈VN ，若 存在?∈ FIRST(?i），则 FIRST(A) ? FOLLOW(A)=?;例如：对输入串 011 进行自上而下分析;例4.5 已知文法如下：;例4.6 利用分析表,写出输入串i*i+i#的分析过程.; 求FIRST(X)的算法;求FOLLOW(A)的算法; 预测分析表的构造算法;任何文法均可用上述算法构造分析表;例4 已知文法： A ?aABc | a  B ?Bb | d;解：(1) 等价的LL(1)文法如下：;;;对输入串)i*+i# 预测分析器作出的移动过程;;问题;问题;问题;(1) first(S)={e , d , a , b , ?} first(T)={a , b , ?} first(R)={d , ?} first(D)={a , b};第五章例:设有文法;例 设有文法;自下而上分析中的主要问题： 哪些字符可以作为“可归约串”？;例如：;自下而上分析的中心问题: ;例5.1：文法：; 文法 E?T | E+T T?F | T*F F?i | (E) 求句型： E+T*F+i 的短语、直接短语和句柄。;可以用句柄进行准确归约。;定义 假设 ? 是文法 G 的一个句子，称序列;例如：; 对于规范句型，句柄的后面不会出现非终结符，即只能全是终结符。 （原因：对于移进-归约来说，这是由句柄的“最左”特征决定的。）; 一个句型的句柄是这个句型的语法树中最左深度为2的子树的叶子从左到右排列。; 已知文法： E?T | E+T |E-T T?F | T*F |T/F F?P | F^P P?i | (E) 求句型： E+T/F-F^i 的短语、直接短语和句柄。;例如5.3 写出输入串i*i+i的规范归约过程：;步骤 栈 输入串 动作 5 #T*i +i# 进栈 6 #T*F +i# 归约 …. 12 #E+T # 归约 13 #E