10 Apr 2001 01:17:23 -0400

Related articles |
---|

EBNF Grammar help - part II paul.meaney@qa.com_NOSPAM.star.co.uk (Paul Meaney) (2001-04-04) |

Re: EBNF Grammar help - part II joachim_d@gmx.de (Joachim Durchholz) (2001-04-10) |

Re: EBNF Grammar help - part II cfc@world.std.com (Chris F Clark) (2001-04-10) |

From: | Chris F Clark <cfc@world.std.com> |

Newsgroups: | comp.compilers,comp.compilers.tools.javacc |

Date: | 10 Apr 2001 01:17:23 -0400 |

Organization: | The World Public Access UNIX, Brookline, MA |

References: | 01-04-025 |

Keywords: | parse |

Posted-Date: | 10 Apr 2001 01:17:23 EDT |

*> 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)

------------------------------------------------------------------------------

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.