背景知识递归下降法语法分析程序的构造一.ppt

总 复 习(一） 后缀式(逆波兰式 ) 例：pos(A*B+C*D)=AB*CD*+ 逆波兰式的特点: 逆波兰式中的变量的次序与中缀式中的变量的次序完全一致。 逆波兰式中无括号。 逆波兰式中的运算符已按计算顺序排列。 例如，假定Si、Sj是某一LR(1)状态机的两个状态， 其中，u1、u2、v1、v2、t1、t2分别为归约展望符集 , a?VT。 在Si中有: u1?v1=?、u1?{a}=?、v1?{a}=?; 在Sj中有: u2?v2=?、u2?{a}=?、v2?{a}=?。 显然Si和Sj是同心状态，合并后得到新状态Sij : 定义1：由某一结点及其所有分支组成的部分树称为原树的一棵子树。 定义2：只有单层分支的子树称为简单子树。 定义3：最左简单子树的叶称为句柄。 定理： 1.每个句型都有一棵语法树，每个语法树的叶组成该句型。 2.每棵子树的叶组成短语，每棵简单子树的叶组成简单短语。 3.最左简单子树的叶组成句柄。 二、 3. 请给出下面文法G[A]的LL(1)分析表。 A ? aABe [1] | Bc [2] B ? dB [3] | ? [4] 三个重要的集合 First集 First(?) = { a ?VT | ??* a...} ? (if ?? *? then {?} else ? ) Follow集 Follow(A) = { a ?VT | S?+ ...Aa...} ? (if S?*...A then {#} else ? ) Predict集(Select集) 对每一文法符号X计算First(X)集(1) 若X ?VT ： First(X)={X} 若X ?VN : 对关于X的每一个产生式进行如下处理: Step1.形如: X? ? , 则: ? ? First(X) Step2.形如:X? a… , a ?VT则 : a ? First(X) 对每一文法符号X计算First(X)集(2) 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)收敛为止。 计算First(?)集 若符号串?=X1X2…Xn， 当X1,X2, … , Xi-1?*?，Xi 不能 ?* ?， 则: First(?)=?1i-1(First(Xj)-{?}) ? First(Xi) 若所有Xi 都能?*?， 则: First(?)= ?1n First(Xj) 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集 LL(1)分析表的构造 LL(1)分析表的构造方法： 对文法的每一个产生式求其predict集； 对文法的每一个产生式A→?进行如下处理： Predict( A→? )=（a1,a2,….,an); 则令： T(A,ai)=A→? ,i=1,2,3…,n LL(1)分析表的其它元素为error。 抽象地址的变化规律 I.处理声明部分: 处理前可用的 处理内容 处理后可用的 抽