Recursion Basics

[smartbeginner]

The Problem is CFG grammar generation
Eg:
Input S->ABC
A->bcd
B->efg
C->hij
It should produce the o/p bcdefghij substituting for every Capitals
found on the way recursively

The C pgm I wrote was:
#include<stdio.h>
#include<conio.h>
int main()
{
int recurPrint(char[15],char[][50],int,int);
int findVar(char,char[]);
char stack[50];
char grmr[15][50];
char lhs[15],ch;
int i=0;
clrscr();
while(1)
{
printf("\n Enter variable:");
scanf("%c",&lhs);
flushall();
printf("\n Enter production:");
gets(grmr);

printf("\n Do you want to continue[y/n]:");
ch=getche();
if(ch=='n'||ch=='N')
break;
++i;
}

lhs[i+1]='\0';

recurPrint(lhs,grmr,0,0);

getche();
return 0;



}
int findVar(char find,char lhs[])
{
int i=0;
while(lhs!='\0')
{
if(lhs==find)
return i;
++i;
}



}

int recurPrint(char lhs[],char grmr[][50],int lims,int ji)
{
static int index;
static int j;
index=lims;
j=ji;
printf("\n Start of function Rep");
printf("\n Index is:%d",index);
printf("\n With j is:%d",j);
getche();
if(grmr[index][j]=='\0')
return 0;


else if(grmr[index][j]>='A' && grmr[index][j]<='Z')
{
printf("\n Capital arrived");
getche();
index=findVar(grmr[index][j],lhs);
recurPrint(lhs,grmr,index,0);
}
else if(grmr[index][j]>='a' && grmr[index][j]<='z')
{
printf("\n Small arrived with j as:%d",j);
getche();
printf("%c",grmr[index][j]);
j++;
recurPrint(lhs,grmr,index,j);
}
}

The O/P I am getting for the input mentioned above is :
Start of function Rep
Index is:0
With j is:0
Capital arrived
Start of function Rep
Index is:1
With j is:0
Small arrived with j as:0 b
Start of function Rep
Index is:1
With j is:1
Small arrived with j as:1 c
Start of function Rep
Index is:1
With j is:2
Small arrived with j as:2 d
Start of function Rep
Index is:1
With j is:3

that is just bcd.I need bcdefghij .Please help me

 

[Barry Schwarz]

The Problem is CFG grammar generation
Eg:
Input S->ABC
A->bcd
B->efg
C->hij
It should produce the o/p bcdefghij substituting for every Capitals
found on the way recursively

The C pgm I wrote was:
#include<stdio.h>
#include<conio.h>

To maximize the chances of getting help here, it is best to restrict
your code to standard C. Not all of us have this non-standard header
and for those that do it may not contain the same code as yours.

int main()
{
int recurPrint(char[15],char[][50],int,int);
int findVar(char,char[]);

Because these declarations are inside main, they go out of scope at
the end of main.

char stack[50];
char grmr[15][50];
char lhs[15],ch;
int i=0;
clrscr();

This serves no purpose. Many here have voiced the opinion that your
code should not decide whether previous information on my screen is
still useful.

while(1)
{
printf("\n Enter variable:");

Due to the lack of a terminating \n, on some systems this prompt may
not appear until the buffer is flushed. You are left with the system
expecting input and the user confused.

scanf("%c",&lhs);
flushall();

A non-standard function.

printf("\n Enter production:");
gets(grmr);

How do you propose to prevent buffer overflow?

printf("\n Do you want to continue[y/n]:");
ch=getche();

A non-standard function

if(ch=='n'||ch=='N')
break;
++i;
}

How do you prevent the user from inputting more than 15 strings?

lhs[i+1]='\0';

If the user stops after the 15th string, this will invoke undefined
behavior by attempting to set the non-existent object lhs[15].

recurPrint(lhs,grmr,0,0);

getche();
return 0;



}
int findVar(char find,char lhs[])

The only reason recurPrint can recognize findVar as a declared
function is because the definition happens to precede the call. You
should move the declarations out of main and place them at file scope.

{
int i=0;
while(lhs!='\0')
{
if(lhs==find)
return i;
++i;
}

If you reach this point in the code, the function will return without
returning an int. This invokes undefined behavior.

}

int recurPrint(char lhs[],char grmr[][50],int lims,int ji)
{
static int index;
static int j;
index=lims;
j=ji;
printf("\n Start of function Rep");
printf("\n Index is:%d",index);
printf("\n With j is:%d",j);
getche();
if(grmr[index][j]=='\0')
return 0;


else if(grmr[index][j]>='A' && grmr[index][j]<='Z')

Not all character systems make the letters consecutive. Look at the
isupper function to perform this test.

{
printf("\n Capital arrived");
getche();

Is it really your intention to have the user press a key for every
letter being printed?

index=findVar(grmr[index][j],lhs);

You never check if findVar succeeded.

recurPrint(lhs,grmr,index,0);

When this incarnation finally returns (after printing bcd), index is 0
and j is 0. j never gets incremented and you fall out of the
function. You never process the B. Either this block must include
some kind of loop or the calling statement in main needs to iterate
through the desired values of j.

}
else if(grmr[index][j]>='a' && grmr[index][j]<='z')

islower. But then, that prevents the expansion from including any
non-alpha characters, such as numbers. Why not just else?

{
printf("\n Small arrived with j as:%d",j);
getche();
printf("%c",grmr[index][j]);
j++;
recurPrint(lhs,grmr,index,j);
}

Your code definitely reaches this point yet you fail to return the
promised int. This invokes undefined behavior.

}

The O/P I am getting for the input mentioned above is :
Start of function Rep
Index is:0
With j is:0
Capital arrived
Start of function Rep
Index is:1
With j is:0
Small arrived with j as:0 b
Start of function Rep
Index is:1
With j is:1
Small arrived with j as:1 c
Start of function Rep
Index is:1
With j is:2
Small arrived with j as:2 d
Start of function Rep
Index is:1
With j is:3

that is just bcd.I need bcdefghij .Please help me

See the logic error identified in the capitals block.


Remove del for email

 

[smartbeginner]

Excuse me please.I know this isn't standard code.
I compiled this in Turbo c++ and my intention is only to make you
people aware of my problem.
Thats in the recursion function.
Regarding the findVar() funtion:suppose all grammar given and it
correctly returns the value.
Just figure out what should i do in my algorithm for realising the
problem.
The recursion pattern i identified is :
S=ABC giving way to A->bcd and then returning to S=ABC fn and then
checking for B then to B=efg and then returning back to S=ABC's C part
and then to C=hij and finally falling out.

I guess problem is regarding the value of index i am using and its not
properly understood on returning from function.
Is this can be solved using static variables and all.

Help me in this.Please

 

[Ben Bacarisse]

Excuse me please.I know this isn't standard code.
I compiled this in Turbo c++ and my intention is only to make you
people aware of my problem.

I don't know that system, but let me give you another reason why
standard C is better. When I am testing a program I don't want to
have to keep typing at it. I want to put the input into a file like
this:

S->ABC
A->def
B->ghi
D->jkl

so I can test it simply by running:

%> my-program <test-data

Not only is that easier, but so is the input:

while (i < 14 && scanf("%c->%49s\n", &lhs, grmr) == 2) i++;

This is short, relatively clear, tests that the input actually worked
and won't read too many inputs nor overrun any buffers. I count 6
reasons to do it this way.

Thats in the recursion function.

Yes. It is trying to do too much. You are trying to recurse over j
(the string index) *and* into rules when you see a capital letter.
You don't need to use recursion for j. Just use it when you need to
"descend" into a rule.

Regarding the findVar() funtion:suppose all grammar given and it
correctly returns the value.

It takes longer to type this than to add "return -1;" to the function.

Just figure out what should i do in my algorithm for realising the
problem.
The recursion pattern i identified is :
S=ABC giving way to A->bcd and then returning to S=ABC fn and then
checking for B then to B=efg and then returning back to S=ABC's C part
and then to C=hij and finally falling out.

That's good but it is not what you are doing. Loop over the
characters on the right-hand-side (grmr) rather than trying to
re-use the recursion. It will be simpler to get right.

 

[smallcool21]

Excuse me please.I know this isn't standard code.
I compiled this in Turbo c++ and my intention is only to make you
people aware of my problem.

I don't know that system, but let me give you another reason why
standard C is better. When I am testing a program I don't want to
have to keep typing at it. I want to put the input into a file like
this:

S->ABC
A->def
B->ghi
D->jkl

so I can test it simply by running:

%> my-program <test-data

Not only is that easier, but so is the input:

while (i < 14 && scanf("%c->%49s\n", &lhs, grmr) == 2) i++;

This is short, relatively clear, tests that the input actually worked
and won't read too many inputs nor overrun any buffers. I count 6
reasons to do it this way.

Thats in the recursion function.

Yes. It is trying to do too much. You are trying to recurse over j
(the string index) *and* into rules when you see a capital letter.
You don't need to use recursion for j. Just use it when you need to
"descend" into a rule.

Regarding the findVar() funtion:suppose all grammar given and it
correctly returns the value.

It takes longer to type this than to add "return -1;" to the function.

Just figure out what should i do in my algorithm for realising the
problem.
The recursion pattern i identified is :
S=ABC giving way to A->bcd and then returning to S=ABC fn and then
checking for B then to B=efg and then returning back to S=ABC's C part
and then to C=hij and finally falling out.

That's good but it is not what you are doing. Loop over the
characters on the right-hand-side (grmr) rather than trying to
re-use the recursion. It will be simpler to get right.

 

[Ben Bacarisse]

That's good but it is not what you are doing. Loop over the
characters on the right-hand-side (grmr) rather than trying to
re-use the recursion. It will be simpler to get right.

Best not to quote sigs (the part including and after the "-- ")

Then how can I correct this.Why you said i am reusing the recursion?

I don't know who to put it any clearer than the above without writing it
for you (which I don't really want to do). In the recursive function,
use a loop to look at every character. If it is a cap. look it up and
recurse.