| /**CFile**************************************************************** |
| |
| FileName [mioParse.c] |
| |
| PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] |
| |
| Synopsis [Parsing Boolean expressions.] |
| |
| Author [MVSIS Group] |
| |
| Affiliation [UC Berkeley] |
| |
| Date [Ver. 1.0. Started - September 8, 2003.] |
| |
| Revision [$Id: mioParse.c,v 1.4 2004/06/28 14:20:25 alanmi Exp $] |
| |
| ***********************************************************************/ |
| |
| #include "mioInt.h" |
| #include "exp.h" |
| |
| ABC_NAMESPACE_IMPL_START |
| |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// DECLARATIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| // the list of operation symbols to be used in expressions |
| #define MIO_EQN_SYM_OPEN '(' // opening parenthesis |
| #define MIO_EQN_SYM_CLOSE ')' // closing parenthesis |
| #define MIO_EQN_SYM_CONST0 '0' // constant 0 |
| #define MIO_EQN_SYM_CONST1 '1' // constant 1 |
| #define MIO_EQN_SYM_NEG '!' // negation before the variable |
| #define MIO_EQN_SYM_NEGAFT '\'' // negation after the variable |
| #define MIO_EQN_SYM_AND '*' // logic AND |
| #define MIO_EQN_SYM_AND2 '&' // logic AND |
| #define MIO_EQN_SYM_XOR '^' // logic XOR |
| #define MIO_EQN_SYM_OR '+' // logic OR |
| #define MIO_EQN_SYM_OR2 '|' // logic OR |
| |
| // the list of opcodes (also specifying operation precedence) |
| #define MIO_EQN_OPER_NEG 10 // negation |
| #define MIO_EQN_OPER_AND 9 // logic AND |
| #define MIO_EQN_OPER_XOR 8 // logic XOR |
| #define MIO_EQN_OPER_OR 7 // logic OR |
| #define MIO_EQN_OPER_MARK 1 // OpStack token standing for an opening parenthesis |
| |
| // these are values of the internal Flag |
| #define MIO_EQN_FLAG_START 1 // after the opening parenthesis |
| #define MIO_EQN_FLAG_VAR 2 // after operation is received |
| #define MIO_EQN_FLAG_OPER 3 // after operation symbol is received |
| #define MIO_EQN_FLAG_ERROR 4 // when error is detected |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// FUNCTION DEFINITIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| /**Function************************************************************* |
| |
| Synopsis [Performs the operation on the top entries in the stack.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Vec_Int_t * Mio_ParseFormulaOper( int * pMan, int nVars, Vec_Ptr_t * pStackFn, int Oper ) |
| { |
| Vec_Int_t * gArg1, * gArg2, * gFunc; |
| // perform the given operation |
| gArg2 = (Vec_Int_t *)Vec_PtrPop( pStackFn ); |
| gArg1 = (Vec_Int_t *)Vec_PtrPop( pStackFn ); |
| if ( Oper == MIO_EQN_OPER_AND ) |
| gFunc = Exp_And( pMan, nVars, gArg1, gArg2, 0, 0 ); |
| else if ( Oper == MIO_EQN_OPER_OR ) |
| gFunc = Exp_Or( pMan, nVars, gArg1, gArg2 ); |
| else if ( Oper == MIO_EQN_OPER_XOR ) |
| gFunc = Exp_Xor( pMan, nVars, gArg1, gArg2 ); |
| else |
| return NULL; |
| // Cudd_Ref( gFunc ); |
| // Cudd_RecursiveDeref( dd, gArg1 ); |
| // Cudd_RecursiveDeref( dd, gArg2 ); |
| Vec_IntFree( gArg1 ); |
| Vec_IntFree( gArg2 ); |
| Vec_PtrPush( pStackFn, gFunc ); |
| return gFunc; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Derives the AIG corresponding to the equation.] |
| |
| Description [Takes the stream to output messages, the formula, the vector |
| of variable names and the AIG manager.] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Vec_Int_t * Mio_ParseFormula( char * pFormInit, char ** ppVarNames, int nVars ) |
| { |
| char * pFormula; |
| int Man = nVars, * pMan = &Man; |
| Vec_Ptr_t * pStackFn; |
| Vec_Int_t * pStackOp; |
| Vec_Int_t * gFunc; |
| char * pTemp, * pName; |
| int nParans, fFound, Flag; |
| int Oper, Oper1, Oper2; |
| int i, v; |
| |
| // make sure that the number of opening and closing parentheses is the same |
| nParans = 0; |
| for ( pTemp = pFormInit; *pTemp; pTemp++ ) |
| if ( *pTemp == '(' ) |
| nParans++; |
| else if ( *pTemp == ')' ) |
| nParans--; |
| if ( nParans != 0 ) |
| { |
| fprintf( stdout, "Mio_ParseFormula(): Different number of opening and closing parentheses ().\n" ); |
| return NULL; |
| } |
| |
| // copy the formula |
| pFormula = ABC_ALLOC( char, strlen(pFormInit) + 3 ); |
| sprintf( pFormula, "(%s)", pFormInit ); |
| |
| // start the stacks |
| pStackFn = Vec_PtrAlloc( 100 ); |
| pStackOp = Vec_IntAlloc( 100 ); |
| |
| Flag = MIO_EQN_FLAG_START; |
| for ( pTemp = pFormula; *pTemp; pTemp++ ) |
| { |
| switch ( *pTemp ) |
| { |
| // skip all spaces, tabs, and end-of-lines |
| case ' ': |
| case '\t': |
| case '\r': |
| case '\n': |
| continue; |
| case MIO_EQN_SYM_CONST0: |
| Vec_PtrPush( pStackFn, Exp_Const0() ); // Cudd_Ref( b0 ); |
| if ( Flag == MIO_EQN_FLAG_VAR ) |
| { |
| fprintf( stdout, "Mio_ParseFormula(): No operation symbol before constant 0.\n" ); |
| Flag = MIO_EQN_FLAG_ERROR; |
| break; |
| } |
| Flag = MIO_EQN_FLAG_VAR; |
| break; |
| case MIO_EQN_SYM_CONST1: |
| Vec_PtrPush( pStackFn, Exp_Const1() ); // Cudd_Ref( b1 ); |
| if ( Flag == MIO_EQN_FLAG_VAR ) |
| { |
| fprintf( stdout, "Mio_ParseFormula(): No operation symbol before constant 1.\n" ); |
| Flag = MIO_EQN_FLAG_ERROR; |
| break; |
| } |
| Flag = MIO_EQN_FLAG_VAR; |
| break; |
| case MIO_EQN_SYM_NEG: |
| if ( Flag == MIO_EQN_FLAG_VAR ) |
| {// if NEGBEF follows a variable, AND is assumed |
| Vec_IntPush( pStackOp, MIO_EQN_OPER_AND ); |
| Flag = MIO_EQN_FLAG_OPER; |
| } |
| Vec_IntPush( pStackOp, MIO_EQN_OPER_NEG ); |
| break; |
| case MIO_EQN_SYM_NEGAFT: |
| if ( Flag != MIO_EQN_FLAG_VAR ) |
| {// if there is no variable before NEGAFT, it is an error |
| fprintf( stdout, "Mio_ParseFormula(): No variable is specified before the negation suffix.\n" ); |
| Flag = MIO_EQN_FLAG_ERROR; |
| break; |
| } |
| else // if ( Flag == PARSE_FLAG_VAR ) |
| Vec_PtrPush( pStackFn, Exp_Not( (Vec_Int_t *)Vec_PtrPop(pStackFn) ) ); |
| break; |
| case MIO_EQN_SYM_AND: |
| case MIO_EQN_SYM_AND2: |
| case MIO_EQN_SYM_OR: |
| case MIO_EQN_SYM_OR2: |
| case MIO_EQN_SYM_XOR: |
| if ( Flag != MIO_EQN_FLAG_VAR ) |
| { |
| fprintf( stdout, "Mio_ParseFormula(): There is no variable before AND, EXOR, or OR.\n" ); |
| Flag = MIO_EQN_FLAG_ERROR; |
| break; |
| } |
| if ( *pTemp == MIO_EQN_SYM_AND || *pTemp == MIO_EQN_SYM_AND2 ) |
| Vec_IntPush( pStackOp, MIO_EQN_OPER_AND ); |
| else if ( *pTemp == MIO_EQN_SYM_OR || *pTemp == MIO_EQN_SYM_OR2 ) |
| Vec_IntPush( pStackOp, MIO_EQN_OPER_OR ); |
| else //if ( *pTemp == MIO_EQN_SYM_XOR ) |
| Vec_IntPush( pStackOp, MIO_EQN_OPER_XOR ); |
| Flag = MIO_EQN_FLAG_OPER; |
| break; |
| case MIO_EQN_SYM_OPEN: |
| if ( Flag == MIO_EQN_FLAG_VAR ) |
| { |
| Vec_IntPush( pStackOp, MIO_EQN_OPER_AND ); |
| // fprintf( stdout, "Mio_ParseFormula(): An opening parenthesis follows a var without operation sign.\n" ); |
| // Flag = MIO_EQN_FLAG_ERROR; |
| // break; |
| } |
| Vec_IntPush( pStackOp, MIO_EQN_OPER_MARK ); |
| // after an opening bracket, it feels like starting over again |
| Flag = MIO_EQN_FLAG_START; |
| break; |
| case MIO_EQN_SYM_CLOSE: |
| if ( Vec_IntSize( pStackOp ) != 0 ) |
| { |
| while ( 1 ) |
| { |
| if ( Vec_IntSize( pStackOp ) == 0 ) |
| { |
| fprintf( stdout, "Mio_ParseFormula(): There is no opening parenthesis\n" ); |
| Flag = MIO_EQN_FLAG_ERROR; |
| break; |
| } |
| Oper = Vec_IntPop( pStackOp ); |
| if ( Oper == MIO_EQN_OPER_MARK ) |
| break; |
| |
| // perform the given operation |
| if ( Mio_ParseFormulaOper( pMan, nVars, pStackFn, Oper ) == NULL ) |
| { |
| fprintf( stdout, "Mio_ParseFormula(): Unknown operation\n" ); |
| ABC_FREE( pFormula ); |
| Vec_PtrFreeP( &pStackFn ); |
| Vec_IntFreeP( &pStackOp ); |
| return NULL; |
| } |
| } |
| } |
| else |
| { |
| fprintf( stdout, "Mio_ParseFormula(): There is no opening parenthesis\n" ); |
| Flag = MIO_EQN_FLAG_ERROR; |
| break; |
| } |
| if ( Flag != MIO_EQN_FLAG_ERROR ) |
| Flag = MIO_EQN_FLAG_VAR; |
| break; |
| |
| |
| default: |
| // scan the next name |
| for ( i = 0; pTemp[i] && |
| pTemp[i] != ' ' && pTemp[i] != '\t' && pTemp[i] != '\r' && pTemp[i] != '\n' && |
| pTemp[i] != MIO_EQN_SYM_AND && pTemp[i] != MIO_EQN_SYM_AND2 && pTemp[i] != MIO_EQN_SYM_OR && pTemp[i] != MIO_EQN_SYM_OR2 && |
| pTemp[i] != MIO_EQN_SYM_XOR && pTemp[i] != MIO_EQN_SYM_NEGAFT && pTemp[i] != MIO_EQN_SYM_CLOSE; |
| i++ ) |
| { |
| if ( pTemp[i] == MIO_EQN_SYM_NEG || pTemp[i] == MIO_EQN_SYM_OPEN ) |
| { |
| fprintf( stdout, "Mio_ParseFormula(): The negation sign or an opening parenthesis inside the variable name.\n" ); |
| Flag = MIO_EQN_FLAG_ERROR; |
| break; |
| } |
| } |
| // variable name is found |
| fFound = 0; |
| // Vec_PtrForEachEntry( char *, vVarNames, pName, v ) |
| for ( v = 0; v < nVars; v++ ) |
| { |
| pName = ppVarNames[v]; |
| if ( strncmp(pTemp, pName, i) == 0 && strlen(pName) == (unsigned)i ) |
| { |
| pTemp += i-1; |
| fFound = 1; |
| break; |
| } |
| } |
| if ( !fFound ) |
| { |
| fprintf( stdout, "Mio_ParseFormula(): The parser cannot find var \"%s\" in the input var list.\n", pTemp ); |
| Flag = MIO_EQN_FLAG_ERROR; |
| break; |
| } |
| /* |
| if ( Flag == MIO_EQN_FLAG_VAR ) |
| { |
| fprintf( stdout, "Mio_ParseFormula(): The variable name \"%s\" follows another var without operation sign.\n", pTemp ); |
| Flag = MIO_EQN_FLAG_ERROR; |
| break; |
| } |
| */ |
| if ( Flag == MIO_EQN_FLAG_VAR ) |
| Vec_IntPush( pStackOp, MIO_EQN_OPER_AND ); |
| |
| Vec_PtrPush( pStackFn, Exp_Var(v) ); // Cudd_Ref( pbVars[v] ); |
| Flag = MIO_EQN_FLAG_VAR; |
| break; |
| } |
| |
| if ( Flag == MIO_EQN_FLAG_ERROR ) |
| break; // error exit |
| else if ( Flag == MIO_EQN_FLAG_START ) |
| continue; // go on parsing |
| else if ( Flag == MIO_EQN_FLAG_VAR ) |
| while ( 1 ) |
| { // check if there are negations in the OpStack |
| if ( Vec_IntSize( pStackOp ) == 0 ) |
| break; |
| Oper = Vec_IntPop( pStackOp ); |
| if ( Oper != MIO_EQN_OPER_NEG ) |
| { |
| Vec_IntPush( pStackOp, Oper ); |
| break; |
| } |
| else |
| { |
| Vec_PtrPush( pStackFn, Exp_Not((Vec_Int_t *)Vec_PtrPop(pStackFn)) ); |
| } |
| } |
| else // if ( Flag == MIO_EQN_FLAG_OPER ) |
| while ( 1 ) |
| { // execute all the operations in the OpStack |
| // with precedence higher or equal than the last one |
| Oper1 = Vec_IntPop( pStackOp ); // the last operation |
| if ( Vec_IntSize( pStackOp ) == 0 ) |
| { // if it is the only operation, push it back |
| Vec_IntPush( pStackOp, Oper1 ); |
| break; |
| } |
| Oper2 = Vec_IntPop( pStackOp ); // the operation before the last one |
| if ( Oper2 >= Oper1 ) |
| { // if Oper2 precedence is higher or equal, execute it |
| if ( Mio_ParseFormulaOper( pMan, nVars, pStackFn, Oper2 ) == NULL ) |
| { |
| fprintf( stdout, "Mio_ParseFormula(): Unknown operation\n" ); |
| ABC_FREE( pFormula ); |
| Vec_PtrFreeP( &pStackFn ); |
| Vec_IntFreeP( &pStackOp ); |
| return NULL; |
| } |
| Vec_IntPush( pStackOp, Oper1 ); // push the last operation back |
| } |
| else |
| { // if Oper2 precedence is lower, push them back and done |
| Vec_IntPush( pStackOp, Oper2 ); |
| Vec_IntPush( pStackOp, Oper1 ); |
| break; |
| } |
| } |
| } |
| |
| if ( Flag != MIO_EQN_FLAG_ERROR ) |
| { |
| if ( Vec_PtrSize(pStackFn) != 0 ) |
| { |
| gFunc = (Vec_Int_t *)Vec_PtrPop(pStackFn); |
| if ( Vec_PtrSize(pStackFn) == 0 ) |
| if ( Vec_IntSize( pStackOp ) == 0 ) |
| { |
| // Cudd_Deref( gFunc ); |
| ABC_FREE( pFormula ); |
| Vec_PtrFreeP( &pStackFn ); |
| Vec_IntFreeP( &pStackOp ); |
| return Exp_Reverse(gFunc); |
| } |
| else |
| fprintf( stdout, "Mio_ParseFormula(): Something is left in the operation stack\n" ); |
| else |
| fprintf( stdout, "Mio_ParseFormula(): Something is left in the function stack\n" ); |
| } |
| else |
| fprintf( stdout, "Mio_ParseFormula(): The input string is empty\n" ); |
| } |
| ABC_FREE( pFormula ); |
| Vec_PtrFreeP( &pStackFn ); |
| Vec_IntFreeP( &pStackOp ); |
| return NULL; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Derives the TT corresponding to the equation.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Vec_Wrd_t * Mio_ParseFormulaTruth( char * pFormInit, char ** ppVarNames, int nVars ) |
| { |
| Vec_Int_t * vExpr; |
| Vec_Wrd_t * vTruth; |
| // derive expression |
| vExpr = Mio_ParseFormula( pFormInit, ppVarNames, nVars ); |
| if ( vExpr == NULL ) |
| return NULL; |
| // convert it into a truth table |
| vTruth = Vec_WrdStart( Abc_Truth6WordNum(nVars) ); |
| Exp_Truth( nVars, vExpr, Vec_WrdArray(vTruth) ); |
| Vec_IntFree( vExpr ); |
| return vTruth; |
| } |
| void Mio_ParseFormulaTruthTest( char * pFormInit, char ** ppVarNames, int nVars ) |
| { |
| Vec_Wrd_t * vTruth; |
| vTruth = Mio_ParseFormulaTruth( pFormInit, ppVarNames, nVars ); |
| // Kit_DsdPrintFromTruth( (unsigned *)Vec_WrdArray(vTruth), nVars ); printf( "\n" ); |
| Vec_WrdFree( vTruth ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Checks if the gate's formula essentially depends on all variables.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Mio_ParseCheckName( Mio_Gate_t * pGate, char ** ppStr ) |
| { |
| Mio_Pin_t * pPin; |
| int i, iBest = -1; |
| // find the longest pin name that matches substring |
| char * pNameBest = NULL; |
| for ( pPin = Mio_GateReadPins(pGate), i = 0; pPin; pPin = Mio_PinReadNext(pPin), i++ ) |
| if ( !strncmp( *ppStr, Mio_PinReadName(pPin), strlen(Mio_PinReadName(pPin)) ) ) |
| if ( pNameBest == NULL || strlen(pNameBest) < strlen(Mio_PinReadName(pPin)) ) |
| pNameBest = Mio_PinReadName(pPin), iBest = i; |
| // if pin is not found, return -1 |
| if ( pNameBest ) |
| *ppStr += strlen(pNameBest) - 1; |
| return iBest; |
| } |
| int Mio_ParseCheckFormula( Mio_Gate_t * pGate, char * pForm ) |
| { |
| Mio_Pin_t * pPin; |
| char * pStr; |
| int i, iPin, fVisit[32] = {0}; |
| if ( Mio_GateReadPins(pGate) == NULL || !strcmp(Mio_PinReadName(Mio_GateReadPins(pGate)), "*") ) |
| return 1; |
| /* |
| // find the equality sign |
| pForm = strstr( pForm, "=" ); |
| if ( pForm == NULL ) |
| { |
| printf( "Skipping gate \"%s\" because formula \"%s\" has not equality sign (=).\n", pGate->pName, pForm ); |
| return 0; |
| } |
| */ |
| //printf( "Checking gate %s\n", pGate->pName ); |
| |
| for ( pStr = pForm; *pStr; pStr++ ) |
| { |
| if ( *pStr == ' ' || |
| *pStr == MIO_EQN_SYM_OPEN || |
| *pStr == MIO_EQN_SYM_CLOSE || |
| *pStr == MIO_EQN_SYM_CONST0 || |
| *pStr == MIO_EQN_SYM_CONST1 || |
| *pStr == MIO_EQN_SYM_NEG || |
| *pStr == MIO_EQN_SYM_NEGAFT || |
| *pStr == MIO_EQN_SYM_AND || |
| *pStr == MIO_EQN_SYM_AND2 || |
| *pStr == MIO_EQN_SYM_XOR || |
| *pStr == MIO_EQN_SYM_OR || |
| *pStr == MIO_EQN_SYM_OR2 |
| ) |
| continue; |
| // return the number of the pin which has this name |
| iPin = Mio_ParseCheckName( pGate, &pStr ); |
| if ( iPin == -1 ) |
| { |
| printf( "Skipping gate \"%s\" because substring \"%s\" does not match with a pin name.\n", pGate->pName, pStr ); |
| return 0; |
| } |
| assert( iPin < 32 ); |
| fVisit[iPin] = 1; |
| } |
| // check that all pins are used |
| for ( pPin = Mio_GateReadPins(pGate), i = 0; pPin; pPin = Mio_PinReadNext(pPin), i++ ) |
| if ( fVisit[i] == 0 ) |
| { |
| // printf( "Skipping gate \"%s\" because pin \"%s\" does not appear in the formula \"%s\".\n", pGate->pName, Mio_PinReadName(pPin), pForm ); |
| return 0; |
| } |
| return 1; |
| } |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// END OF FILE /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| |
| ABC_NAMESPACE_IMPL_END |
| |
