Compilers - Grammar generator

Author

Grammar generator

Thomas Duwe

2006-04-08, 7:03 pm

Hello NG,

in my student research project i got the task to
compare compiler-compiler generators like Antlr or JavaCC.

To do that, one suggestion from my tutor was, to
write a tool, which automatically generates a random grammar
( in bnf or ebnf or other format ) from a given/chosen alphabet.

So now my question : has anybody heard of such work before?

Regards,

Thomas.
[We've seen sentence generators that generate random source code from
a grammar, shouldn't be any harder than that. -John]

Thomas Duwe

2006-04-21, 10:04 pm

Hello NG,

> [We've seen sentence generators that generate random source code from
> a grammar, shouldn't be any harder than that. -John]

That's in principle right.

But I Want To Generate A Grammar ( in ebnf or bnf ) where the
rules, if i parse the resulting grammar, are producing something.

So I Have To Specify, That I Need To Generate A Random Grammar,
where the rules produce something and all the rules are also used.

I read some papers regarding generating sentences from a grammar
( e.g. Purdom's algorithm and variants of that ).

Unfortunately, that isn't helping me much.

Perhaps someone have further suggestions?

I've taken now following steps to accomplish my task :

-I've taken the grammar of ebnf and implemented these rules as methods,
which are recursively called according to the grammar of ebnf.

-And i specified some rules, such as nesting level of +,*,?, so
that the generated tree is not to deep.

But up till now, nothing 'useful' is generated.

Any suggestions?

Thomas.

Hans-Peter Diettrich

2006-04-25, 7:15 pm

Thomas Duwe wrote:

>
> That's in principle right.
>
> But I Want To Generate A Grammar ( in ebnf or bnf ) where the
> rules, if i parse the resulting grammar, are producing something.

Perhaps your problem is the difference between syntax and semantics.

Did you also realize, that you are working with multiple instances of a
grammar, in different representations? One grammar may be hard-coded, to
produce another grammar, encoded in e.g. a tree.

In a formal grammar you can specify the syntax, for use in both an
syntax checker (parser) or phrase generator/producer. The semantics or
actions, however, will be different for both applications.

Assuming that you already have an parser for your (E)BNF grammars,
that parser can create an AST from that grammar. Now you need visitors
for that tree, which know about the semantics of the nodes, and act
according to their intended operation. These visitors must know, in
the first place, what the nodes in that tree *mean*, e.g. what's a
rule node, a sequence node etc., so that they can can walk through the
tree in a "meaningful" manner, and can execute "meaningful" operations
(checks, productions...).

>
> So I Have To Specify, That I Need To Generate A Random Grammar,
> where the rules produce something and all the rules are also used.

This is the first visitor for an BNF grammar tree. It will most probably
use random numbers to select one of alternative subtrees for further
processing. On the root (goal) node of the grammar, the random value
might specify the number of rules of the new grammar (how often to enter
the "goal.rule" subtree), before it stops on the epsilon (EOI,
"goal.done"...) node. Entering an "rule" node, it will have to produce a
new rule, which is completed by further random selections of the
alternative subtrees, until it happens to select the "rule.done" node.
And so on for all node types...

It is your task to implement reasonable restrictions with regards to the
random decisions, and to assure that your constraints (all rules must
exist and must be used...) finally are satisfied. Perhaps you'll
implement two modes, one for the production of a grammar "skeleton", and
one for the completion of that skeleton, so that the result satisfies
your constraints.

In the next step you can implement another visitor, for an general
grammar tree, that produces arbitrary sentences from that grammar, based
on other restrictions (length of the sentence...).

> I've taken now following steps to accomplish my task :
>
> -I've taken the grammar of ebnf and implemented these rules as methods,
> which are recursively called according to the grammar of ebnf.

Is this one monolithic class, or did you implement distinct classes for
all node types, based on a common "node" class?

Did you consider to add an "dispatch" method to every (node type) class,
so that it's possible to invoke one of the applicable actions by e.g. a
random number parameter?

> -And i specified some rules, such as nesting level of +,*,?, so
> that the generated tree is not to deep.

How do your represent that generated tree, and how is it related to the
grammar class(es)?

DoDi

Sponsored Links