C++求文法的first和follow集合

1. #include \ 2. #include \ 3. #include \ 4.

5. #ifdef _DEBUG 6. #undef THIS_FILE

7. static char THIS_FILE[]=__FILE__; 8. #define new DEBUG_NEW 9. #endif

10. //----调试部分使用的代码

11. CString MLR1::GetFirst(int i){

12. if(i<0||i>=GetIdentNum())return \;

13. return FirstSet5(m_first[i].Fi,m_first[i].flag&2); 14. }

15. CString MLR1::GetFollow(int i){

16. if(i<0||i>=GetIdentNum())return \;

17. return FollowSet1(m_first[i].Fo,m_first[i].flag&0x08); 18. }

19. //----构造部分 20. MLR1::MLR1(){ 21. }

22. MLR1::~MLR1(){ 23. }

24. void MLR1::ReSet(FILE* pf){ 25. //使用文件指针pf来重新驱动程序 26. int i; 27. p_file=pf;

28. list_Express.RemoveAll(); 29. list_Ident.RemoveAll();

30. for(i=0;i

T-1;\ for(char* bit_map[i]=\>=(char*)m_first;p--) 31. *p=0; 32. Lex3(); 33. FirstSet6(); 34. // FollowSet3(); 35. }

36. //----输入分析部分 37. bool MLR1::Lex1(){

38. //截取一个分号段到tocken中 39. //功能字符取其负数 40. char ch=0; 41. bool end=false; 42. token_len=0;

43. if(feof(p_file))return false;

44. while(!end&&!feof(p_file)){

45. if(token_len>=LINE_LENGTH)break; 46. if(fread(&ch,1,1,p_file)<=0)break; 47. if(ch<=0)goto error; 48. switch(ch){ 49. case ';': 50. end=true; 51. case '<': 52. case '>': 53. case '=': 54. ch=-ch; 55. break; 56. case '\\\\':

57. fread(&ch,1,1,p_file); 58. if(ch<=0)goto error; 59. break; 60. }

61. token[token_len++]=ch; 62. }

63. token[token_len]=0; 64. return true; 65. error:

66. fprintf(stderr,\); 67. return false; 68. }

69. int MLR1::Lex2_1(char*&s,bool isUse){ 70. //识别非终结符并加入list_Ident 71. char ident[ID_LENGTH+1]; 72. int t=0;

73. if((int)*s++!=-'<')return 0; 74. if(isalpha(*s))ident[t++]=*s++; 75. else return 0;

76. while(isalpha(*s)||isdigit(*s))ident[t++]=*s++; 77. while(*s=='\\'')ident[t++]=*s++; 78. if((int)*s++!=-'>')return 0; 79. if(t==0)return 0; 80. ident[t]=0;

81. for(t=list_Ident.GetSize()-1;t>=0;t--) 82. if(list_Ident[t]==(CString)ident)break; 83. if(t<0){

84. if(list_Ident.GetSize()>=MAX_IDENT)return false; 85. list_Ident.Add((CString)ident); 86. t=list_Ident.GetSize()-1;

87. if(isUse)bit_map[t/8]|=1<<(t%8);

88. }

89. if(!isUse)bit_map[t/8]&=~(1<<(t%8)); 90. return t+1; 91. }

92. bool MLR1::Lex2(){

93. //将token中的非终结符用(-1) -- (-127)表示 94. //进行语法判断<终结符>=符号表; 95. register char *s,*d; 96. char * end; 97. int i; 98. s=d=token;

99. end=&token[token_len]; 100. if(i=Lex2_1(s))*d++=-i; 101. else return false;

102. if(*s++!=-'=')return false;

103. while(s

式X能否推出LR_NULL *X){ MLR1::FirstSet1(const bool * 首先判断某非终结符能否推出LR_NULL ----First

集 } true; return false; if(bit_map[i]!=\ i=\)\ for(int else list_Express.Add((CString)token); if(Lex2()) if(token_len=\ while(Lex1()){ 判断bit_map是否为全零，如果不是则表示有未定义的非终结符 循环调用Lex1读入一句，调用Lex2进行语法分

析 MLR1::Lex3(){ s=1){ 104. return false; 105. }else{

106. if(*p==*X)return false; 107. if(!FirstSet2(*p)) 108. return false; 109. } 110. p++; 111. }

112. return true; 113. }

114. bool MLR1::FirstSet2(const char X){ 115. //判断非终结符X能否推出LR_NULL 116. CString temp;

117. if(m_first[-X-1].flag&0x40)return false; 118. if(m_first[-X-1].flag&1)

119. return (m_first[-X-1].flag&2)!=0; 120. m_first[-X-1].flag|=0x40;

121. for(int i=list_Express.GetSize();i>0;i--){ 122. temp=list_Express.GetAt(i-1); 123. if(temp[0]==X){

124. if(FirstSet1((LPCSTR)temp)){ 125. m_first[-X-1].flag|=3; 126. return true; 127. } 128. } 129. }

130. m_first[-X-1].flag|=1; 131. m_first[-X-1].flag^=0x40; 132. return false; 133. }

134. bool MLR1::FirstSet3(const char *X,char*Fi){

135. //求产生式X的First集放在F中,如果LR_NULL在First集中则返回true 136. //如果要求符号串的First集,就将X[0]设为0 137. //假设X中不出现LR_NULL,LR_EOF和LR_EOS 138. //假设F的长度为MAP_SIZE,有128b 139. const char *p=X; 140. X++;

141. while(*X!=0){ 142. if(*X>=1){

143. Fi[(*X)/8]|=1<<(*X)%8; 144. return false; 145. }else{

146. if(*X==*p){

147. if(!FirstSet2(*X)) 148. return false;

149. }else if(!FirstSet4(*X,Fi)){ 150. return false; 151. } 152. } 153. X++; 154. }

155. return true; 156. }

157. bool MLR1::FirstSet4(char const X,char*Fi){ 158. //求非终结符X的First集放在F中 159. //如果LR_NULL在其中则返回true 160. CString temp;

161. …… 此处隐藏：3128字，全部文档内容请下载后查看。喜欢就下载吧 ……