Solved

implement the construction of Simple LR parsing table

Posted on 2009-04-05
28
7,249 Views
Last Modified: 2012-06-21
I have to implement the construction of Simple LR parsing table, given the grammar productions in a file and then write the SLR table in another file and if possible parse a given string using the table.
I have attached the file specifying the Grammar for which the SLR parsing table has to be constructed
The implementation can be in C or Java
I have the compiler design  2 edition aho lam ullman sethi book where algorithms are given from page 241 to 255 and 1 edition aho sethi ullman from page 217 to 228
if anybody wants soft copy of these books i will be pleased to give
Please help me in this
I have also attached the algorithms necessary.
Simple Googling of SLR parsing construction yields algorithms which are very clear.  
 please help


input.txt
SLR-Parse-Table-Construction-1-.pdf
0
Comment
Question by:majinharish
  • 15
  • 8
  • 5
28 Comments
 
LVL 40

Expert Comment

by:mrjoltcola
Comment Utility
The way I see it, you have things to accomplish other than building the parsing table. You need to parse a grammar yourself and convert it to discrete token values, because a parsing table works (at least traditionally) on integer tokens, not strings.

Which part do you need help with? We cannot do the assignment for you, due to EE rules, but we can answer questions. Have you started a program? Have you an idea of the different phases? Do you even have a program that will read your grammar file?
0
 

Author Comment

by:majinharish
Comment Utility
I have an idea I can do it by hand but i am not able to implement via program
I need help with construction of Simple LR parsing table given the grammar productions in a file
I am not able to implement the closure, goto and to find the sets of items construction my main problem is the position of parser that is . how to implement this.

please help me I am ready to forgo anything for this. please get me started my posting some code for these functions and combining them for building the slr parsing table

if anybody needs the algorithms simple google of construction of slr parsing table will give the algorithms clearly if anybody wants the dragon book that is compilers book I am pleased to upload.

I know how to separate identifiers ,keywords,operators from a file given the productions in a file.I have posted the code.
#include<stdio.h>

#include<conio.h>

#include<string.h>

main()

{

char exp[500];

char op[21]={'+','-','*','/','%','^','[',']','(',')','{','}','=',';','<','>','#',',','&','"','|'};

char keys[30][30]={"if","while","for","do","include","printf","main","void","scanf","getch","int","char","break","continue","case","const","default","else","double","float","void","isaplha","isdigit","strcmp"};

char token[20];

int i,j,pos,k,h,m,len,c=0,g;

FILE *fp;

FILE *fp1;

int p=0;

clrscr();

fp=fopen("C:\\users\\nasch\\data.c","r");

fp1=fopen("C:\\users\\nasch\\result.txt","w");

while(!feof(fp))

{

p++;

if(fgets(exp,500,fp)!=NULL)

{

len=strlen(exp);

for(i=0;i<=len;i++)

{

if(isalpha(exp[i]))

{

pos=i;

g=i;

while(isalpha(exp[g])||isdigit(exp[g]))

g++;

for(j=0;j<20;j++)

token[j]=NULL;

k=0;

for(j=pos;j<g;j++)

{

3

token[k]=exp[j];

k++;

}

c=0;

if((strcmp(token,"stdio")==0)||(strcmp(token,"conio")==0)||(strcmp(token,"string")==0))

{

fprintf(fp1,"%s.h is a header file\n",token);

g=g+2;

}

else

{

fprintf(fp1,"%s",token);

for(m=0;m<30;m++)

{

if(strcmp(token,keys[m])==0)

c++;

}

if(c==0)

fprintf(fp1," - It is a identifier\n");

else

fprintf(fp1," - It is a key word\n");

}

i=g-1;

}

else if(isdigit(exp[i]))

{

while(isdigit(exp[i+1]))

{

fprintf(fp1,"%c",exp[i]);

i++;

}

fprintf(fp1,"%c",exp[i]);

fprintf(fp1," - It is a digit\n");

}

else

{

if(exp[i]=='+'||exp[i]=='-'||exp[i]=='='||exp[i]=='|'||exp[i]=='<'||exp[i]=='>'||exp[i]=='!')

{

4

i++;

if(exp[i]=='+'||exp[i]=='-'||exp[i]=='='||exp[i]=='|')

fprintf(fp1,"%c%c - It is an operator\n",exp[i-1],exp[i]);

else

{

fprintf(fp1,"%c - It is an operator\n",exp[i-1]);

i--;

}

}

else

{

for(h=0;h<21;h++)

{

if(exp[i]==op[h])

{

fprintf(fp1,"%c - It is an operator\n",op[h]);

break;

}

}

}

}

}

}

}

getch();

}

Open in new window

0
 
LVL 40

Expert Comment

by:mrjoltcola
Comment Utility
This is completely unformatted code.  It does not even compile.

You are asking for help on an advanced subject, LR parser generators, and you are posting code that has no indentation code and does not compile.
 
0
 

Author Comment

by:majinharish
Comment Utility
It compiles i just forgot to add <ctype.h> and just a typo mistake was there i corrected now I post after correcting
#include<stdio.h>

#include<conio.h>

#include<string.h>

#include<ctype.h>

void main()

{

char exp[500];

char op[21]={'+','-','*','/','%','^','[',']','(',')','{','}','=',';','<','>','#',',','&','"','|'};

char keys[30][30]={"if","while","for","do","include","printf","main","void","scanf","getch","int","char","break","continue","case","const","default","else","double","float","void","isaplha","isdigit","strcmp"};

char token[20];

int i,j,pos,k,h,m,len,c=0,g;

FILE *fp;

FILE *fp1;

int p=0;

clrscr();

fp=fopen("C:\\users\\nasch\\data.c","r");

fp1=fopen("C:\\users\\nasch\\result.txt","w");

  while(!feof(fp))

{

  p++;

	  if(fgets(exp,500,fp)!=NULL)

	{

	  len=strlen(exp);

 for(i=0;i<=len;i++)

{

	if(isalpha(exp[i]))

  {

	pos=i;

	g=i;

	  while(isalpha(exp[g])||isdigit(exp[g]))

			g++;

		 for(j=0;j<20;j++)

		 token[j]=NULL;

	k=0;

		 for(j=pos;j<g;j++)

	 {

		 token[k]=exp[j];

		 k++;

	 }

		c=0;

	  if((strcmp(token,"stdio")==0)||(strcmp(token,"conio")==0)||(strcmp(token,"string")==0))

	  {

		 fprintf(fp1,"%s.h is a header file\n",token);

		 g=g+2;

	  }

	  else

	  {

		fprintf(fp1,"%s",token);

		for(m=0;m<30;m++)

	  {

		 if(strcmp(token,keys[m])==0)

		  c++;

	  }

 if(c==0)

	fprintf(fp1," - It is a identifier\n");

 else

	fprintf(fp1," - It is a key word\n");

	 }

 i=g-1;

  }

			else if(isdigit(exp[i]))

		{

			  while(isdigit(exp[i+1]))

			{

			  fprintf(fp1,"%c",exp[i]);

			  i++;

			}

	fprintf(fp1,"%c",exp[i]);

	fprintf(fp1," - It is a digit\n");

  }

	else

  {

	 if(exp[i]=='+'||exp[i]=='-'||exp[i]=='='||exp[i]=='|'||exp[i]=='<'||exp[i]=='>'||exp[i]=='!')

	  {

		  i++;

			  if(exp[i]=='+'||exp[i]=='-'||exp[i]=='='||exp[i]=='|')

			  fprintf(fp1,"%c%c - It is an operator\n",exp[i-1],exp[i]);

			  else

			 {

			  fprintf(fp1,"%c - It is an operator\n",exp[i-1]);

			  i--;

			 }

	  }

  else

 {

	for(h=0;h<21;h++)

  {

	  if(exp[i]==op[h])

	 {

		fprintf(fp1,"%c - It is an operator\n",op[h]);

		  break;

	 }

  }

 }

}

}

}

}

getch();

}

Open in new window

0
 

Author Comment

by:majinharish
Comment Utility
please don't forgot my fopen function arguments refers to my system so u have to create a new file and give the new pathname in the arguments same for the other


0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
I'm sorry. I gave up trying to read your code about half way through. It's impossible to read, as the indentation changes with each line in a completely inconsistent way. Please clean up your code - you'll do yourself (and us) a big favor, and make your code a lot easier to read/maintain.

From what I did read, it seems like you have to be able to parse C code. Are you sure that that's what you need to do (not just a small subset of C for example) ? Writing a parser for C is by no means a simple task (especially if you can't make use of parser generators like yacc and lexer generators like lex).

Can you post the exact wording of your assignment ? And also give us a bit of background on your C programming experience ?
0
 

Author Comment

by:majinharish
Comment Utility
In my assignment there is no need to parse C code, All I have to do is construct Simple LR parsing table for a given Grammar production in a file and parse the input string given using the table

I posted the code in reply to expert mrjoltcola who asked to parse a grammer production.

I have modified and again i am posting i have also hand coded the table and parsed the given string that i have attached in a different file I have attached also the grammar productions for which I have to construct Simple LR parsing table.I am not very good in C programming I know the syntax of C well
Please help me in constructing the Simple LR parsing table.
lexC.txt
strparse.txt
input.txt
0
 
LVL 40

Assisted Solution

by:mrjoltcola
mrjoltcola earned 200 total points
Comment Utility
It looks like you are making progress. Since you aren't really asking any specific questions, I don't know what to answer.

Constructing it by hand is tedious, but maybe that is the assignment? Can you clarify for us? Is the assignment to hand-code the parser or to write a parser generator like yacc?

I see you have created the ACTION and GOTO tables, so that is a good start. The approach looks correct. Key is, does it run, and when it does, what does it do?

ACTION table

The action table is for deciding, for the current state and input token, what to do?
a) Should you shift the token?
If shifting (pushing the current input onto the parse stack) allows the parser to keep matching rules and consume tokens, then shift is the choic; shift-reduce parsers are greedy (shift when possible).
b) Should you reduce? That means you leave the input token in the input stream while you pop all off the tokens off the stack that equate to a production. You then push the production's left hand side "token" onto the stack, and consult the GOTO table to find out which state to move to. Then start over, with the same token on the input, which might mean yet another reduce, or might mean a shift.

GOTO table:
Contains the state to move to after executing a reduce (production), given the state that was stored on the stack immediately under the tokens that were popped off for the reduction. Its simply keeping track of where it was when it started the latest set of "shifting".

How are you implementing your stack?
0
 

Author Comment

by:majinharish
Comment Utility
Actually what I have done is I saw the productions i worked in my note how to construct the table though it is there in the book and without constructing the Simple LR parsing table using a C program I have parsed the string using those arrays which I have to actually implement using C program

Could I get back on Friday evening in India time because I have two exams on Thursday and Friday.
0
 

Author Comment

by:majinharish
Comment Utility
There is still the problem of constructing the closure, goto and to find the sets of items construction.
I have not constructed the parsing table i have just used the table in the book and parsed the string

I hope i am clear
0
 

Author Comment

by:majinharish
Comment Utility
I probably need the yacc source code or some Simple LR parser table construction source code
0
 
LVL 40

Expert Comment

by:mrjoltcola
Comment Utility
Well my question is still:

Must you hand-construct a parser, or must you write a parser generator, like yacc?
0
 

Author Comment

by:majinharish
Comment Utility
I can't use Yacc parser. but probably the source code might help me to construct Simple LR parsing table
0
 
LVL 40

Expert Comment

by:mrjoltcola
Comment Utility
Thats not my question.

Which must you implement for your project?
1) A hand-coded parser?
2) A yacc? (parser generator)
0
Top 6 Sources for Identifying Threat Actor TTPs

Understanding your enemy is essential. These six sources will help you identify the most popular threat actor tactics, techniques, and procedures (TTPs).

 

Author Comment

by:majinharish
Comment Utility
I don't get what is hand-coded parser if you mean it is a slr parser which we have to implement on our own  in some programming language then yes

I can't use yacc ( parser generator)
0
 
LVL 40

Expert Comment

by:mrjoltcola
Comment Utility
I didn't ask if you could USE yacc, I asked if you had to _write_ a yacc.

A parser and a parser generator are not the same thing. Believe it or not, some 4th and 5th year students actually do implement "yacc".

But, it sounds like you have to hand-code a parser. I'm glad, at least, as its a much more reasonable task. :)
0
 

Author Comment

by:majinharish
Comment Utility
I am in second year engineering, could you help me now how to proceed in this SLR table construction
0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
Maybe if you posted the exact wording of your assignment (like I asked earlier), we could avoid all this confusion about what actually needs to be done.

Could you do that ?


You mention that you don't have to parse C, but the code you posted starts out by doing exactly that (it seems to try to parse C standard headers like stdio.h etc., and try to match C specific keywords like if, while, etc.) ... So, you can understand my confusion.
0
 

Author Comment

by:majinharish
Comment Utility
I actually have done that in response to expert mrjoltcola who asked me if i could parse a general grammar that's what i understood so I took C generally and i did that

I told my madam that i am unable to do and i showed her what i had done so she now asks me to do using YACC.
I have never used it, I just know it is a parser generator I will try to find information on it with the books available with me i have to do it on Friday as i have two exams

Sorry if i am not clear with my question,as well with YACC as I didn't know what it was sorry for my ignorance.I have posted again the question.

Implement the construction of SLR Parsing table for a given Grammar productions given in a file and then parse the input string using the table.You can use YACC that's what she told me today.
I think YACC uses LALR parsing table so please forgive me if there is anything wrong with my understanding of the question.
 
0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
>> Implement the construction of SLR Parsing table for a given Grammar productions given in a file and then parse the input string using the table.

Is this file of "grammar productions" fixed, or does your program have to be able to support any such file that is passed to it as argument ?
If it's fixed, then can you post it ? If not, then you need to at least know the format of the file.

If I understand the assignment correctly, then I'm not sure whether yacc would help you here, as it seems this is simply an exercise of implementing a few simple grammar rules as an SLR  parser.


Now, I'll assume (correct me if I'm wrong) that you need to implement it for these rules :

        E'->E              //This is augmentation for this grammar
        E->E+T
        E->T
        T->T*F
        T->F
        F->(E)
        F->id

and that 'id' is defined as an easily recognizable series of characters (like alphanumeric "words", separated by whitespace). Is that right ?

If so, what you have to do, is construct the parse table for the above rules, and implement it so it can be used by your code. Then you simply read the input data, get the different tokens from it (id's), and use the parse table to match the rules.
0
 

Author Comment

by:majinharish
Comment Utility
Actually my problem is i am not experienced to implement the construction of SLR parsing table even for the fixed productions in a file the same productions you have given and let id be defined as only digits.
the problem of constructing the closure, goto and to find the sets of items construction is proving difficult for me because of use of recursive functions and finding insufficient time because of other subjects.

So I have asked madam to do something and I asked her if i could use YACC, she replied yes. Now if i am using YACC and if the productions are fixed then i don't think the project will be worth so i assume they are not fixed and they could give any grammar production in the file.



0
 
LVL 40

Expert Comment

by:mrjoltcola
Comment Utility
>>So I have asked madam to do something and I asked her if i could use YACC, she replied yes. Now if i am using YACC and if the productions are fixed then i don't think the project will be worth so i assume they are not fixed and they could give any grammar production in the

She may mean that you may use YACC to construct the parser for the grammar file itself, but not the target input. But you still have to create the parsing table. What do you think? Can you she clarify?
0
 

Author Comment

by:majinharish
Comment Utility
I do not know anything about YACC to be frank and I am not able to understand your question forgive me if i am ignorant, Actually thanks to you that is why i asked if i could use YACC and she told yes though she did not agree first.
0
 
LVL 40

Expert Comment

by:mrjoltcola
Comment Utility
>>I do not know anything about YACC to be frank and I am not able to understand your question forgive me if i am ignorant

Nothing wrong with ignorance, we are all ignorant of many things.

However, I feel that this subject level is overly advanced for your current skill level in C and Yacc. I am surprised that you are given such an advanced task as a year 2 engineering student. I do not suggest that you should give up, but given the constraints of Experts Exchange, I cannot give you code to start with. So I advise you to seek assistance from your Professor or Madam on this, and return to us when you have a clearer understanding of both the problem and the tools to use to accomplish it, and give us a place to start so that we can help you.

Good luck.
0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
>> Actually my problem is i am not experienced to implement the construction of SLR parsing table

You mentioned earlier that you could do it on paper.
If you know how to do it on paper, then you know how to do it in code. Just take it step by step. Start by constructing the parse table based on the given rules. Can you do that, and post it here ?
0
 

Author Comment

by:majinharish
Comment Utility
Sorry I had exam so could not reply quicker, Doing them by hand is easy the book tells first compute closure, In paper we follow the steps , there is initialization , we list the productions the .(dot) means the position of parser and recursive means we do it again and again till some condition. It is easy, Now you try to implement this using C code I know for you experts it is piece of cake but for me I have a mind block to be frank no time also and then combining each of these type functions so that they produce the table for me looks very tough, I know we have to split them into modules ,etc but still.

So that's why I think i'l use YACC. First i will read about it and then come back here

I have another exam so i will read on Friday. Please remember me when I get back here.
0
 
LVL 53

Accepted Solution

by:
Infinity08 earned 300 total points
Comment Utility
>> Doing them by hand is easy
>> In paper we follow the steps

It's not harder in code than on paper :) You follow the same steps, in the same way. The only difference is that you use the C language.


>> no time also

Time is something we can't give you. So, you'll have to find/make the time to do this. We're here to assist you.


>> but for me I have a mind block

That's why you need to do things one small step at a time. As I suggested earlier. Can you start by constructing the parse table based on the given rules, and post it here ? Once you have that, you can start putting it in code.
0
 

Author Comment

by:majinharish
Comment Utility
the advice helps a lot and i am surely going to give a try in the summer.
I have to submit it by Monday so now i don't think i can start from scratch. I have downloaded parser generator from the link     http://www.bumblebeesoftware.com/downloads.htm

the readme file i have attached the two things it says is this
the Parser Generator versions of YACC and Lex
"      Generate C, C++ and Java parsers and lexical analysers.
"      AYACC can generate LALR(1), CLR(1) and SLR(1) parsers

i didn't understand much.I am still reading lex and yacc orielly book


ReadMe.doc
0

Featured Post

How to improve team productivity

Quip adds documents, spreadsheets, and tasklists to your Slack experience
- Elevate ideas to Quip docs
- Share Quip docs in Slack
- Get notified of changes to your docs
- Available on iOS/Android/Desktop/Web
- Online/Offline

Join & Write a Comment

An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use switch statements in the C programming language.

771 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

7 Experts available now in Live!

Get 1:1 Help Now