编译原理第四章 (1.5).ppt

非终极符X计算First(X)集 若X ?VN : 对关于X的每一个产生式进行如下处理: Step1.形如: X? ? , 则: ? ? First(X) Step2.形如:X? a… , a ?VT则 : a ? First(X) Step3.对形如下的产生式: X?Y1Y2…Yi-1Yi…Yn 若：Y1,Y2, … ,Yi ?VN且Y1,Y2, … ,Yi-1?* ? 则: First(Y1)- {?} , First(Y2)- {?}, … , First(Yi-1)- {?}, First(Yi)都包含在First(X)中。 若： Yi ?VN且Yi ?* ? (i=1,2,…n), 则: First(Y1) , First(Y2), … , First(Yn) 都包含在First(X)中。 重复Step3 ，直至对所有A?VN，First(A)收敛为止。 1: 对所有A?VN 且 A非开始符 : 令Follow(A):={ }； 对开始符 S : 令Follow(S)={ # }； 2: 若有产生式A→xBy： 如果? ?First(y) 则： Follow(B) = Follow(B) ? (First(y)－{?}) ? Follow(A) 否则： Follow(B) = Follow(B) ? First(y) 3: 重复2和3，直至对所有A?VN，Follow(A)收 敛为止。 计算Predict集 非确定的自顶向下语法分析方法主要问题：虚假匹配而引起回溯，原因是： 1.由于相同左部的产生式的右部的FIRST集的交集不为空而引起回溯。 例：有如下文法G[Z]： Z? cAe | cAd A ? eb | a 分析字符串cad 。 2.由于某非终极符的产生式的右部能推导出?，且该非终极符的FOLLOW集中含有其某个产生式右部的FIRST集中的元素。 例：有如下文法G[S]： S ? aAS | b A ? bAS | ? | d 分析字符串ab 。 3.由于文法的左递归。 例：有如下文法G[S]： S? Sa S ? b 分析字符串baa。 非LL(1)文法到LL(1)文法的等价转换 消除左公共前缀 消除直接左递归 消除左递归  4.2 递归下降法4.2.1 递归下降法语法分析原理 递归下降法(Recursive-Descent Parsing) 对每个非终极符构造相应的一个子程序(称为语法分析子程序)，其功能是识别、分析该非终极符所能推导出的字符串。 4.2.2 递归下降法语法分析程序的构造 一、引进下面两个基本动作： ReadToken：从输入流把下一个TOKEN码读到变量token中。 Match(a)：检查token=a? 若是，则执行ReadToken，否则报错并作相应的处理。其中a是终极符（TOKEN的语法信息）。 对每一个非终极符A构造子程： 当产生式中形如: A ? ?1| ?2| …| ?n 则按下面的方法编写子程序A： procedure A( ) begin if token?Predict(A??1) then ?(?1) else if token?Predict(A??2) then ?(?2) else …… if token?Predict(A??n) then ?(?n) else err( ) end 例： E? ? T E’ E’ ? + T E’ | ? T ? F T’ T’ ? * F T’ | ? F ? id | ( E ) procedure E’ ( ) begin if token=“+” then Match(+); T； E’ else if token? { ) , # }