Main Page   Class Hierarchy   Compound List   File List   Compound Members   File Members  

/magnus/back_end/general/include/WordParser.h

Go to the documentation of this file.
00001 /*
00002  *   $Id: WordParser.h,v 1.6 2000/02/10 00:14:45 bormotov Exp $
00003  */
00004 
00005 // Copyright (C) 1994 The New York Group Theory Cooperative
00006 // See magnus/doc/COPYRIGHT for the full notice.
00007 
00008 // Contents: Definition of parser for Words, and private helper classes.
00009 //
00010 // Principal Author: Roger Needham
00011 //
00012 // Status: in progress
00013 //
00014 // Revision History:
00015 //
00016 // * 4/20/95 rn altered
00017 //     void parseError(const char*)
00018 //   to store the error message in the form: <n> <mesg>
00019 //   where n is the index in the input of the problem, and mesg
00020 //   is the description.
00021 //
00022 // * 7/96 Dmitry B. made porting to gcc 2.7.2.
00023 //
00024 // * 05/98 Alexei M. added void isIvertibleName( char* ) and changed 
00025 //   bool invertName( char* ) functions
00026 //
00027 
00028 #ifndef _WORD_PARSER_H_
00029 #define _WORD_PARSER_H_
00030 
00031 #include "Word.h"
00032 #include "Chars.h"
00033 #include "Vector.h"
00034 
00035 
00036 // The grammar for Word:
00037 //
00038 // Literals are delimited by ''.
00039 // The symbols ., *, +, -, |, ?, [, ], (, and ) are part of regular expressions
00040 // unless quoted.
00041 //
00042 // <whitespace>     ::= ' ' | '\t' | '\n' | '#'.*'\n'
00043 // <index>          ::= 0 | [1-9]+[0-9]*
00044 // <integer>        ::= <index> | -<index>
00045 // <generator>      ::= [a-zA-Z]+<index>?
00046 // <atom>           ::= '1' | <generator> | '('<word>')' |
00047 //                      '['<word>','<word>(','<word>)*']'
00048 // <term>           ::= <atom>('^'<atom>)* | <term>'^'<integer>
00049 // <word>           ::= <term>('*'<term>)* | <term>(<whitespace><term>)*
00050 //
00051 // - whitespace may occur anywhere except within lexemes.
00052 // 
00053 // Semantic conventions:
00054 //
00055 // - x^y is y^-1 x y.
00056 // - ^ is left-associative, so a^t^2 is (a^t)^2.
00057 // - [x,y] is x^-1 y^-1 x y.
00058 // - [x1, x2, ..., xn] is left-normed: [[x1,x2], x3, ..., xn].
00059 // - Given the print name of a generator, the print name of its inverse
00060 //   has each character changed to the opposite case.
00061 //   Thus aB2^-1 is the same as Ab2.
00062 
00063 
00064 
00065 #define NAME_SIZE      100
00066 #define INPUT_BUF_SIZE 1024
00067 #define MAX_WORD_LENGTH 2000000000
00068 
00069 typedef enum
00070 {
00071    LANGLE, RANGLE, LPAREN, RPAREN, LSQUARE, RSQUARE, STAR, CARET, COMMA, BAR,
00072    COLON, SEMICOLON, EQUALS, GENERATOR, INT, EOS, BAD, INIT, LSET, RSET,
00073    ARROW, DOT
00074 }  TokenType;
00075 
00076 
00077 class ParseNode;  // defined below
00078 
00079 class WordParser {
00080 
00081 public:
00082 
00083   WordParser(istream &str) : istr(str) {
00084          tokenBufIndex = 0;
00085          curToken = INIT;
00086   }
00087 
00088   // Destructor supplied by compiler.
00089 
00090   void popToken( ) { getToken(); }  // To read over unwanted tokens.
00091 
00092   // If there is no parse error, the following return the parsed object,
00093   // and do not change the Chars argument.
00094   // Otherwise an error message is put in the Chars argument, and a
00095   // default object is returned.
00096   //
00097   // None read more from the stream than needed, and all leave the
00098   // internal state ready for subsequent calls.
00099 
00100   Word parseWord( const VectorOf<Chars>&, Chars& );
00101   // Read a word in the given generator names, and freely reduce it.
00102 
00103   Word parseWordVerbatim( const VectorOf<Chars>&, Chars& );
00104   // Read a word in the given generator names, without freely reducing it.
00105 
00106 
00107 protected:
00108 
00109   int          tokenInt;                 // Value of INT token, or ord
00110                                          //  of GENERATOR token
00111   int          tokenBufIndex;            // Index into tokenBuf
00112   char         tokenName[NAME_SIZE+1];   // Print name of GENERATOR token
00113   char         tokenBuf[INPUT_BUF_SIZE]; // Input buffer
00114   TokenType    curToken;                 // The current token
00115 
00116   VectorOf<Chars>  genNames;  // Put these where getToken can find them.
00117 
00118   Chars          parseErrorMessage;
00119 
00120   istream&       istr;       // The caller owns istr.
00121 
00122 
00123   // Utility functions
00124 
00125   char peekCh( );
00126   char getCh( );
00127   virtual void getToken( );
00128   void parseError(const char*);
00129   Bool atStartOfWord( );
00130   void invertName(char*);
00131 
00132   bool isInvertibleName( char* ); 
00133   // @am according to the new standard
00134   // names of gerators consisting of several letters 
00135   // can't be inverted by switching the letters cases.
00136 
00137   ParseNode *parseExpression( );
00138   ParseNode *parseTerm( );
00139   ParseNode *parseAtom( );
00140 
00141 #ifdef DEBUG
00142   //friend int main( );
00143 #endif
00144 
00145 };
00146 
00147 
00148 
00149 // Helper classes for recursive descent parsing of Words:
00150 
00151 
00152 typedef enum {
00153   ILLEGAL_NODE, COMMUTATOR_NODE, INT_NODE, CONCAT_NODE,
00154   IDENT_NODE, POWER_OR_CONJUGATE_NODE
00155 } ParseNodeType;
00156 
00157 
00158 typedef enum {
00159   PT_OK = 0, PT_TOO_LONG
00160 } ParseTypeState;
00161 
00162 typedef int ParseData;
00163 
00164 //typedef int ParseType;  // eval methods return ptr to this
00165 
00166 class ParseType {
00167 public:
00168   ParseType( ) : len(0), data(0), status(PT_OK) { }
00169   ParseType( int gen );
00170 
00171   Word makeWord( ) const;
00172   ParseType invertWord( ) const;
00173   ParseType makeCopies( unsigned int numOfCopies ) const;
00174   static ParseType join( const ParseType& x, const ParseType& y );
00175 
00176   void destroy( ) { delete data; data = 0; status = PT_OK; }
00177 
00178   ParseTypeState state( ) const { return status; }
00179   Chars errorMessage( ) const;
00180 
00181 private:
00182 
00183   ParseType( ParseTypeState s, ParseData *ptr, int plen ) 
00184     : len(plen), data(ptr), status(s) { }
00185 
00186   int len;
00187   ParseData *data;
00188   ParseTypeState status;
00189 };
00190 
00191 
00192 class  ParseNode        // Base for Parsing Nodes
00193 {
00194 public:
00195   ParseNode( ) { }
00196   virtual ~ParseNode( ) { }
00197   virtual ParseType eval( ) = 0; // { return 0; }
00198   virtual ParseNodeType whatAmI( ) = 0;
00199 
00200   // Utility functions
00201   //  int getLength( ParseType* );
00202   //  ParseType *invertWord( ParseType* );
00203   //  ParseType *makeCopies( int, ParseType* );
00204   //  ParseType *join( ParseType*, ParseType* );
00205 };
00206 
00207 
00208 class Int : public ParseNode
00209 {       
00210 public:
00211   Int( int n ) { number = n; }
00212   ParseType eval( ) { return ParseType(0); }
00213   ParseNodeType  whatAmI( ) { return INT_NODE; }
00214 
00215   int intEval( ) { return number; }
00216 
00217 private:
00218   int number;
00219 };
00220 
00221 
00222 class Ident : public ParseNode
00223 {
00224 public:
00225   Ident( ParseType val ) {
00226          gen = val;
00227   }
00228   ~Ident( ) { }
00229 
00230   ParseNodeType  whatAmI( ) { return IDENT_NODE; }
00231 
00232   ParseType eval( ) {
00233     return ParseType( gen );
00234   }
00235 
00236 private:
00237   ParseType  gen;
00238 };
00239 
00240 
00241 class BinOp : public ParseNode
00242 {  
00243 public:
00244 
00245   BinOp( ParseNode *left, ParseNode *right ) : arg1(left), arg2(right) { }
00246 
00247   ~BinOp( ) {
00248     delete arg1;
00249     delete arg2;
00250     result1.destroy();
00251     result2.destroy(); 
00252   }
00253 
00254 protected:
00255   ParseNode *arg1, *arg2;
00256   ParseType result1, result2;
00257 };
00258 
00259 
00260 class Concat : public BinOp
00261 {
00262 public:
00263 
00264   Concat( ParseNode *left, ParseNode *right ) : BinOp( left, right ) { }
00265   ParseType eval( );
00266   ParseNodeType whatAmI( ) { return CONCAT_NODE; }
00267 };
00268 
00269 
00270 class  PowerOrConjugate : public BinOp
00271 {
00272 public:
00273 
00274   PowerOrConjugate( ParseNode *left, ParseNode *right) : BinOp( left, right) {}
00275   ParseType eval( );
00276   ParseNodeType whatAmI( ) { return POWER_OR_CONJUGATE_NODE; }
00277 };
00278 
00279 
00280 class  Commutator : public BinOp
00281 {
00282 public:
00283 
00284   Commutator( ParseNode *left, ParseNode *right ) : BinOp( left, right ) { }
00285   ParseType eval( );
00286   ParseNodeType whatAmI( ) { return COMMUTATOR_NODE; }
00287 };
00288 
00289 #endif

Generated at Tue Jun 19 09:49:35 2001 for Magnus Classes by doxygen1.2.6 written by Dimitri van Heesch, © 1997-2001