编译原理算法总结

1、双重嵌套case：先初始化状态变量state；当state =（所有非接受状态列表），执行：case state of1： case input character of（符 号）：advance the input；state :=（下一个状态）；表驱动：state := 1;ch := next input chara ctei；vvdiile not Acceptf state and not error state donewstate -Tstate, ch;if Advance state, ch then ch :=next input char;state := newstat

2、e,end while;if Acceptstate then accept,First集合算法：对于所有的非终结符A,执行First（A） -）：对任意First。）有修改时，执行：对于每一个产生式选择A-XX?治，执行：k 1 ； Continue true；当 Continue = true 且 k = n 时，执彳亍:将 FirstQQ - 添加到 First。）中；如果 FirstQQ中没有 6,则 Continue := false；k := k+ 1：如果 Continue = true,则将 e 添加入 First；Follow集合算法：初始化开始符号的Foilov/集Foll

3、owS姑待幻:=$：对于所有的不是开始符号的非终结符A,执行初始化：Follow :=,当对任意Follow集合有修改时，执行：对于每一个产生式A-X% .X，执行：对于每个是非终结符的K，执行：将 First(X+iX+2一 代添加到 Follow。中：(*注意：如果 i = n,则 X+iX+2 .X = e*)如果 FirstQJiX+2 . X0中有 8，则将 Follow添加到 FollowQQ中。LL(1)构造算法: 对每一个非终结符A和产生式选择A-重复以下两个步骤：1、对于First（a）中的每一个token（记号）,将A添加入MA可中；3、如果First（a）中有e的话，对于

4、Follow（A）中的每一个元素。（一个token（记号）或$）, 将A-添加入MA,可中。当满足一下两个条件时，该文法是LL（1）文法：1、对于每一个产生式 A-*（z】|q2| 1%，First0j）nFirst（勺），lWi,jWh, i若j,为空。2、对于每一个First（A）中包含8的非终结符A, First CFollow为空。LR（0）分析算法：设s为当前状态（在分析栈顶端）。然后执行以下动作：1、如果状态s包含任意的形如A-a.X6的移进项目（X为终结符），则接下来应执行动作为： 将当前的输入token压入分析栈栈顶。如果这个token是X,旦状态s包括 K.X$,则将 要被压

5、入分析栈的新状态就是包括了项目A-aX.p的状态。如果这个token不是状态s中的 形如前述的项目的X,则声明一个eiTor （错误）。2、如果状态s包含任意归约项（形如A-），的项），则接下来的动作应为：用规则A”进行 归约。（1）如果是用规则S，一S进行归约，S是开始状态，则这个动作等价于接受，输入为 空时是接受，输入不为空时是错误。（2）在所有的其他情况下，新状态按照以下步骤计算：。从分析栈中移除字符串7和所有与它相关的状态（根据DFA的构造，字符串丁必 须在堆栈顶部）在DFA中回到），结构体开始的状态（这一定是没有被7的移除所覆盖的状态）。再 一次，根据DFA的构造，这个状态必须包括形

6、如B-a.Ap的项目将A压入堆栈，并且将包含项目B-aA.p的状态作为新状态压入堆栈。一个文法是LR（O）文法当且仅当每一个状态都是一个移进状态或者是只包含一个归约 项目的归约态。SLR （1）分析算法：设s为当前状态（在分析栈顶端）。然后执行以下动作：1、如果状态s包含任意的形如AFX6的移进项目（X为终结符），且X是输入串中的下一 个token,则应执行的动作为：将当前输入token压入分析栈，且将要被压入分析栈的新状 态就是包括了项目A-aX.B的状态。2、如果状态s包含项目A-y,且输入串中的下一个token在Folio中，则应执行的动作 为：用规则Ap，.进行归约。（1）如果是用规则S，一S进行归约，S是开始状态，这等价于接受。这只会发生在下 个输入token是$的时候。（2）在所有的其他情况下，新状态按照以下步骤计算：。从分析栈中移除字符串y和所有与它相关的状态在DFA中回到），结构体开始的状态。这个状态必须包括形如B-a.Ap的项目将A压入堆栈，并且将包含项目B-aA.p的状态作为新状态压入堆栈。3、如果下一个输入token不在以上提供的两种情况中的话，则声明一个错误。一个文法是SLR文法，