LR语法分析器 北邮 编译原理 实验.doc

/*Title(c+): LR语法分析器.cpp Author: volantfish num:10211xxx Class:2010211309 Date: 2012.11 (volantfish)Introduction: Version: */#include #include #include #include #include #include #include #include using namespace std;/#define DEBUG_/枚举常量：用来表示LR分析表中表项的状态 enum formStyleSHIFT, REDUCE, ACCEPT, GOTO, ERROR;/the element of result of lexical analysisclass WordElepublic:WordEle():style(-1), real(init)WordEle(int st, string re):style(st), real(re)int style;/the string real;/;/the element of the formclass formElepublic:formStyle style;/enumint num;/the number of production.;/the element of stackclass stackElepublic:stackEle():state(-1), ch(-1)stackEle(int st, int c):state(st), ch(c)int state;/the number of ch;/the number of character.;/*Global variable*/map charNum;/char-numbervector numChar;/number-charvector proListL;/the left side of productionsvectorvector proListR;/the right side of productionsvector wordList;/the list of result of lexical analysismappair, formEle form;/the action and goto form/*Description: 打印此刻的分析动作 *Arguments: 输入此刻分析表的一个元素 *Returns: 用string表示的分析动作 */string PrintOption(const formEle &formTemp)string output;char charTemp100;/装门用于atoi()函数的参数，没有其他作用 if(formTemp.style = SHIFT)output += Shift ;output += itoa(formTemp.num, charTemp, 10);elseif(formTemp.style = REDUCE)output += Reduced by ;output += numChar.at(proListL.at(formTemp.num);output += -;vector vecTemp = proListR.at(formTemp.num);for(vector:iterator i = vecTemp.begin(); i != vecTemp.end(); +i)output += numChar.at(*i);elseif(formTemp.style = ACCEPT)output = acc;return output;/*Description: 打印未处理的输入串 *Arguments: 输入字符串的迭代器，指向正在处理的字符 *Returns: 未处理的输入串 */string PrintInput(vector:const_iterator iterWord)string output;for(; iterWord != wordList.end(); +iterWord)output += iterWord-real;return output;/*Description: 打印栈的全部元素 *Arguments: 栈 *Returns: 储存栈元素的string */string PrintStack(const list &st)char charTemp100;/装门用于atoi()函数的参数，没有其他作用 string output;/for(list:const_reverse_iterator i = st.rbegin(); i != st.rend(); +i)output += numChar.at(i-ch);output += itoa(i-state, charTemp, 10);return output;/*Description: LR语法分析主程序 *Arguments:*Returns:*/void GramAna()vector:const_iterator iterWord = wordList.begin();/指向当前正在处理的字符 list st;/stack used in the analysisst.push_front(stackEle(0, charNum$);/在栈底压入状态0 formEle formTemp;/充当中间变量的角色 printf(nn*LR语法分析过程*n);printf(n 栈 输 入 分析动作 n);/printf(%-18s%18s %-15sn, PrintStack(st).c_str(), /PrintInput(iterWord).c_str(), PrintOption(formTemp).c_str(); while(iterWord != wordList.end()formTemp = formmake_pair(st.front().state, iterWord-style);if(formTemp.style = SHIFT)/ 移进 printf(%-18s%18s %-15sn, PrintStack(st).c_str(), PrintInput(iterWord).c_str(), PrintOption(formTemp).c_str(); st.push_front(stackEle(formTemp.num, iterWord-style);+iterWord;elseif(formTemp.style = REDUCE)/ 归约 printf(%-18s%18s %-15sn, PrintStack(st).c_str(), PrintInput(iterWord).c_str(), PrintOption(formTemp).c_str(); for(vector:size_type i = 0; i (proListR.at(formTemp.num).size(); +i)st.pop_front();int iTemp = formmake_pair(st.front().state, proListL.at(formTemp.num).num;st.push_front(stackEle(iTemp, proListL.at(formTemp.num);elseif(formTemp.style = ACCEPT)/ 接受，分析成功 printf(%-18s%18s %-15sn, PrintStack(st).c_str(), PrintInput(iterWord).c_str(), PrintOption(formTemp).c_str();cout nGrammatical analysis success endl;+iterWord;else/error processing cout error: analysis endl;+iterWord;/end of while(iterWord != wordList.end()/*Description: 词法分析程序 *Arguments: 未经处理的输入符号串 *Returns:*/void LexiAna(const string inputStr)string:const_iterator iter = inputStr.begin();string token;/存储记号 int charState = 0;/表示开头字符的类别 while(iter != inputStr.end()if(isalpha(*iter) != 0)/ 字母 charState = 1;elseif(isdigit(*iter) != 0)/ 数字 charState = 2;elsestring tempIter;tempIter.push_back(*iter);/ 如果在终结符串中可以搜到 if(count(numChar.begin(), numChar.begin()+8, tempIter) != 0)charState = 3;elsecharState = 4;WordEle wTemp(-1, error);switch(charState)case 1:/标识符while(*iter = _ | isalpha(*iter) != 0 | isdigit(*iter) != 0)token.push_back(*iter);+iter;wTemp.style = charNumid;wTemp.real = token;token.clear();wordList.push_back(wTemp);break;case 2:/数字 while(isdigit(*iter) != 0)token.push_back(*iter);+iter;if(*iter = .)token.push_back(*iter);+iter;while(isdigit(*iter) != 0)token.push_back(*iter);+iter;wTemp.style = charNumnum;wTemp.real = token;token.clear();wordList.push_back(wTemp);break;case 3:/操作符 token.push_back(*iter);wTemp.style = charNumtoken;wTemp.real = token;token.clear();wordList.push_back(wTemp);+iter;break;default:/出现space 或 错误终结符 时的处理 if(isspace(*iter) = 0)/when iter belongs to space, ignore it.printf(!lexical analyse errorn);printf(!there do not exist character: %cn, *iter);+iter;break;/end of switch(charState)/end of while(iter != inputStr.end()/打印词法分析结果printf(nn*词法分析过程*n);cout The result of lexical analysis is: endl;for(vector:iterator i = wordList.begin(); i != wordList.end(); +i)cout style , real endl; /在输入字符串末尾加上符号$wordList.push_back(WordEle(charNum$, $); /*Description: 由文件input.txt读入分析程序所需的的数据 *Arguments:*Returns:*/void inputData()ifstream inFileStre(input.txt);/读入文件流 if(!inFileStre)cerr error: unable to open input.txt word)/read in terminal character.charNumword = number+;numChar.push_back(word);getline(inFileStre, line);getline(inFileStre, line);inStrStre.clear();inStrStre.str(line);/read in non-terminal character.#ifdef DEBUG_cout 11 inStrStre.str() word)#ifdef DEBUG_cout 22 word word;#ifdef DEBUG_cout 77 line word word;vector vecTemp;while(inStrStre word)vecTemp.push_back(charNumword);proListR.push_back(vecTemp);getline(inFileStre, line);getline(inFileStre, line);getline(inFileStre, line);getline(inFileStre, line);int xTemp;string yTemp;char sTemp;formEle fEleTemp;while(line != end)/read in form iteminStrStre.clear();inStrStre.str(line);inStrStre xTemp yTemp sTemp fEleTemp.num;#ifdef DEBUG_cout 55 xTemp yTemp endl;#endifswitch(sTemp)case s:fEleTemp.style = SHIFT;bre