On 17-Apr-99 Steven T. Hatton wrote:
>
> I am trying to write a "logical parser" that will read in symbolic
> logic statements and parse them into trees. For example it would read
> A & B and create a tree with & as the root, A as the left child, and B
> as the right child. After the tree is created I want to evaluate
> (traverse) the tree for every possible combination of truth values.
> [snip]
> One question I have regarding an implementation of this is whether I
> should attempt to use OOP, messages and methods for the act of adding
> children and redirecting the root pointer etc., or just use structures
> and functions to do the job. I would love to try both approaches and
> see what happens in each. Currently I don't deal with parentheses.
[Best viewed in fixed-width font]
You're undoubtedlyly right that anything approaching depth on this topic
is out of place on this list, but it's probably relevant to your question
and the list to suggest looking at flex and yacc, which are designed
precisely for assisting with coding this kind of parsing exercise.
These will enable you also to deal with precedence and parentheses.
For your examples, one intermediate target might be to construct a
"reverse Polish" stack which you then implement from left to right.
E.g. (using "|" for "or")
(A&B)|(C&D) -> A B & C D & |
which you can implement successively as
|
& & & & & & &
A -> A B -> A B -> A B C -> A B C D -> A B C D -> A B C D
I think you will also have to decide what you want to achieve with an
expression like (A&B)|(A&C). Are you content to simply let the second
"A" be what it is because that is what the parser encounters at that
point, or do you want the parser to copy the values of duplicate symbols
up the stack (so that you "only need to input their values once")?
In the second case you will end up with trees cross-linked to trees,
so that the resulting graph is no longer a tree.
It's hard to find anything like a good introduction to flex (lex)
and yacc: the O'Reilly book "Lex and Yacc" is sound but not easy.
One of the best introductions is in the chapter "Program Development"
in Kernighan and Pike's "The UNIX Programming Environment", but even that
can leave you wondering what to do next.
Good luck,
Ted.
--------------------------------------------------------------------
E-Mail: (Ted Harding) <[EMAIL PROTECTED]>
Date: 18-Apr-99 Time: 10:30:42
------------------------------ XFMail ------------------------------
--
To get out of this list, please send email to [EMAIL PROTECTED] with
this text in its body: unsubscribe suse-linux-e
Check out the SuSE-FAQ at http://www.suse.com/Support/Doku/FAQ/ and the
archive at http://www.suse.com/Mailinglists/suse-linux-e/index.html
