/* This program implements and tests a recursive descent parser for a language defined by a grammar given below. The function "test" expects the name of a file containing a program in the language. It attempts to parse the program, printing "ok" after a successful parse and the name of an unexpected token otherwise. It prints all token successfully matched. The functions processing nonterminals are constructed by the algorithm mapping grammar rules into recognition functions, and are thus not commented. The "main" function simply tests this function by calling it with 7 files. Each file is expected to be in the current directory. The grammar for the language is: ::= . ::= function [] begin [] [] end ::= {} ::= {} ::= {} ::= call {} */ #include #include #include #include typedef int BOOLEAN; const TRUE = 1; const FALSE = 0; char token[20]; /* the current token */ FILE *fp; /* the file containing the program */ /******************* some utility functions *************************/ /* Read the next token into the global variable "token", consuming it */ void GetToken(FILE *fp) { fscanf(fp,"%s",&token); printf("%s\n",token); } /* Determine whether a string is a reserved word by comparing it with each known reserved word */ BOOLEAN reserved(char *w) { if (strcmp(w,"function")==0) return TRUE; if (strcmp(w,"begin")==0) return TRUE; if (strcmp(w,"end")==0) return TRUE; if (strcmp(w,"call")==0) return TRUE; if (strcmp(w,"local")==0) return TRUE; return FALSE; } BOOLEAN is_id(void) { return !reserved(token); } /***************** FUNCTIONS TO PROCESS NONTERMINALS *****************/ /******************* Process the nonterminal "id" ********************/ BOOLEAN id(void) { if (!is_id()) { printf("unexpected token: %s\n",token); return FALSE; } GetToken(fp); return TRUE; } /***************** Process the nonterminal "params" ********************/ BOOLEAN params(void) { BOOLEAN success; success=id(); if (!success) return FALSE; while (is_id()) { success=id(); } return TRUE; } /***************** Process the nonterminal "call" ********************/ BOOLEAN call(void) { BOOLEAN success; if (!strcmp(token,"call")==0) { printf("unexpected token: %s\n",token); return FALSE; } GetToken(fp); if (!id()) return FALSE; while (is_id()) id(); return TRUE; } /* This forward declaration allows the indirect recursion between the nonterminals "function" and "functions" */ /**************** Process the nonterminal "functions" *******************/ BOOLEAN functions(void); /**************** Process the nonterminal "body" *******************/ BOOLEAN body(void) { BOOLEAN success; success=call(); if (!success) return FALSE; while (strcmp(token,"call")==0) { success=call(); if (!success) return FALSE; } return success; } /*************** Process the nonterminal "function" *******************/ BOOLEAN funct(void) { BOOLEAN success; if (strcmp(token,"function")!=0) { printf("unexpected token: %s\n",token); return FALSE; } GetToken(fp); if (!id()) { return FALSE; } if (is_id()) { success=params(); if (!success) { return FALSE; } } if (strcmp(token,"begin")!=0) { printf("unexpected token: %s\n",token); return FALSE; } GetToken(fp); if (strcmp(token,"function")==0) { success=functions(); if (!success) return FALSE; } if (strcmp(token,"call")==0) { success=body(); if (!success) return FALSE; } if (strcmp(token,"end")!=0) { printf("unexpected token: %s\n",token); return FALSE; } GetToken(fp); return TRUE; } /**************** Process the nonterminal "functions" *******************/ BOOLEAN functions(void) { BOOLEAN success; success=funct(); if (!success) return FALSE; while (strcmp(token,"function")==0) { success=funct(); if (!success) return FALSE; } success=TRUE; return success; } /**************** Process the start symbol "program" *******************/ BOOLEAN program(void) { BOOLEAN success; success=funct(); if (!success) return FALSE; if (strcmp(token,".")!=0) { printf("unexpected token: %s\n",token); return FALSE; } GetToken(fp); return TRUE; } /* To compile, read the first token and try to match the start symbol "program" */ BOOLEAN compile(void) { BOOLEAN success; GetToken(fp); /* using one symbol of lookahead, */ return program(); /* parse as function with no caller */ } /* The "test" function attempts to parse the text given in the file "filename" */ void test(char *filename) { BOOLEAN s; fp=fopen(filename,"r"); if (!fp) { printf("can't find file\n"); return; } s=compile(); if (!s) printf("%s\n","failed to compile"); else printf("%s\n","ok"); fclose(fp); } /* The "main" function requires the test files to be in the current directory */ int main(void) { test("data1"); printf("\n"); test("data2"); printf("\n"); test("data3"); printf("\n"); test("data4"); printf("\n"); test("data5"); printf("\n"); test("data6"); printf("\n"); test("data7"); printf("\n"); return 0; }