Building Predictive Parsing Tables in C++ language.

Project name: Building Predictive Parsing Tables in C++ language. Conceptually, a compiler operates in phases, each of which transforms the source program from one representation to another. A typical decomposition of a compiler is:Source program, to lexical analyzer, to syntax analyzer, to semantic analyzer, to intermediate code generator, to code optimizer, to code generator, to target program. Recursive-descent parsing is a top-down method of syntax analysis in which we execute a set of recursive procedures to process the input. A procedure is associated with each nonterminal of a grammar. Here, we consider a special form of Recursive-descent parsing, called predictive parsing. I need the source code of top-down parser in C++ language. The code must be commented. You can use these reference books: [login to view URL], Sethi, [login to view URL], COMPILERS Principles, Techniques, and Tools [login to view URL] [login to view URL], COMPILER DESIGN in C Algorithm for Construction of Predictive Parsing Tables: Repeat: for each production A=>alpha of the grammar do for each terminal a in FIRST(alpha) add A=>alpha to M [A, a] if FIRST(alpha) contains epcylon add A=>alpha to M[A,b] for each b in FOLLOW(A) if epcylon is in FIRST(alpha) and $ is in FOLLOW(A) add A =>alpha to M[A,$] make each undefined entry of M be error sample input/output is given in zip file. ## Deliverables 1) Complete and fully-functional working program(s) in executable form as well as complete source code of all work done. 2) Deliverables must be in ready-to-run condition, as follows? (depending on the nature? of the deliverables): a)? For web sites or? other server-side deliverables intended to only ever exist in one place in the Buyer's environment--Deliverables must be installed by the Seller in ready-to-run condition in the Buyer's environment. b) For all others including desktop software or software the buyer intends to distribute: A software? installation package that will install the software in ready-to-run condition on the platform(s) specified in this bid request. 3) All deliverables will be considered "work made for hire" under U.S. Copyright law. Buyer will receive exclusive and complete copyrights to all work purchased. (No GPL, GNU, 3rd party components, etc. unless all copyright ramifications are explained AND AGREED TO by the buyer on the site per the coder's Seller Legal Agreement). Building Predictive Parsing Tables in C++ language Computing the Function FIRST: To compute FIRST(X) for all grammar symbols X apply the following rules until no more terminals or epcylon can be added to any FIRST set: [login to view URL] X is terminal, then FIRST(X) is {X}. [login to view URL] X => epcylon is a production, then add epcylon to FIRST(X). [login to view URL] X is non terminal and X=>Y1,Y2,…,Yk is a production, then place a in FIRST(X) if a is in FIRST(Yi) for some i, and epcylon is in all of FIRST(Y1), FIRST(Y2),…,FIRST(Yi-1);that is Y1,Y2,…Yi-1 => * epcylon. [login to view URL] epcylon is in FIRST (Yj), all j=1, 2,…,k then add epcylon to FIRST(X). Computing the Function FOLLOW: To compute FOLLOW(A) for all nonterminals A apply the following rules until nothing can be added to any FOLLOW set: [login to view URL] $ in FOLLOW(S) where S is the start symbol and $ is the input right marker [login to view URL] there is a production A=>alphaBbeta, then everything in FIRST(beta) except the symbol epcylon is placed in FOLLOW(B). [login to view URL] there is a production A=>alphaB, or a production A=>alphaBbeta where FIRST(beta) contains epcylon, then everything in FOLLOW(A) is also in FOLLOW(B). Algorithm for Construction of Predictive Parsing Tables: Repeat: for each production A=>alpha of the grammar do for each terminal a in FIRST(alpha) add A=>alpha to M [A, a] if FIRST(alpha) contains epcylon add A=>alpha to M[A,b] for each b in FOLLOW(A) if epcylon is in FIRST(alpha) and $ is in FOLLOW(A) add A =>alpha to M[A,$] make each undefined entry of M be error Sample Input: Construct a predictive parsing table for the following grammar: P=>bSe S=>AR R=>AR | epcylon A=>id=E; E=>FT T=>+FT | epcylon F=>(E) | id | INT Sample Output: The construction of the predictive parsing table begins with the computation of the functions FIRST and FOLLOW: FIRST(P) = {b} FOLLOW(P) = {$} FIRST(S) = {id} FOLLOW(S) = {e} FIRST(R) = {id,epcylon} FOLLOW(R) = {e} FIRST(A) = {id} FOLLOW(A) = {id,epcylon} FIRST(E) = {(,id,INT} FOLLOW(E) = {; , )} FIRST(T) = {+,epcylon} FOLLOW(T) = {; , )} FIRST(F) = {(,id,INT} FOLLOW(F) = {+ , ; , )} The parsing table for the grammar then becomes: id INT = + ; ( ) b e $ P P=>bSe S S=>AR R R=>AR R=>epcylon A A=>id = E ; E E=>FT E=>FT E=>FT T T=>+FT T=>epcylon T=>epcylon F F=>id F=>INT F=>(E) Using the above parsing table a simple string will be parsed as follows: Stack Input Output $P b id = id + 1 ; e $ $eSb b id = id + 1 ; e $ P=>bSe $eS id = id + 1 ; e $ $eRA id = id + 1 ; e $ S=>AR $eR;E=id id = id + 1 ; e $ A=>id = E ; $eR;E= = id + 1 ; e $ $eR;E id + 1 ; e $ $eR;TF id + 1 ; e $ E=>FT $eR;Tid id + 1 ; e $ F=>id $eR;T + 1 ; e $ $eR;TF+ + 1 ; e $ T=>+FT $eR;TF 1 ; e $ $eR;TINT 1 ; e $ F=>INT $eR;T ; e $ $eR; ; e $ T=>epcylon $eR e $ $e e $ R=>epcylon $ $ ## Platform Windows XP,2000,98