Parsing Logical Expressions

[Wapeka]

Hopefully I am posting this in the correct group - If not, please suggest
alternate group.

I am writing a program that reads logic statements (dependency) downloaded
from SAP and applies the same logic in my ACCESS database application.


Basically a dependency is an expression that results in a true or false
value. I am sure I can convert the expressions into simple SQL WHERE
clauses that can be applied to the user's temp table. If a record is
returned from the query then the condition will be considered true.

please consider these types of Expressions Found in SAP

Case 1:
ExpA
example: MG1_D1CA NE 'K'

Case 2
NOT ExpA
example: NOT STG_D1CA IN ('1','3')

Case 3:
ExpA OR ExpB ( also ExpA AND ExpB)
example: PA_D1CA NE '2' or MG1_D1CA EQ 'K'

Case4:
NOT(ExpA AND ExpB )
eg: NOT (WERT_BT5A EQ 'L0' AND DKW_BT5A EQ 'PV')

Case5:
(Exp A AND Exp B) OR (ExpC AND ExpD)
eg: ( M13_5_DGMA <= '1' AND M25_DGMA > '0' ) OR ( M13_5_DGMA > '0' AND M25
_DGMA <= '2' )

Case6:
NOT(ExpA AND ExpB AND ExpC)
eg: NOT (SIG_D1CA IN ('0','1','3') AND LEA_D1CA IN ('A','G') AND PA_D1CA EQ
'0')

Obviously much more complex logic expressions can be constructed in SAP and
may need to be handled in the future by the parser

For example: ( (ExpA or ExpB) AND (ExpD OR ExpE) ) AND ( (ExpF or ExpG)
AND (ExpH OR ExpI) )

I am concerned about the possibility of "Nested" parentheses - that is:
parentheses inside of parentheses (not including the IN clause)

I have be doing some practice by simplifying logic expressions this weekend
and I am seeing a pattern that may be able to be translated into a string
manipulation logic:

My goal is to write a program in Visual Basic that will do the following
steps:

Step 1: Identify the nesting level of all parentheses and the individual
expressions

Step 2: start first with expressions that have the highest nesting value

Step 3: move simple, single expression terms to the front flipping the
OR/And Term around
example: (ExpA or ExpB) AND ExpC ---> ExpC AND (ExpA or ExpB)

Step 4a: Use normalization rules to simplify certain expressions
(associative, distributive, etc...)
example: ExpC AND (ExpA or ExpB) ---> ExpC AND ExpA OR ExpC AND ExpB
example: NOT (ExpA and ExpB) ---> NOT ExpA OR NOT ExpB

Step 4b: More complex expressions need to be processed with several steps:
example: (ExpA OR Exp B) AND (ExpC OR ExpD) --->
[x] AND (ExpC OR ExpD) ---->
[x] AND ExpC OR [x] AND ExpD
Now expand the [x] term:
(ExpA OR ExpB) AND ExpC OR (ExpA OR ExpB) AND ExpD ---->

Now go back to Step 3 and 4a
(be sure to process pairs separated by AND before pairs separated with OR)

first apply step 3:
ExpC AND (ExpA OR ExpB)
OR
ExpD AND (ExpA OR ExpB)

now apply step 4a

ExpC AND ExpA OR ExpC AND ExpB
OR
ExpD AND ExpA OR ExpD AND ExpB

Now we are done!

ExpC AND ExpA OR ExpC AND ExpB OR ExpD AND ExpA OR Exp D AND ExpB


I think it is possible to write a recursive procedure that can handle any
number of nested parentheses and simply the expressions to the most basic
form of AND's OR's and NOT's with all parentheses removed. I was hoping
someone has already solved this type of problem and I could copy the logic
but I have not been able to find anything to date.

I have been looking at different books on compiler theory but most are too
generalized to be of much help. And I am not really interested in the
typical theoretical discussions.

At this point am asking for any suggestions on how to simplify logical
expressions using visual basic.

-Wapeka

 

[Marshall Barton]

I'm not sure you have to go to all that trouble. Assuming
that things like MG1_D1CA are field names in the table, all
of your example expressions are legal SQL where conditions.

So, I have to ask the question - what about your expressions
won't work without you doing any processing?

Even if there are some differences, it might be easier to
translate one syntax to another without doing a complete
parsing and reconstruction.
--
Marsh
MVP [MS Access]

Hopefully I am posting this in the correct group - If not, please suggest
alternate group.

I am writing a program that reads logic statements (dependency) downloaded
from SAP and applies the same logic in my ACCESS database application.

Basically a dependency is an expression that results in a true or false
value. I am sure I can convert the expressions into simple SQL WHERE
clauses that can be applied to the user's temp table. If a record is
returned from the query then the condition will be considered true.

please consider these types of Expressions Found in SAP

Case 1:
ExpA
example: MG1_D1CA NE 'K'

Case 2
NOT ExpA
example: NOT STG_D1CA IN ('1','3')

Case 3:
ExpA OR ExpB ( also ExpA AND ExpB)
example: PA_D1CA NE '2' or MG1_D1CA EQ 'K'

Case4:
NOT(ExpA AND ExpB )
eg: NOT (WERT_BT5A EQ 'L0' AND DKW_BT5A EQ 'PV')

Case5:
(Exp A AND Exp B) OR (ExpC AND ExpD)
eg: ( M13_5_DGMA <= '1' AND M25_DGMA > '0' ) OR ( M13_5_DGMA > '0' AND M25
_DGMA <= '2' )

Case6:
NOT(ExpA AND ExpB AND ExpC)
eg: NOT (SIG_D1CA IN ('0','1','3') AND LEA_D1CA IN ('A','G') AND PA_D1CA EQ
'0')

Obviously much more complex logic expressions can be constructed in SAP and
may need to be handled in the future by the parser

For example: ( (ExpA or ExpB) AND (ExpD OR ExpE) ) AND ( (ExpF or ExpG)
AND (ExpH OR ExpI) )

I am concerned about the possibility of "Nested" parentheses - that is:
parentheses inside of parentheses (not including the IN clause)

[snip]

 

[Wapeka]

First of all, thanks for the response.


I think you are right and it does seem like a
lot of work in an effor to gain some processing
speed. I have my doubts that using the parser will be
any faster then just converting the expressions using
a simple search and replace.

I belive all I need to do is fix up
"EQ" into "=" and replace the field names in SAP with
the field names in my access database.

Have you ever heard of anybody trying to normalize logical
expressions for something like this?

-Wapeka

 

[Dirk Goldgar]

Have you ever heard of anybody trying to normalize logical
expressions for something like this?

A long time ago, I wrote a C routine that did this. It parsed a complex
loigical expression and built a decision tree. I don't remember the
details now, but I'm sure it would be simpler to let Jet or the Eval
function do the parsing for you, if you can just transform your initial
expression into locally understood terms.

 

[Marshall Barton]

Sure I've heard of it (and even done it several times),
every expression evaluation language has to do it to
translate the user level language to an execution level
language. OTOH, It's definitely not something you want to
get into if you can avoid it.

As far as replacing a few things like EQ and some field
names, check the Replace function. It sounds like it may do
most of the work for you.