1 /**CFile****************************************************************
2
3 FileName [mioParse.c]
4
5 PackageName [MVSIS 1.3: Multi-valued logic synthesis system.]
6
7 Synopsis [Parsing Boolean expressions.]
8
9 Author [MVSIS Group]
10
11 Affiliation [UC Berkeley]
12
13 Date [Ver. 1.0. Started - September 8, 2003.]
14
15 Revision [$Id: mioParse.c,v 1.4 2004/06/28 14:20:25 alanmi Exp $]
16
17 ***********************************************************************/
18
19 #include "mioInt.h"
20 #include "exp.h"
21
22 ABC_NAMESPACE_IMPL_START
23
24
25 ////////////////////////////////////////////////////////////////////////
26 /// DECLARATIONS ///
27 ////////////////////////////////////////////////////////////////////////
28
29 // the list of operation symbols to be used in expressions
30 #define MIO_EQN_SYM_OPEN '(' // opening parenthesis
31 #define MIO_EQN_SYM_CLOSE ')' // closing parenthesis
32 #define MIO_EQN_SYM_CONST0 '0' // constant 0
33 #define MIO_EQN_SYM_CONST1 '1' // constant 1
34 #define MIO_EQN_SYM_NEG '!' // negation before the variable
35 #define MIO_EQN_SYM_NEGAFT '\'' // negation after the variable
36 #define MIO_EQN_SYM_AND '*' // logic AND
37 #define MIO_EQN_SYM_AND2 '&' // logic AND
38 #define MIO_EQN_SYM_XOR '^' // logic XOR
39 #define MIO_EQN_SYM_OR '+' // logic OR
40 #define MIO_EQN_SYM_OR2 '|' // logic OR
41
42 // the list of opcodes (also specifying operation precedence)
43 #define MIO_EQN_OPER_NEG 10 // negation
44 #define MIO_EQN_OPER_AND 9 // logic AND
45 #define MIO_EQN_OPER_XOR 8 // logic XOR
46 #define MIO_EQN_OPER_OR 7 // logic OR
47 #define MIO_EQN_OPER_MARK 1 // OpStack token standing for an opening parenthesis
48
49 // these are values of the internal Flag
50 #define MIO_EQN_FLAG_START 1 // after the opening parenthesis
51 #define MIO_EQN_FLAG_VAR 2 // after operation is received
52 #define MIO_EQN_FLAG_OPER 3 // after operation symbol is received
53 #define MIO_EQN_FLAG_ERROR 4 // when error is detected
54
55 ////////////////////////////////////////////////////////////////////////
56 /// FUNCTION DEFINITIONS ///
57 ////////////////////////////////////////////////////////////////////////
58
59 /**Function*************************************************************
60
61 Synopsis [Performs the operation on the top entries in the stack.]
62
63 Description []
64
65 SideEffects []
66
67 SeeAlso []
68
69 ***********************************************************************/
Mio_ParseFormulaOper(int * pMan,int nVars,Vec_Ptr_t * pStackFn,int Oper)70 Vec_Int_t * Mio_ParseFormulaOper( int * pMan, int nVars, Vec_Ptr_t * pStackFn, int Oper )
71 {
72 Vec_Int_t * gArg1, * gArg2, * gFunc;
73 // perform the given operation
74 gArg2 = (Vec_Int_t *)Vec_PtrPop( pStackFn );
75 gArg1 = (Vec_Int_t *)Vec_PtrPop( pStackFn );
76 if ( Oper == MIO_EQN_OPER_AND )
77 gFunc = Exp_And( pMan, nVars, gArg1, gArg2, 0, 0 );
78 else if ( Oper == MIO_EQN_OPER_OR )
79 gFunc = Exp_Or( pMan, nVars, gArg1, gArg2 );
80 else if ( Oper == MIO_EQN_OPER_XOR )
81 gFunc = Exp_Xor( pMan, nVars, gArg1, gArg2 );
82 else
83 return NULL;
84 // Cudd_Ref( gFunc );
85 // Cudd_RecursiveDeref( dd, gArg1 );
86 // Cudd_RecursiveDeref( dd, gArg2 );
87 Vec_IntFree( gArg1 );
88 Vec_IntFree( gArg2 );
89 Vec_PtrPush( pStackFn, gFunc );
90 return gFunc;
91 }
92
93 /**Function*************************************************************
94
95 Synopsis [Derives the AIG corresponding to the equation.]
96
97 Description [Takes the stream to output messages, the formula, the vector
98 of variable names and the AIG manager.]
99
100 SideEffects []
101
102 SeeAlso []
103
104 ***********************************************************************/
Mio_ParseFormula(char * pFormInit,char ** ppVarNames,int nVars)105 Vec_Int_t * Mio_ParseFormula( char * pFormInit, char ** ppVarNames, int nVars )
106 {
107 char * pFormula;
108 int Man = nVars, * pMan = &Man;
109 Vec_Ptr_t * pStackFn;
110 Vec_Int_t * pStackOp;
111 Vec_Int_t * gFunc;
112 char * pTemp, * pName;
113 int nParans, fFound, Flag;
114 int Oper, Oper1, Oper2;
115 int i, v;
116
117 // make sure that the number of opening and closing parentheses is the same
118 nParans = 0;
119 for ( pTemp = pFormInit; *pTemp; pTemp++ )
120 if ( *pTemp == '(' )
121 nParans++;
122 else if ( *pTemp == ')' )
123 nParans--;
124 if ( nParans != 0 )
125 {
126 fprintf( stdout, "Mio_ParseFormula(): Different number of opening and closing parentheses ().\n" );
127 return NULL;
128 }
129
130 // copy the formula
131 pFormula = ABC_ALLOC( char, strlen(pFormInit) + 3 );
132 sprintf( pFormula, "(%s)", pFormInit );
133
134 // start the stacks
135 pStackFn = Vec_PtrAlloc( 100 );
136 pStackOp = Vec_IntAlloc( 100 );
137
138 Flag = MIO_EQN_FLAG_START;
139 for ( pTemp = pFormula; *pTemp; pTemp++ )
140 {
141 switch ( *pTemp )
142 {
143 // skip all spaces, tabs, and end-of-lines
144 case ' ':
145 case '\t':
146 case '\r':
147 case '\n':
148 continue;
149 case MIO_EQN_SYM_CONST0:
150 Vec_PtrPush( pStackFn, Exp_Const0() ); // Cudd_Ref( b0 );
151 if ( Flag == MIO_EQN_FLAG_VAR )
152 {
153 fprintf( stdout, "Mio_ParseFormula(): No operation symbol before constant 0.\n" );
154 Flag = MIO_EQN_FLAG_ERROR;
155 break;
156 }
157 Flag = MIO_EQN_FLAG_VAR;
158 break;
159 case MIO_EQN_SYM_CONST1:
160 Vec_PtrPush( pStackFn, Exp_Const1() ); // Cudd_Ref( b1 );
161 if ( Flag == MIO_EQN_FLAG_VAR )
162 {
163 fprintf( stdout, "Mio_ParseFormula(): No operation symbol before constant 1.\n" );
164 Flag = MIO_EQN_FLAG_ERROR;
165 break;
166 }
167 Flag = MIO_EQN_FLAG_VAR;
168 break;
169 case MIO_EQN_SYM_NEG:
170 if ( Flag == MIO_EQN_FLAG_VAR )
171 {// if NEGBEF follows a variable, AND is assumed
172 Vec_IntPush( pStackOp, MIO_EQN_OPER_AND );
173 Flag = MIO_EQN_FLAG_OPER;
174 }
175 Vec_IntPush( pStackOp, MIO_EQN_OPER_NEG );
176 break;
177 case MIO_EQN_SYM_NEGAFT:
178 if ( Flag != MIO_EQN_FLAG_VAR )
179 {// if there is no variable before NEGAFT, it is an error
180 fprintf( stdout, "Mio_ParseFormula(): No variable is specified before the negation suffix.\n" );
181 Flag = MIO_EQN_FLAG_ERROR;
182 break;
183 }
184 else // if ( Flag == PARSE_FLAG_VAR )
185 Vec_PtrPush( pStackFn, Exp_Not( (Vec_Int_t *)Vec_PtrPop(pStackFn) ) );
186 break;
187 case MIO_EQN_SYM_AND:
188 case MIO_EQN_SYM_AND2:
189 case MIO_EQN_SYM_OR:
190 case MIO_EQN_SYM_OR2:
191 case MIO_EQN_SYM_XOR:
192 if ( Flag != MIO_EQN_FLAG_VAR )
193 {
194 fprintf( stdout, "Mio_ParseFormula(): There is no variable before AND, EXOR, or OR.\n" );
195 Flag = MIO_EQN_FLAG_ERROR;
196 break;
197 }
198 if ( *pTemp == MIO_EQN_SYM_AND || *pTemp == MIO_EQN_SYM_AND2 )
199 Vec_IntPush( pStackOp, MIO_EQN_OPER_AND );
200 else if ( *pTemp == MIO_EQN_SYM_OR || *pTemp == MIO_EQN_SYM_OR2 )
201 Vec_IntPush( pStackOp, MIO_EQN_OPER_OR );
202 else //if ( *pTemp == MIO_EQN_SYM_XOR )
203 Vec_IntPush( pStackOp, MIO_EQN_OPER_XOR );
204 Flag = MIO_EQN_FLAG_OPER;
205 break;
206 case MIO_EQN_SYM_OPEN:
207 if ( Flag == MIO_EQN_FLAG_VAR )
208 {
209 Vec_IntPush( pStackOp, MIO_EQN_OPER_AND );
210 // fprintf( stdout, "Mio_ParseFormula(): An opening parenthesis follows a var without operation sign.\n" );
211 // Flag = MIO_EQN_FLAG_ERROR;
212 // break;
213 }
214 Vec_IntPush( pStackOp, MIO_EQN_OPER_MARK );
215 // after an opening bracket, it feels like starting over again
216 Flag = MIO_EQN_FLAG_START;
217 break;
218 case MIO_EQN_SYM_CLOSE:
219 if ( Vec_IntSize( pStackOp ) != 0 )
220 {
221 while ( 1 )
222 {
223 if ( Vec_IntSize( pStackOp ) == 0 )
224 {
225 fprintf( stdout, "Mio_ParseFormula(): There is no opening parenthesis\n" );
226 Flag = MIO_EQN_FLAG_ERROR;
227 break;
228 }
229 Oper = Vec_IntPop( pStackOp );
230 if ( Oper == MIO_EQN_OPER_MARK )
231 break;
232
233 // perform the given operation
234 if ( Mio_ParseFormulaOper( pMan, nVars, pStackFn, Oper ) == NULL )
235 {
236 fprintf( stdout, "Mio_ParseFormula(): Unknown operation\n" );
237 ABC_FREE( pFormula );
238 Vec_PtrFreeP( &pStackFn );
239 Vec_IntFreeP( &pStackOp );
240 return NULL;
241 }
242 }
243 }
244 else
245 {
246 fprintf( stdout, "Mio_ParseFormula(): There is no opening parenthesis\n" );
247 Flag = MIO_EQN_FLAG_ERROR;
248 break;
249 }
250 if ( Flag != MIO_EQN_FLAG_ERROR )
251 Flag = MIO_EQN_FLAG_VAR;
252 break;
253
254
255 default:
256 // scan the next name
257 for ( i = 0; pTemp[i] &&
258 pTemp[i] != ' ' && pTemp[i] != '\t' && pTemp[i] != '\r' && pTemp[i] != '\n' &&
259 pTemp[i] != MIO_EQN_SYM_AND && pTemp[i] != MIO_EQN_SYM_AND2 && pTemp[i] != MIO_EQN_SYM_OR && pTemp[i] != MIO_EQN_SYM_OR2 &&
260 pTemp[i] != MIO_EQN_SYM_XOR && pTemp[i] != MIO_EQN_SYM_NEGAFT && pTemp[i] != MIO_EQN_SYM_CLOSE;
261 i++ )
262 {
263 if ( pTemp[i] == MIO_EQN_SYM_NEG || pTemp[i] == MIO_EQN_SYM_OPEN )
264 {
265 fprintf( stdout, "Mio_ParseFormula(): The negation sign or an opening parenthesis inside the variable name.\n" );
266 Flag = MIO_EQN_FLAG_ERROR;
267 break;
268 }
269 }
270 // variable name is found
271 fFound = 0;
272 // Vec_PtrForEachEntry( char *, vVarNames, pName, v )
273 for ( v = 0; v < nVars; v++ )
274 {
275 pName = ppVarNames[v];
276 if ( strncmp(pTemp, pName, i) == 0 && strlen(pName) == (unsigned)i )
277 {
278 pTemp += i-1;
279 fFound = 1;
280 break;
281 }
282 }
283 if ( !fFound )
284 {
285 fprintf( stdout, "Mio_ParseFormula(): The parser cannot find var \"%s\" in the input var list.\n", pTemp );
286 Flag = MIO_EQN_FLAG_ERROR;
287 break;
288 }
289 /*
290 if ( Flag == MIO_EQN_FLAG_VAR )
291 {
292 fprintf( stdout, "Mio_ParseFormula(): The variable name \"%s\" follows another var without operation sign.\n", pTemp );
293 Flag = MIO_EQN_FLAG_ERROR;
294 break;
295 }
296 */
297 if ( Flag == MIO_EQN_FLAG_VAR )
298 Vec_IntPush( pStackOp, MIO_EQN_OPER_AND );
299
300 Vec_PtrPush( pStackFn, Exp_Var(v) ); // Cudd_Ref( pbVars[v] );
301 Flag = MIO_EQN_FLAG_VAR;
302 break;
303 }
304
305 if ( Flag == MIO_EQN_FLAG_ERROR )
306 break; // error exit
307 else if ( Flag == MIO_EQN_FLAG_START )
308 continue; // go on parsing
309 else if ( Flag == MIO_EQN_FLAG_VAR )
310 while ( 1 )
311 { // check if there are negations in the OpStack
312 if ( Vec_IntSize( pStackOp ) == 0 )
313 break;
314 Oper = Vec_IntPop( pStackOp );
315 if ( Oper != MIO_EQN_OPER_NEG )
316 {
317 Vec_IntPush( pStackOp, Oper );
318 break;
319 }
320 else
321 {
322 Vec_PtrPush( pStackFn, Exp_Not((Vec_Int_t *)Vec_PtrPop(pStackFn)) );
323 }
324 }
325 else // if ( Flag == MIO_EQN_FLAG_OPER )
326 while ( 1 )
327 { // execute all the operations in the OpStack
328 // with precedence higher or equal than the last one
329 Oper1 = Vec_IntPop( pStackOp ); // the last operation
330 if ( Vec_IntSize( pStackOp ) == 0 )
331 { // if it is the only operation, push it back
332 Vec_IntPush( pStackOp, Oper1 );
333 break;
334 }
335 Oper2 = Vec_IntPop( pStackOp ); // the operation before the last one
336 if ( Oper2 >= Oper1 )
337 { // if Oper2 precedence is higher or equal, execute it
338 if ( Mio_ParseFormulaOper( pMan, nVars, pStackFn, Oper2 ) == NULL )
339 {
340 fprintf( stdout, "Mio_ParseFormula(): Unknown operation\n" );
341 ABC_FREE( pFormula );
342 Vec_PtrFreeP( &pStackFn );
343 Vec_IntFreeP( &pStackOp );
344 return NULL;
345 }
346 Vec_IntPush( pStackOp, Oper1 ); // push the last operation back
347 }
348 else
349 { // if Oper2 precedence is lower, push them back and done
350 Vec_IntPush( pStackOp, Oper2 );
351 Vec_IntPush( pStackOp, Oper1 );
352 break;
353 }
354 }
355 }
356
357 if ( Flag != MIO_EQN_FLAG_ERROR )
358 {
359 if ( Vec_PtrSize(pStackFn) != 0 )
360 {
361 gFunc = (Vec_Int_t *)Vec_PtrPop(pStackFn);
362 if ( Vec_PtrSize(pStackFn) == 0 )
363 if ( Vec_IntSize( pStackOp ) == 0 )
364 {
365 // Cudd_Deref( gFunc );
366 ABC_FREE( pFormula );
367 Vec_PtrFreeP( &pStackFn );
368 Vec_IntFreeP( &pStackOp );
369 return Exp_Reverse(gFunc);
370 }
371 else
372 fprintf( stdout, "Mio_ParseFormula(): Something is left in the operation stack\n" );
373 else
374 fprintf( stdout, "Mio_ParseFormula(): Something is left in the function stack\n" );
375 }
376 else
377 fprintf( stdout, "Mio_ParseFormula(): The input string is empty\n" );
378 }
379 ABC_FREE( pFormula );
380 Vec_PtrFreeP( &pStackFn );
381 Vec_IntFreeP( &pStackOp );
382 return NULL;
383 }
384
385 /**Function*************************************************************
386
387 Synopsis [Derives the TT corresponding to the equation.]
388
389 Description []
390
391 SideEffects []
392
393 SeeAlso []
394
395 ***********************************************************************/
Mio_ParseFormulaTruth(char * pFormInit,char ** ppVarNames,int nVars)396 Vec_Wrd_t * Mio_ParseFormulaTruth( char * pFormInit, char ** ppVarNames, int nVars )
397 {
398 Vec_Int_t * vExpr;
399 Vec_Wrd_t * vTruth;
400 // derive expression
401 vExpr = Mio_ParseFormula( pFormInit, ppVarNames, nVars );
402 if ( vExpr == NULL )
403 return NULL;
404 // convert it into a truth table
405 vTruth = Vec_WrdStart( Abc_Truth6WordNum(nVars) );
406 Exp_Truth( nVars, vExpr, Vec_WrdArray(vTruth) );
407 Vec_IntFree( vExpr );
408 return vTruth;
409 }
Mio_ParseFormulaTruthTest(char * pFormInit,char ** ppVarNames,int nVars)410 void Mio_ParseFormulaTruthTest( char * pFormInit, char ** ppVarNames, int nVars )
411 {
412 Vec_Wrd_t * vTruth;
413 vTruth = Mio_ParseFormulaTruth( pFormInit, ppVarNames, nVars );
414 // Kit_DsdPrintFromTruth( (unsigned *)Vec_WrdArray(vTruth), nVars ); printf( "\n" );
415 Vec_WrdFree( vTruth );
416 }
417
418 /**Function*************************************************************
419
420 Synopsis [Checks if the gate's formula essentially depends on all variables.]
421
422 Description []
423
424 SideEffects []
425
426 SeeAlso []
427
428 ***********************************************************************/
Mio_ParseCheckName(Mio_Gate_t * pGate,char ** ppStr)429 int Mio_ParseCheckName( Mio_Gate_t * pGate, char ** ppStr )
430 {
431 Mio_Pin_t * pPin;
432 int i, iBest = -1;
433 // find the longest pin name that matches substring
434 char * pNameBest = NULL;
435 for ( pPin = Mio_GateReadPins(pGate), i = 0; pPin; pPin = Mio_PinReadNext(pPin), i++ )
436 if ( !strncmp( *ppStr, Mio_PinReadName(pPin), strlen(Mio_PinReadName(pPin)) ) )
437 if ( pNameBest == NULL || strlen(pNameBest) < strlen(Mio_PinReadName(pPin)) )
438 pNameBest = Mio_PinReadName(pPin), iBest = i;
439 // if pin is not found, return -1
440 if ( pNameBest )
441 *ppStr += strlen(pNameBest) - 1;
442 return iBest;
443 }
Mio_ParseCheckFormula(Mio_Gate_t * pGate,char * pForm)444 int Mio_ParseCheckFormula( Mio_Gate_t * pGate, char * pForm )
445 {
446 Mio_Pin_t * pPin;
447 char * pStr;
448 int i, iPin, fVisit[32] = {0};
449 if ( Mio_GateReadPins(pGate) == NULL || !strcmp(Mio_PinReadName(Mio_GateReadPins(pGate)), "*") )
450 return 1;
451 /*
452 // find the equality sign
453 pForm = strstr( pForm, "=" );
454 if ( pForm == NULL )
455 {
456 printf( "Skipping gate \"%s\" because formula \"%s\" has not equality sign (=).\n", pGate->pName, pForm );
457 return 0;
458 }
459 */
460 //printf( "Checking gate %s\n", pGate->pName );
461
462 for ( pStr = pForm; *pStr; pStr++ )
463 {
464 if ( *pStr == ' ' ||
465 *pStr == MIO_EQN_SYM_OPEN ||
466 *pStr == MIO_EQN_SYM_CLOSE ||
467 *pStr == MIO_EQN_SYM_CONST0 ||
468 *pStr == MIO_EQN_SYM_CONST1 ||
469 *pStr == MIO_EQN_SYM_NEG ||
470 *pStr == MIO_EQN_SYM_NEGAFT ||
471 *pStr == MIO_EQN_SYM_AND ||
472 *pStr == MIO_EQN_SYM_AND2 ||
473 *pStr == MIO_EQN_SYM_XOR ||
474 *pStr == MIO_EQN_SYM_OR ||
475 *pStr == MIO_EQN_SYM_OR2
476 )
477 continue;
478 // return the number of the pin which has this name
479 iPin = Mio_ParseCheckName( pGate, &pStr );
480 if ( iPin == -1 )
481 {
482 printf( "Skipping gate \"%s\" because substring \"%s\" does not match with a pin name.\n", pGate->pName, pStr );
483 return 0;
484 }
485 assert( iPin < 32 );
486 fVisit[iPin] = 1;
487 }
488 // check that all pins are used
489 for ( pPin = Mio_GateReadPins(pGate), i = 0; pPin; pPin = Mio_PinReadNext(pPin), i++ )
490 if ( fVisit[i] == 0 )
491 {
492 // printf( "Skipping gate \"%s\" because pin \"%s\" does not appear in the formula \"%s\".\n", pGate->pName, Mio_PinReadName(pPin), pForm );
493 return 0;
494 }
495 return 1;
496 }
497
498 ////////////////////////////////////////////////////////////////////////
499 /// END OF FILE ///
500 ////////////////////////////////////////////////////////////////////////
501
502
503 ABC_NAMESPACE_IMPL_END
504
505