Ted,
> 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.
If I understand correctly flex and yacc will produce a compiler (in some
sense) from a grammar. In other words I would need to formulate the problem
in terms of BNF. I've thought about this. If that "making a living" thing
didn't matter to me so much I might try it. I may seek a math related NG to
take this thread so as not to clutter up the suse linux ML.
> These will enable you also to deal with precedence and parentheses.
Part of the reason I want to undertake this exercise is to solve these
problems from scratch. That doesn't mean I will not look at how yacc and
flex do it. My algorithm should handle precedence, and could be modified to
handle parentheses without too much problem.
> For your examples, one intermediate target might be to construct a
> "reverse Polish" stack which you then implement from left to right.
Actually I did that in one of my programming classes. I believe I can find
an algorithm for it in McCracken. The Jon Lukasiewicz (JL, AKA 'Polish'),
calculator is normally done using stacks. This may produce an
algorithmically more efficient way of approaching the problem, but for me it
is less intuitive. I believe the coding of the algorithm I presented is
straight forward, and it will allow for an infix notation. My big question
is, how would one approach this using using OOP as opposed to a procedural
programming? Which is best?
> 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.
You raise a good point by asking how to handle things like A & B | A. There
is a distinction between what I am trying to do and what a typical JL
calculator will do. I am attempting to evaluate the input expression for
all possible combinations of variable values. If I were just interested in
evaluating a given expression for predetermined variable values, I would use
T & T | F. Of course I could use a stack based JL calculator and reset the
stack pointers for each different evaluation of the variable set. I.e., fill
the stack with variables and run through once with A=T, B=T, C=T. Reset the
pointers and run through with A=F, B=T, C=T, etc. Handling parentheses
could also be done using a stack. Parentheses seems to fall out naturally
when using the recursive data type tree structure. What ever is in the ()
just becomes a subtree linked to the left or right child of the appropriate
node in the overall 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.
Hmmm, I have K & P, and I guess there are man pages and source code for
yacc and flex. Don't know if I will have time to do that research or not.
Thanks for taking the time to respond. I guess to summarize my response I
could say:
1) I want to do this with a tree structure even if it is not the most
efficient approach. Other approaches are worth considering as learning
exercises.
2) I am interested in suggestions on how to use OOP to accomplish this task.
3) I would like to generate a BNF for this problem. I am very rusty on how
to do this, and was never as good at it as I should have been.
Steve
--
http://www.winehq.com | I think.
http://www.suse.com | I think I am.
http://www.kde.org | Therefore I am.
http://samba.anu.edu.au | I think? - Moody Blues
--
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
