编译课程设计

❶ 一个编译原理的课程设计，急急急

回答：alkaid_pku
学长
4月14日 06:31 1. 预处理
2. 编译
3. 汇编
4. 查找库函数
5. 连接

❷ < DFA M状态最少化的程序实现>编译课程设计啊！！！还要求MFC的界面！！！ 求大神啊！搞定给财富值~

DFA状态数的最小化
package chapter3;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
/**
* 算法 3.39 最小化一个DFA的状态数
* @author Administrator
*
*/
publicclass Arithmetic_3_39
{
/**
* 输入一个DFA D
* @param d DFA状态转换表
* @param S 状态集合
* @param E 输入字符表
* @param s 开始状态
* @param F 接受状态集
* @return 一个DFA D', 它和D接受相同的语言, 且输入状态数最少
*/
publicint[][] convert(int[][] d, Set<Integer> S, char[] E, int s, Set<Integer> F)
{
// 首先用接受状态组和非接受状态组划分 PI
Set<Set<Integer>> PI = new HashSet<Set<Integer>>();
// 计算 S - F
S.removeAll(F);
PI.add(F);
PI.add(S);
// 最初, 令PInew = PI
Set<Set<Integer>> PInew = new HashSet<Set<Integer>>();
// TODO 解决浅复制带来的问题
PInew.addAll(PI);
while (true)
{
// 对PI中的每个组G
for (Iterator<Set<Integer>> it = PI.iterator(); it.hasNext(); )
{
List<Object> groupList = new ArrayList<Object>();
Set<Integer> G = it.next();
// 使用字符表测试G的元素
// 对于字符表的每个输入a
for (int i = 0; i < E.length; i++)
{
Map<Integer, Set<Integer>> groupMap = new HashMap<Integer, Set<Integer>>();
char a = E[i];
for (Iterator<Integer> sIt = G.iterator(); sIt.hasNext(); )
{
int stat = sIt.next();
// 从状态S出发 沿着a能够到达的状态
int tar = d[stat][a];
// 获取目标状态在PI中的位置
int idx = getElelementIdx(PI, tar);
Set<Integer> group = groupMap.get(idx);
if (group == null)
{
group = new HashSet<Integer>();
groupMap.put(idx, group);
}
group.add(stat);
}
groupList.add(groupMap);
}
// 在PInew中将G替换为对G进行分组得到的那些小组
PInew.remove(G);
PInew.addAll(setListPoly(groupList));
}
// 判断2个集合组是否相等
if (!isTwoSetGrpEqual(PI, PInew))
{
PI.clear();
PI.addAll(PInew);
} else
{
break;
}
}
// TODO 步骤4
for (Iterator<Set<Integer>> it = PI.iterator(); it.hasNext(); )
{
Set<Integer> set = it.next();
// 令S1是PI组中某个G的代表
for (Iterator<Integer> sIt = set.iterator(); sIt.hasNext(); )
{
int s1 = sIt.next();
while (sIt.hasNext())
{
// 用S1替换SWP
int swp = sIt.next();
for (int i = 0; i < d.length; i++)
{
for (int j = 0; j < d[i].length; j++)
{
if (d[i][j] == swp)
{
d[i][j] = s1;
}
}
}
// 删除SWP的转换函数
d[swp] = newint[]{};
}
}
}
return d;
}
/**
* 获取某个元素在集合组中的索引
* @param set
* @param element
* @return
*/
privateint getElelementIdx(Set<Set<Integer>> set, int element)
{
int idx = 0;
for (Iterator<Set<Integer>> it = set.iterator(); it.hasNext(); )
{
Set<Integer> g = it.next();
if (g.contains(element))
{
// TODO 检查HASHCODE 是否代表了集合的位置
return idx;
}
idx++;
}
return -1;
}
// 计算集合组聚合的结果
@SuppressWarnings("unchecked")
private Set<Set<Integer>> setListPoly(List<Object> oriSetList)
{
Set<Set<Integer>> result = new HashSet<Set<Integer>>();
if (oriSetList.size() > 0)
{
// 读取第一个集合组
Map<Integer, Set<Integer>> groupMap = (Map<Integer, Set<Integer>>)oriSetList.get(0);
for (Iterator<Integer> it = groupMap.keySet().iterator(); it.hasNext(); )
{
result.add(groupMap.get(it.next()));
}
for (int i = 1; i < oriSetList.size(); i++)
{
// 获取中间集合
Map<Integer, Set<Integer>> midMap = (Map<Integer, Set<Integer>>)oriSetList.get(i);
List<Set<Integer>> midSetList = new ArrayList<Set<Integer>>();
for (Iterator<Integer> it = midMap.keySet().iterator(); it.hasNext(); )
{
midSetList.add(midMap.get(it.next()));
}
// 开始计算
// 运算结果
List<Set<Integer>> calcResult = new ArrayList<Set<Integer>>();
for (Iterator<Set<Integer>> it = result.iterator(); it.hasNext(); )
{
Set<Integer> srcSet = it.next();
for (int k = 0; k < midSetList.size(); k++)
{
// 计算2个集合的交集
Set<Integer> mixed = getSetMixed(srcSet, midSetList.get(k));
// 如果结果不为空
if (!mixed.isEmpty())
{
// 保存运算结果
calcResult.add(mixed);
}
}
}
// 将计算结果替换result
result.clear();
result.addAll(calcResult);
}
}
return result;
}
// 计算二个集合的交集
private Set<Integer> getSetMixed(Set<Integer> set1, Set<Integer> set2)
{
Set<Integer> mixed = new HashSet<Integer>();
for (Iterator<Integer> it = set1.iterator(); it.hasNext(); )
{
int emu = it.next();
if (set2.contains(emu))
{
mixed.add(emu);
}
}
return mixed;
}
/**
* 判断2个集合组是否相等
* @param setGrp1
* @param setGrp2
* @return
*/
privateboolean isTwoSetGrpEqual(Set<Set<Integer>> setGrp1, Set<Set<Integer>> setGrp2)
{
boolean same = false;
int matchCounts = 0;
if (setGrp1.size() == setGrp2.size())
{
for (Iterator<Set<Integer>> it = setGrp1.iterator(); it.hasNext(); )
{
Set<Integer> set1 = it.next();
for (Iterator<Set<Integer>> it2 = setGrp2.iterator(); it2.hasNext(); )
{
Set<Integer> set2 = it2.next();
if (set2.equals(set1))
{
matchCounts++;
}
}
}
if (matchCounts == setGrp1.size())
{
same = true;
}
}
return same;
}
}
// 测试:
package test;
import java.util.HashSet;
import java.util.Set;
import chapter3.Arithmetic_3_39;
publicclass TestCase
{
publicstaticvoid main(String[] args)
{
new TestCase().test_339();
}
publicvoid test_339()
{
// DFA的转换表
int[][] d = {{}, {2, 3}, {2, 4}, {2, 3}, {2, 5}, {2, 3}};
// 输入状态集合
Set<Integer> S = new HashSet<Integer>();
S.add(1);
S.add(2);
S.add(3);
S.add(4);
S.add(5);
// 输入字符
char[] E = {0, 1};
int s = 1;
Set<Integer> F = new HashSet<Integer>();
F.add(5);
Arithmetic_3_39 a339 = new Arithmetic_3_39();
a339.convert(d, S, E, s, F);
}
}

对于一个NFA，当把它确定化之后，得到的DFA所具有的状态数可能并不是最小的。其原因之一，就在于上面所给出的确定化算法没有考虑到DFA中具有某种“同一性”的一些状态可加以合并的问题。所谓一个DFA M状态数的最小化，是指构造一个等价的DFA M′，而后者有最小的状态数。为了说明状态数最小化算法的思想，我们先引入可区分状态的概念。设M=(K,Σ,f,S0,Z)为一DFA，并设s和t是M的两个不同状态，我们说状态s,t为某一输入串w所区分，是指从s,t中之一出发，当扫视完w之后到达M的终态，但从其中的另一个状态出发，当扫视完同一个w后而进入非终态。如果两个状态s和t不可区分 (即对任何输入串w，当且仅当f(s,w)∈Z,f(t,w)∈Z)，则称s和t等价。显然，在一个DFA中，就识别符号串的作用而言，相互等价的状态处于同等的地位，故可设法将它们合并，以减少DFA的状态个数。下面给出一个将DFA M状态数最小化的算法。此算法的基本思想，就是将M的状态集K逐步进行划分，以期最后按上述状态的等价关系将K分裂为r个 (r≤|K|)互不相交的子集，使得属于同一子集中的任何两个状态都是等价的，而属于不同子集的任意两个状态都是可区分的。此算法的执行步骤如下：(1) 首先，将M的状态集K按终态与非终态划分为两个子集Z及K-Z，以构成初始分划，记为π={Z,K-Z}。(2) 设当前的分划π中已含有m个子集，即π={I1, I2, …, Im}其中，属于不同子集的状态是可区分的，而属于同一子集中的诸状态则是待区分的。即需对每一子集Ii={Si1,Si2,…,Sin}中各状态Sir (Sir∈K,1≤r≤n)进行考察，看是否还能对它们再进行区分。例如，Sip和Siq是Ii中的两个状态，若有某个a∈Σ，使f(Sip,a)=Sju及f(Siq,a)=Skv，而状态Sju及Skv分别属于π中两个不同的子集Ij和Ik，故Sju与Skv为某一w所区分，从而Sip和Siq必为w所区分，故应将子集Ii进一步细分，使Sip和Siq分别属于Ii的不同的子集。也就是说，对于每一子集Ii及每一a∈Σ，我们需考察Iai=f(Ii,a)=∪n[]r=1f(Sir,a)若Iai中的状态分别落于π中的p个不同的子集，则将Ii分为p个更小的状态子集I(1)i,I(2)i,…，I(p)i，使得对于每一个I(j)i,f(I(j)i,a)中的全部状态都落于π的同一子集之中。注意，若对某状态Sir,f(Sir,a)无意义，则Sir与任何Sit(f(Sit,a)有定义)都是可区分的。这样，每细分一次，就得一个新的分划πnew，且分划中的子集数也由原来的m个变为m+p-1个。(3) 若πnew≠π，则将πnew作为π再重复第2步中的过程，如此等等，直到最后得到一个分划π，使πnew=π，即π中的各个子集不能再细分为止。(4) 对于所得的最后分划π，我们从它的每一子集Ij={Sj1,Sj2,…,Sjr}中任选一个状态，如Sj1，作为Ij中所含各状态的代表，这些所选出的状态便组成了M′的状态集K′。而且，若Ij中含有M的初态，则Sj1为M′的初态；若Ij中含有M的终态，则Sj1为M′的一个终态。此外，为构成DFA M′，还应将各子集中落选的状态从原DFA M中删去，并将原来进入这些状态的所有矢线都改为进入它们的代表状态。例36设已给DFAM=({S0,S1,…,S4}, {a,b},f,S0,{S4})相应的状态转换图和状态转移矩阵如图314(a)及(b)所示。现用上述算法将M最小化。(1) 初始分划由两个子集组成，即π:{S0,S1,S2,S3}, {S4}(2) 为得到下一分划，考察子集{S0,S1,S2,S3}。为叙述方便起见，下面我们用记号{}a表示：当M分别处于该子集各状态之下，对输入符号a转移到的下一状态所组成的集合。因为{S0,S1,S2,S3}a={S1}{S0,S1,S2,S3}但{S0,S1,S2}b={S2,S3}{S3}b={S4}即{S0,S1,S2,S3}b不包含在π的同一子集之中，故应将{S0,S1,S2,S3}分为两个子集{S0,S1,S2}及{S3}，于是便得到下一分划πnew:{S0,S1,S2}, {S3}, {S4}又因πnew≠π，现以πnew作为π，即π:{S0,S1,S2}, {S3}, {S4}再考虑{S0,S1,S2}，因为{S0,S1,S2}a={S1}{S0,S1,S2}而{S0,S2}b={S2}{S1}b={S3}故应将{S0,S1,S2}再分为{S0,S2}及{S1}，从而又得到πnew:{S0,S2}, {S1}, {S3}, {S4}由于此时仍有πnew≠π，故再以πnew作为π，即π:{S0,S2}, {S1}, {S3}, {S4}现考察{S0,S2}，由于{S0,S2}a={S1}而{S0,S2}b={S2}{S0,S2}即{S0,S2}a与{S0,S2}b已分别包含在π的同一子集{S1}及{S0,S2}之中，故子集{S0,S2}已不能再分裂。此时πnew=π，子集分裂的过程宣告结束。(3) 现选择状态S0作为{S0,S2}的代表，将状态S2从状态转换图中删去，并将原来引向S2的矢线都引至S0，这样，我们就得到了化简后的DFA M′，如图315(a)及(b)所示。最后，再考察图314(a)及图315(b)所示的FA。容易看出，它们所接受的语言均是以abb为后缀的任意a,b符号串所组成的集合，也就说，这两个FA是相互等价的。实际上，我们还可以进一步证明如下的定理。定理32对于有同一接受集的FA，与之等价且具有最小状态数的DFA在同构意义下 (即不顾状态的命名)是惟一的。

❸ 编译原理课程设计－词法分析器设计（C语言）

#include"stdio.h"/*定义I/O库所用的某些宏和变量*/

#include"string.h"/*定义字符串库函数*/

#include"conio.h"/*提供有关屏幕窗口操作函数*/

#include"ctype.h"/*分类函数*/

charprog[80]={''},

token[8];/*存放构成单词符号的字符串*/

charch;

intsyn,/*存放单词字符的种别码*/

n,

sum,/*存放整数型单词*/

m,p;/*p是缓冲区prog的指针，m是token的指针*/

char*rwtab[6]={"begin","if","then","while","do","end"};

voidscaner(){

m=0;

sum=0;

for(n=0;n<8;n++)

token[n]='';

ch=prog[p++];

while(ch=='')

ch=prog[p++];

if(isalpha(ch))/*ch为字母字符*/{

while(isalpha(ch)||isdigit(ch))/*ch为字母字符或者数字字符*/{

token[m++]=ch;

ch=prog[p++];}

token[m++]='';

ch=prog[p--];

syn=10;

for(n=0;n<6;n++)

if(strcmp(token,rwtab[n])==0)/*字符串的比较*/{

syn=n+1;

break;}}

else

if(isdigit(ch))/*ch是数字字符*/{

while(isdigit(ch))/*ch是数字字符*/{

sum=sum*10+ch-'0';

ch=prog[p++];}

ch=prog[p--];

syn=11;}

else

switch(ch){

case'<':m=0;token[m++]=ch;ch=prog[p++];

if(ch=='>'){

syn=21;

token[m++]=ch;}

elseif(ch=='='){

syn=22;

token[m++]=ch;}

else{

syn=20;

ch=prog[p--];}

break;

case'>':m=0;token[m++]=ch;ch=prog[p++];

if(ch=='='){

syn=24;

token[m++]=ch;}

else{

syn=23;

ch=prog[p--];}

break;

case':':m=0;token[m++]=ch;ch=prog[p++];

if(ch=='='){

syn=18;

token[m++]=ch;}

else{

syn=17;

ch=prog[p--];}

break;

case'+':syn=13;token[0]=ch;break;

case'-':syn=14;token[0]=ch;break;

case'*':syn=15;token[0]=ch;break;

case'/':syn=16;token[0]=ch;break;

case'=':syn=25;token[0]=ch;break;

case';':syn=26;token[0]=ch;break;

case'(':syn=27;token[0]=ch;break;

case')':syn=28;token[0]=ch;break;

case'#':syn=0;token[0]=ch;break;

default:syn=-1;}}

main()

{

printf(" Thesignificanceofthefigures: "

"1.figures1to6saidKeyword "

"2. "

"3.figures13to28saidOperators ");

p=0;

printf(" pleaseinputstring: ");

do{

ch=getchar();

prog[p++]=ch;

}while(ch!='#');

p=0;

do{

scaner();

switch(syn){

case11:printf("(%d,%d) ",syn,sum);break;

case-1:printf(" ERROR; ");break;

default:printf("(%d,%s) ",syn,token);

}

}while(syn!=0);

getch();

}

程序测试结果

对源程序beginx:=9:ifx>9thenx:=2*x+1/3;end#的源文件，经过词法分析后输出如下图5-1所示：

具体的你在修改修改吧

❹ 编译原理 课程设计

好大的题，要用到bison【如何使用，请下载bison源代码分析--gcc源代码分析语法分析部分的电子版】和flex工具吧。