Original: (46 messages) Design and implementation of parser
Problem Description]
Please design and implement a grammatical analysis program according to the given grammar, which can recognize various grammatical components based on the words recognized by the lexical analysis program of the previous assignment. The input and output and processing requirements are as follows:
(1) All kinds of grammatical components defined in the grammar must be analyzed by recursive subroutine method according to grammar rules;
(2) In order to facilitate automatic evaluation, the input compiled source file is uniformly named testfile.txt (be careful not to write the wrong file name); the output result file is uniformly named output.txt (be careful not to write the wrong file name); the result The file contains the following two kinds of information:
1) According to the order in which words are recognized by lexical analysis, output the information of each word by line (requires the same lexical analysis job, and cannot be output for pre-reading).
2) Before the analysis of the following highlighted grammatical components is finished, start another line to output the name of the current grammatical component, in the form of "<constant description>" (Note: grammatical components that are not required to be output still need to be analyzed)
[grammar definition]
<Addition operator> ::= +|-
<multiplication operator> ::= *|/
<relational operator> ::= <|<=|>|>=|!=|==
＜Alphabet＞ ::= ＿｜a｜． ．．|z|A|. ．．｜Z
<number> ::= 0 | <non-zero number>
<non-zero number> ::= 1|. ．．｜9
<character> ::= '<addition operator>'|'<multiplication operator>'|'<letter>'|'<number>'
<string> ::= "{ASCII characters whose decimal encoding is 32,33,35-126}"
<program> ::= [<constant description>][<variable description>]{<function definition with return value>|<function definition without return value>}<main function>
<constant specification> ::= const<constant definition>;{ const<constant definition>;}
<constant definition> ::= int <identifier>=<integer>{,<identifier>=<integer>}
char<identifier>=<character>{,<identifier>=<character>}
<unsigned integer> ::= <non-zero number>{<number>}| 0
<integer> ::= [+|-]<unsigned integer>
<identifier> ::= <letter>{<letter>｜<number>}
<declaration header> ::= int<identifier> | char<identifier>
<variable description> ::= <variable definition>;{<variable definition>;}
<variable definition> ::= <type identifier>(<identifier>|<identifier>'['<unsigned integer>']'){,(<identifier>|<identifier>'['< unsigned integer > ']' )}
//<unsigned integer> indicates the number of array elements, and its value must be greater than 0
<type identifier> ::= int | char
<function definition with return value> ::= <declaration header>'('<parameter list>')' '{'<compound statement>'}'
<function definition without return value> ::= void <identifier>'('<parameter list>')''{'<compound statement>'}'
<compound statement> ::= [<constant specification>] [<variable specification>] <statement list>
<parameter list> ::= <type identifier><identifier>{,<type identifier><identifier>}| <null>
<main function> ::= void main'('')' '{'<compound statement>'}'
<expression> ::= [+|-]<term>{<addition operator><term>} //[+|-] only works on the first <term>
<term> ::= <factor>{<multiplication operator><factor>}
<factor> ::= <identifier>｜<identifier>'['<expression>']'|'('<expression>')'｜<integer>|<character>|<function with return value call statement >
<statement> ::= <conditional statement>｜<loop statement>| '{'<statement column>'}'| <function call statement with return value>;
|<function call statement with no return value>;｜<assignment statement>;｜<read statement>;｜<write statement>;｜<null>;|<return statement>;
<assignment> ::= <identifier>=<expression>|<identifier>'['<expression>']'=<expression>
<conditional statement> ::= if '('<condition>')' <statement> [else<statement>]
<condition> ::= <expression><relational operator><expression> //Relational operations can only be performed between integer expressions
｜ ｜<expression> //The expression is an integer, its value is 0, the condition is false, and when the value is not 0, the condition is true
<loop statement> ::= while '('<condition>')'<statement>| do<statement>while '('<condition>')' |for'('<identifier>=<expression>; <condition>;<identifier>=<identifier>(+|-)<step>')'<statement>
<step>::= <unsigned integer>
<function call statement with return value> ::= <identifier>'('<value parameter list>')'
<function call statement without return value> ::= <identifier>'('<value parameter list>')'
<value parameter list> ::= <expression>{,<expression>}｜<empty>
<statement list> ::= {<statement>}
<read statement> ::= scanf '('<identifier>{,<identifier>}')'
<write statement> ::= printf '(' <string>,<expression> ')'| printf '('<string> ')'| printf '('<expression>')'
<return statement> ::= return['('<expression>')']
[Input form] The test program in testfile.txt that meets the grammar requirements.
[Output format] Output the grammatical analysis results to output.txt according to the above requirements. The encoding format of Chinese characters is required to be UTF-8.
[Special reminder] (1) This assignment only evaluates the processing of the correct program, but it is necessary to reserve an interface for possible errors in the future.
(2) The output currently required is only for the convenience of evaluation. This information does not need to appear in the completed compiler. Please design a scheme to facilitate opening/closing of these outputs.
[Sample input]
const int const1 = 1, const2 = -100;
const char const3 = '_';
int change1;
char change3;
int gets1(int var1,int var2){
change1 = var1 + var2;
return (change1);
}
void main(){
printf("Hello World");
printf(gets1(10, 20));
}
[Example output]
CONSTTK const
INTTK int
IDENFR const1
ASSIGN =
INTCON 1
<unsigned integer>
<integer>
COMMA ,
IDENFR const2
ASSIGN =
MINU -
INTCON 100
<unsigned integer>
<integer>
<constant definition>
SEMICN ;
CONSTTK const
CHARTK char
IDENFR const3
ASSIGN =
CHARCON _
<constant definition>
SEMICN ;
<Constant Description>
INTTK int
IDENFR change1
<variable definition>
SEMICN ;
CHARTK char
IDENFR change3
<variable definition>
SEMICN ;
<variable description>
INTTK int
IDENFR gets1
<declaration header>
LPARENT (
INTTK int
IDENFR var1
COMMA ,
INTTK int
IDENFR var2
<parameter table>
RPARENT )
LBRACE {
IDENFR change1
ASSIGN =
IDENFR var1
<factor>
<item>
PLUS +
IDENFR var2
<factor>
<item>
<expression>
<assignment statement>
SEMICN ;
<statement>
RETURNTK return
LPARENT (
IDENFR change1
<factor>
<item>
<expression>
RPARENT )
<return statement>
SEMICN ;
<statement>
<statement column>
<compound statement>
RBRACE }
<function definition with return value>
VOIDTK void
MAINTK main
LPARENT (
RPARENT )
LBRACE {
PRINTFTK printf
LPARENT (
STRCON Hello World
<string>
RPARENT )
<write statement>
SEMICN ;
<statement>
PRINTFTK printf
LPARENT (
IDENFR gets1
LPARENT (
INTCON 10
<unsigned integer>
<integer>
<factor>
<item>
<expression>
COMMA ,
INTCON 20
<unsigned integer>
<integer>
<factor>
<item>
<expression>
<value parameter table>
RPARENT )
<function call statement with return value>
<factor>
<item>
<expression>
RPARENT )
<write statement>
SEMICN ;
<statement>
<statement column>
<compound statement>
RBRACE }
<main function>
<program>
1 #include <iostream> 2 #include <vector> 3 #include <map> 4 #include <string> 5 #include <cstdio> 6 #include <cctype> 7 #include <regex> 8 #include <algorithm> 9 #include <fstream> 10 using namespace std; 11 //keywords 12 static vector<string> keyWordKey = {"const", "int", "char", "void", "main", "getint", "if", "else", "switch", "case", "default", "while", "for", "scanf", "printf", "return", "auto", "short", "long", "float", "double", "struct", "union", "enum", "typedef", "unsigned", "signed", "extern", "register", "static", "volatile", "do", "goto", "continue", "break", "sizeof"}; 13 14 //keyword category code 15 static vector<string> keyWordValue = {"CONSTTK", "INTTK", "CHARTK", "VOIDTK", "MAINTK", "GETINTTK", "IFTK", "ELSETK", "SWITCHTK", "CASETK", "DEFAULTTK", "WHILETK", "FORTK", "SCANFTK", "PRINTFTK", "RETURNTK", "AUTOTK", "SHORTTK", "LONGTK", "FLOATTK", "DOUBLETK", "STRUCTTK", "UNIONTK", "ENUMTK", "TYPEDEFTK", "UNSIGNEDTK", "SIGNEDTK", "EXTERNTK", "REGISTERTK", "STATICTK", "VOLATILLETK", "DOTK", "GOTOTK", "CONTINUETK", "BREAKTK", "SIZEOFTK"}; 16 17 //operator 18 static vector<string> operationKey = {"+", "-", "*", "/", "<", "<=", ">", ">=", "==", "!=", "="}; 19 //operator class code 20 static vector<string> operationValue = {"PLUS", "MINU", "MULT", "DIV", "LSS", "LEQ", "GRE", "GEQ", "EQL", "NEQ", "ASSIGN"}; 21 22 //delimiter 23 static vector<string> symbolKey = {":", ";", ",", "(", ")", "{", "}", "[", "]"}; 24 25 //delimiter type code 26 static vector<string> symbolValue = {"COLON", "SEMICN", "COMMA", "LPARENT", "RPARENT", "LBRACE", "RBRACE", "LBRACK", "RBRACK"}; 27 28 //Parse the category code of the current word 29 static vector<string> Tokens; 30 //Parse the current word 31 static vector<string> vals; 32 33 //key is the method name of the function, Value A value of 1 indicates that the method is a method with a return value 34 static map<string,int> NVoidFunction; 35 36 static map<string,string> keywords; 37 static map<string,string> operations; 38 static map<string,string> symbols; 39 40 //pointer to the position of the currently read string 41 static int p, lines; 42 43 //Parse the current word position 44 static int q; 45 46 47 48 ofstream write("output.txt"); 49 ifstream read("testfile.txt"); 50 void lexAnalysing(string str); 51 void init(); 52 void digitCheck(string str); 53 void letterCheck(string str); 54 void stringCheck(string str); 55 void charCheck(string str); 56 void symbolCheck(string str); 57 void parsing(); 58 void parse0(); 59 void parse1(); 60 void parse2(); 61 void parse3(); 62 void parse4(); 63 void parse5(); 64 void parse6(); 65 void parse7(); 66 void parse8(); 67 void parse9(); 68 void parse10(); 69 void parse11(); 70 void parse12(); 71 void parse13(); 72 void parse14(); 73 void parse15(); 74 void parse16(); 75 void parse17(); 76 void parse18(); 77 void parse19(); 78 void parse20(); 79 void parse21(); 80 void parse22(); 81 void parse23(); 82 void parse234(); 83 void parse25(); 84 void parse26(); 85 void parse27(); 86 void parse28(); 87 void parse29(); 88 void MatchToken(string expected); 89 int main(){ 90 init(); 91 lines=1; 92 string line; 93 while(getline(read,line)){ 94 lexAnalysing(line); 95 lines++; 96 } 97 parsing(); 98 write.close(); 99 read.close(); 100 return 0; 101 } 102 void init(){ 103 for(int i=0;i<keyWordKey.size();i++){ 104 keywords[keyWordKey[i]]=keyWordValue[i]; 105 } 106 for(int i=0;i<operationKey.size();i++){ 107 operations[operationKey[i]]=operationValue[i]; 108 } 109 for(int i=0;i<symbolKey.size();i++){ 110 symbols[symbolKey[i]]=symbolValue[i]; 111 } 112 } 113 void lexAnalysing(string str) { 114 p=0; 115 char ch; 116 str.erase(0, str.find_first_not_of(' ')); 117 str.erase(str.find_last_not_of(' ')+1); 118 for(;p<str.length();p++){ 119 ch=str.at(p); 120 if(isdigit(ch)){ 121 digitCheck(str); 122 } 123 else if(isalpha(ch) || ch == '_'){ 124 letterCheck(str); 125 } 126 else if(ch == '"'){ 127 stringCheck(str); 128 } 129 else if(ch == '\''){ 130 charCheck(str); 131 } 132 else if(ch == ' '){ 133 continue; 134 } 135 else { 136 symbolCheck(str); 137 } 138 } 139 } 140 void digitCheck(string str) { 141 142 string token; 143 token.push_back(str.at(p++)); 144 //Determine whether the decimal point of a number has and is greater than 1 145 int flag = 0; 146 bool err = false; 147 char ch; 148 for (; p < str.length(); p++) { 149 ch = str.at(p); 150 if (ch == ' ' || (!isalnum(ch) && ch != '.')) { 151 //encountered a space character,operator or delimiter 152 break; 153 } else if (err) { 154 token += ch; 155 } else { 156 token += ch; 157 if (ch == '.') { 158 if (flag == 1) { 159 err = true; 160 } else { 161 flag++; 162 } 163 } else if (isalpha(ch)) { 164 err = true; 165 } 166 } 167 } 168 if (token.at(token.length() - 1) == '.') { 169 err = true; 170 } 171 Tokens.emplace_back("INTCON"); 172 vals.push_back(token); 173 if (p != str.length() - 1 || (p == str.length() - 1 && !isdigit(str.at(p)))) { 174 p--; 175 } 176 } 177 void letterCheck(string str) { 178 string token; 179 token.push_back(str.at(p++)); 180 char ch; 181 for (; p < str.length(); p++) { 182 ch = str.at(p); 183 if (!isalnum(ch) && ch != '_') { 184 break; 185 } else { 186 token += ch; 187 } 188 } 189 if (keywords.count(token)) { 190 Tokens.push_back(keywords[token]); 191 vals.push_back(token); 192 } else { 193 Tokens.emplace_back("IDENFR"); 194 vals.push_back(token); 195 } 196 if (p != str.length() - 1 || (p == str.length() - 1 && (!isalnum(str.at(p)) && str.at(p) != '_'))) { 197 p--; 198 } 199 } 200 void stringCheck(string str) { 201 202 string token; 203 token.push_back(str.at(p++)); 204 char ch; 205 for (; p < str.length(); p++) { 206 ch = str.at(p); 207 token += ch; 208 if (ch == '"') { 209 break; 210 } 211 } 212 token.erase(remove(token.begin(),token.end(),'\"'), token.end()); 213 Tokens.emplace_back("STRCON"); 214 vals.emplace_back(token); 215 } 216 void charCheck(string str) { 217 218 string token; 219 token.push_back(str.at(p++)); 220 char ch; 221 for (; p < str.length(); p++) { 222 ch = str.at(p); 223 token += ch; 224 if (ch == '\'') { 225 break; 226 } 227 } 228 token.erase(remove(token.begin(),token.end(),'\''), token.end()); 229 Tokens.emplace_back("CHARCON"); 230 vals.push_back(token); 231 } 232 void symbolCheck(string str) { 233 234 string token; 235 token.push_back(str.at(p++)); 236 char ch; 237 if (symbols.count(token)) { 238 Tokens.push_back(symbols[token]); 239 vals.push_back(token); 240 p--; 241 } else { 242 if (operations.count(token) || token=="!") { 243 if (p < str.length()) { 244 ch = str.at(p); 245 if (operations.count(token + ch)) { 246 token += ch; 247 p++; 248 if (p < str.length()) { 249 ch = str.at(p); 250 if (operations.count(token + ch)) { 251 token += ch; 252 Tokens.push_back(operations[token]); 253 vals.push_back(token); 254 } else { 255 p--; 256 Tokens.push_back(operations[token]); 257 vals.push_back(token); 258 } 259 } else { 260 Tokens.push_back(operations[token]); 261 vals.push_back(token); 262 } 263 } else { 264 p--; 265 Tokens.push_back(operations[token]); 266 vals.push_back(token); 267 } 268 } 269 } else { 270 p--; 271 } 272 } 273 } 274 275 void parsing(){ 276 q = 0; 277 parse1(); //from<program>Node starts 278 } 279 void parse0() { 280 //＜string＞ ::= "｛Decimal encoding is 32,33,35-126 of ASCII character｝" 281 MatchToken("STRCON"); 282 write<<"<string>"<<endl; 283 cout<<"<string>"<<endl; 284 } 285 void parse1() { 286 //＜program＞ ::= ［＜Constant Description＞］［＜variable description＞］{＜Function definition with return value＞|＜Function definition with no return value＞}＜main function＞ 287 if (Tokens[q] == "CONSTTK") { 288 parse2(); //＜Constant Description＞ 289 } 290 if ((Tokens[q] == "INTTK" || Tokens[q] == "CHARTK") && Tokens[q+1] == "IDENFR" && Tokens[q+2] != "LPARENT") { 291 parse7(); //＜variable description＞ 292 } 293 while ((Tokens[q] == "INTTK" || Tokens[q] == "CHARTK" || Tokens[q] == "VOIDTK") && 294 Tokens[q+1] == "IDENFR" && Tokens[q+2] == "LPARENT") { 295 if (Tokens[q] == "VOIDTK") { 296 parse10(); //＜Function definition with no return value＞ 297 } else { 298 parse9(); //＜Function definition with return value＞ 299 } 300 } 301 if (Tokens[q] == "VOIDTK" && Tokens[q+1]== "MAINTK") { 302 parse13(); //＜main function＞ 303 } 304 if (q == Tokens.size()) { 305 cout<<"<program>"<<endl; 306 write<<"<program>"<<endl; 307 } 308 } 309 void parse2() { 310 //＜Constant Description＞ ::= const＜constant definition＞;{ const＜constant definition＞;} 311 do { 312 MatchToken("CONSTTK"); 313 parse3(); //＜constant definition＞ 314 MatchToken("SEMICN"); 315 } while (Tokens[q] == "CONSTTK"); 316 cout<<"<Constant Description>"<<endl; 317 write<<"<Constant Description>"<<endl; 318 } 319 320 void parse3() { 321 //＜constant definition＞ ::= int＜identifier＞＝＜integer＞{,＜identifier＞＝＜integer＞}| char＜identifier＞＝＜character＞{,＜identifier＞＝＜character＞} 322 if (Tokens[q]== "INTTK") { 323 MatchToken("INTTK"); 324 MatchToken("IDENFR"); 325 MatchToken("ASSIGN"); 326 parse5(); //＜integer＞ 327 while (Tokens[q] == "COMMA") { 328 MatchToken("COMMA"); 329 MatchToken("IDENFR"); 330 MatchToken("ASSIGN"); 331 parse5(); 332 } 333 } 334 if (Tokens[q] == "CHARTK") { 335 MatchToken("CHARTK"); 336 MatchToken("IDENFR"); 337 MatchToken("ASSIGN"); 338 MatchToken("CHARCON"); 339 while (Tokens[q] == "COMMA") { 340 MatchToken("COMMA"); 341 MatchToken("IDENFR"); 342 MatchToken("ASSIGN"); 343 MatchToken("CHARCON"); 344 } 345 } 346 cout<<("<constant definition>")<<endl; 347 write<<("<constant definition>")<<endl; 348 349 } 350 351 void parse4() { 352 //<unsigned integer> 353 MatchToken("INTCON"); 354 cout<<("<unsigned integer>")<<endl; 355 write<<("<unsigned integer>")<<endl; 356 357 } 358 359 void parse5() { 360 //＜integer＞ ::= ［＋｜－］＜unsigned integer＞ 361 if (Tokens[q] == "PLUS") 362 MatchToken("PLUS"); 363 else if (Tokens[q] == "MINU") 364 MatchToken("MINU"); 365 parse4(); //<unsigned integer> 366 cout<<("<integer>")<<endl; 367 write<<("<integer>")<<endl; 368 369 } 370 371 void parse6() { 372 //＜declaration header＞ ::= int＜identifier＞ |char＜identifier＞ 373 if (Tokens[q] == "INTTK") 374 MatchToken("INTTK"); 375 else if (Tokens[q] == "CHARTK") 376 MatchToken("CHARTK"); 377 MatchToken("IDENFR"); 378 cout<<("<declaration header>")<<endl; 379 write<<("<declaration header>")<<endl; 380 381 } 382 383 void parse7() { 384 //＜variable description＞ ::= ＜Variable definitions＞;{＜Variable definitions＞;} 385 do { 386 parse8(); //＜Variable definitions＞ 387 MatchToken("SEMICN"); 388 } while ((Tokens[q] == "INTTK" || Tokens[q] == "CHARTK") && 389 Tokens[q + 1] == "IDENFR" && Tokens[q + 2] != "LPARENT"); 390 cout<<("<variable description>")<<endl; 391 write<<("<variable description>")<<endl; 392 393 } 394 void parse8() { 395 //＜Variable definitions＞ ::= ＜type identifier＞(＜identifier＞|＜identifier＞'['＜unsigned integer＞']'){,(＜identifier＞|＜identifier＞'['＜unsigned integer＞']')} 396 if (Tokens[q] == "INTTK") 397 MatchToken("INTTK"); 398 else if (Tokens[q] == "CHARTK") 399 MatchToken("CHARTK"); 400 MatchToken("IDENFR"); 401 if (Tokens[q] == "LBRACK") { 402 MatchToken("LBRACK"); 403 parse4(); //<unsigned integer> 404 MatchToken("RBRACK"); 405 } 406 while (Tokens[q] == "COMMA") { 407 MatchToken("COMMA"); 408 MatchToken("IDENFR"); 409 if (Tokens[q] == "LBRACK") { 410 MatchToken("LBRACK"); 411 parse4(); //<unsigned integer> 412 MatchToken("RBRACK"); 413 } 414 } 415 cout<<("<Variable definitions>")<<endl; 416 write<<("<Variable definitions>")<<endl; 417 418 } 419 void parse9() { 420 //＜Function definition with return value＞ ::= ＜declaration header＞'('＜Parameters Table＞')' '{'＜compound statement＞'}' 421 parse6(); //＜declaration header＞ 422 NVoidFunction.insert({vals[q - 1], 1}); 423 MatchToken("LPARENT"); 424 parse12(); //＜Parameters Table＞ 425 MatchToken("RPARENT"); 426 MatchToken("LBRACE"); 427 parse11(); //＜compound statement＞ 428 MatchToken("RBRACE"); 429 cout<<("<Function definition with return value>")<<endl; 430 write<<("<Function definition with return value>")<<endl; 431 432 } 433 void parse10() { 434 //＜Function definition with no return value＞ ::= void＜identifier＞'('＜Parameters Table＞')''{'＜compound statement＞'}' 435 MatchToken("VOIDTK"); 436 MatchToken("IDENFR"); 437 MatchToken("LPARENT"); 438 parse12(); //＜Parameters Table＞ 439 MatchToken("RPARENT"); 440 MatchToken("LBRACE"); 441 parse11(); //＜compound statement＞ 442 MatchToken("RBRACE"); 443 cout<<("<Function definition with no return value>")<<endl; 444 write<<("<Function definition with no return value>")<<endl; 445 446 } 447 void parse11() { 448 //＜compound statement＞ ::= ［＜Constant Description＞］［＜variable description＞］＜statement column＞ 449 if (Tokens[q] == "CONSTTK") { 450 parse2(); //＜Constant Description＞ 451 } 452 if ((Tokens[q] == "INTTK" || Tokens[q] == "CHARTK") && 453 Tokens[q + 1]== "IDENFR" && Tokens[q + 2] != "LPARENT") { 454 parse7(); //＜variable description＞ 455 } 456 parse26(); //＜statement column＞ 457 cout<<("<compound statement>")<<endl; 458 write<<("<compound statement>")<<endl; 459 460 } 461 void parse12() { 462 //＜Parameters Table＞ ::= ＜type identifier＞＜identifier＞{,＜type identifier＞＜identifier＞}| ＜null＞ 463 if (Tokens[q] != "RPARENT")//if the next token is a closing parenthesis, it is empty 464 { 465 if (Tokens[q] == "INTTK") 466 MatchToken("INTTK"); 467 else if (Tokens[q] == "CHARTK") 468 MatchToken("CHARTK"); 469 MatchToken("IDENFR"); 470 while (Tokens[q] == "COMMA") { 471 MatchToken("COMMA"); 472 if (Tokens[q] == "INTTK") 473 MatchToken("INTTK"); 474 else if (Tokens[q] == "CHARTK") 475 MatchToken("CHARTK"); 476 MatchToken("IDENFR"); 477 } 478 } 479 cout<<("<Parameters Table>")<<endl; 480 write<<("<Parameters Table>")<<endl; 481 482 } 483 484 void parse13() { 485 //＜main function＞ ::= void main'('')' '{'＜compound statement＞'}' 486 MatchToken("VOIDTK"); 487 MatchToken("MAINTK"); 488 MatchToken("LPARENT"); 489 MatchToken("RPARENT"); 490 MatchToken("LBRACE"); 491 parse11(); //＜compound statement＞ 492 MatchToken("RBRACE"); 493 cout<<("<main function>")<<endl; 494 write<<("<main function>")<<endl; 495 496 } 497 498 void parse14() { 499 //＜expression＞ ::= ［＋｜－］＜item＞{＜addition operator＞＜item＞} 500 if (Tokens[q] == "PLUS") 501 MatchToken("PLUS"); 502 else if (Tokens[q] == "MINU") 503 MatchToken("MINU"); 504 parse15(); //＜item＞ 505 while (Tokens[q] == "PLUS" || Tokens[q] == "MINU") { 506 if (Tokens[q] == "PLUS") 507 MatchToken("PLUS"); 508 else if (Tokens[q] == "MINU") 509 MatchToken("MINU"); 510 parse15(); //＜item＞ 511 } 512 cout<<("<expression>")<<endl; 513 write<<("<expression>")<<endl; 514 515 } 516 517 void parse15() { 518 //＜item＞ ::= ＜factor＞{＜multiplication operator＞＜factor＞} 519 parse16(); //＜factor＞ 520 while (Tokens[q] == "MULT" || Tokens[q] == "DIV") { 521 if (Tokens[q] == "MULT") 522 MatchToken("MULT"); 523 else if (Tokens[q] == "DIV") 524 MatchToken("DIV"); 525 parse16(); //＜factor＞ 526 } 527 cout<<("<item>")<<endl; 528 write<<("<item>")<<endl; 529 530 } 531 532 void parse16() { 533 //＜factor＞ ::= ＜identifier＞｜＜identifier＞'['＜expression＞']'|'('＜expression＞')'｜＜integer＞|＜character＞｜＜Function call statement with return value＞ 534 if (Tokens[q] == "IDENFR") { 535 if (Tokens[q + 1]== "LBRACK") { 536 MatchToken("IDENFR"); 537 MatchToken("LBRACK"); 538 parse14(); //＜expression＞ 539 MatchToken("RBRACK"); 540 } else if (Tokens[q + 1 ]== "LPARENT") 541 parse234(); //＜Function call statement with return value＞ 542 else MatchToken("IDENFR"); 543 } else if (Tokens[q] == "LPARENT") { 544 MatchToken("LPARENT"); 545 parse14(); //＜expression＞ 546 MatchToken("RPARENT"); 547 } else if (Tokens[q] == "INTCON" || Tokens[q] == "PLUS" || Tokens[q] == "MINU") 548 parse5(); //＜integer＞ 549 else if (Tokens[q] == "CHARCON") 550 MatchToken("CHARCON"); 551 cout<<("<factor>")<<endl; 552 write<<("<factor>")<<endl; 553 554 } 555 556 void parse17() { 557 /*＜statement> ::= <conditional statement>｜<loop statement>| '{'<statement string>'}' 558 | ＜Function call statement with return value>; |<function call statement without return value>;|<assignment statement>; 559 ｜＜read statement>;｜<write statement>;｜<empty>;|<return statement>;*/ 560 if (Tokens[q] == "IFTK") 561 parse19(); //＜Conditional statements＞ 562 else if (Tokens[q] == "WHILETK" || Tokens[q] == "DOTK" || Tokens[q] == "FORTK") 563 parse21(); //＜loop statement＞ 564 else if (Tokens[q] == "LBRACE") { 565 MatchToken("LBRACE"); 566 parse26(); //＜statement column＞ 567 MatchToken("RBRACE"); 568 } else if (Tokens[q] == "IDENFR") { 569 if (Tokens[q + 1] == "LPARENT") { 570 parse234(); //＜Function call statement with or without return value＞ 571 MatchToken("SEMICN"); 572 } else { 573 parse18(); //＜assignment statement＞ 574 MatchToken("SEMICN"); 575 } 576 } else if (Tokens[q] == "SCANFTK") { 577 parse27(); //＜read statement＞ 578 MatchToken("SEMICN"); 579 } else if (Tokens[q] == "PRINTFTK") { 580 parse28(); //＜write statement＞ 581 MatchToken("SEMICN"); 582 } else if (Tokens[q] == "RETURNTK") { 583 parse29(); //＜return statement＞ 584 MatchToken("SEMICN"); 585 } else if (Tokens[q] == "SEMICN") 586 MatchToken("SEMICN"); 587 cout<<("<statement>")<<endl; 588 write<<("<statement>")<<endl; 589 590 } 591 592 void parse18() { 593 //＜assignment statement＞ ::= ＜identifier＞＝＜expression＞|＜identifier＞'['＜expression＞']'=＜expression＞ 594 MatchToken("IDENFR"); 595 if (Tokens[q] == "LBRACK") { 596 MatchToken("LBRACK"); 597 parse14(); //＜expression＞ 598 MatchToken("RBRACK"); 599 } 600 MatchToken("ASSIGN"); 601 parse14(); //＜expression＞ 602 cout<<("<assignment statement>")<<endl; 603 write<<("<assignment statement>")<<endl; 604 605 } 606 607 void parse19() { 608 //＜Conditional statements＞ ::= if '('＜condition＞')'＜statement＞［else＜statement＞］ 609 MatchToken("IFTK"); 610 MatchToken("LPARENT"); 611 parse20(); //＜condition＞ 612 MatchToken("RPARENT"); 613 parse17(); //＜statement＞ 614 if (Tokens[q] == "ELSETK") { 615 MatchToken("ELSETK"); 616 parse17(); //＜statement＞ 617 } 618 cout<<("<Conditional statements>")<<endl; 619 write<<("<Conditional statements>")<<endl; 620 621 } 622 623 void parse20() { 624 //＜condition＞ ::= ＜expression＞＜relational operator＞＜expression＞ //Only relational operations can be performed between integer expressions｜＜expression＞ 625 // The expression is an integer whose value is 0 and the condition is false, and if the value is not 0, the condition is true 626 parse14(); //＜expression＞ 627 if (Tokens[q] == "LSS" || Tokens[q] == "LEQ" || Tokens[q] == "GRE" 628 || Tokens[q] == "GEQ" || Tokens[q] == "EQL" || Tokens[q] == "NEQ") { 629 MatchToken((string) Tokens[q]); 630 parse14(); //＜expression＞ 631 } 632 cout<<("<condition>")<<endl; 633 write<<("<condition>")<<endl; 634 635 } 636 637 void parse21() { 638 //＜loop statement＞ ::= while '('＜condition＞')'＜statement＞ 639 // |do＜statement＞while '('＜condition＞')' 640 // |for'('＜identifier＞＝＜expression＞;＜condition＞;＜identifier＞＝＜identifier＞(+|-)＜step size＞')'＜statement＞ 641 if (Tokens[q] == "WHILETK") { 642 MatchToken("WHILETK"); 643 MatchToken("LPARENT"); 644 parse20(); //＜condition＞ 645 MatchToken("RPARENT"); 646 parse17(); //＜statement＞ 647 } else if (Tokens[q] == "DOTK") { 648 MatchToken("DOTK"); 649 parse17(); //＜statement＞ 650 MatchToken("WHILETK"); 651 MatchToken("LPARENT"); 652 parse20(); //＜condition＞ 653 MatchToken("RPARENT"); 654 } else if (Tokens[q] == "FORTK") { 655 MatchToken("FORTK"); 656 MatchToken("LPARENT"); 657 MatchToken("IDENFR"); 658 MatchToken("ASSIGN"); 659 parse14(); //＜expression＞ 660 MatchToken("SEMICN"); 661 parse20(); //＜condition＞ 662 MatchToken("SEMICN"); 663 MatchToken("IDENFR"); 664 MatchToken("ASSIGN"); 665 MatchToken("IDENFR"); 666 if (Tokens[q] == "PLUS") 667 MatchToken("PLUS"); 668 else if (Tokens[q] == "MINU") 669 MatchToken("MINU"); 670 parse22(); //＜step size＞ 671 MatchToken("RPARENT"); 672 parse17(); //＜statement＞ 673 } 674 cout<<("<loop statement>")<<endl; 675 write<<("<loop statement>")<<endl; 676 677 } 678 679 void parse22() { 680 //＜step size＞::= ＜unsigned integer＞ 681 parse4(); //＜unsigned integer＞ 682 cout<<("<step size>")<<endl; 683 write<<("<step size>")<<endl; 684 685 } 686 687 void parse234() { 688 //＜Function call statement with or without return value＞ ::= ＜identifier＞'('＜Value parameter table＞')' 689 int FunctionType = 0; 690 if(NVoidFunction.count(vals[q])) { 691 FunctionType = NVoidFunction[vals[q]]; 692 } 693 MatchToken("IDENFR"); 694 MatchToken("LPARENT"); 695 parse25(); //＜Value parameter table＞ 696 MatchToken("RPARENT"); 697 if (FunctionType == 1) { 698 cout<<("<Function call statement with return value>")<<endl; 699 write<<("<Function call statement with return value>")<<endl; 700 701 } else { 702 cout<<("<Function call statement with no return value>")<<endl; 703 write<<("<Function call statement with no return value>")<<endl; 704 705 } 706 } 707 708 void parse25() { 709 //＜Value parameter table＞ ::= ＜expression＞{,＜expression＞}｜＜null＞ 710 if (Tokens[q] != "RPARENT") { 711 parse14(); //＜expression＞ 712 while (Tokens[q] == "COMMA") { 713 MatchToken("COMMA"); 714 parse14(); 715 } 716 } 717 cout<<("<Value parameter table>")<<endl; 718 write<<("<Value parameter table>")<<endl; 719 720 } 721 722 void parse26() { 723 //＜statement column＞ ::= ｛＜statement＞｝ 724 while (Tokens[q] != "RBRACE") 725 parse17(); //＜statement＞ 726 cout<<("<statement column>")<<endl; 727 write<<("<statement column>")<<endl; 728 729 } 730 731 void parse27() { 732 //＜read statement＞ ::= scanf '('＜identifier＞{,＜identifier＞}')' 733 MatchToken("SCANFTK"); 734 MatchToken("LPARENT"); 735 MatchToken("IDENFR"); 736 while (Tokens[q] == "COMMA") { 737 MatchToken("COMMA"); 738 MatchToken("IDENFR"); 739 } 740 MatchToken("RPARENT"); 741 cout<<("<read statement>")<<endl; 742 write<<("<read statement>")<<endl; 743 744 } 745 746 void parse28() { 747 //＜write statement＞ ::= printf '(' ＜string＞,＜expression＞ ')' 748 // | printf '('＜string＞ ')' 749 // | printf '('＜expression＞')' 750 MatchToken("PRINTFTK"); 751 MatchToken("LPARENT"); 752 if (Tokens[q] == "STRCON") 753 parse0(); //＜string＞ 754 else 755 parse14(); //＜expression＞ 756 if (Tokens[q] == "COMMA") { 757 MatchToken("COMMA"); 758 parse14(); //＜expression＞ 759 } 760 MatchToken("RPARENT"); 761 cout<<("<write statement>")<<endl; 762 write<<("<write statement>")<<endl; 763 764 } 765 766 void parse29() { 767 //＜return statement＞ ::= return['('＜expression＞')'] 768 MatchToken("RETURNTK"); 769 if (Tokens[q] == "LPARENT") { 770 MatchToken("LPARENT"); 771 parse14(); //＜expression＞ 772 MatchToken("RPARENT"); 773 } 774 cout<<("<return statement>")<<endl; 775 write<<("<return statement>")<<endl; 776 777 } 778 779 void MatchToken(string expected) { 780 if (Tokens[q] == expected) { 781 cout<<Tokens[q]<<" "<<vals[q]<<endl; 782 write<<Tokens[q]<<" "<<vals[q]<<endl; 783 q++; //next word 784 } 785 }