SLR.rar_SLR_SLR 语法分析_slr parser_语法分析器

#include< iostream > #include< fstream > #include< cstdlib > #include< string > #include< iomanip > using namespace std; //#define first_no 8 //#define follow_no 8 #define pro_no 16 #define nt_no 8 #define t_no 16 #define stack_size 32 #define stack_increment 32 #define queue_size 32 #define item_no 8// perhaps too small for some bigger grammar #define state_no 16 typedef struct production production; typedef struct item item; typedef struct step step; struct production { string left; string right; }; struct step { char act; int next; }; class nonTerminal { public: nonTerminal() {}; bool find_first( const char &ch) { if( first.find( ch, 0 ) < first.length() ) return true; return false; }; bool find_follow( const char &ch ) { if( follow.find( ch, 0 ) <follow.length() ) return true; return false; }; void set_sign( string s ) { sign = s; }; string get_sign() { return sign; }; void set_added( bool a ) { added = a; }; bool get_added() { return added; }; void set_null() { isNull = true; }; bool is_null() { return isNull; }; string get_first() { return first; }; string get_follow() { return follow; }; int add_first( const char &ch ) { int i = 0; for( i = 0; i < first.length(); i ++ ) { if( first[ i ] == ch ) return -1; } first += ch; return 0; }; int add_follow( const char &ch ) { if( ch == ' ' ) return -1;//extra and unnecessary insurance int i = 0; for( i = 0; i < follow.length(); i ++ ) { if( follow[ i ] == ch ) return -1; } follow += ch; return 0; }; private: string sign; string first; string follow; bool isNull; bool added; }; template< class T > class queue { public: queue() { base = ( T * )malloc( queue_size * sizeof( T ) ); if( ! base ) exit( 0 ); memset( base, 0, queue_size * sizeof( T ) ); front = 0; rear = 0; }; int get_size() { return ( rear - front + queue_size ) % queue_size; }; T get_front() { if( front == rear ) { cout<<"Get_front failed! The queue is empty!"<<endl; exit( 0 ); } return base[ front ]; }; T pop() { if( front == rear ) { cout<<"Pop failed! The queue is empty!"<<endl; exit( 0 ); } if( front + 1 == queue_size )//unnecessary to use '>=' { front = 0; return base[ queue_size - 1 ]; } return base[ front ++ ]; }; int push( const T ch ) { if( ( rear + 1 ) % queue_size == front ) return -1; base[ rear ] = ch; rear = ( rear + 1 ) % queue_size; return 0; }; bool isEmpty() { return ( front == rear ); }; string traverse() { T *tmp = NULL; string str = ""; for( tmp = front; tmp != rear; tmp = ( ( tmp + 1 ) % queue_size ) ) { str += *tmp; } return str; }; string int_traverse() { int tmp = 0; string str = ""; char *buffer = ( char * )malloc( sizeof( char ) * 8 ); for( tmp = front; tmp != rear; tmp = ( ( tmp + 1 ) % queue_size ) ) { memset( buffer, 0, sizeof( char ) * 8 ); str += itoa( base[ tmp ], buffer, 10 ); } return str; }; private: T *base; int front; int rear; }; template< class T > class stack { public: stack() { base = ( T * )malloc( stack_size * sizeof( T ) ); if( ! base ) exit( 0 ); memset( base, 0, stack_size * sizeof( T ) ); top = base; size = stack_size; }; int get_size() { return size; }; T get_top() { if( top == base ) { cout<<"Get_top failed! The stack is empty!"<<endl; exit( 0 ); } return *( top - 1 ); }; int push( const T &ch ) { if( ( top - base ) >= size ) { base = ( T * )realloc( base, ( size + stack_increment ) * sizeof( T ) ); if( ! base ) exit( 0 ); top = base + size; size += stack_increment; } *top = ch; top ++; return 0; }; T pop() { if( top == base ) { cout<<"Pop failed! The stack is empty!"<<endl; exit( 0 ); } top --; return *top; }; bool isEmpty() { return ( base == top ); }; string traverse() { T *tmp = NULL; string str = ""; for( tmp = base; tmp != top; tmp ++ ) { str += *tmp; } return str; }; string int_traverse() { T *tmp = NULL; string str = ""; char *buffer = ( char * )malloc( sizeof( char ) * 8 ); for( tmp = base; tmp != top; tmp ++ ) { memset( buffer, 0, sizeof( char ) * 8 ); str += itoa( *tmp, buffer, 10 ); } return str; }; private: T *base; T *top; int size; }; struct item { string left; string right; int start;//start is the index of the first element after the dot '.' bool considered; bool operator==( const item &aim ) { return ( ( left == aim.left ) && ( right == aim.right ) && ( start == aim.start ) ); }; }; production pro[ pro_no ]; nonTerminal nt[ nt_no ]; item state[ state_no ][ item_no ]; string select_aggregate[ nt_no ][ t_no + 1 ], sentence; char t[ t_no ]; bool changed = true; int go_to[ state_no ][ nt_no ], end_pos = 0; step action[ state_no ][ t_no + 1 ]; int get_sentence() { fstream read; char ch = 0; sentence = ""; read.open( "sentence.in", ios_base::in | ios::binary ); if( ! read ) { cout<<"Sentence Input File Opening Error!"<<endl; exit( 0 ); } read.get( ch ); while( read.fail() == false ) { if( ch == ' ' || ch == '\t' || ch == '\r' || ch == '\n' ) { read.get( ch ); continue; } sentence += ch; read.get( ch ); } sentence += "#";//once forgot! read.close(); return 0; }; int in_nt( const char &ch )//premise: nonTerminals are all characters { int i = 0; string aim = "", str = ""; aim += ch; str = nt[ 0 ].get_sign(); while( str != "" ) { if( str == aim ) return i; i++; str = nt[ i ].get_sign(); } return -1; }; int in_t( const char &aim ) { int i = 0; char *ch = t; bool exist = false; while( *ch != 0 ) { if( *ch == aim ) { exist = true; break; } ch ++; i++; } if( exist == false ) return -1; else return i; }; int analyze() { int i = 0, count = 0;// count records how many times of output have been done char *next = &sentence[ 0 ], ch = 0;// ch to store the character just popped string to_pop = "", str = ""; int t_pos = 0, nt_pos = 0, now = 0, current_nt = 0; fstream write; step *current_t = &action[ 0 ][ 0 ]; production *to_recurse = pro; stack< char > signs; stack< int > states; write.open( "output.out", ios::out | ios::app ); if( ! write ) { cout<<" Output File Opening Error!"<<endl; exit( 0 ); } write<<"The analysis process is as follows:"<<endl<<endl; write<<'\t'<<'\t'<<"States"<<"\t\t"<<"Signs"<<"\t\t"<<"Input"<<"\t\t"<<"Production"<<endl;// the first line signs.push( '#' ); states.push( 0 ); now = states.get_top(); while( current_t->act != 'a' ) { str = states.int_traverse(); write<<'\t'<<( count ++ )<<'\t'<<str<<'\t'; if( str.length() < 8 ) write<<'\t'; str = signs.traverse(); write<<str<<'\t'; if( str.length() <= 8 ) write<<'\t'; str = next; write<<str<<'\t'; if( str.length() < 10 ) write<<'\t'; nt_pos = in_nt( signs.get_top() ); if( nt_pos != -1 )// deal with go_to with more priority { current_nt= go_to[ now ][ nt_pos ]; if( current_nt != -1 )// no state defined in 'goto' { states.push( current_nt ); now = states.get_top(); write<<endl; continue; } } t_pos = in_t( *next ); if( t_pos == -1 ) return -1;// *next is an illegal character current_t = &action[ now ][ t_pos ]; if( current_t->act == 0 ) return -1;//no action defined in 'action' if( current_t->act == 'a' ) continue;//accept state met if( current_t->act == 's' )// step forward { signs.push( *next ); states.push( current_t->next ); write<<endl; next ++;