?? parsing.cpp
字號:
// Parsing.cpp: implementation of the CParsing class.
//
//////////////////////////////////////////////////////////////////////
#include "stdafx.h"
#include "scanner.h"
#include "Parsing.h"
#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
//初始化文法產生式
/************************************************************
* E -> E + T
* E -> E - T
* E -> T
* T -> T * F
* T -> T / F
* T -> F
* F -> i
* F -> ( E )
************************************************************/
const GProduction CParsing::m_production[PRODUCTIONSIZE][PRODUCTIONLEN+1]={
{{Nonterminal,'E'},{Nonterminal,'E'},{Terminal,'+'},{Nonterminal,'T'},{Other,' '}},
{{Nonterminal,'E'},{Nonterminal,'E'},{Terminal,'-'},{Nonterminal,'T'},{Other,' '}},
{{Nonterminal,'E'},{Nonterminal,'T'},{Other,' '}},
{{Nonterminal,'T'},{Nonterminal,'T'},{Terminal,'*'},{Nonterminal,'F'},{Other,' '}},
{{Nonterminal,'T'},{Nonterminal,'T'},{Terminal,'/'},{Nonterminal,'F'},{Other,' '}},
{{Nonterminal,'T'},{Nonterminal,'F'},{Other,' '}},
{{Nonterminal,'F'},{Terminal,'i'},{Other,' '}},
{{Nonterminal,'F'},{Terminal,'('},{Nonterminal,'E'},{Terminal,')'},{Other,' '}}
};
/**優先矩陣符號標示順序
*************************************************************
* + - * / ( ) i #
************************************************************/
const char CParsing::m_operTableIndex[OPERTABLESIZE]={
'+','-','*','/','(',')','i','#'
};
/**優先矩陣
/*************************************************************
* + - * / ( ) i #
*
* + > > < < < > < >
* - > > < < < > < >
* * > > > > < > < >
* / > > > > < > < >
* ( < < < < < = < >
* ) > > > > > >
* i > > > > > >
* # < < < < < < <
************************************************************/
const OperCompare CParsing::m_operTable[OPERTABLESIZE][OPERTABLESIZE]={
{More, More, Less, Less, Less, More, Less, More},
{More, More, Less, Less, Less, More, Less, More},
{More, More, More, More, Less, More, Less, More},
{More, More, More, More, Less, More, Less, More},
{Less, Less, Less, Less, Less, Equal, Less, More},
{More, More, More, More, Unknown,More, Unknown,More},
{More, More, More, More, Unknown,More, Unknown,More},
{Less, Less, Less, Less, Less, Less, Less, Unknown}
};
/**
* 語法分析構造函數
*
* @param pWordCode 字符表數組
* @param pTokenFile token串頭指針
* @param pSymbolTable 符號表頭指針
* @param pErrorCollection 錯誤信息頭指針
*
*/
CParsing::CParsing(const char *pWordCode[],
PTokenNode pTokenFile,
PSTable pSymbolTable,
PErrorNode pErrorCollection)
{
//初始化分析棧和當前識別的最左素短語
this->m_stckTerTop.next=NULL;
this->m_stckTop.next=NULL;
InitStck();
this->m_llp.next=NULL;
this->m_pMorpheme=new CMorpheme(pWordCode,pTokenFile,pSymbolTable,pErrorCollection);
this->m_pSymbolTable=pSymbolTable;
for (int i=0;i<KEYWORDCOUNT+1;i++)
{
this->m_pWordCode[i]=pWordCode[i];
}
}
/**
* 語法分析構造函數
*
* @param pWordCode 字符表數組
* @param pTokenFile token串頭指針
* @param pSymbolTable 符號表頭指針
* @param pErrorCollection 錯誤信息頭指針
* @param strSourceFile 源文件路徑
*
*/
CParsing::CParsing(const char *pWordCode[],
PTokenNode pTokenFile,
PSTable pSymbolTable,
PErrorNode pErrorCollection,
CString strSourceFile)
{
//初始化分析棧和當前識別的最左素短語
this->m_stckTerTop.next=NULL;
this->m_stckTop.next=NULL;
InitStck();
this->m_llp.next=NULL;
this->m_pMorpheme=new CMorpheme(pWordCode,pTokenFile,pSymbolTable,pErrorCollection,strSourceFile);
this->m_pSymbolTable=pSymbolTable;
for (int i=0;i<KEYWORDCOUNT+1;i++)
{
this->m_pWordCode[i]=pWordCode[i];
}
}
CParsing::~CParsing()
{
//釋放分析棧
DisposeStck();
//釋放最左素短語
PGSymbol gs;
while (this->m_llp.next!=NULL)
{
gs=this->m_llp.next;
this->m_llp.next=gs->next;
delete gs;
}
}
//函數功能：進行語法分析 return CString 語法分析結果
CString CParsing::Parsing(CString strSourceFile/*=""*/)
{
PTokenNode pToken=NULL;
char word='0';
bool morSucc=false;
bool returnValue=true;
//表達式結果為整型還是浮點型：false為整型
bool resultType=false;
//將#壓入分析棧
this->GSPut('#',pToken);
//分析源程序
morSucc=this->m_pMorpheme->StepMorpheme(pToken,strSourceFile);
while (morSucc)
{
word='0';
if (this->m_pWordCode[pToken->keycode]=="constfloat" ||
this->m_pWordCode[pToken->keycode]=="constint")
{
word='i';
//表達式結果為整型還是浮點型：false為整型
if (this->m_pWordCode[pToken->keycode]=="constfloat") resultType=true;
}
else if (this->m_pWordCode[pToken->keycode]=="+" ||
this->m_pWordCode[pToken->keycode]=="-" ||
this->m_pWordCode[pToken->keycode]=="*" ||
this->m_pWordCode[pToken->keycode]=="/" ||
this->m_pWordCode[pToken->keycode]=="(" ||
this->m_pWordCode[pToken->keycode]==")" )
{
word=this->m_pWordCode[pToken->keycode][0];
}
else
{
this->m_pMorpheme->AddError("表達式非法!",this->m_pMorpheme->GetCurRow(),this->m_pMorpheme->GetCurCol());
}
//識別并歸約
if (this->CompOperator(this->GetNextTerSymbol()->word,word)==More)
{
returnValue=this->RecogLLP();
if (returnValue)
{
returnValue=this->MatchProduction();
}
if (!returnValue)
{
this->m_pMorpheme->CloseSource();
break;
}
}
else
{
this->GSPut(word,pToken);
morSucc=this->m_pMorpheme->StepMorpheme(pToken,strSourceFile);
}
}
//源程序分析完畢，將分析棧剩余的句型規約
CString str;
if (returnValue)
{
while (this->GetGSTopSymbol()->next->word!='#' || this->GetGSTopSymbol()->sType!=Nonterminal)
{
returnValue=this->RecogLLP();
if (returnValue)
{
returnValue=this->MatchProduction();
if (!returnValue) break;
}
else break;
}
//歸約完成
if (this->GetGSTopSymbol()->next->word=='#')
{
//CString str;
if (resultType) str.Format("歸約成功！\n表達式結果為：%f",this->GetGSTopSymbol()->value.dValue);
else str.Format("歸約成功！\n表達式結果為：%d",(int)this->GetGSTopSymbol()->value.dValue);
//::AfxMessageBox(str);
//return str;
}
else
{
returnValue=false;
}
}
if (!returnValue) //::AfxMessageBox("歸約失敗，請檢查表達式是否有錯誤！");
str = "歸約失敗，請檢查表達式是否有錯誤！";
return str;
}
/**
* 進行終結符優先級比較
* @param char chOper1 比較符一
* @param char chOper2 比較符二
*
* @return OperCompare 比較結果
*
*/
OperCompare CParsing::CompOperator(char chOper1,char chOper2)
{
OperCompare returnValue=Unknown;
//匹配符號編號
int iOper1=-1,iOper2=-1;
for (int i=0;i<OPERTABLESIZE;i++)
{
if (iOper1 == -1) iOper1=(chOper1==this->m_operTableIndex[i])? i:-1;
if (iOper2 == -1) iOper2=(chOper2==this->m_operTableIndex[i])? i:-1;
}
if (iOper1 != -1 && iOper2 != -1)
{
returnValue=this->m_operTable[iOper1][iOper2];
}
return returnValue;
}
/**
* 識別素短語,先清空素短語列表
*
* @return bool 是否識別最左素短語
*
*/
bool CParsing::RecogLLP()
{
bool returnValue=false;
//釋放當前素短語
PGSymbol topGS;
while (this->m_llp.next!=NULL)
{
topGS=this->m_llp.next;
this->m_llp.next=topGS->next;
delete topGS;
}
this->m_llp.next=NULL;
//識別素短語,以Less為標志
PGSymbol oper1,oper2;//分析棧中oper1在oper2下面
oper2=this->GetNextTerSymbol();
if (oper2!=NULL)
{
oper1=this->GetNextTerSymbol(oper2);
while (oper1!=NULL)
{
if (Less==this->CompOperator(oper1->word,oper2->word))
{
//提取素短語
PGSymbol pGS=this->GetGSTopSymbol();
while (pGS!=oper1)
{
pGS=this->GSPop();
pGS->next=this->m_llp.next;
this->m_llp.next=pGS;
pGS=this->GetGSTopSymbol();
}
returnValue=true;
break;
}
oper2=oper1;
oper1=this->GetNextTerSymbol(oper2);
}
}
return returnValue;
}
/**
* 匹配當前識別的最左素短語，并進行歸約計算表達式的值
*
* @return bool 是否存在相應的產生式匹配并歸約
*
*/
bool CParsing::MatchProduction()
{
bool returnValue=false;
int iProIndex=-1;
PGSymbol pGS=NULL;
bool bMatch=false;
//匹配產生式
for (int i=0;i<PRODUCTIONSIZE;i++)
{
pGS=this->m_llp.next;
if (pGS==NULL) break;
bMatch=false;
for (int j=1;j<PRODUCTIONLEN+1;j++)
{
if (this->m_production[i][j].sType==Other && pGS==NULL)
{
iProIndex=i;
bMatch=true;
}
else
{
if (this->m_production[i][j].sType==Other) break;
if (pGS==NULL) break;
if (this->m_production[i][j].sType == pGS->sType)
{
if (pGS->sType==Terminal)
{
if (pGS->word != m_production[i][j].word) break;
}
}
else break;
pGS=pGS->next;
}
}
if (bMatch) break;
}
//進行歸約
if (bMatch)
{
returnValue=true;
PGSymbol pOper1,pOper2,pOper3;
pOper1=this->m_llp.next;
if (iProIndex!=6)
{
pOper2=pOper1->next;
pOper3=pOper2->next;
}
switch (iProIndex)
{
case 6: //F->i
this->GSPut('F',
this->m_pSymbolTable->sSubTable[pOper1->value.pToken->strId-1].val);
break;
case 0: //E->E+T
this->GSPut('E',pOper1->value.dValue + pOper3->value.dValue);
break;
case 1: //E->E-T
GSPut('E',pOper1->value.dValue - pOper3->value.dValue);
break;
case 3: //T->T*F
GSPut('T',pOper1->value.dValue * pOper3->value.dValue);
break;
case 4: //T->T/F
if (pOper3->value.dValue==0)
{
this->m_pMorpheme->AddError("除數為零！",m_pMorpheme->GetCurRow());
returnValue=false;
}
else
GSPut('T',pOper1->value.dValue / pOper3->value.dValue);
break;
case 7: //F->(E)
GSPut('F',pOper2->value.dValue);
break;
default:
//無法識別
returnValue=false;
}
}
return returnValue;
}
/**
* 歸約當前識別的素短語并將歸約結果入棧
*
* @param int 規約產生式表達式編號
*
* @return bool 歸約成功
*
*
bool CParsing::Reduce(int iProIndex)
{
bool returnValue=true;
PGSymbol pOper1,pOper2,pOper3;
pOper1=this->m_llp.next;
if (pOper1!=NULL)
{
//檢驗已經識別的素短語
if (iProIndex!=6)
{
pOper2=pOper1->next;
if (pOper2==NULL)
{
return false;
}
else
{
pOper3=pOper2->next;
if (pOper3==NULL)
{
return false;
}
}
}
switch (iProIndex)
{
case 0: //E->E+T
break;
case 1: //E->E-T
break;
case 3: //T->T*F
break;
case 4: //T->T/F
break;
case 6: //F->i
break;
case 7: //F->(E)
break;
default:
//無法識別
returnValue=false;
}
}
else
{
returnValue=false;
}
return returnValue;
}*/
/**
* 初始化分析棧
*
*/
void CParsing::InitStck()
{
DisposeStck();
this->m_stckTop.next=NULL;
this->m_stckTerTop.next=NULL;
}
/**
* 彈出所有分析棧元素
*
*/
void CParsing::DisposeStck()
{
PGSymbol gs;
while (m_stckTop.next!=NULL)
{
gs=this->m_stckTop.next;
this->m_stckTop.next=gs->next;
//釋放相應的token字
if (gs->sType==Terminal)
this->m_pMorpheme->DeleteToken(gs->value.pToken);
delete gs;
}
this->m_stckTop.next=NULL;
PTerNode tn;
while (this->m_stckTerTop.next!=NULL)
{
tn=this->m_stckTerTop.next;
this->m_stckTerTop.next=tn->next;
delete tn;
}
this->m_stckTerTop.next=NULL;
}
/**
* 彈出棧頂元素
*
* @return PGSymbol 返回棧頂元素
*
*/
PGSymbol CParsing::GSPop()
{
PGSymbol returnValue=NULL;
PTerNode pTerNode=NULL;
if (this->m_stckTop.next!=NULL)
{
returnValue=this->m_stckTop.next;
this->m_stckTop.next=returnValue->next;
//清空相應的引用
if (this->m_stckTerTop.next!=NULL && this->m_stckTerTop.next->pTerminal==returnValue)
{
pTerNode=this->m_stckTerTop.next;
this->m_stckTerTop.next=pTerNode->next;
delete pTerNode;
}
}
return returnValue;
}
/**
* 獲取棧頂元素
*
* @return PGSymbol 返回棧頂元素
*
*/
PGSymbol CParsing::GetGSTopSymbol()
{
PGSymbol returnValue=NULL;
if (this->m_stckTop.next!=NULL)
{
returnValue=this->m_stckTop.next;
}
return returnValue;
}
/**
* 根據當前終結符獲取分析棧中下一個終結符元素
*
* @param PGSymbol pGS 指定當前終結符元素
*
* @return PGSymbol 返回下一個終結符元素
*
*/
PGSymbol CParsing::GetNextTerSymbol(PGSymbol pGS/*=NULL*/)
{
PGSymbol returnValue=NULL;
PTerNode pTerNode=&this->m_stckTerTop;
if (pGS==NULL)
{
if (pTerNode->next!=NULL)
{
returnValue=pTerNode->next->pTerminal;
}
}
else
{
while (pTerNode->next!=NULL)
{
if (pTerNode->pTerminal == pGS)
{
if (pTerNode->next!=NULL)
{
returnValue=pTerNode->next->pTerminal;
}
break;
}
else
{
pTerNode=pTerNode->next;
}
}
}
return returnValue;
}
/**
* 壓棧，終結符
*
* @param PTokenNode pToken 非終結符對應的token
* @param char word 終結符在產生式中的表示
*
* @return bool 壓棧成功
*
*/
bool CParsing::GSPut(char word,PTokenNode pToken)
{
PGSymbol pGS=new GSymbol;
if (pGS==NULL) return false;
pGS->next=this->m_stckTop.next;
this->m_stckTop.next=pGS;
pGS->sType=Terminal;
pGS->value.pToken=pToken;
pGS->word=word;
//對終結符進行引用
PTerNode pTN=new TerNode;
if (pTN==NULL) return false;
pTN->next=this->m_stckTerTop.next;
this->m_stckTerTop.next=pTN;
pTN->pTerminal=pGS;
return true;
}
/**
* 壓棧，非終結符
*
* @param double dValue 終結符對應的規約值
* @param char word 終結符在產生式中的表示
*
* @return bool 壓棧成功
*
*/
bool CParsing::GSPut(char word,double dValue)
{
PGSymbol pGS=new GSymbol;
if (pGS==NULL) return false;
pGS->next=this->m_stckTop.next;
this->m_stckTop.next=pGS;
pGS->sType=Nonterminal;
pGS->value.dValue=dValue;
pGS->word=word;
return true;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -