parser for evaluating arbitrarily complex boolean function in a stringby jce (Novice)
|on Oct 14, 2004 at 20:24 UTC||Need Help??|
jce has asked for the
wisdom of the Perl Monks concerning the following question:
I have a string which contains something like this (minus the quotes of course): $function = "((S0*B)|((!S0)*A))"; These functions are coming from some other parsing I have setup for some Verilog Library files. In this instance this equation describes a 2 input 1 ouput multiplexer. | being a Logical OR, ! being NOT, and * being AND, ^ being XOR etc. There will be an arbitrary number of boolean operands, operators, and parenthetical phrases. There is an order of operations, ! is highest precedence, (of course parantheses are evaluated first), AND is higher then OR, etc.
This is what i am looking to do. These libraries are megabytes in size, text files, with amoung other things these functional equations. I want to take the function that is in $string, and generate a truth table showing all possible combinations of inputs and then the corresponding result. I have written some parsing that counts the number of unique operands, the total number of operators (AND count, Or Count etc, and counts the number of parenthesized expressions, which is 4 in the MUX equation.
The problem is I am not sure how to proceed, given that the function might be as simple as (A*B*C), or more complex then the one given above. On a side note, we are only talking about no more then 4 unique boolean operands in a function (each may or may not be used more then 1 time). I want to use this method on each of the 1000 odd functions in this HDL code library, to make truth tables.
I am hoping someone may have done something like this, know of some code snippets that do something similar to this, or maybe just have some pointers or tips as to how they would do this. Im not a Regex expert, but have dabbled in some easy to moderate pattern matching before.