mioParse.c File Reference

#include "mioInt.h"
#include "exp.h"

Go to the source code of this file.

Macros
#define	MIO_EQN_SYM_OPEN   '('
	DECLARATIONS ///. More...
#define	MIO_EQN_SYM_CLOSE   ')'
#define	MIO_EQN_SYM_CONST0   '0'
#define	MIO_EQN_SYM_CONST1   '1'
#define	MIO_EQN_SYM_NEG   '!'
#define	MIO_EQN_SYM_NEGAFT   '\''
#define	MIO_EQN_SYM_AND   '*'
#define	MIO_EQN_SYM_AND2   '&'
#define	MIO_EQN_SYM_XOR   '^'
#define	MIO_EQN_SYM_OR   '+'
#define	MIO_EQN_SYM_OR2   '|'
#define	MIO_EQN_OPER_NEG   10
#define	MIO_EQN_OPER_AND   9
#define	MIO_EQN_OPER_XOR   8
#define	MIO_EQN_OPER_OR   7
#define	MIO_EQN_OPER_MARK   1
#define	MIO_EQN_FLAG_START   1
#define	MIO_EQN_FLAG_VAR   2
#define	MIO_EQN_FLAG_OPER   3
#define	MIO_EQN_FLAG_ERROR   4

Functions
Vec_Int_t *	Mio_ParseFormulaOper (int *pMan, int nVars, Vec_Ptr_t *pStackFn, int Oper)
	FUNCTION DEFINITIONS ///. More...
Vec_Int_t *	Mio_ParseFormula (char *pFormInit, char **ppVarNames, int nVars)
Vec_Wrd_t *	Mio_ParseFormulaTruth (char *pFormInit, char **ppVarNames, int nVars)
void	Mio_ParseFormulaTruthTest (char *pFormInit, char **ppVarNames, int nVars)
int	Mio_ParseCheckName (Mio_Gate_t *pGate, char **ppStr)
int	Mio_ParseCheckFormula (Mio_Gate_t *pGate, char *pForm)

Macro Definition Documentation

#define MIO_EQN_FLAG_ERROR   4

Definition at line 53 of file mioParse.c.

#define MIO_EQN_FLAG_OPER   3

Definition at line 52 of file mioParse.c.

#define MIO_EQN_FLAG_START   1

Definition at line 50 of file mioParse.c.

#define MIO_EQN_FLAG_VAR   2

Definition at line 51 of file mioParse.c.

#define MIO_EQN_OPER_AND   9

Definition at line 44 of file mioParse.c.

#define MIO_EQN_OPER_MARK   1

Definition at line 47 of file mioParse.c.

#define MIO_EQN_OPER_NEG   10

Definition at line 43 of file mioParse.c.

#define MIO_EQN_OPER_OR   7

Definition at line 46 of file mioParse.c.

#define MIO_EQN_OPER_XOR   8

Definition at line 45 of file mioParse.c.

#define MIO_EQN_SYM_AND   '*'

Definition at line 36 of file mioParse.c.

#define MIO_EQN_SYM_AND2   '&'

Definition at line 37 of file mioParse.c.

#define MIO_EQN_SYM_CLOSE   ')'

Definition at line 31 of file mioParse.c.

#define MIO_EQN_SYM_CONST0   '0'

Definition at line 32 of file mioParse.c.

#define MIO_EQN_SYM_CONST1   '1'

Definition at line 33 of file mioParse.c.

#define MIO_EQN_SYM_NEG   '!'

Definition at line 34 of file mioParse.c.

#define MIO_EQN_SYM_NEGAFT   '\''

Definition at line 35 of file mioParse.c.

#define MIO_EQN_SYM_OPEN   '('

DECLARATIONS ///.

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

]

Definition at line 30 of file mioParse.c.

#define MIO_EQN_SYM_OR   '+'

Definition at line 39 of file mioParse.c.

#define MIO_EQN_SYM_OR2   '|'

Definition at line 40 of file mioParse.c.

#define MIO_EQN_SYM_XOR   '^'

Definition at line 38 of file mioParse.c.

Function Documentation

int Mio_ParseCheckFormula	(	Mio_Gate_t *	pGate,
		char *	pForm
	)

Definition at line 444 of file mioParse.c.

{
    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;
}

int Mio_ParseCheckName	(	Mio_Gate_t *	pGate,
		char **	ppStr
	)

Function*************************************************************

Synopsis [Checks if the gate's formula essentially depends on all variables.]

Description []

SideEffects []

SeeAlso []

Definition at line 429 of file mioParse.c.

{
    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;
}

Vec_Int_t* Mio_ParseFormula	(	char *	pFormInit,
		char **	ppVarNames,
		int	nVars
	)

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 []

Definition at line 105 of file mioParse.c.

{
    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 parantheses 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 parantheses ().\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 paranthesis 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 paranthesis\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 paranthesis\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 paranthesis 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;
}

Vec_Int_t* Mio_ParseFormulaOper	(	int *	pMan,
		int	nVars,
		Vec_Ptr_t *	pStackFn,
		int	Oper
	)

FUNCTION DEFINITIONS ///.

Function*************************************************************

Synopsis [Performs the operation on the top entries in the stack.]

Description []

SideEffects []

SeeAlso []

Definition at line 70 of file mioParse.c.

{
    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;
}

Vec_Wrd_t* Mio_ParseFormulaTruth	(	char *	pFormInit,
		char **	ppVarNames,
		int	nVars
	)

Function*************************************************************

Synopsis [Derives the TT corresponding to the equation.]

Description []

SideEffects []

SeeAlso []

Definition at line 396 of file mioParse.c.

{
    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
	)

Definition at line 410 of file mioParse.c.

{
    Vec_Wrd_t * vTruth;
    vTruth = Mio_ParseFormulaTruth( pFormInit, ppVarNames, nVars );
//    Kit_DsdPrintFromTruth( (unsigned *)Vec_WrdArray(vTruth), nVars ); printf( "\n" );
    Vec_WrdFree( vTruth );
}