uva 464 - Sentence/Phrase Generator

Sentence/Phrase Generator

Write a program that generates English language phrases and sentences conforming to the following rules:
<sentence> ::= <trans-sentence> | <sentence> ::= <intrans-sentence>
<trans-sentence> ::= <subject> <verb-phrase> <object> <prep-phrase>
<intrans-sentence> ::= <subject> <intrans-verb-phrase> <prep-phrase>
<subject> ::= <noun-phrase>
<object> ::= <noun-phrase>
<noun-phrase> ::= <article> <modified-noun>
<modified-noun> ::= <noun> | <modifier> <noun>
<modifier> ::= <adjective> | <adverb> <adjective>
<verb-phrase> ::= <trans-verb> | <adverb> <trans-verb>
<intrans-verb-phrase> ::= <intrans-verb> | <adverb> <intrans-verb>
<prep-phrase> ::= <preposition> <noun-phrase> | <empty>
<noun> ::= man | dog | fish | computer | waves
<trans-verb> ::= struck | saw | bit | took
<intrans-verb> ::= slept | jumped | walked | swam
<article> ::= the | a
<adjective> ::= green | small | rabid | quick
<adverb> ::= nearly | suddenly | restlessly
<preposition> ::= on | over | through
<empty> ::= ""

For example, the first two lines say that to generate a sentence, one may generate a ``trans-sentence'' or an ``intrans-sentence''. A transitive sentence, according to the third rule, consists of a ``subject'', followed by a ``verb-phrase'', followed by an ``object'', followed by a ``prep-phrase''. Similarly, the next-to-last rule indicates that a ``preposition'' can be any of the three words on, over, or through.

Your program should read from the input a number of requests for various kinds of phrases. Each request may be for any of the phrase names appearing on the left hand side of the above rules. It should then attempt to generate the requested phrase by applying these rules until all of the <...> have been replaced with appropriate words.

In many cases, you will face a choice of alternate rules for expanding a phrase name. In these cases, you should make a choice as follows: Suppose that this is the  such choice that you have faced since the start of execution of your program, and that you must choose one of n rules for expanding a given kind of phrase. Let the rules for that phrase be numbered from  in the order of appearance above, and then choose rule number  .

Input

The input will consist of an unspecified number of lines. Each line will contain, left-justified, a phrase name corresponding to one of the names appearing on the left-hand-side of the rules above (without the surrounding brackets).

Output

For each phrase named in the output, print a single line containing the expansion of that phrase according to the above rules. Each word in the phrase should be separated from the others by a single space.

Sample Input

sentence
noun
sentence

Sample Output

the small dog restlessly jumped through the quick dog
fish
a dog took the quick computer

BNF grammers

#include<stdio.h>
#include<vector>
#include<string>
#include<cstring>
#include<algorithm>
#include<map>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define DBG 0

using namespace std;

/*{"sentence",            0
"trans-sentence",       1
"intrans-sentence",     2
"subject",              3
"object",               4
"noun-phrase",          5
"modified-noun",        6
"modifier",             7
"verb-phrase",          8
"intrans-verb-phrase",  9
"prep-phrase",          10
"noun",                 11
"trans-verb",           12
"intrans-verb",         13
"article",              14
"adjective",            15
"adverb",               16
"preposition",          17
"empty"                 18*/
char rname[20][25]={"sentence","trans-sentence","intrans-sentence","subject",
    "object","noun-phrase","modified-noun","modifier","verb-phrase",
    "intrans-verb-phrase","prep-phrase","noun","trans-verb","intrans-verb",
    "article","adjective","adverb","preposition","empty"};
struct Rule{
    Rule(){chs=0;}
    bool type;
    vector<string>nouns;
    vector<int>ens[2];
    int chs;
    string name;
    void add(int a,int b){chs=a+1,ens[a].push_back(b);}
    void addN(string a){nouns.push_back(a);}
    void getType(){type=nouns.size()>0?0:1;}
};
map<string,int>mp;
vector<Rule>vr;
int K=1;
bool F;
void init(){
    rep(i,19){
        mp[rname[i]]=i;
        vr.push_back(Rule());
    }
    vr[11].addN("man"),vr[11].addN("dog"),vr[11].addN("fish"),vr[11].addN("computer"),vr[11].addN("waves");
    vr[12].addN("struck"),vr[12].addN("saw"),vr[12].addN("bit"),vr[12].addN("took");
    vr[13].addN("slept"),vr[13].addN("jumped"),vr[13].addN("walked"),vr[13].addN("swam");
    vr[14].addN("the"),vr[14].addN("a");
    vr[15].addN("green"),vr[15].addN("small"),vr[15].addN("rabid"),vr[15].addN("quick");
    vr[16].addN("nearly"),vr[16].addN("suddenly"),vr[16].addN("restlessly");
    vr[17].addN("on"),vr[17].addN("over"),vr[17].addN("through");
    vr[0].add(0,1),vr[0].add(1,2),                          //grammers
    vr[1].add(0,5),vr[1].add(0,8),vr[1].add(0,5),vr[1].add(0,10),
    vr[2].add(0,5),vr[2].add(0,9),vr[2].add(0,10);
    vr[3].add(0,5);           //no subject
    vr[4].add(0,5);               //no object
    vr[5].add(0,14),vr[5].add(0,6);                     
    vr[6].add(0,11),vr[6].add(1,7),vr[6].add(1,11);
    vr[7].add(0,15),vr[7].add(1,16),vr[7].add(1,15);
    vr[8].add(0,12),vr[8].add(1,16),vr[8].add(1,12);
    vr[9].add(0,13),vr[9].add(1,16),vr[9].add(1,13);
    vr[10].add(0,17),vr[10].add(0,5),vr[10].add(1,18);
    rep(i,19)vr[i].getType();
}
void gen(int rc){
    int chs;
    if(DBG)printf("\ngen %s\n",rname[rc]);
    if(vr[rc].type==0){
        chs=K%vr[rc].nouns.size();
        if(!F)printf(" ");F=0;
        printf("%s",vr[rc].nouns[chs].c_str());
        K++;
    }
    else{
        chs=0;
        if(vr[rc].chs){
            if(vr[rc].chs>1)chs=K%vr[rc].chs,K++;
            rep(i,vr[rc].ens[chs].size()){
                gen(vr[rc].ens[chs][i]);
            }
        }
    }
}
void ans(char chs[]){
    F=1;
    int cr=mp[chs];
    gen(cr);
    printf("\n");
}
int main(){
    char chs[30];
    init();
    while(scanf("%s",chs)==1){
        if(DBG)printf("------------%s--------------\n",chs);
        ans(chs);
        
    }
}