MATH 5700 SPRING
2023
LAB 3 INSTRCTIONS
Objective: To write a Recursive Descent parser and
implement it in C
OVERVIEW:
Suppose we need to construct a Recursive Descent
Parser for the following grammar:
G = ({(S,L), {(, ), a, , }, (S →(L) | a; L →L, S} , S)
The above construct is representing the fact that:
(a) Non
terminals are S, L
(b) Terminal
symbols are { (, ), a, ,}
(c) Production
Rules: S →A(L) |a , L →L,S | S}
(d) Start
symbol is S
We can use the above grammar to determine if the
strings (a, (a,a)) and (a, (a(a,a), (a,a))) are acceptable in the grammar.
Note that the grammar has left recursion and we need
to remove it. The following becomes the new grammar:
S →(L) | a
L →S L’
L’ →, SL’ | Ɛ
Below is the C code that can be used to implement a
Recursive Descent parser for the above grammar
/* Recursive Descent Parser for the Expression Grammar:
S → (L) |a
L' →,SL'|ε
L → SL'
Valid inputs: (a,(a,a)) and (a,((a,a),(a,a)))
Invalid inputs:(aa,a)
*/
#include <stdio.h>
#include <string.h>
int S(), Ldash(),
L();
char *ip;
char string[50];
int main()
{
printf("Enter
the string\n");
scanf("%s",
string);
ip = string;
printf("\n\nInput\t\tAction\n
------------------------------\n");
if (S())
{
printf("\n------------------------------------------------\n");
printf("\n
String is successfully parsed\n");
}
else
{
printf("\n
------------------------------------------------\n");
printf("Error
in parsing string\n");
}
}
int L()
{
printf("%s\t\tL →SL' \n", ip);
if (S())
{
if (Ldash())
{
return 1;
}
else
return 0;
}
else
return 0;
}
int Ldash()
{
if (*ip == ',')
{
printf("%s\t\tL' →, SL' \n", ip);
ip++;
if (S())
{
if (Ldash())
{
return 1;
}
else
return 0;
}
else
return 0;
}
else
{
printf("%s\t\tL' →ε \n", ip);
return 1;
}
}
int S()
{
if (*ip == '(')
{
printf("%s\t\tS →(L) \n", ip);
ip++;
if (L())
{
if (*ip == ')')
{
ip++;
return 1;
}
else
return 0;
}
else
return 0;
}
else if (*ip == 'a')
{
ip++;
printf("%s\t\tS →a \n", ip);
return 1;
}
else
return 0;
}
What
you need to do:
1. Type
that code up and run it to make sure that it is doing what it is supposed to do.
Provide the strings in the header of the program when prompted.
2. Use
the logic in that program to design your own Recursive Descent parser in C for
the following grammar:
S →aAB
A →Abc
| b
B →d
3. Make
sure that you choose at least two strings that pass the grammar and one string
that does not pass the grammar just like I did in the model program
4. Submit
both the code and a screen shot of your results for the choice of strings that you
provided.
/******************************************************************************
Online C++ Compiler.
Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.
*******************************************************************************/
#include <stdio.h>
#include <string.h>
char input[100];
int inputIndex = 0;
int error = 0;
void S();
void A();
void B();
void match(char c) {
if(input[inputIndex] == c) {
inputIndex++;
} else {
error = 1;
}
}
void S() {
if(input[inputIndex] == 'a') {
match('a');
A();
B();
} else {
error = 1;
}
}
void A() {
if(input[inputIndex] == 'b') {
match('b');
} else if(input[inputIndex] == 'a') {
match('a');
A();
}
else if(input[inputIndex] == 'c'){
match('c');
A();
} else {
error = 1;
}
}
void B() {
if(input[inputIndex] == 'd') {
match('d');
} else {
error = 1;
}
}
int main() {
// Passes the grammar: "a bd"
strcpy(input, "abd");
inputIndex = 0;
error = 0;
S();
if(inputIndex == strlen(input) && !error) {
printf("Passes the grammar: %s\n", input);
} else {
printf("Does not pass the grammar: %s\n", input);
}
// Passes the grammar: "abcdbc"
strcpy(input, "acbd");
inputIndex = 0;
error = 0;
S();
if(inputIndex == strlen(input) && !error) {
printf("Passes the grammar: %s\n", input);
} else {
printf("Does not pass the grammar: %s\n", input);
}
// Does not pass the grammar: "ab"
strcpy(input, "ab");
inputIndex = 0;
error = 0;
S();
if(inputIndex == strlen(input) && !error) {
printf("Passes the grammar: %s\n", input);
} else {
printf("Does not pass the grammar: %s\n", input);
}
return 0;
}