CS453 Intro and PA1 1CS453 Lecture Intro to Parsing 2Plan for Today How do you implement DFAs?– For recognizing strings in a language– For recognizing tokens in a string Context Free Grammars– What is it?– Derivations– Parse trees– Specifying them in SableCCCS453 Lecture Intro to Parsing 3DFAs for Recognizing Language and TokensCS453 Lecture Intro to Parsing 4Implementing DFAs state = 1; char c = read(); while ( !error && c !=eol ) { switch ( state ) { case 1: switch ( c ) { case letter: state = 2; break; default: error = true; } case 2: switch ( c ) { case letter: case digit: case us: state = 2; break; default: error = true; } } char c = read(); } if (!error && state==2) accept else rejectCS453 Lecture Intro to Parsing 5Implementing a DFA that recognizes tokens(token,string) lex() { char buffer[MAXBUF]; if (firsttime) { state = 1; lastfinal = -1; lastindex = -1; startindex = 0; currindex = 0; buffer = whole input file; c = buffer[currindex]; } while ( currindex!=MAXBUF && !error && c!= eol ) { switch ( state ) { case 1: switch ( c ) { case 'i': state = 2; lastfinal = 2; lastindex = currindex; case not_i: state = 4; lastfinal = 4; lastindex = currindex; break; default: error = true; } case 2: switch ( c ) { case 'f': state = 3; lastfinal = 3; lastindex = currindex; case not_f: case digit: case us: state = 4; lastfinal = 4; lastindex = currindex; break; default: error = true; }CS453 Intro and PA1 2CS453 Lecture Intro to Parsing 6Token Impl cont. case 3: case 4: switch ( c ) { case letter: case not_f: case digit: case us: state = 4; lastfinal = 4; lastindex = currindex; break; default: error = true; } } if (error) { if (lastfinal!=-1) { token = statetoken[lastfinal]; string = buffer[startindex..lastindex]; lastfinal = -1; currindex = lastindex; startindex = currindex+1; c = buff[currindex++]; error = false; return (token,string); } else { return error; } } c = buffer[currindex++]; } if (!error && state== (2 | 3 | 4) ) { token = statetoken[lastfinal]; string = buffer[startindex..lastindex]; return (token,string); } else return error;}CS453 Lecture Intro to Parsing 7Parse Tree Examplea := ( b := ( c := 3, 2 ), 1 )Stm --> id := ExpExp --> numExp --> ( Stm, Exp )GrammarStringParse TreeCS453 Lecture Intro to Parsing 8Specifying Grammars with SableCC SableCC example input file: Package minijava; Helpers ... Tokens ... Productions stm = exp_list ; exp = {plus_rule} exp plus term | {term_rule} term ; term = {mult_rule} term mult factor | {fact_rule} factor ; factor = {id_rule} id ; exp_list = exp exp_rest* ; exp_rest = comma exp
View Full Document
Unlocking...