第09讲-语法分析-V-浅色

1、本讲纲要本讲纲要v回顾回顾 重点：重点：FIRSTFIRST集、集、FOLLOWFOLLOW集集v自上而下分析实现自上而下分析实现 非递归的预测分析方法非递归的预测分析方法 构造预测分析表构造预测分析表 预测分析的错误恢复预测分析的错误恢复23本讲纲要本讲纲要v回顾回顾 重点：重点：FIRSTFIRST集、集、FOLLOWFOLLOW集集v自上而下分析实现自上而下分析实现 非递归的预测分析方法非递归的预测分析方法 构造预测分析表构造预测分析表 预测分析的错误恢复预测分析的错误恢复4预测分析程序结构预测分析程序结构5v预测分析方法中的预测分析表的构建预测分析方法中的预测分析表的构建6v文法文法S

2、-ACD A-a| S-ACD A-a| C-c D-d C-c D-d7预测分析表的构建预测分析表的构建8 文法S-ACD A-a| C-c D-d910删除其解决二义性11本讲纲要本讲纲要v回顾回顾 重点：重点：FIRSTFIRST集、集、FOLLOWFOLLOW集集v自上而下分析实现自上而下分析实现 非递归的预测分析方法非递归的预测分析方法 构造预测分析表构造预测分析表 预测分析的错误恢复预测分析的错误恢复1213141516171819出错的一般处理方法出错的一般处理方法v1 1 查表，当前表项空白，指向记号流查表，当前表项空白，指向记号流的指针后移；的指针后移；v2 2 查表，当前表

3、项中含有同步记号查表，当前表项中含有同步记号synchsynch，将当前栈中的非终结符弹出栈；，将当前栈中的非终结符弹出栈；v3 3 栈顶终结符和当前指针指向的终结栈顶终结符和当前指针指向的终结符不匹配，将栈顶终结符弹出栈。符不匹配，将栈顶终结符弹出栈。v1 1 栈顶不动；栈顶不动；2,32,3指针不动指针不动20同步记号加到表同步记号加到表3.13.1的分析表的分析表上上非终非终结符结符输输 入入 符符 号号 id + * ( ) $E E TE E TE synch synchE E +TE E E T T FT synchT FT synch synchT T T * *FT T T F

4、 F id synch synchF (E) synch synch21栈输入输出$E+id*+id$出错，跳过$Eid*+id$id属于first（E）$E Tid*+id$E T Fid*+id$E T idid*+id$E T *+id$E T F* *+id$E T F+id$出错：“”正好在F的同步记号集合中，无须跳过任何记号；F被弹出$E T +id$22$E +id$E T+id$E Tid$E T Fid$E T idid$E T $E $2324 then aaaaa, bbbbcaaaaa, aa, bbbc, bbc当非终结符的产生式有多种选当非终结符的产生式有多种选择，

5、即意味着分析过程有不同择，即意味着分析过程有不同的展开方式。的展开方式。只能根据当前输入符号来决定只能根据当前输入符号来决定采用哪种展开方式（选择），采用哪种展开方式（选择），这样就有了这样就有了 FIRST（）函数。（）函数。25栈栈 输输 入入 输输 出出 $E id * * id $ $E T id * * id $ E TE $E T F id * * id $ T FT $E T id id * * id $ F id $E T * * id $ $E T F* * * * id $ T * *FT $E T F id $ $E T id id $ F id $E T $E $T $

6、E 26EE$栈栈 输输 入入 输输 出出 $E id * * id $ $E T id * * id $ E TE $E T F id * * id $ T FT $E T id id * * id $ F id $E T * * id $ $E T F* * * * id $ T * *FT $E T F id $ $E T id id $ F id $E T $E $T $E 27ETE TE$栈栈 输输 入入 输输 出出 $E id * * id $ $E T id * * id $ E TE $E T F id * * id $ T FT $E T id id * * id $ F

7、id $E T * * id $ $E T F* * * * id $ T * *FT $E T F id $ $E T id id $ F id $E T $E $T $E 28ETE FT FTE$栈栈 输输 入入 输输 出出 $E id * * id $ $E T id * * id $ E TE $E T F id * * id $ T FT $E T id id * * id $ F id $E T * * id $ $E T F* * * * id $ T * *FT $E T F id $ $E T id id $ F id $E T $E $T $E 29ETE FT idid

8、TE$栈栈 输输 入入 输输 出出 $E id * * id $ $E T id * * id $ E TE $E T F id * * id $ T FT $E T id id * * id $ F id $E T * * id $ $E T F* * * * id $ T * *FT $E T F id $ $E T id id $ F id $E T $E $T $E 30ETE FT idTE$栈栈 输输 入入 输输 出出 $E id * * id $ $E T id * * id $ E TE $E T F id * * id $ T FT $E T id id * * id $ F

9、 id $E T * * id $ $E T F* * * * id $ T * *FT $E T F id $ $E T id id $ F id $E T $E $T $E 31ETE FT id *T F*FTE$栈栈 输输 入入 输输 出出 $E id * * id $ $E T id * * id $ E TE $E T F id * * id $ T FT $E T id id * * id $ F id $E T * * id $ $E T F* * * * id $ T * *FT $E T F id $ $E T id id $ F id $E T $E $T $E 32ET

10、E FT id *T FFTE$栈栈 输输 入入 输输 出出 $E id * * id $ $E T id * * id $ E TE $E T F id * * id $ T FT $E T id id * * id $ F id $E T * * id $ $E T F* * * * id $ T * *FT $E T F id $ $E T id id $ F id $E T $E $T $E 33ETE FT id *T FididTE$栈栈 输输 入入 输输 出出 $E id * * id $ $E T id * * id $ E TE $E T F id * * id $ T FT

11、 $E T id id * * id $ F id $E T * * id $ $E T F* * * * id $ T * *FT $E T F id $ $E T id id $ F id $E T $E $T $E 34ETE FT id *T FidTE$栈栈 输输 入入 输输 出出 $E id * * id $ $E T id * * id $ E TE $E T F id * * id $ T FT $E T id id * * id $ F id $E T * * id $ $E T F* * * * id $ T * *FT $E T F id $ $E T id id $ F

12、 id $E T $E $T $E 35ETE FT id *T FidE$栈栈 输输 入入 输输 出出 $E id * * id $ $E T id * * id $ E TE $E T F id * * id $ T FT $E T id id * * id $ F id $E T * * id $ $E T F* * * * id $ T * *FT $E T F id $ $E T id id $ F id $E T $E $T $E 36ETE FT id *T Fid$37作业作业38本讲纲要本讲纲要v语言和文法语言和文法v语法分析方法语法分析方法v自上而下分析自上而下分析vFIR

13、STFIRST集和集和FOLLOWFOLLOW集集393.23.2 语言和文法语言和文法3.2.83.2.8 非上下文无关的语言结构非上下文无关的语言结构vL L1 1 = = wcw | wwcw | w属于属于( (a | ba | b) )* * 标识符的声明应先于其引用的抽象标识符的声明应先于其引用的抽象 vL L2 2 = = a an nb bm mc cn nd dm m | | n n 0, 0, m m 0 0 形参个数和实参个数应该相同的抽象形参个数和实参个数应该相同的抽象 vL L3 3 = = a an nb bn nc cn n | | n n 0 0 早先排版描述的

14、一个现象的抽象早先排版描述的一个现象的抽象403.23.2 语言和文法语言和文法vL L1 1 = = wcwwcwR R | w | w ( (a|ba|b) )* * S S aSa | bSb | c aSa | bSb | c vL L2 2 = = a a n nb bm mc cm md dn n | | n n 1, 1, m m 1 1 S S aSd | aAdaSd | aAdA A bAc | bcbAc | bcvL L 2 2 = = a a n nb bn nc cm md dm m | | n n 1 1，m m 1 1 S S ABABA A aAb | aba

15、Ab | abB B cBd | cdcBd | cd41有些类似的语言却是上下文无关的3.23.2 语言和文法语言和文法vL L3 3 =a a n nb b n n | | n n 1 1 S S aSb | ab aSb | abvL L3 3 是不能用正规式描述的语言的一个范例是不能用正规式描述的语言的一个范例 若存在接受若存在接受L L3 3 的的DFA DFA D D，状态数为状态数为k k个个 设设D D读完读完 , , a a, , aa aa, , , , a ak k 分别到达状态分别到达状态s s0 0, , s s1 1, , , , s sk k 至少有两个状态相同，

16、例如是至少有两个状态相同，例如是s si i和和s sj j，则则a aj jb bi i属于属于L L3 3 42sifs0标记为标记为ai的路径的路径标记为标记为bi的路径的路径标记为标记为aj i的路径的路径 有些类似的语言却是上下文无关的3.23.2 语言和文法语言和文法3.2.93.2.9 形式语言鸟瞰形式语言鸟瞰v 文法文法 G G = (= (V VT T , , V VN N, , S S, , P P) )v 0 0型文法：型文法： ， , , ( (V VN N V VT T) )* *, | , | | | 1 1v 1 1型文法：型文法：| | | | | | | |，

17、但但S S 可以例外可以例外v 2 2型文法：型文法：A A ，A A V VN N , , ( (V VN N V VT T) )* *v 3 3型文法：型文法：A A aBaB或或A A a a，A, BA, B V VN N , , a a V VT T v 短语文法、上下文有关文法、上下文无关文法、正规文法短语文法、上下文有关文法、上下文无关文法、正规文法 433.23.2 语言和文法语言和文法v例：例：L L3 3 a a n nb b n nc c n n| | n n 1 1的上下文有关文的上下文有关文法法S S aSBCaSBC S S aBCaBC CBCB BCBCaB aB abab bB bB bbbb bC bC bcbccC cC cccca an nb bn nc cn n的推导过程如下：的推导过程如下：S S * * a a n n-1-1S S ( (BCBC) ) n n 1 1用用S S aSBC naSBC n-1-1次次 S S + + a an n( (BCBC) )n n 用用S S aBC aBC 1 1次次 S S