編譯課程設計

❶ 一個編譯原理的課程設計，急急急

回答：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工具吧。