石河子大学信息科学与技术学院编译原理课件第五章 语法分析――自上而下.ppt

预测分析法中总控程序算法 BEGIN 首先把’#‘和文法开始符号推入栈； 把第一个输入符号读进a; FLAG：=TRUE； WHILE FLAG DO BEGIN 把栈顶符号上托出去并放在Ｘ中； IF X ? VT THEN IF X=a THEN 把下一个输入符号读进a ELSE ERROR ELSE IF X=‘#’ THEN IF X=a THEN FLAG:=FALSE ELSE ERROR ELSE IF ?[X,a]={X – X1X2..XK} THEN 把XK，X K-1,..,X1一一推进栈 ELSE　ERROR END OF WHILE; STOP/*分析成功，过程完毕*／ END 预测分析中的错误处理 在预测分析过程中，出现了下列两种情况，则说明遇到了语法错误： 栈顶的终结符与当前的输入符号不匹配； 非终结符A处于栈顶，面临的输入符号a，但分析表M中M[A,a]为空。 错误处理方法 遇到错误后，跳过输入串中的一些符号直至遇到“同步符号为止”。 预测分析中的错误处理 同步符号集的选择（原则） 把Follow(A)中的所有符号放入非终结符A的同步符号集。 把First(A)中的符号加入非终结符A的同步符号集。 如果一个非终结符产生空串，那么，推导ε的产生式可以作为缺省情况，可以推迟作错误检查。 如果不能匹配栈顶的终结符，弹出这个终结符，并发出一条消息，说明已经插入这个终结符，并继续进行分析。 预测分析法的错误处理 分析时： 若发现M[A，a]为空，则跳过输入符号a； 若该项为“同步”，则弹出栈顶的非终结符； 若栈顶的终结符号不匹配输入符号，则弹出栈顶的终结符。 发现语法错误时，除了使语法分析继续下去之外，还 要形成诊断信息。专门错误处理过程ERROR。 F —＞(E) F —＞id F T′—＞ ε T′—＞ ε T′—＞ *FT′ T′—＞ ε T′ T —＞ FT′ T —＞ FT′ T E′—＞ ε E′—＞ ε E′—＞ +TE′ E′ E —＞ TE′ E —＞ TE′ E # ) ( * + id E —＞ TE′ E′—＞ +TE′|ε T —＞ FT′ T′—＞ *FT′ |ε F —＞（E）|i 例 5.9：同步符号集 synch synch F —＞(E) synch F —＞id F T′—＞ ε T′—＞ ε T′—＞ *FT′ T′—＞ ε T′ synch synch T —＞ FT′ synch T —＞ FT′ T E′—＞ ε E′—＞ ε E′—＞ +TE′ E′ synch synch E —＞ TE′ E —＞ TE′ E # ) ( * + id 加入同步符号的LL（1）分析表 如：M[X，a]={X—＞UVW},就用WVU（U在顶）替换栈顶的X作为输出； 如：M[X，a]=error，则调用error程序。 对第3）条， X∈VN，查分析表M的元素M[X，a] 分析表格式 F —＞(E) F —＞id F T′—＞ ε T′—＞ ε T′—＞ *FT′ T′—＞ ε T′ T —＞ FT′ T —＞ FT′ T E′—＞ ε E′—＞ ε E′—＞ +TE′ E′ E —＞ TE′ E —＞ TE′ E # ) ( * + id E —＞ TE′ E′—＞ +TE′|ε T —＞ FT′ T′—＞ *FT′ |ε F —＞（E）|i 例5.5 按预测分析程序，对于输入 id+id*id 所作动作如下所示： 栈 输 入 输 出 1 #E id+id*id# 2 #E′T id+id*id# E—＞TE′ 3 #E′T′F id+id*id# T—＞FT′ 4 #E′T′id id+id*id# F—＞id 5 #E′T′ +id*id#