第4章(小结)白底黑字详解.ppt

确定的自上而下分析法 ; 确定的自上而下分析法要求描述 语言的文法是 LL(1)文法。 ; (3)?求文法每个产生式的SELECT集。; 2. LL(1)文法是无左递归、无二义性文 法。;(2) 提取公共左因子; 4.根据文法规则构造递归下降分析程序 和预测分析表的方法;例1 设有文法G[E]：; T { +T | －T }; 例2 设有文法G[S];本章小结; FIRST(S)=FIRST(aAbDe)∪FIRST(d)={ a,d };本章小结; FOLLOW(S)={$,a,b,c,d,e}; 根据LL(1)文法的定义有:; 例3 已知一个有限输入字符集合Σ={a, b}, 请用高级程序语言编写一个能识别集合 L={an bn | n≥0}的程序。;本章小结;例 设有文法G[E]： ; 分析 首先消去文法左递归，得到文法 G[E]; 无左递归的文法不一定是LL(1)文法，根据LL(1)文法的判断条件，对非终结符 E, T, F有： ; SELECT(E →+TE)∩SELECT(E →ε) =FIRST(+TE)∩{FIRST(ε)∪FOLLOW(E)} ={ + }∩{ ), $ }= Φ; SELECT(F→id )∩SELECT(F→(E)) = FIRST(id)∩FIRST((E))={id}∩{(}= Φ;;;句子 id+id*id $ 的分析过程;1. 算符优先分析法特别适合于分析算 术表达式,但不是专用于分析算术表 达式的。;2. 算符优先文法的判别方法;(3) 根据算符优先关系定义，计算文法 G中任意两个终结符之间的优先关 系,即构造优先关系表。;3. 算符优先分析法只在终结符之间定 义了优先关系，因而它的归约过程 与规范归约是不同的，它不是对句 柄进行归约，而是对最左素短语进 行归约。;4. 求最左素短语的方法; 5. 根据优先关系定义构造优先关系表 的方法。;例1 设有文法G[S]:;S;例2 设有文法G[E]:;本章小结; 例3 设有表格结构文G[S]：; 计算文法G[S]的FIRSVT集和LASTVT集如下:;; 寻找终结符在左边，非终结符在右边的符号对有 ; 文法G[S]的优先关系表如下表所示;S → a | ∧| (T) T → T, S | S;本章小结;本章小结;本章小结;本章小结;本章小结;本章小结;本章小结;本章小结;本章小结;(1) 识别文法活前缀的DFA如下图所示。 ;(1) 识别文法活前缀的DFA如下图所示。 ;本章小结;本章小结;本章小结;本章小结;本章小结;本章小结;本章小结;本章小结;本章小结;本章小结;本章小结;本章小结;本章小结;本章小结;本章小结;符号串(( ))$的分析过程如下：;本章小结;本章小结;本章小结;其LR(1)分析表如下表：