3 Replies - 2549 Views - Last Post: 24 March 2014 - 08:20 PM Rate Topic: -----

#1 mr_zebes  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 22-March 14

Recursive descent parser

Posted 22 March 2014 - 10:00 PM

Hi everyone

I am implementing a recursive descent parser that recognizes strings in the language below.

The grammar:
A -> I = E | E
E -> T + E | T - E | T
T -> F * T | F / T | F
F -> P ^ F | P
P -> I | L | UI | UL | (A)
U -> + | - | !
I -> C | CI
C -> a | b | ... | y | z
L -> D | DL
D -> 0 | 1 | ... | 8 | 9

My input file has the following two strings:
a=a+b-c*d
a=a**b++c

The desired output:

String read from file: a=a+b-c*d
The string "a=a+b-c*d" is in the language.
String read from file: a=a**b++c
The string "a=a**b++c" is not in the language.

/** 
    C++ 
  * The Grammar
  * A -> I = E | E 
  *	E -> T + E | T - E | T
  *	T -> F * T | F / T | F
  *	F -> P ^ F | P
  *	P -> I | L | UI | UL | (A)
  *	U -> + | - | !
  *	I -> C | CI
  *	C -> a | b | ... | y | z
  *	L -> D | DL
  *	D -> 0 | 1 | ... | 8 | 9
**/


#include <stdio.h>
#include <fstream>
#include <iostream>
#include <string>

using std::endl;
using std::ifstream;
using std::ios;
using std::ofstream;
using std::string;
using namespace std;

bool A(void);
bool E(void);
bool T(void);
bool F(void);
bool P(void);
bool U(void);
bool I(void);
bool C(void);
bool L(void);
bool D(void);

string s;

bool A(void) 
{

    if (I()) 
	{
        if (s[0] == '=') 
		{
			s = s.substr(1);
            if (E()) 
			{
                return true;
            }
        }
		else
		{		
		return true;
		}
    }
    return false;
}

bool E(void) 
{

    if (T()) 
	{
        if (s[0] == '+' || s[0] == '-') 
		{
            s = s.substr(1);
            if (E()) 
			{
                return true;
            }
        }
        else 
		{
            return true;
        }
    }

    return false;
}

bool T(void) {

    if (F()) 
	{
        if (s[0] == '*' || s[0] == '/')
		{
			s = s.substr(1);
			if (T())
			{
				return true;
			}
		}
		else
		{
			return true;
		}
	}	    
    return false;
}

bool F(void)
{
	if (P())
	{
		if (s[0] == '^')
		{
			s = s.substr(1);
			if (T())
			{
				return true;
			}
		}
		else
		{
			return true;
		}
	}
	return false;
}

bool P(void)
{
	if (I())
	{
		return true;
	}
	else if (L())
	{
		return true;
	}
	else if (U() && I())
	{
		return true;
	}
	else if (U() && L())
	{
		return true;
	}
	else if(s[0] == '(')
	{
		s=s.substr(1);
		if (A())
		{
			if(s[0] == ')')
				s=s.substr(1);
			return true;
		}
	}
	return false;
}

bool U(void)
{
	if (s[0] == '+' || s[0] == '-' || s[0] == '!')
	{
		s=s.substr(1);
		return true;
	}
	return false;
}

bool I(void)
{
	if (C())
	{
		return true;
	}
	else if (C() && I())
	{
		return true;
	}
	return false;
}


bool C(void) {

    if ('a' <= s[0] && s[0] <= 'z') 
	{
        s = s.substr(1);
        return true;
    }
    return false;
}

bool L(void)
{
	if(D())
	{
		return true;
	}
	else if(D() && L())
	{
		return true;
	}
	return false;
}

bool D(void) 
{

    if ('0' <= s[0] && s[0] <= '9') 
	{
        s = s.substr(1);
        return true;
    }

    return false;
}

int main(int argc, char *argv[]) 
{
	s = argc == 2 ? argv[1] : "";
	
	ifstream fin("input.txt");
	string buf;
		
	while (fin >> buf) 
	{
		
	       cout << "The string read from file: ";
               cout << buf << endl;
		for(int i=1; i<argc;i++)
		{
			if (A() && s[i] == s.length()) 
			{
				cout << "The string \"" << argv[i] << "\" is in the language" << endl;
			}
			else 
			{
				cout << "The string \"" << argv[i] << "\" is not in the language" << endl;
			}
		
		}
	}

   	fin.close();
  	getchar();
        return 0;

}


My output shows as follow though:

The string read from file: a=a+b-c*d
The string read from file: a=a**b++c



When I test the code without reading the text file and just write a string in the source code, it appears to parse fine. I believe my main problem is in the int main function and how i am reading the text file and outputting it. I was able to write the same program fine in Java. I am still getting used to using c++. Any tips or pointers would be appreciated.

Is This A Good Question/Topic? 0
  • +

Replies To: Recursive descent parser

#2 Salem_c  Icon User is offline

  • void main'ers are DOOMED
  • member icon

Reputation: 2130
  • View blog
  • Posts: 4,196
  • Joined: 30-May 10

Re: Recursive descent parser

Posted 22 March 2014 - 10:48 PM

135	    else if (U() && I())
136	    {
137	        return true;
138	    }
139	    else if (U() && L())

Look at your U() function. It modifies the state of the parser.
So if it returned true on the first call, then I() returned false, the second call to U() is dealing with a completely different part of the expression.

192	    if(D())
193	    {
194	        return true;
195	    }
196	    else if(D() && L())

If the first call to D() returned true, you get line 194
If the first call to D() returned false, then calling it again will return false as well.
So line 196 will never evaluate to true either.
Was This Post Helpful? 0
  • +
  • -

#3 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2511
  • View blog
  • Posts: 3,985
  • Joined: 21-June 11

Re: Recursive descent parser

Posted 23 March 2014 - 06:58 AM

Why do you print the strings that you read from the file and then check the strings that you got from the command line? Shouldn't you be printing the same strings that you are checking?

Anyway since your loop doesn't seem to run, is it possible that you just didn't specify any command line arguments?
Was This Post Helpful? 0
  • +
  • -

#4 mr_zebes  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 22-March 14

Re: Recursive descent parser

Posted 24 March 2014 - 08:20 PM

Thanks fellas. I've done some revisions. Output is okay now.

Still trying to figure out case for P,I,L. Trying to get the string "a+b" to be read and know its in the language.

bool P(void)
{
	if (I())
	{
		return true;
	}
	else if (L())
	{
		return true;
	}
	else if(U())
	{
		if (I() || L())
		{
			return true;
		}
	}
		else if (I())
		{
			return true;
		}
		else if(L())
		{
			return true;
		}
		else if(s[0] == '(')
		{
			s=s.substr(1);
			if (A())
			{
				if(s[0] == ')')
					s=s.substr(1);
				return true;
			}
		}
		return false;
}


bool I(void)
{
	if (C())
	{
		return true;
	}
	if (C()) 
	{
		if(I())
		{
			return true;
		}
	}
	return false;
}


bool L(void)
{
	if(D())
	{
		return true;
	}
	if(D())
	{
		if(L())
		{
			return true;
		}
	}
	return false;
}




The string a=a**b++c is not in the language
The string a=a+b-c*d is in the language
The string a=b is in the language
The string a+b is not in the language


Was This Post Helpful? 0
  • +
  • -

Page 1 of 1