Luận văn Xây dựng bộ công cụ thực hiện một số giải thuật trong môn học ngôn ngữ hình thức và Automata

k=q; return (pt); } //============================================== //Hien thi cac trang thai trong tap thuc the void gtEARLEY::Display_Items(items *f, int th) { items *q; char st[20]; char ft[10]; CString trangthai; CString str_t,str_s; int ls,ch,s;//luat sinh, dau cham , trang thai q=f; sprintf(st,"TrÁng ThÀi : S[%d]",th); m_list_thuc_the.AddString(st); while(q!=NULL) { ls=q->p;//lay so thu tu luat sinh ch=q->i;//Lay vi tri dau cham s=q->f;//lay vi tri con tro str_t=StrBeforeDot(ls,ch); str_s=StrAfterDot(ls,ch); sprintf(ft,"%d ]",s); trangthai="[ " + ArrayVeTrai[ls]+"---->"+str_t+ " . "+str_s+" , "+ft; m_list_thuc_the.AddString(trangthai); q=q->link; } } //============================================== void gtEARLEY::OnButtonEarley() { // TODO: Add your control notification handler code here CString str; CString stdx; int chieudaichuoi; int i,ls,soluatdanxuat; char st[50]; m_chuoi_nhap.GetWindowText(str); chieudaichuoi=str.GetLength(); m_list_thuc_the.ResetContent(); m_list_dan_xuat.ResetContent(); DanXuat_So.RemoveAll(); DanXuat_Chuoi.RemoveAll(); Init_thucthe(); luat123(); luat456(); if (chieudaichuoi==0) Display_Items(tapthucthe[0],0); else { for (i=0;i<=chieudaichuoi; i++) if(tapthucthe[i]!=NULL) Display_Items(tapthucthe[i],i); else { sprintf(st,"Læi TÁi Kü Tø NhËp Th÷ %d",i); m_list_thuc_the.AddString(st); m_list_thuc_the.AddString("CÀc TËp TrÁng ThÀi Trê VÒ Sau Lª Ræng"); i=chieudaichuoi+1; } } ls=KiemTraThuocLG(chieudaichuoi); if(ls==-1) m_list_dan_xuat.AddString("Chuæi NhËp Kh¤ng Thuèc VŸn PhÁm !"); else {//In ra ccay dan xuat m_list_dan_xuat.AddString("+ Chuæi NhËp Thuèc VŸn PhÁm !"); XayDungTapT_N(); ChuoiDanXuat(ls,ArrayVePhai[ls].GetLength(),0,chieudaichuoi); soluatdanxuat=DanXuat_So.GetSize(); for(i=0;i<soluatdanxuat;i++) stdx=stdx+DanXuat_So[i]+" "; m_list_dan_xuat.AddString("+ Th÷ Tø CÀc LuËt Sinh Tham Gia Vªo QuÀ TrØnh DÉn XuÊt :"); InDanXuat(stdx,114); m_list_dan_xuat.AddString("+ Chuæi DÉn XuÊt Ra Chuæi NhËp :"); DanXuatRaChuoiNhap(); stdx=""; soluatdanxuat=DanXuat_Chuoi.GetSize(); for(i=0;i<soluatdanxuat;i++) stdx=stdx+DanXuat_Chuoi[i]; /*int lendx; int j; CString temp; soluatdanxuat=DanXuat_Chuoi.GetSize(); for(i=0;i<soluatdanxuat;i++) { temp=DanXuat_Chuoi[i]; lendx=temp.GetLength(); for(j=0;j<lendx;j++) stdx=stdx+temp[j]; }*/ stdx=stdx.Left(stdx.GetLength()-2); InDanXuat(stdx,72); } } //============================================== //TÛnh tËp trÁng thÀi S0 void gtEARLEY::luat123() { int i; int kq23; int soluatsinh; soluatsinh=ArrayVeTrai.GetSize(); //luat 1 for(i=0;i<soluatsinh;i++) { if (ArrayVeTrai[i]==BienKhoiDau) if (ArrayVePhai[i]=="#") tapthucthe[0]=Insert_data(tapthucthe[0],i,1,0); else tapthucthe[0]=Insert_data(tapthucthe[0],i,0,0); }//het luat 1 do { kq23=luat23(); } while (kq23==1); } //Thuc hien luat thu 3 int gtEARLEY::luat23() { items *q; items *pt; int soluat; int i,flay; q=tapthucthe[0]; flay=0; soluat=ArrayVeTrai.GetSize(); while(q!=NULL) { if (ChrAfterDot(q)=="")//neu dau cham o sau cung {//luat 2 pt=tapthucthe[0];//quay lai tap thuc the i=q->f while(pt!=NULL) { if(ChrAfterDot(pt)==ArrayVeTrai[q->p]) if(KiemTraTrangThai(0,pt->p,(pt->i)+1,0)==0) {tapthucthe[0]=Insert_data(tapthucthe[0],pt->p,(pt->i)+1,0); flay=1;} pt=pt->link; } } else //luat 3 { for (i=0;i<soluat;i++) if (ArrayVeTrai[i]==ChrAfterDot(q)) { if (ArrayVePhai[i]=="#") { if(KiemTraTrangThai(0,i,1,0)==0) tapthucthe[0]=Insert_data(tapthucthe[0],i,1,0); } else if(KiemTraTrangThai(0,i,0,0)==0) tapthucthe[0]=Insert_data(tapthucthe[0],i,0,0); } } q=q->link; } if (flay==1) return 1; else return 0; } //Thuc hien luat so 4 void gtEARLEY::luat456() { CString str; int j,chieudaichuoi; items *q; CString a; m_chuoi_nhap.GetWindowText(str); chieudaichuoi=str.GetLength(); for (j=0;j<chieudaichuoi;j++) { //luat 4 q=tapthucthe[j]; a=str[j]; while(q!=NULL) { if (ChrAfterDot(q)==a) if(KiemTraTrangThai(j+1,(q->p),(q->i)+1,(q->f))==0) tapthucthe[j+1]=Insert_data(tapthucthe[j+1],(q->p),(q->i)+1,(q->f)); q=q->link; } //het luat 4 luat56(j+1);//ap dung lien tiep luat 5 va 6 cho den khi khong them va duoc nua } } //========================================== //Thuc hien luat so 5 va so 6 void gtEARLEY::luat56(int th) { items *q;// con tro cua tap j=th items *pt;//con tro cua tap i int i; int soluat; q=tapthucthe[th]; soluat=ArrayVeTrai.GetSize(); while(q!=NULL) { if (ChrAfterDot(q)=="")//neu dau cham o sau cung {//luat 5 pt=tapthucthe[q->f];//quay lai tap thuc the i=q->f while(pt!=NULL) { if(ChrAfterDot(pt)==ArrayVeTrai[q->p]) if(KiemTraTrangThai(th,pt->p,(pt->i)+1,pt->f)==0) tapthucthe[th]=Insert_data(tapthucthe[th],pt->p,(pt->i)+1,pt->f); pt=pt->link; } } else {//luat 6 for (i=0;i<soluat;i++) if (ArrayVeTrai[i]==ChrAfterDot(q)) { if (ArrayVePhai[i]=="#") { if(KiemTraTrangThai(th,i,1,th)==0) tapthucthe[th]=Insert_data(tapthucthe[th],i,1,th); } else if(KiemTraTrangThai(th,i,0,th)==0) tapthucthe[th]=Insert_data(tapthucthe[th],i,0,th); } } q=q->link; } }//ket thuc luat56 //================================================ //Tra ve chuoi ky tu truoc dau cham CString gtEARLEY::StrBeforeDot(int ls, int ch) { int i; CString Temp,Vp; Vp=ArrayVePhai[ls]; Temp=""; for(i=0; i<ch;i++) Temp=Temp+Vp[i]; return Temp; } //================================================ //Tra ve chuoi ky tu sau dau cham CString gtEARLEY::StrAfterDot(int ls, int ch) { int lenvephai; int i; CString Temp,Vp; Vp=ArrayVePhai[ls]; lenvephai=Vp.GetLength(); Temp=""; for (i=ch; i<lenvephai;i++) Temp=Temp+Vp[i]; return Temp; } //================================================ //Tra ve ky ttu sau dau cham CString gtEARLEY::ChrAfterDot(items *pt) { int sl,ch; CString Vp; sl=(pt->p); ch=(pt->i); Vp=ArrayVePhai[sl]; if (ch<Vp.GetLength()) return (Vp[ch]); else return ""; } //Kiem tra xem trong trang thai thu pt co tap trang thai (p,i,ft) chua int gtEARLEY::KiemTraTrangThai(int pt, int p, int i,int ft) { items *q; q=tapthucthe[pt]; while (q!=NULL) { if ((q->p==p) && (q->i==i) && (q->f==ft)) return 1; else q=q->link; } return 0; } void gtEARLEY::OnButtonVP_Goc() { // TODO: Add your control notification handler code here BanDau.DoModal(); } int gtEARLEY::KiemTraThuocLG(int th) { int i,len; int soluat; if (tapthucthe[th]==NULL) return -1;//chuoi khong thuoc van pham else { soluat=ArrayVeTrai.GetSize(); for (i=0; i<soluat;i++) { len=ArrayVePhai[i].GetLength(); if (ArrayVeTrai[i]==BienKhoiDau) if(KiemTraTrangThai(th,i,len,0)==1) return i; } } return -1; } //=================================================== void gtEARLEY::ChuoiDanXuat(int ls,int ch, int i, int j) { char stt[10]; int k,l,m,r; items *q; items *pt; CString Vp; sprintf(stt,"%d",ls); DanXuat_So.Add(stt); Vp=ArrayVePhai[ls]; m=Vp.GetLength(); k=m-1; l=j; while(k!=-1) { if (FindChar(Vp[k],TapT)==1) { k=k-1; l=l-1; } else { q=tapthucthe[l]; while(q!=NULL) { if(ArrayVeTrai[q->p]==Vp[k] && ChrAfterDot(q)=="") { r=q->f; pt=tapthucthe[r];//tim trong tap thuc the r=q->j; while(pt!=NULL) { if((ChrAfterDot(pt)==Vp[k])&&(k==pt->i) && ((pt->f)==i) && (ArrayVePhai[pt->p]==ArrayVePhai[ls])&&//(ArrayVePhai[pt->p].GetLength()==m) && (ArrayVeTrai[pt->p]==ArrayVeTrai[ls])) { ChuoiDanXuat(q->p,q->i,r,l);//ArrayVePhai[q->p].GetLength(),r,l); k=k-1; l=r; pt=NULL; q=NULL; } else { pt=pt->link; if (pt==NULL) q=q->link; } }//end while pt }//end if else q=q->link; }//end while q }//end else }//end while k }//end function //============================================== //tra ve 1 neu co tra ve 0 neu khong co int gtEARLEY::FindChar(CString string, CString V) { if (V.Find(string)!=-1) return 1; else return 0; } //============================================= void gtEARLEY::XayDungTapT_N() { int sokytu; int i; //Xay dung tap T sokytu=ArrayKt.GetSize(); for(i=0;i<sokytu;i++) TapT=TapT+ArrayKt[i]; //Xay dung tap N sokytu=ArrayKkt.GetSize(); for(i=0;i<sokytu;i++) TapN=TapN+ArrayKkt[i]; } //=============================================== void gtEARLEY::InDanXuat(CString stdx,int so) { CString s1; CString s2; while (stdx.GetLength()>so) { s1=stdx.Left(so); m_list_dan_xuat.AddString(s1); s2=stdx.Mid(so,stdx.GetLength()); stdx=s2; } m_list_dan_xuat.AddString(stdx); } //======================================= void gtEARLEY::DanXuatRaChuoiNhap() { int i,n,l,k,j; int len_so,len_chuoi; CString st,str,str1; len_so=DanXuat_So.GetSize(); i=atoi(DanXuat_So[0]); DanXuat_Chuoi.Add(ArrayVeTrai[i]); DanXuat_Chuoi.Add("=>"); DanXuat_Chuoi.Add(ArrayVePhai[i]); DanXuat_Chuoi.Add("=>"); len_chuoi=DanXuat_Chuoi.GetSize(); n=len_chuoi-2; for(j=1;j<len_so;j++) { st=DanXuat_Chuoi[n]; l=st.GetLength(); k=l-1; i=atoi(DanXuat_So[j]); while(k>=0) { if (st[k]==ArrayVeTrai[i]) { str=st.Left(k); str=str+ArrayVePhai[i]; str1=st.Mid(k+1,st.GetLength()); str=str+str1; DanXuat_Chuoi.Add(str); DanXuat_Chuoi.Add("=>"); len_chuoi=DanXuat_Chuoi.GetSize(); n=len_chuoi-2; k=-1; } else k=k-1; }//while }//for } void gtEARLEY::OnButtonHelp() { // TODO: Add your control notification handler code here WinHelp(8,HELP_CONTEXT);//(0,HELP_CONTENTS); } void gtEARLEY::OnChangeChuoi_Nhap() { // TODO: If this is a RICHEDIT control, the control will not // send this notification unless you override the CDialog::OnInitDialog() // function to send the EM_SETEVENTMASK message to the control // with the ENM_CHANGE flag ORed into the lParam mask. // TODO: Add your control notification handler code here m_list_dan_xuat.ResetContent(); m_list_thuc_the.ResetContent(); } GIAÛI THUAÄT CYK // gtCKY.cpp : implementation file #include "stdafx.h" #include "Automat.h" #include "gtCKY.h" #ifdef _DEBUG #define new DEBUG_NEW #undef THIS_FILE static char THIS_FILE[] = __FILE__; #endif ///////////////////////////////////////////////////////////////////////////// // gtCKY dialog gtCKY::gtCKY(CWnd* pParent /*=NULL*/) : CDialog(gtCKY::IDD, pParent) { //{{AFX_DATA_INIT(gtCKY) //}}AFX_DATA_INIT } void gtCKY::DoDataExchange(CDataExchange* pDX) { CDialog::DoDataExchange(pDX); //{{AFX_DATA_MAP(gtCKY) DDX_Control(pDX, IDC_EDIT_STR, m_chuoi_nhap); DDX_Control(pDX, IDC_LIST_TABLE_T, m_list_t); DDX_Control(pDX, IDC_LIST_P, m_list_p); DDX_Control(pDX, IDC_LIST_DAN_XUAT, m_list_dan_xuat); //}}AFX_DATA_MAP } BEGIN_MESSAGE_MAP(gtCKY, CDialog) //{{AFX_MSG_MAP(gtCKY) ON_BN_CLICKED(IDC_BUTTON_CYK, OnButtonCYK) ON_BN_CLICKED(IDC_BUTTON_VP_DAU, OnButtonVP_Goc) ON_EN_CHANGE(IDC_EDIT_STR, OnChangeChuoiNhap) //}}AFX_MSG_MAP END_MESSAGE_MAP() ///////////////////////////////////////////////////////////////////////////// // gtCKY message handlers BOOL gtCKY:: OnInitDialog() { int soluat;//So luat sinh da luu int i; char st[250]; CString luatsinh; CDialog::OnInitDialog(); Chomsky(); soluat=ChomskyVeTrai.GetSize(); //Cho hien lai tap luat sinh for(i=0;i<soluat;i++) { sprintf(st,"(%d) ",i); luatsinh=st+ChomskyVeTrai[i]+"---->"+ChomskyVePhai[i]; m_list_p.AddString(luatsinh); } m_list_t.SetHorizontalExtent(3000); m_list_dan_xuat.SetHorizontalExtent(700); m_list_p.SetHorizontalExtent(200); //Copy cac bien toan cuc cho Dialog VPBanDau Goc_Chomsky.ArrayKkt.Copy(ArrayKkt); Goc_Chomsky.ArrayKt.Copy(ArrayKt); Goc_Chomsky.ArrayVePhai.Copy(ArrayVePhai); Goc_Chomsky.ArrayVeTrai.Copy(ArrayVeTrai); Goc_Chomsky.ArrayLuatSinh.Copy(ArrayLuatSinh); Goc_Chomsky.BienKhoiDau=BienKhoiDau; Goc_Chomsky.ChomskyKkt.Copy(ChomskyKkt); Goc_Chomsky.ChomskyKt.Copy(ChomskyKt); Goc_Chomsky.ChomskyVePhai.Copy(ChomskyVePhai); Goc_Chomsky.ChomskyVeTrai.Copy(ChomskyVeTrai); Goc_Chomsky.ChomskyBanDau=ChomskyBanDau; Goc_Chomsky.VeTrai_TG.Copy(VeTraiVoDung); Goc_Chomsky.VePhai_TG.Copy(VePhaiVoDung); return TRUE; } //Thuc hien giai thuat CYK void gtCKY::OnButtonCYK() { // TODO: Add your control notification handler code here int i,j,chieudaichuoi; int soluatdanxuat; CString str,stdx; m_chuoi_nhap.GetWindowText(str); Goc_Chomsky.str=str; m_list_t.ResetContent(); m_list_dan_xuat.ResetContent(); DanXuat_So.RemoveAll(); DanXuat_Chuoi.RemoveAll(); chieudaichuoi=str.GetLength(); for (i=0;i<250;i++) for (j=0;j<250;j++) T[i][j]=""; XayDungBangT(str); //Kiem tra chuoi nhap co thuoc van pham hay khong if (KiemTraChuoiThuocL(T[1][chieudaichuoi])==0) m_list_dan_xuat.AddString("Chuæi NhËp Kh¤ng Thuèc Ng¤n Ngö L(G)"); else { m_list_dan_xuat.AddString("+ Chuæi NhËp Thuèc Ng¤n Ngö L(G)"); //tao chuoi dan xuat gen(1,chieudaichuoi,BienKhoiDau,str); //In ra chuoi dan xuat so m_list_dan_xuat.AddString("+ Th÷ Tø Àp Dóng CÀc LuËt Sinh TrÀi NhÊt :"); InDanXuat_Chuoi(InDanXuat_So(),70); DanXuatRaChuoiNhap(); stdx=""; soluatdanxuat=DanXuat_Chuoi.GetSize(); for(i=0;i<soluatdanxuat;i++) stdx=stdx+DanXuat_Chuoi[i]; m_list_dan_xuat.AddString("+ Chuæi DÉn XuÊt TrÀi NhÊt Ra C¡u NhËp :"); stdx=stdx.Left(stdx.GetLength()-2); InDanXuat_Chuoi(stdx,50); } //Copy cac bien cho class VPgoc_ch Goc_Chomsky.DanXuat_So.Copy(DanXuat_So); Goc_Chomsky.DanXuat_Chuoi.Copy(DanXuat_Chuoi); } /////////////////////////////////////////// //Xay dung bang phan tich T void gtCKY::XayDungBangT(CString str) { int i,j; int chieudaichuoi; CString st; chieudaichuoi=str.GetLength(); if (chieudaichuoi==0) MessageBox("BÁn Ch§a ThËt Sø NhËp Vªo Chuæi CÇn Ph¡n TÛch", "Th¤ng BÀo",MB_ICONSTOP); else { //buoc 1 for(i=0;i<chieudaichuoi;i++) T[i+1][1]=TimLuatSinh_a(str[i]); j=1; while (j!=chieudaichuoi) { j=j+1; line(j,chieudaichuoi); } } //Hien thi bang phan tich T for (j=1; j<=chieudaichuoi;j++) { st=""; for (i=1;i<=chieudaichuoi-j+1;i++) { int l; CString s; char s1[250]; s=T[i][j]; sprintf(s1,"T%d,%d=",i,j); l=s.GetLength(); while(l<5) {s=s+" "; l=s.GetLength();} st=st+s1+"{"+s+"}"+" "; } m_list_t.AddString(st); } } /////////////////////////////////////////// void gtCKY::line(int j, int n) { int i,j1,j11,k,k1,x,y; CString Tik,Tk1_j11,B,C; //(1) i=1;j1=n-j+1; while(i<=j1) { k=1; //(2) while (k<=j) { k1=i+k;j11=j-k; //(3) //Khao sat Tik va Tk1j11 (4) Tik=T[i][k]; Tk1_j11=T[k1][j11]; for (x=0;x<Tik.GetLength();x++) for (y=0;y<Tk1_j11.GetLength(); y++) { B=Tik[x]; C=Tk1_j11[y]; T[i][j]=Hoi(T[i][j],TimLuatSinhBC(B,C)); }//for k=k+1; //(5) }//while (k<j) //(7)(8) i=i+1; }//while (i<j1) } //////////////////////////////////////////////////// //neu co luat sinh co ve trai =BC thi tra ve chuoi so //chua ve trai cua tat ca cac luat sinh do //nguoc lai tra ve trong CString gtCKY::TimLuatSinhBC(CString B, CString C) { int soluat; CString temp,st; int i; temp=B+C; soluat=ChomskyVeTrai.GetSize(); for(i=0;i<soluat;i++) if (temp==ChomskyVePhai[i]) st=st+ChomskyVeTrai[i]; if (st.GetLength() !=0) return st; else return ""; } //neu co luat sinh thi tra ve string chua tat ca ve trai //nguoc lai tra ve chuoi rong CString gtCKY::TimLuatSinh_a(CString a) { int soluat; CString st; int i; soluat=ChomskyVeTrai.GetSize(); for(i=0;i<soluat;i++) if (ChomskyVePhai[i]==a) st=st+ChomskyVeTrai[i]; if (st.GetLength() !=0) return st; else return ""; } ///////////////////////////////////////////// //Tra ve hoi cua nhai CString CString gtCKY::Hoi(CString B, CString C) { int i; CString Temp; Temp=""; for(i=0;i<B.GetLength();i++) if (Temp.Find(B[i])==-1) Temp=Temp+B[i]; for(i=0;i<C.GetLength();i++) if (Temp.Find(C[i])==-1) Temp=Temp+C[i]; return Temp; } //Neu chuoi thuoc ngon ngu L thi tra ve 1 //nguoc lai tra ve 0 int gtCKY::KiemTraChuoiThuocL(CString st) { int i,len; len=st.GetLength(); for(i=0;i<len;i++) if(st[i]==BienKhoiDau) return 1; return 0; } //tao ra chuoi dan xuat void gtCKY::gen(int i, int j, CString A, CString Str) { int k,len1,len2,x,y; int h; char st[250]; CString B,C,BC; CString Tik,Tik_jk; if (j==1) { sprintf(st,"%d",Pa(A,Str[i-1])); DanXuat_So.Add(st); } else if (j>1) { k=1; while(k<j) { Tik=T[i][k]; Tik_jk=T[i+k][j-k]; len1=Tik.GetLength(); len2=Tik_jk.GetLength(); for (x=0;x<len1;x++) for (y=0;y<len2;y++) { B=Tik[x]; C=Tik_jk[y]; BC=B+C; if (Pa(A,BC)!=-1) { sprintf(st,"%d",Pa(A,BC)); DanXuat_So.Add(st); y=len2; x=len1; h=k; k=j; } } k=k+1; }//end while gen(i,h,B,Str); gen(i+h,j-h,C,Str); }//end else } //Tra ve so thu tu cua luat sinh P-->ai int gtCKY::Pa(CString A, CString a) { int soluat; int i; soluat=ChomskyVeTrai.GetSize(); for(i=0;i<soluat;i++) if ((ChomskyVeTrai[i]==A)&&(ChomskyVePhai[i]==a)) return i; return -1; } ////////////////////////////////////////// //In ra chuoi dan xuat so CString gtCKY::InDanXuat_So() { int len,i; CString dxs; len=DanXuat_So.GetSize(); for(i=0;i<len;i++) dxs=dxs+DanXuat_So[i]+" "; dxs=" "+dxs; return dxs; } //Dan xuat ra chuoi nhap tu tap dan xuat so A=>abgd void gtCKY::DanXuatRaChuoiNhap() { int i,n,l,k,j; int len_so,len_chuoi; CString st,str,str1; len_so=DanXuat_So.GetSize(); i=atoi(DanXuat_So[0]); DanXuat_Chuoi.Add(ChomskyVeTrai[i]); DanXuat_Chuoi.Add("=>"); DanXuat_Chuoi.Add(ChomskyVePhai[i]); DanXuat_Chuoi.Add("=>"); len_chuoi=DanXuat_Chuoi.GetSize(); n=len_chuoi-2; for(j=1;j<len_so;j++) { st=DanXuat_Chuoi[n]; l=st.GetLength(); k=0; i=atoi(DanXuat_So[j]); while(k<l) { if (st[k]==ChomskyVeTrai[i]) { str=st.Left(k); str=str+ChomskyVePhai[i]; str1=st.Mid(k+1,st.GetLength()); str=str+str1; DanXuat_Chuoi.Add(str); DanXuat_Chuoi.Add("=>"); len_chuoi=DanXuat_Chuoi.GetSize(); n=len_chuoi-2; k=l; } else k=k+1; }//while }//for } //=============================================== void gtCKY::InDanXuat_Chuoi(CString stdx,int so) { CString s1; CString s2; while (stdx.GetLength()>so) { s1=stdx.Left(so); m_list_dan_xuat.AddString(s1); s2=stdx.Mid(so,stdx.GetLength()); stdx=s2; } m_list_dan_xuat.AddString(stdx); } //////////////////////////////////////////// //Hien Thi van pham goc void gtCKY::OnButtonVP_Goc() { // TODO: Add your control notification handler code here Goc_Chomsky.DoModal(); } /////////////////////////////////////////// //Phan chuyen van pham bat ky ve gtCKY void gtCKY::LoaiBoTatCa() { //Loai Bo Rong { CStringArray Vn;//Mang chua cac ve trai co kha ngag sinh ra rong; CString V; CString string; CString stringp; CString Vtemp; CString stringkt; CString stringkkt_kt; int i;//bien de duyet int soluat; int soluattrong; int sokt; //Xoa het cac gia tri trong VePhaiRong & VeTraiRong VePhaiRong.RemoveAll(); VeTraiRong.RemoveAll(); {//Tim cac ky hieu khong ket thuc dan xuat ra rong sokt=ArrayKt.GetSize(); for(i=0;i<sokt;i++) if(ArrayKt[i]!="#") stringkt=stringkt+ ArrayKt[i]; soluat=ArrayVeTrai.GetSize(); for(i=0;i<soluat;i++) { string=ArrayVePhai[i]; if(FindStr(string,stringkt)!=0) stringkkt_kt=stringkkt_kt+ArrayVeTrai[i]; }//end for stringkkt_kt=stringkkt_kt+stringkt; //Tim tap cac bien dan xuat ra cac ky tu ket thuc for(i=0;i<soluat;i++) { string=ArrayVePhai[i]; if((FindStr(string,stringkkt_kt)!=0) &&(FindStr(ArrayVeTrai[i],stringkkt_kt)==0)) { stringkkt_kt=stringkkt_kt+ArrayVeTrai[i]; i=-1; } } }//het tim cac ky hieu khong ket thuc dan xuat ra rong soluat=ArrayVeTrai.GetSize(); V=""; //Duyet qua cac luat sinh rong; for(i=0;i<soluat;i++) { string=ArrayVePhai[i]; if(string=="#") Vn.Add(ArrayVeTrai[i]); } soluattrong=Vn.GetSize(); //In ra cua so minh hoa tap Vn for(i=0;i<soluattrong;i++) V=V+Vn[i]; //Duyet qua cac luat sinh ma ve phai tat ca cac ki tu van pham man trong tap Vn int j; int chieudaivephai; i=0; while (i<soluat) { string=ArrayVePhai[i]; chieudaivephai=string.GetLength(); j=0; while(j<chieudaivephai) { if(V.Find(string[j])!=-1) { j=j+1; if (j==chieudaivephai) { if(V.Find(ArrayVeTrai[i])==-1) { Vn.Add(ArrayVeTrai[i]); V=V+ArrayVeTrai[i]; i=0; } } } else break; } i=i+1; } //Xay dung to hop thay the cac chuoi ve phai bang cac ky hieu trong Vn { int cd;//bien de cap nhat chieu dai luat int j;//bien duyet int k; int n; CStringArray VeTraiTemp; CStringArray VePhaiTemp; CString strp; CString str1; CStringArray strtemp; //Chuoi temp de luu chuoi xoa int chieudaistr; int flag; soluat=ArrayVeTrai.GetSize(); for(i=0;i<soluat;i++) { if(ArrayVePhai[i] !="#") { VeTraiTemp.Add(ArrayVeTrai[i]); VePhaiTemp.Add(ArrayVePhai[i]); cd=VeTraiTemp.GetSize(); for(j=0;j<cd;j++) { strp=VePhaiTemp[j]; chieudaistr=strp.GetLength(); for(k=0;k<chieudaistr;k++) { if(V.Find(strp[k])!=-1) { int m; CString st; for(m=0;m<chieudaistr;m++) {st=strp[m];strtemp.Add(st);} strtemp.RemoveAt(k); for(m=0;m<chieudaistr-1;m++) str1=str1+strtemp[m]; //kiem tra xem strtemp co trong mang VePhaiTemp chua { int soluatsinh; int l; soluatsinh=VePhaiTemp.GetSize(); for(l=0;l<soluatsinh;l++) { stringp=VePhaiTemp[l]; if(stringp.Compare(str1)==0) { flag=0; l=soluatsinh+1; } else flag=1; } if((flag==1) || (soluatsinh==0)) flag= 1; } if ((flag!=0) && (str1!="")) { VePhaiTemp.Add(str1); VeTraiTemp.Add(ArrayVeTrai[i]); cd=VePhaiTemp.GetSize(); } strtemp.RemoveAll(); str1=""; }//end if(V.Find... }//end for(k=0;... }//end for(j=0;... cd=VePhaiTemp.GetSize(); for (n=0;n<cd;n++) { if(KiemTraChuoiPhai(VePhaiTemp[n],VeTraiTemp[n])!=0) { if((KiemTraChuoiPhaiRong(VePhaiTemp[n],V) !=0) || (FindChar(VePhaiTemp[n],stringkkt_kt) !=0)) { VePhaiRong.Add(VePhaiTemp[n]); VeTraiRong.Add(VeTraiTemp[n]); } } } VePhaiTemp.RemoveAll(); VeTraiTemp.RemoveAll(); }//end if(ArrayVePhai[i] !="#") }//end for(i=0;i<soluat;i++) }//end procedure }//end procedure loai bo rong // Loai bo don vi { // TODO: Add your control notification handler code here int soluatsinh; int i;//bien duyet int sokkt; int soluat; int flag; CString strkkt; CString str; CStringArray DonViTrai; CStringArray DonViPhai; CStringArray KhongDonViTrai; CStringArray KhongDonViPhai; CStringArray TempT; CStringArray TempP; CStringArray DVT; CStringArray DVP; int tm; int n,j,k; int soluatkdv; int daitemp; VeTraiDonVi.RemoveAll(); VePhaiDonVi.RemoveAll(); strkkt=""; sokkt=ArrayKkt.GetSize(); //Tim chuoi cac ki tu khong ketthuc for(i=0;i<sokkt;i++) { strkkt=strkkt+ArrayKkt[i]; } soluatsinh=VeTraiRong.GetSize(); //Tim nhung luat sinh la don vi for(i=0;i<soluatsinh;i++) { str=VePhaiRong[i]; if((strkkt.Find(str)!=-1) && (str.GetLength()==1)) { DonViTrai.Add(VeTraiRong[i]); DonViPhai.Add(str); }//end for(i=0;i<soluatsinh;i++) else { KhongDonViTrai.Add(VeTraiRong[i]); KhongDonViPhai.Add(str); } } //Tim cac cay dan xuat cua cac luat sinh don vi soluat=DonViTrai.GetSize(); for(i=0;i<soluat;i++) { TempT.Add(DonViTrai[i]); TempP.Add(DonViPhai[i]); daitemp=TempT.GetSize(); for (j=0;j<daitemp;j++) { for(k=0;k<soluat;k++) { if((TempP[j]==DonViTrai[k]) && (TempT[j].Compare(DonViPhai[k]) !=0)) { { CString string1; CString string2; int a;//Bien dung de duyet qua int soluatsinh; soluatsinh=TempT.GetSize(); for(a=0;a<soluatsinh;a++) { string1=TempT[a]; string2=TempP[a]; if(string1.Compare(TempT[j])==0 && string2.Compare(DonViPhai[k])==0) { flag=0; a=soluatsinh+1; } else flag=1; } if((flag==1) || (soluatsinh==0)) flag=1;else flag= 0; }//end khoi if (flag !=0) { TempT.Add(TempT[j]); TempP.Add(DonViPhai[k]); daitemp=TempT.GetSize(); } }//end if (Temp.... }//end for(k... }//end for j tm=TempT.GetSize(); for (n=0;n<tm;n++) { if(DVT.GetSize() ==0) {DVT.Add(TempT[n]); DVP.Add(TempP[n]);} else { CString string1; CString string2; int b;//Bien dung de duyet qua int soluatsinh; soluatsinh=DVT.GetSize(); for(b=0;b<soluatsinh;b++) { string1=DVT[b]; string2=DVP[b]; if(string1.Compare(TempT[n])==0 && string2.Compare(TempP[n])==0) { flag=0; b=soluatsinh+1; } else flag=1; } if((flag==1) || (soluatsinh==0)) flag= 1;else flag= 0; if (flag !=0) { DVT.Add(TempT[n]); DVP.Add(TempP[n]); } }//end khoi } //end for (n... TempT.RemoveAll(); TempP.RemoveAll(); }//end for i soluatkdv=KhongDonViTrai.GetSize(); for(i=0;i<soluatkdv;i++) { VeTraiDonVi.Add(KhongDonViTrai[i]); VePhaiDonVi.Add(KhongDonViPhai[i]); } int soluatDVT; soluatDVT=DVT.GetSize(); for(i=0;i<soluatDVT;i++) { for(j=0;j<soluatkdv;j++) { if(DVP[i].Compare(KhongDonViTrai[j])==0) { { CString string1; CString string2; int c;//Bien dung de duyet qua int soluatsinh; soluatsinh=VeTraiDonVi.GetSize(); for(c=0;c<soluatsinh;c++) { string1=VeTraiDonVi[c]; string2=VePhaiDonVi[c]; if(string1.Compare(DVT[i])==0 && string2.Compare(KhongDonViPhai[j])==0) { flag=0; c=soluatsinh+1; } else flag=1; } if((flag==1) || (soluatsinh==0)) flag=1;else flag=0; }//end khoi if (flag!=0) { VeTraiDonVi.Add(DVT[i]); VePhaiDonVi.Add(KhongDonViPhai[j]); } } } } }//end procedure loai bo don vi // Loai Bo luat sing vo dung { // TODO: Add your control notification handler code here int soluat; int i; int sokt; CString stringkt; CString string; CString strdx; CString strkt; CString strkt_dx; CString stringkkt_kt; CString B_thuoc_S; stringkt =""; stringkkt_kt="";//BienKhoiDau; B_thuoc_S=BienKhoiDau; CStringArray TempTrai; CStringArray TempPhai; CStringArray VeTraiVDLoai1; CStringArray VePhaiVDLoai1; CStringArray VeTraiVDLoai2; CStringArray VePhaiVDLoai2; TempTrai.Copy(VeTraiDonVi); TempPhai.Copy(VePhaiDonVi); VeTraiVoDung.RemoveAll(); VePhaiVoDung.RemoveAll(); sokt=ArrayKt.GetSize(); for(i=0;i<sokt;i++) stringkt=stringkt+ ArrayKt[i]; soluat=TempTrai.GetSize(); for(i=0;i<soluat;i++) { string=TempPhai[i]; if((FindStr(string,stringkt)!=0) && (FindStr(TempTrai[i],stringkkt_kt)==0)) stringkkt_kt=stringkkt_kt+TempTrai[i]; }//end for strkt=stringkkt_kt; stringkkt_kt=stringkkt_kt+stringkt; //Tim tap cac bien dan xuat ra cac ky tu ket thuc for(i=0;i<soluat;i++) { string=TempPhai[i]; if((FindStr(string,stringkkt_kt)!=0) &&(FindStr(TempTrai[i],stringkkt_kt)==0)) { strdx=strdx+TempTrai[i]; stringkkt_kt=stringkkt_kt+TempTrai[i]; i=-1; } } //het viec tim cac bien dan xuat strkt_dx=strkt+strdx; //Cho nhung luat sinh dan xuat ra rong //ma co trong chuoi dan xuat tu S for(i=0;i<soluat;i++) { string=TempPhai[i]; if((TempTrai[i]==BienKhoiDau) && (FindStr(string,stringkkt_kt)!=0)) if(FindStr(string,B_thuoc_S)==0) B_thuoc_S=B_thuoc_S+string; } for (i=0;i<soluat;i++) { string=TempPhai[i]; if((TempTrai[i]!=BienKhoiDau) && (FindStr(string,stringkkt_kt)!=0)) if((FindStr(TempTrai[i],B_thuoc_S)!=0)&&(FindStr(string,B_thuoc_S)==0)) {B_thuoc_S=B_thuoc_S+string; i=-1;} } for(i=0;i<soluat;i++) { string=TempPhai[i]; if(FindStr(string,stringkkt_kt)!=0) if(FindStr(TempTrai[i],B_thuoc_S)!=0) { VeTraiVoDung.Add(TempTrai[i]); VePhaiVoDung.Add(TempPhai[i]); } else { VeTraiVDLoai2.Add(TempTrai[i]); VePhaiVDLoai2.Add(TempPhai[i]); } else { VeTraiVDLoai1.Add(TempTrai[i]); VePhaiVDLoai1.Add(TempPhai[i]); } }//end for }//end khoi } ////////////////////////////////////////////////////////////// int gtCKY::KiemTraChuoiPhai(CString chuoivephai,CString chuoivetrai) { CString string1; CString string2; int i;//Bien dung de duyet qua int soluatsinh; int flag; soluatsinh=VePhaiRong.GetSize(); for(i=0;i<soluatsinh;i++) { string1=VePhaiRong[i]; string2=VeTraiRong[i]; if(string1.Compare(chuoivephai)==0 && string2.Compare(chuoivetrai)==0) { flag=0; i=soluatsinh+1; } else flag=1; } if((flag==1) || (soluatsinh==0)) return 1;else return 0; } //-------------------------------------- int gtCKY::KiemTraChuoiPhaiRong(CString chuoiphai, CString V) { int chieudaichuoi; int i; //bien duyet int flag; chieudaichuoi=chuoiphai.GetLength(); for (i=0;i<chieudaichuoi;i++) { if(V.Find(chuoiphai[i])!=-1) flag=0; else { flag=1; i=chieudaichuoi+1; } } if (flag==1) return 1; else return 0; } int gtCKY::FindStr(CString string, CString V) { int chieudai; int i; int flag; chieudai=string.GetLength(); for(i=0;i<chieudai;i++) { if (V.Find(string[i])==-1) { flag=0; i=chieudai+1; } else flag=1; } if (flag==1) return 1; else return 0; } //===================================== int gtCKY::FindChar(CString string, CString V) { int chieudai; int i; int flag; chieudai=string.GetLength(); for(i=0;i<chieudai;i++) { if (V.Find(string[i])!=-1) { flag=1; i=chieudai+1; } else flag=0; } if (flag==1) return 1; else return 0; } //============================== void gtCKY::Chomsky() { // TODO: Add your control notification handler code here //Khai Bao cac bien int i,b; int soluat; int len; int j; int n; int sokytu; int haiso; int k; CStringArray VePhai; CStringArray VeTrai; CStringArray PhaiTemp; CStringArray Len2T; CStringArray Len2P; CStringArray TgianT; CStringArray TgianP; CString string; CString stringphai; CString stringT; CString Strp,St,Stp,Str1; char Str[20]; CString T;//Tap Cac ky hieu ket thuc CString V;//Tap cac ky hieu khonng ket thuc //Loai bo tat cac cac luat sinh rong, don vi, vo dung ChomskyVePhai.RemoveAll(); ChomskyVeTrai.RemoveAll(); ChomskyKt.RemoveAll(); ChomskyKkt.RemoveAll(); PhaiX.RemoveAll(); TraiX.RemoveAll(); LoaiBoTatCa(); k=65; //Xay dung tap T soluat=ArrayKt.GetSize(); for(i=0;i<soluat;i++) { if(ArrayKt[i]!="#") ChomskyKt.Add(ArrayKt[i]); T=T+ArrayKt[i]; } //Xay dung tap V soluat=ArrayKkt.GetSize(); for(i=0;i<soluat;i++) V=V+ArrayKkt[i]; //Copy tap luat sinh sau khi loai bo vo dung VePhai.Copy(VePhaiVoDung); VeTrai.Copy(VeTraiVoDung); //============================================ soluat=VeTrai.GetSize(); for(i=0;i<soluat;i++) { stringphai=VePhai[i]; len=stringphai.GetLength(); if(len==1) { ChomskyVeTrai.Add(VeTrai[i]); ChomskyVePhai.Add(VePhai[i]); } else if((len==2) && (FindStr(VePhai[i],V) !=0)) { //Cho vao Chomsy nhung luat sinh ve phai toan la nhung ky hieu //khong ket thuc ma co chieu dai la 2 ChomskyVeTrai.Add(VeTrai[i]); ChomskyVePhai.Add(VePhai[i]); Len2T.Add(VeTrai[i]); Len2P.Add(VePhai[i]); } else { stringT=VeTrai[i]; for(j=0;j<len;j++) { if(FindStr(stringphai[j],T)!=0) { n=KiemTraSinhKetThuc(stringphai[j]); if(n==-1) { //sprintf(Str,"(X%d)",k); sprintf(Str,"%c",k); while(FindStr(Str,V)==1) {k++;sprintf(Str,"%c",k);} { TraiX.Add(Str); Strp=stringphai[j]; PhaiX.Add(Strp); PhaiTemp.Add(Str); k++; } } else {CString st; st=TraiX[n];PhaiTemp.Add(st);} } else {Strp=stringphai[j];PhaiTemp.Add(Strp);} }//end for j sokytu=PhaiTemp.GetSize(); //Ghi nhan lÁi viec thay the cac ki tu ket thuc bang cac bien dai dien TgianT.Add(stringT); { int u; CString s; for(u=0;u<sokytu;u++) s=s+PhaiTemp[u]; TgianP.Add(s); } haiso=sokytu; b=0; while(sokytu >=2) {//begin while if(sokytu==2) { Str1=PhaiTemp[haiso-2]+PhaiTemp[haiso-1]; ChomskyVeTrai.Add(stringT); ChomskyVePhai.Add(Str1); } else { St=PhaiTemp[b]; //sprintf(Str,"(X%d)",k); sprintf(Str,"%c",k); while(FindStr(Str,V)==1) {k++;sprintf(Str,"%c",k);} Stp=St+Str; ChomskyVeTrai.Add(stringT); ChomskyVePhai.Add(Stp); stringT=Str; k++; } sokytu=sokytu-1; b=b+1; }//end while PhaiTemp.RemoveAll(); }//end else }//end for ChomskyVeTrai.Append(TraiX); ChomskyVePhai.Append(PhaiX); //Copy Cac bien cho van pham Dialog Chdlog; {//bat dau CStringArray Temp; CString Vv; soluat=ChomskyVeTrai.GetSize(); for (i=0;i<soluat;i++) { if(Vv.Find(ChomskyVeTrai[i]) ==-1) { Temp.Add(ChomskyVeTrai[i]); Vv=Vv+ChomskyVeTrai[i]; } } ChomskyKkt.Copy(Temp); ChomskyBanDau=BienKhoiDau; }//ket thuc viec copy }//Ket thuc ham ///////////////////////////////////////////// //tra ve 0 neu khong co, tra ve vi tri neu co int gtCKY::KiemTraSinhKetThuc(CString luatsinh) { CString string; int i;//Bien dung de duyet qua int j; int soluatsinh; int flag; soluatsinh=PhaiX.GetSize(); for(i=0;i<soluatsinh;i++) { string=PhaiX[i]; if(string.Compare(luatsinh)==0) { j=i; flag=0; i=soluatsinh+1; } else flag=1; } if((flag==1) || (soluatsinh==0)) return -1;else return j; } //============================================== void gtCKY::OnChangeChuoiNhap() { // TODO: If this is a RICHEDIT control, the control will not // send this notification unless you override the CDialog::OnInitDialog() // function to send the EM_SETEVENTMASK message to the control // with the ENM_CHANGE flag ORed into the lParam mask. // TODO: Add your control notification handler code here m_list_dan_xuat.ResetContent(); m_list_t.ResetContent(); } NHAÄN DAÏNG NGOÂN NGÖÕ TÖÏ NHIEÂN // ndnntn.cpp : implementation file #include "stdafx.h" #include "Automat.h" #include "ndnntn.h" #include "fstream.h" #ifdef _DEBUG #define new DEBUG_NEW #undef THIS_FILE static char THIS_FILE[] = __FILE__; #endif ///////////////////////////////////////////////////////////////////////////// // ndnntn dialog ndnntn::ndnntn(CWnd* pParent /*=NULL*/) : CDialog(ndnntn::IDD, pParent) { //{{AFX_DATA_INIT(ndnntn) // NOTE: the ClassWizard will add member initialization here //}}AFX_DATA_INIT } void ndnntn::DoDataExchange(CDataExchange* pDX) { CDialog::DoDataExchange(pDX); //{{AFX_DATA_MAP(ndnntn) DDX_Control(pDX, IDC_EDIT_TIENG_VIET, m_nghia_viet); DDX_Control(pDX, IDC_EDIT_Cau_Nhap, m_chuoi_nhap); DDX_Control(pDX, IDC_LIST_TOKEN, m_list_token); DDX_Control(pDX, IDC_LIST_THUC_THE, m_list_thuc_the); DDX_Control(pDX, IDC_LIST_DAN_XUAT, m_list_dan_xuat); //}}AFX_DATA_MAP } BEGIN_MESSAGE_MAP(ndnntn, CDialog) //{{AFX_MSG_MAP(ndnntn) ON_BN_CLICKED(IDC_BUTTON_PT, OnButtonPhanTich) ON_BN_CLICKED(IDC_BUTTON_XEM_VP, OnButtonXemVPTN) ON_EN_CHANGE(IDC_EDIT_Cau_Nhap, OnChangeChuoiNhap) //}}AFX_MSG_MAP END_MESSAGE_MAP() ///////////////////////////////////////////////////////////////////////////// // ndnntn message handlers BOOL ndnntn::OnInitDialog() { CString st; CDialog::OnInitDialog(); VP_TN.ArrayKkt2.Copy(ArrayKkt2); VP_TN.ArrayKt1.Copy(ArrayKt1); VP_TN.ArrayKt2.Copy(ArrayKt2); VP_TN.ArrayVePhai2.Copy(ArrayVePhai2); VP_TN.ArrayVeTrai2.Copy(ArrayVeTrai2); VP_TN.BienKhoiDau2=BienKhoiDau2; st="Token\tLexme\tLoÁi Tô"; m_list_token.AddString(st); return TRUE; } ///////////////////////////////////////////////// //Khoi dong mot con tro its *ndnntn::Init(its *f) { f=NULL; return f; } //==================================== //Khoi dong tap thuc the void ndnntn::Init_thucthe() { int i; for (i=0;i<MAX; i++) tapthucthe[i]=Init(tapthucthe[i]); } //Dua du lieu vao tap thuc the //====================================== its *ndnntn::Insert_data(its *pt, int k,int j ,int f) { its *p,*q,*before; p=new its; (p->p)=k; (p->i)=j; (p->f)=f; q=pt; while(q!=NULL) { before=q; q=q->link; } if(q==pt) pt=p; else before->link=p; p->link=q; return (pt); } //============================================== //Hien thi cac trang thai trong tap thuc the void ndnntn::Display_its(its *f, int th) { its *q; char st[20]; char ft[10]; CString trangthai; CString str_t,str_s; int ls,ch,s;//luat sinh, dau cham , trang thai q=f; sprintf(st,"TrÁng ThÀi : S[%d]",th); m_list_thuc_the.AddString(st); while(q!=NULL) { ls=q->p;//lay so thu tu luat sinh ch=q->i;//Lay vi tri dau cham s=q->f;//lay vi tri con tro str_t=StrBeforeDot(ls,ch); str_s=StrAfterDot(ls,ch); str_t=DoiToSt2(str_t); str_s=DoiToSt2(str_s); sprintf(ft,"%d ]",s); //trangthai="[ " + ArrayVeTrai1[ls]+"---->"+str_t+ " . "+str_s+" , "+ft; trangthai="[ " + ArrayVeTrai2[ls]+"---->"+str_t+ " . "+str_s+" , "+ft; m_list_thuc_the.AddString(trangthai); q=q->link; } m_list_thuc_the.AddString(" "); } //============================================== //TÛnh tËp trÁng thÀi S0 void ndnntn::luat123() { int i; int kq23; int soluatsinh; soluatsinh=ArrayVeTrai1.GetSize(); //luat 1 for(i=0;i<soluatsinh;i++) { if (ArrayVeTrai1[i]==BienKhoiDau1) if (ArrayVePhai1[i]=="#") tapthucthe[0]=Insert_data(tapthucthe[0],i,1,0); else tapthucthe[0]=Insert_data(tapthucthe[0],i,0,0); }//het luat 1 do { kq23=luat23(); } while (kq23==1); } //Thuc hien luat thu 3 int ndnntn::luat23() { its *q; its *pt; int soluat; int i,flay; q=tapthucthe[0]; flay=0; soluat=ArrayVeTrai1.GetSize(); while(q!=NULL) { if (ChrAfterDot(q)=="")//neu dau cham o sau cung {//luat 2 pt=tapthucthe[0];//quay lai tap thuc the i=q->f while(pt!=NULL) { if(ChrAfterDot(pt)==ArrayVeTrai1[q->p]) if(KiemTraTrangThai(0,pt->p,(pt->i)+1,0)==0) {tapthucthe[0]=Insert_data(tapthucthe[0],pt->p,(pt->i)+1,0); flay=1;} pt=pt->link; } } else //luat 3 { for (i=0;i<soluat;i++) if (ArrayVeTrai1[i]==ChrAfterDot(q)) { if (ArrayVePhai1[i]=="#") { if(KiemTraTrangThai(0,i,1,0)==0) tapthucthe[0]=Insert_data(tapthucthe[0],i,1,0); } else if(KiemTraTrangThai(0,i,0,0)==0) tapthucthe[0]=Insert_data(tapthucthe[0],i,0,0); } } q=q->link; } if (flay==1) return 1; else return 0; } //Thuc hien luat so 4 void ndnntn::luat456() { CString str; int j,chieudaichuoi; its *q; CString a; str=token; //m_chuoi_nhap.GetWindowText(str); chieudaichuoi=str.GetLength(); for (j=0;j<chieudaichuoi;j++) { //luat 4 q=tapthucthe[j]; a=str[j]; while(q!=NULL) { if (ChrAfterDot(q)==a) if(KiemTraTrangThai(j+1,(q->p),(q->i)+1,(q->f))==0) tapthucthe[j+1]=Insert_data(tapthucthe[j+1],(q->p),(q->i)+1,(q->f)); q=q->link; } //het luat 4 luat56(j+1);//ap dung lien tiep luat 5 va 6 cho den khi khong them va duoc nua } } //========================================== //Thuc hien luat so 5 va so 6 void ndnntn::luat56(int th) { its *q;// con tro cua tap j=th its *pt;//con tro cua tap i int i; int soluat; q=tapthucthe[th]; soluat=ArrayVeTrai1.GetSize(); while(q!=NULL) { if (ChrAfterDot(q)=="")//neu dau cham o sau cung {//luat 5 pt=tapthucthe[q->f];//quay lai tap thuc the i=q->f while(pt!=NULL) { if(ChrAfterDot(pt)==ArrayVeTrai1[q->p]) if(KiemTraTrangThai(th,pt->p,(pt->i)+1,pt->f)==0) tapthucthe[th]=Insert_data(tapthucthe[th],pt->p,(pt->i)+1,pt->f); pt=pt->link; } } else {//luat 6 for (i=0;i<soluat;i++) if (ArrayVeTrai1[i]==ChrAfterDot(q)) { if (ArrayVePhai1[i]=="#") { if(KiemTraTrangThai(th,i,1,th)==0) tapthucthe[th]=Insert_data(tapthucthe[th],i,1,th); } else if(KiemTraTrangThai(th,i,0,th)==0) tapthucthe[th]=Insert_data(tapthucthe[th],i,0,th); } } q=q->link; } }//ket thuc luat56 //================================================ //Tra ve chuoi ky tu truoc dau cham CString ndnntn::StrBeforeDot(int ls, int ch) { int i; CString Temp,Vp; Vp=ArrayVePhai1[ls]; Temp=""; for(i=0; i<ch;i++) Temp=Temp+Vp[i]; return Temp; } //================================================ //Tra ve chuoi ky tu sau dau cham CString ndnntn::StrAfterDot(int ls, int ch) { int lenvephai; int i; CString Temp,Vp; Vp=ArrayVePhai1[ls]; lenvephai=Vp.GetLength(); Temp=""; for (i=ch; i<lenvephai;i++) Temp=Temp+Vp[i]; return Temp; } //================================================ //Tra ve ky ttu sau dau cham CString ndnntn::ChrAfterDot(its *pt) { int sl,ch; CString Vp; sl=(pt->p); ch=(pt->i); Vp=ArrayVePhai1[sl]; if (ch<Vp.GetLength()) return (Vp[ch]); else return ""; } //Kiem tra xem trong trang thai thu pt co tap trang thai (p,i,ft) chua int ndnntn::KiemTraTrangThai(int pt, int p, int i,int ft) { its *q; q=tapthucthe[pt]; while (q!=NULL) { if ((q->p==p) && (q->i==i) && (q->f==ft)) return 1; else q=q->link; } return 0; } /////////////////////////////////////////////////// int ndnntn::KiemTraThuocLG(int th) { int i,len; int soluat; if (tapthucthe[th]==NULL) return -1;//chuoi khong thuoc van pham else { soluat=ArrayVeTrai1.GetSize(); for (i=0; i<soluat;i++) { len=ArrayVePhai1[i].GetLength(); if (ArrayVeTrai1[i]==BienKhoiDau1) if(KiemTraTrangThai(th,i,len,0)==1) return i; } } return -1; } //=================================================== void ndnntn::ChuoiDanXuat(int ls,int ch, int i, int j) { char stt[10]; int k,l,m,r; its *q; its *pt; CString Vp; sprintf(stt,"%d",ls); DanXuat_So.Add(stt); Vp=ArrayVePhai1[ls]; m=Vp.GetLength(); k=m-1; l=j; while(k!=-1) { if (FindChar(Vp[k],TapT)==1) { k=k-1; l=l-1; } else { q=tapthucthe[l]; while(q!=NULL) { if(ArrayVeTrai1[q->p]==Vp[k] && ChrAfterDot(q)=="") { r=q->f; pt=tapthucthe[r];//tim trong tap thuc the r=q->j; while(pt!=NULL) { if((ChrAfterDot(pt)==Vp[k])&&(k==pt->i) && ((pt->f)==i) && (ArrayVePhai1[pt->p]==ArrayVePhai1[ls])&&//(ArrayVePhai1[pt->p].GetLength()==m) && (ArrayVeTrai1[pt->p]==ArrayVeTrai1[ls])) { ChuoiDanXuat(q->p,q->i,r,l);//ArrayVePhai1[q->p].GetLength(),r,l); k=k-1; l=r; pt=NULL; q=NULL; } else { pt=pt->link; if (pt==NULL) q=q->link; } }//end while pt }//end if else q=q->link; }//end while q }//end else }//end while k }//end function //============================================== //tra ve 1 neu co tra ve 0 neu khong co int ndnntn::FindChar(CString string, CString V) { if (V.Find(string)!=-1) return 1; else return 0; } //============================================= void ndnntn::XayDungTapT_N() { int sokytu; int i; //Xay dung tap T sokytu=ArrayKt1.GetSize(); for(i=0;i<sokytu;i++) TapT=TapT+ArrayKt1[i]; //Xay dung tap N sokytu=ArrayKkt1.GetSize(); for(i=0;i<sokytu;i++) TapN=TapN+ArrayKkt1[i]; } //=============================================== void ndnntn::InDanXuat(CString stdx,int so) { CString s1; CString s2; while (stdx.GetLength()>so) { s1=stdx.Left(so); m_list_dan_xuat.AddString(s1); s2=stdx.Mid(so,stdx.GetLength()); stdx=s2; } m_list_dan_xuat.AddString(stdx); } //======================================= void ndnntn::DanXuatRaChuoiNhap() { int i,n,l,k,j; int len_so,len_chuoi; CString st,str,str1; len_so=DanXuat_So.GetSize(); i=atoi(DanXuat_So[0]); DanXuat_Chuoi.Add(ArrayVeTrai1[i]); DanXuat_Chuoi.Add("=>"); DanXuat_Chuoi.Add(ArrayVePhai1[i]); DanXuat_Chuoi.Add("=>"); len_chuoi=DanXuat_Chuoi.GetSize(); n=len_chuoi-2; for(j=1;j<len_so;j++) { st=DanXuat_Chuoi[n]; l=st.GetLength(); k=l-1; i=atoi(DanXuat_So[j]); while(k>=0) { if (st[k]==ArrayVeTrai1[i]) { str=st.Left(k); str=str+ArrayVePhai1[i]; str1=st.Mid(k+1,st.GetLength()); str=str+str1; DanXuat_Chuoi.Add(str); DanXuat_Chuoi.Add("=>"); len_chuoi=DanXuat_Chuoi.GetSize(); n=len_chuoi-2; k=-1; } else k=k-1; }//while }//for } void ndnntn::OnButtonPhanTich() { // TODO: Add your control notification handler code here CString str; CString stdx,temp; int chieudaichuoi; int i,ls,soluatdanxuat; char st[50]; m_list_thuc_the.ResetContent(); m_list_dan_xuat.ResetContent(); m_list_token.ResetContent(); m_list_token.AddString("Token\tLexme\tLoÁi Tô"); DanXuat_So.RemoveAll(); DanXuat_Chuoi.RemoveAll(); token=nexttoken(); str=token; //m_chuoi_nhap.GetWindowText(str); chieudaichuoi=str.GetLength(); Init_thucthe(); luat123(); luat456(); if (chieudaichuoi==0) Display_its(tapthucthe[0],0); else { for (i=0;i<=chieudaichuoi; i++) if(tapthucthe[i]!=NULL) Display_its(tapthucthe[i],i); else { sprintf(st,"Læi TÁi Tô NhËp Th÷ %d",i); m_list_thuc_the.AddString(st); m_list_thuc_the.AddString("CÀc TËp TrÁng ThÀi Trê VÒ Sau Lª Ræng"); i=chieudaichuoi+1; } } ls=KiemTraThuocLG(chieudaichuoi); if(ls==-1) m_list_dan_xuat.AddString("Chuæi NhËp Kh¤ng Thuèc Ng¤n Ngö L(G) !"); else {//In ra ccay dan xuat m_list_dan_xuat.AddString("+ Chuæi NhËp Thuèc Ng¤n Ngö L(G) !"); XayDungTapT_N(); ChuoiDanXuat(ls,ArrayVePhai1[ls].GetLength(),0,chieudaichuoi); soluatdanxuat=DanXuat_So.GetSize(); for(i=0;i<soluatdanxuat;i++) stdx=stdx+DanXuat_So[i]+" "; m_list_dan_xuat.AddString("+ Th÷ Tø CÀc LuËt Sinh Tham Gia Vªo QuÀ TrØnh DÉn XuÊt :"); InDanXuat(stdx,114); m_list_dan_xuat.AddString("+ Chuæi DÉn XuÊt Ra Chuæi NhËp :"); DanXuatRaChuoiNhap(); stdx=""; soluatdanxuat=DanXuat_Chuoi.GetSize(); for(i=0;i<soluatdanxuat;i++) stdx=stdx+DanXuat_Chuoi[i]; stdx=stdx.Left(stdx.GetLength()-2); stdx=DoiToSt2(stdx); m_chuoi_nhap.GetWindowText(temp); stdx=stdx+"=>"+temp; stdx=stdx.Left(stdx.GetLength()-1); InDanXuat(stdx,85); m_nghia_viet.SetWindowText(nghia_viet); } } /////////////////////////////////////////////////////////// void ndnntn::OnButtonXemVPTN() { // TODO: Add your control notification handler code here VP_TN.DoModal(); } /////////////////////////////////////////////////// //Tra ve so thu tu cua ky hieu khong ket thuc int ndnntn::SoThuTu(CString st) { int i,stt; stt=ArrayKkt1.GetSize(); for(i=0;i<stt;i++) if (ArrayKkt1[i]==st) return i; return -1; } ///////////////////////////////////////// //Doi mot chuoi tu st1 sang st2 CString ndnntn::DoiToSt2(CString st) { int i,len,stt; CString st_temp; len=st.GetLength(); for (i=0;i<len;i++) { stt=SoThuTu(st[i]); if(stt!=-1) st_temp=st_temp+ArrayKkt2[stt]; else st_temp=st_temp+st[i]; } return st_temp; } //Tra ve mot token khi doc het mot chu CString ndnntn::nexttoken() { int i,len,stt; int beginning,forward; CString str,token,c,st; m_chuoi_nhap.GetWindowText(str); len=str.GetLength(); beginning=0; forward=0; if (len==0) MessageBox("BÁn Ch§a NhËp Vªo C¡u CÇn Ph¡n TÛch","Th¤ng BÀo"); else if (str[len-1]!='.') MessageBox("Læi NhËp C¡u, Cuçi C¡u Ph¶i Câ DÊu ChÊm (.)","Th¤ng BÀo"); else { while(forward<len) { if(str[forward]==' ') {forward++;beginning++;} else if ((isalpha(str[forward])&& (str[forward+1]==' ')) ||(isalpha(str[forward])&& (str[forward+1]=='.'))) { for(i=beginning;i<=forward;i++) c=c+str[i]; forward++; beginning=forward; stt=Find_TD(c); if(stt==-1) { token=token+"$"; st="$\t"+c+"\tLæi Ch§a CËp NhËt Vªo Tô ˜iÓn"; m_list_token.AddString(st); } else { token=token+token_td[stt]; st=token_td[stt]+"\t"+lexme_td[stt]+"\t"+loaitu_td[stt]+"\t"+tiengviet_td[stt]; if (nghia_viet.GetLength()==0)nghia_viet=nghia_viet+tiengviet_td[stt]; else nghia_viet=nghia_viet+" "+tiengviet_td[stt]; m_list_token.AddString(st); } c=""; } else forward++; } } return token; } //////////////////////////////////////////////// int ndnntn::Find_TD(CString st) { int i,stt; stt=lexme_td.GetSize(); for(i=0;i<stt;i++) if (lexme_td[i]==st) return i; return -1; } void ndnntn::OnChangeChuoiNhap() { // TODO: If this is a RICHEDIT control, the control will not // send this notification unless you override the CDialog::OnInitDialog() // function to send the EM_SETEVENTMASK message to the control // with the ENM_CHANGE flag ORed into the lParam mask. // TODO: Add your control notification handler code here m_list_thuc_the.ResetContent(); m_list_dan_xuat.ResetContent(); m_list_token.ResetContent(); nghia_viet=""; } PHAÀN 10 TAØI LIEÄU THAM KHAÛO A Introduction To Formal Languages And Automata Peter Linz University of California at Davis 372 Trang Compilers - Principle, Techniques, and Tool Alfred V. Aho Ravi Sethi Jeffrey D. Ulman 796 Trang The Theory Of Parsing, Translation, and Compiling - Volume 1 : Parsing Alfred V. Aho Feffrey D. Ullman 541 Trang Trình Bieân Dòch Phan Thò Töôi 458 Trang - Nhaø xuaát baûn giaùo duïc An Efficient Context-Free Parsing Algorithm - Jay Earley University of California Natural Language Processing In LISP Gazdar Gerald Chris Mellish 524 Trang 7- Website :