Re: EBNF Grammar help - part II

> My stumbling block is how to parse the string expression to derive a
> set of concrete java expressions which I can the evaluate. For
> instance the ''one out of three' expression would be treated as an
> array that I can step through and evaluate, but I have no Idea how
> to generate this.


You are either asking a very simple question or a very hard one, since
you seem to be starting out and its a common question I'll assume the
simple one first.


The simple question is: "I know the grammar of my expressions, how do
I write out a Java expression to implement them?" The answer is also
simple, you look at each point in the grammar and decide what to write
out for that point.


> The objectives read like "you must have done A and (B or C) or (D
> and E and F) and one out of (G, H, I)".


1) Take the simplest examples possible first. Write down the input
      and write down the desired output.


input: "you must have done A."
output: if (A) pass() else fail();


input: "you must have done A and B."
output: if (A && B) pass() else fail();


and so forth.


2) Match the parts of the input and output up that vary and the parts
      that are constant. Above the "if (" and ") pass() else fail();"
      seem to be constant parts. The "A && B" seem to be variable parts.


The variable parts will match to things your grammar recognizes. Use
them to match things up. Now, imagine that your grammar is a tree,
with the top, root, or goal production as the root of the tree, and
each reference to another production being a branch in the tree,
eventually reaching the tokens or terminals of the grammar, which are
the leaves. This is your "parse tree". (You can even get tools, such
as JTB and JJTree which will build a real tree in memory that
instantiates your parse tree. Use them!)


3) Write recursive routines to generate the desired outputs from the
      example inputs.


If you start at the root of the tree, you can write recursive routines
that build up (as a string) the Java expression you want to output.


You write those recursive routines by looking at the example inputs,
example output (and the tree that your parser would build from the
sample input) and deciding at each point in the tree what parts of the
input and output match. The resulting correspondence should be
trivial and obvious. You should not have to think hard to make the
match. For example, the A in the input matches the A in the output.
The part of the tree, an IDENTIFIER token is what captures the A in
the input. Thus, when the traversal of the tree reaches the
IDENTIFIER token, it should write out the name of the identifier.


Taking your problem case "one out of (G, H, I)" should generate an
array. Then, at the point where the grammar matches "one out of", it
should output an array. The size of the array comes from the number
of elements in "(G, H, I)". Thus, the "one out of" routine should
make a call to the child non-terminal that asks how many elements are
in the list (and that will be a recursive routine that counts the
sub-tree), and so forth. There will be another recursive call that
writes the code to fill in what to do with G, H, and I--that is to put
the appropriate values in the right slots of the array for each
element of the list, G filling in the first slot, H the second, and I
the third.


If the answer isn't trivial and obvious, then you maybe on to hard
question. The hard question is "how do I figure out what the output
should be?" For example, in your problem, "when does one use an
array?" If the answer isn't "use an array any time one sees 'one out
of'", but involves some other criteria, then you have to understand
those criteria and create data structures and algorithms that capture
the desired semantics. Depending on what the criteria are and whether
you understand them or not, the problem can be potentially insoluable.


BTW, if all you are interested in is "the answer" (i.e. calculating
the value of the expression). What you may want is a "desktop
calculator" example. A desktop calculator is a grammar whose
recursive routines build up "the answer" (that is the value of the
expression) rather than a string representing a program that will
calculate the example. The same recursive style applies. You write a
rule at the root that calculates its version of "the answer" from the
non-terminals that the root rule references. You repeat that process
for every rule in your grammar.


> The reason I thought of using JavaCC is that it would have
> generated JavaCode from the input expression which I could have then
> evaluated. From a description of my problem, is this still viable?


The Java that JavaCC generates solves about half the problem (well,
actually about 1/3, but if you use a tree builder with it, you get a
full half). You have to write the other half that maps the trees into
the desired outputs. Note, this is true of any of the tools,
e.g. ANTLR, yacc.


Well, that may be not completely true these days. There are some very
high-end tools that automate the output process to varying extents.
Metatool (ATT) and FNC (Inria) are two examples that come quickly to
mind. However, even with the high end tools you have to understand
what the output "should be" and write that down in the appropriate
notation. There is no tool that "intuits" what the output should be,
unless the tool works in a very restricted domain.


Note, I apologize for not using JavaCC examples to illustrate the
point even though the question was cross-posted to the JavaCC group.
Unfortunately, I am not sufficiently facile with the JavaCC syntax to
write examples in it. It's simply that I use different but equivalent
tools.


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
3 Proctor Street voice : (508) 435-5016
Hopkinton, MA 01748 USA fax : (508) 435-4847 (24 hours)
------------------------------------------------------------------------------

Return to the comp.compilers page.
Search the comp.compilers archives again.