C
| Created by | Borhan |
|---|---|
| Last edited time | |
| Tag |
// Windows Flex
flex t.l
gcc lex.yy.c
a.exe
// Linux Flex
flex t.l
gcc lex.yy.c
./a.out
// Windows (YACC)
bison -dy y.y
flex y.y
gcc lex.yy.c y.tab.c
a.exe
// Linux (YACC)
bison -dy y.y
flex y.y
gcc lex.yy.c y.tab.c
./a.out
- Write a C program to handle errors in lexical analysis phase (See Lecture-3 for more
examples)
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <ctype.h>
#define MAX_LINES 5
#define MAX_LINE_LENGTH 100
#define MAX_ARRAY_SIZE 500
bool keyword(char *token)
{
char keywords[32][10] = {
"auto", "break", "case", "char", "const", "continue", "default",
"do", "double", "else", "enum", "extern", "float", "for", "goto",
"if", "int", "long", "register", "return", "short", "signed", "sizeof",
"static", "struct", "switch", "typedef", "union", "unsigned", "void",
"volatile", "while"};
for (int i = 0; i < 32; i++)
{
if (strcmp(token, keywords[i]) == 0)
{
return true;
}
}
return false;
}
bool isValidIdentifier(char *token)
{
if (!isalpha(token[0]) && token[0] != '_')
{
return false;
}
for (int i = 1; token[i] != '\0'; i++)
{
if (!isalnum(token[i]) && token[i] != '_')
{
return false;
}
}
return true;
}
bool isStringLiteral(char *token)
{
return (token[0] == '"' && token[strlen(token) - 1] == '"');
}
// Function to tokenize and analyze the input string
void lexicalAnalysis(char result[MAX_ARRAY_SIZE])
{
char *token = strtok(result, " \t\n\r{}()\";"); // Split by space, tab, newline, carriage return, and parentheses/braces/quotes/semicolon
while (token != NULL)
{
if (strcmp(token, "(") == 0 || strcmp(token, ")") == 0 || strcmp(token, "{") == 0 || strcmp(token, "}") == 0)
{
}
else if (keyword(token))
{
}
else if (isdigit(token[0]))
{
}
else if (isValidIdentifier(token))
{
}
else if (isStringLiteral(token))
{
}
else
{
printf("Lexical error! Invalid token: %s\n", token);
return;
}
token = strtok(NULL, " \t\n\r{}()\";");
}
printf("No lexical errors found!\n");
}
int main()
{
char result[MAX_ARRAY_SIZE] = "";
char buffer[MAX_LINE_LENGTH];
printf("Enter up to %d lines (type 'STOP' to end early):\n", MAX_LINES);
for (int i = 0; i < MAX_LINES; i++)
{
if (fgets(buffer, MAX_LINE_LENGTH, stdin) != NULL)
{
size_t len = strlen(buffer);
if (len > 0 && buffer[len - 1] == '\n')
{
buffer[len - 1] = '\0';
}
if (strcmp(buffer, "STOP") == 0)
{
break;
}
if (strlen(result) + len < MAX_ARRAY_SIZE)
{
strcat(result, buffer);
strcat(result, " ");
}
else
{
printf("Error: Result array is full!\n");
break;
}
}
}
// Perform lexical analysis
lexicalAnalysis(result);
return 0;
}
/*
Input:
int main()
{
printf(“HI”); $
Return 0;
}
*/
- Write a C program that accept integer and floating-point numbers with exponentiation.
// From Shoikot
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int isDigit(char c) {
return (c >= '0' && c <= '9');
}
void accept () {
printf("Accepted!!\n"); exit(0);
}
void state18(char s[], int ptr) {
if(strlen(s) == ptr) accept();
if(isDigit(s[ptr])) state18(s, ptr + 1);
}
void state17(char s[], int ptr) {
if(strlen(s) == ptr) return;
if(isDigit(s[ptr])) state18(s, ptr + 1);
}
void state16(char s[], int ptr) {
if(strlen(s) == ptr) return;
if(isDigit(s[ptr])) state18(s, ptr + 1);
else if(s[ptr] == '+' || s[ptr] == '-') state17(s, ptr + 1);
}
void state15(char s[], int ptr) {
if(strlen(s) == ptr) accept();
if(isDigit(s[ptr])) state15(s, ptr + 1);
else if(s[ptr] == 'E') state16(s, ptr + 1);
}
void state14(char s[], int ptr) {
if(strlen(s) == ptr) return;
if(isDigit(s[ptr])) state15(s, ptr + 1);
}
void state13(char s[], int ptr) {
if(strlen(s) == ptr) accept();
if(isDigit(s[ptr])) state13(s, ptr + 1);
else if(s[ptr] == '.') state14(s, ptr + 1);
else if(s[ptr] == 'E') state16(s, ptr + 1);
}
int main()
{
printf("Enter a number: ");
char s[100]; scanf("%s", s);
int n = strlen(s);
if(isDigit(s[0])) state13(s, 1);
printf("Rejected!!\n");
return 0;
}
// ChatGPT
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define MAX_LENGTH 10
void checkNumber(char *str)
{
int i = 0;
int dot = 0;
int e = 0;
int possible = 1;
while (i < strlen(str))
{
if (i == 0 & !isdigit(str[i]))
{
possible = 0;
break;
}
else if (str[i] == '.')
{
if (dot == 1 || e == 1)
{
possible = 0;
break;
}
dot = 1;
}
else if (str[i] == 'E')
{
if (e == 1)
{
possible = 0;
break;
}
e = 1;
if (i + 1 < strlen(str) && (str[i + 1] == '+' || str[i + 1] == '-'))
{
if (i + 2 >= strlen(str) || !isdigit(str[i + 2]))
{
possible = 0;
break;
}
i++;
}
else if (i + 1 >= strlen(str) || !isdigit(str[i + 1]))
{
possible = 0;
break;
}
}
else if (!isdigit(str[i]))
{
possible = 0;
break;
}
i++;
}
if (possible)
{
printf("Accepted!!\n");
}
else
{
printf("Rejected!!\n");
}
}
int main()
{
while (1)
{
char str[MAX_LENGTH];
printf("(Write 'STOP' to end the program)\n");
printf("Enter a number:\n");
scanf("%s", str);
if (strcmp(str, "STOP") == 0)
{
break;
}
checkNumber(str);
}
}
- Write a C program to find epsilon closure of an NFA
// CPP from Soikot
#include <bits/stdc++.h>
using namespace std;
/*
Input:
q0 e q1
q1 e q2
q2 a q3
q0 b q4
q4 e q1
*/
map<char, set<char>> mp;
set<char> states;
set<char> e_closure;
void transition(char state) {
if(e_closure.count(state)) return;
e_closure.insert(state);
for(char s : mp[state]) {
transition(s);
}
}
int main()
{
char state, t, dstate;
while(cin >> state >> t >> dstate) {
states.insert(state); states.insert(dstate);
if(t != 'e' or state == dstate) continue;
mp[state].insert(dstate);
}
cout << "No of states: " << states.size() << endl;
cout << "States are:\n";
for(char c : states) cout << c << endl;
for(char state : states) {
e_closure.clear();
transition(state);
cout << "Epsilon closure of (" << state << ") = { ";
for(char c : e_closure) cout << c << " ";
cout << "}\n";
}
return 0;
}
/*
Enter number of production :3
S=ictSR
R=eS
R=N
*/
#include<bits/stdc++.h>
using namespace std;
string s[10];
int n;
vector<char>first[10],follow[10];
map<char,int>mp;
map<int,char>mm;
void cal_first(int idx,int cnt)
{
for(int i=1; i<=n; i++)
{
if(s[i][0]==s[idx][0])
{
char ch=s[i][2];
first[cnt].push_back(ch);
}
}
}
void process_first(int cnt)
{
// cout<<"cnt "<<cnt<<endl;
// for(int i=1;i<=cnt;i++)
// {
// for(auto it:first[i])
// cout<<it<<" ";
// cout<<endl;
// }
for(int i=cnt;i>=1;i--)
{
for(int j=0;j<first[i].size();j++)
{
if(isupper(first[i][j]))
{
first[i].erase(first[i].begin()+j);
int p=mp[first[i][j]];
for(auto itt:first[p])
first[i].push_back(itt);
}
}
}
for(int i=1;i<=cnt;i++)
{
cout<<"First "<<mm[i]<<" = ";
for(auto it:first[i]){
if(isupper(it))
continue;
cout<<it<<" ";
}
cout<<endl;
}
}
void cal_follow(int idx,int cnt)
{
for(int i=1;i<=n;i++)
{
for(int j=2;j<s[i].size();j++)
{
if(s[i][j]==s[idx][0])
{
if(j==s[i].size()-1)
{
if(s[i][j]!=s[i][0])
follow[cnt].push_back(s[i][0]);
}
else if( isupper(s[i][j+1]))
{
// cout<<"else if "<<mm[cnt]<<" "<<s[i][0]<<" "<<s[i][j+1]<<endl;
for(auto it:first[mp[s[i][j+1]]]){
// cout<<it<<endl;
if(it=='n')
{
if(s[i][j]!=s[i][0])
follow[cnt].push_back(s[i][0]);
continue;
}
else{
if(count(follow[cnt].begin(),follow[cnt].end(),it)==0)
follow[cnt].push_back(it);
}
}
}
else
{
follow[cnt].push_back(s[i][j+1]);
}
}
}
}
}
void process_follow(int cnt)
{
// cout<<"cnt "<<cnt<<endl;
for(int i=1;i<=cnt;i++)
{
//cout<<mm[i]<<endl;
for(int j=0;j<follow[i].size();j++)
{
if(isupper(follow[i][j]))
{
//cout<<"follow "<<follow[i][j]<<endl;
follow[i].erase(follow[i].begin()+j);
int p=mp[follow[i][j]];
for(auto itt:follow[p])
follow[i].push_back(itt);
}
}
}
for(int i=1;i<=cnt;i++)
{
cout<<"Follow "<<mm[i]<<" = ";
for(auto it:follow[i]){
if(isupper(it))
continue;
cout<<it<<" ";
}
cout<<endl;
}
}
int main()
{
cout<<"Enter number of production :";
cin>>n;
for(int i=1; i<=n; i++)
cin>>s[i];
map<char,int>isDone,isFollow;
int cnt=0;
for(int i=1; i<=n; i++)
{
if(isDone[s[i][0]]==0)
{
cnt++;
mp[s[i][0]]=cnt;
mm[cnt]=s[i][0];
cal_first(i,cnt);
isDone[s[i][0]]=1;
}
}
process_first(cnt);
int cn=0;
for(int i=1; i<=n; i++)
{
if(isFollow[s[i][0]]==0)
{
cn++;
cal_follow(i,cn);
isFollow[s[i][0]]=1;
}
}
follow[1].push_back('$');
process_follow(cn);
}
- Write a Lex program that recognizes integer, floating-point numbers, and floating-point number with exponentiation (use transition diagram).
%{
#include <stdio.h>
%}
digit [0-9]
letter [a-zA-Z]
%%
{digit}+ { printf("%s: Integer number\n", yytext); }
{digit}+"."{digit}+ { printf("%s: Floating point number\n", yytext); }
{digit}+"."{digit}+"E"([+-]?{digit}+) { printf("%s: Floating point number with exponentiation\n", yytext); }
{digit}+"E"([+-]?{digit}+) { printf("%s: Floating point number with exponentiation\n", yytext); }
{letter}+ { printf("%s: Not a number\n", yytext); }
. { /* Ignore other characters */ }
%%
int main() {
printf("Enter a number: ");
yylex(); // Perform lexical analysis
return 0;
}
int yywrap(){
return 1;
}
- Write a Lex program that counts characters, words and lines in a given input.
// Soikot
%{
int words = 0, characters = 0, lines = 0;
%}
%%
[a-zA-Z_][a-zA-Z0-9_]* { words++; characters += yyleng; }
[ \t] { characters++; }
\n { lines++; }
[0-9]+ { characters += yyleng; }
[(){}<>;=+\-*/] { characters++; }
. { characters++; }
%%
int yywrap() {
return 1;
}
int main(void) {
yylex();
printf("Character: %d, Word: %d, Line: %d\n", characters, words, lines);
return 0;
}%{
#include <stdio.h>
int char_count = 0; // Count of characters
int word_count = 0; // Count of words
int line_count = 0; // Count of lines
// Define the yywrap function to avoid the undefined reference error.
int yywrap(void) {
return 1; // Return 1 indicates end of input
}
%}
%%
\n { line_count++; } // Increment line count on newline
[ \t] { char_count++; } // Space and tab count as characters
[a-zA-Z0-9]+ { word_count++; char_count += yyleng; } // Word count and character count
. { char_count++; } // Any other character count
%%
int main() {
printf("Enter text (Ctrl+D or Ctrl+Z to end):\n");
int result = yylex(); // Perform lexical analysis
// Output the counts after processing input
printf("\nLines: %d\n", line_count);
printf("Words: %d\n", word_count);
printf("Characters: %d\n", char_count);
return 0;
}
- Install flex in your pc. Please follow the guidelines provided in Lab slides. Then run the following
code:
%%
[\t ]+ /* Ignore Whitespace */;
[+-]?[0-9]+(\.[0-9]+)?([eE][+-]?[0-9]+)? printf(" %s:number", yytext);
[a-zA-Z]+ printf(" %s:NOT number", yytext);
%%
int yywrap(){
return 1;
}
main()
{
yylex();
}
%%
[ \t]+ /* Ignore Whitespace */;
[+-]?[0-9]+(\.[0-9]+)?([eE][+-]?[0-9]+)? printf("%s:number", yytext);
[a-zA-Z]+ printf(" %s:NOT number", yytext);
%%
int yywrap(){
return 1;
}
int main()
{
yylex();
return 0;
}
- Write a C program that recognizes integer, floating-point numbers, and floating-point number with exponentiation. (using transition diagram)
// Soikot
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int isDigit(char c) {
return (c >= '0' && c <= '9');
}
void accept (const char *s) {
printf("%s\n", s); exit(0);
}
void state18(char s[], int ptr) {
if(strlen(s) == ptr) accept("Floating point number with exponentiation");
if(isDigit(s[ptr])) state18(s, ptr + 1);
}
void state17(char s[], int ptr) {
if(strlen(s) == ptr) return;
if(isDigit(s[ptr])) state18(s, ptr + 1);
}
void state16(char s[], int ptr) {
if(strlen(s) == ptr) return;
if(isDigit(s[ptr])) state18(s, ptr + 1);
else if(s[ptr] == '+' || s[ptr] == '-') state17(s, ptr + 1);
}
void state15(char s[], int ptr) {
if(strlen(s) == ptr) accept("Floating point number");
if(isDigit(s[ptr])) state15(s, ptr + 1);
else if(s[ptr] == 'E') state16(s, ptr + 1);
}
void state14(char s[], int ptr) {
if(strlen(s) == ptr) return;
if(isDigit(s[ptr])) state15(s, ptr + 1);
}
void state13(char s[], int ptr) {
if(strlen(s) == ptr) accept("Integer number");
if(isDigit(s[ptr])) state13(s, ptr + 1);
else if(s[ptr] == '.') state14(s, ptr + 1);
else if(s[ptr] == 'E') state16(s, ptr + 1);
}
int main()
{
printf("Enter a number: ");
char s[100]; scanf("%s", s);
int n = strlen(s);
printf("%s: ", s);
if(isDigit(s[0])) state13(s, 1);
printf("Not a number\n");
return 0;
}
6. Write a Lex program that returns token type in a given input.
Input:
int a=2+b;
Output:
int: Integer
a: Identifier
=: Assignment Operator
2: digit
+: plus
b: Identifier
;: Semicolon
%{
#include <stdio.h>
#include <string.h>
%}
%%
int { printf("%s: Integer\n", yytext); }
[a-zA-Z_][a-zA-Z0-9_]* { printf("%s: Identifier\n", yytext); }
[=] { printf("%s: Assignment Operator\n", yytext); }
[0-9]+ { printf("%s: digit\n", yytext); }
[+] { printf("%s: plus\n", yytext); }
[-] { printf("%s: minus\n", yytext); }
[;] { printf("%s: Semicolon\n", yytext); }
[ \t\n]+ ; // Ignore whitespace
. { printf("%s: Unknown token\n", yytext); }
%%
int main() {
printf("Enter input: \n");
yylex();
return 0;
}
int yywrap() {
return 1;
}
// V2
%{
#include <stdio.h>
%}
%%
[0-9]+ { printf("%s: Integer number\n", yytext); }
[0-9]+\.[0-9]+ { printf("%s: Floating point number\n", yytext); }
[0-9]+\.[0-9]+[E][+-]?[0-9]+ { printf("%s: Floating point number with exponentiation\n", yytext); }
[a-zA-Z]+ { printf("%s: Not a number\n", yytext); }
. { printf("%s: Not a number\n", yytext); }
%%
int yywrap() {
return 1; // Indicates no more input.
}
int main() {
printf("Enter a number: ");
yylex();
return 0;
}
- Write a C program to compute FIRST and FOLLOW for the following grammar:
S -> iCtSS’
S’ -> eS|N
Where N is a null character.
// Soikot
/*
Input:
S -> AB
A -> a | N
B -> b | N
*/
#include <bits/stdc++.h>
using namespace std;
bool isTerminal(char c) {
return !(c >= 'A' and c <= 'Z' and c != 'N');
}
struct Grammar {
map<char, vector<string>> productions;
map<char, set<char>> first_sets;
map<char, set<char>> follow_sets;
char start_symbol;
set<char> non_terminals;
void add_production(char nonTerminal, string production) {
productions[nonTerminal].push_back(production);
non_terminals.insert(nonTerminal);
}
void set_start_symbol(char symbol) {
start_symbol = symbol;
non_terminals.insert(symbol);
}
set<char> calculate_first(char symbol) {
if (first_sets.count(symbol)) {
return first_sets[symbol];
}
set<char> first;
if (isTerminal(symbol)) {
first.insert(symbol);
} else {
for (const string& production : productions[symbol]) {
for (char c : production) {
set<char> c_first = calculate_first(c);
first.insert(c_first.begin(), c_first.end());
if (c_first.count('N') == 0) {
break;
}
}
}
}
first_sets[symbol] = first;
return first;
}
void calculate_follow() {
follow_sets[start_symbol].insert('$');
bool changed = true;
while (changed) {
changed = false;
for (const auto& p : productions) {
char A = p.first;
for (const string& production : p.second) {
for (int i = 0; i < production.length(); i++) {
char B = production[i];
if (non_terminals.count(B)) {
set<char> first_beta;
if (i < production.length() - 1) {
first_beta = calculate_first(production[i + 1]);
} else {
first_beta.insert('N');
}
for (char b : first_beta) {
if (b != 'N') {
if (follow_sets[B].insert(b).second) {
changed = true;
}
} else {
for (char f : follow_sets[A]) {
if (follow_sets[B].insert(f).second) {
changed = true;
}
}
}
}
}
}
}
}
}
}
};
string get_next(int &i, string &line) {
string str;
while(line[i] == ' ') ++i;
while(i < line.size() and line[i] != '|') {
str.push_back(line[i]); ++i;
}
++i;
while(str.back() < '(' or str.back() == ' ') str.pop_back();
return str;
}
int main() {
Grammar grammar;
string line; char _start = 'N';
while(getline(cin, line)) {
if(_start == 'N') { _start = line[0]; }
int i = 2;
while(line[i-1] != '>') i++;
while(i < line.size()) {
string str = get_next(i, line);
grammar.add_production(line[0], str);
}
}
grammar.set_start_symbol(_start);
for (auto& p : grammar.productions) {
grammar.calculate_first(p.first);
}
grammar.calculate_follow();
for (auto& p : grammar.first_sets) {
if (grammar.non_terminals.count(p.first)) {
cout << "First(" << p.first << "): { ";
for (char c : p.second) {
cout << c << ", ";
}
cout << "}" << endl;
}
}
cout << endl;
for (auto& p : grammar.follow_sets) {
if (grammar.non_terminals.count(p.first)) {
cout << "Follow(" << p.first << "): { ";
for (char c : p.second) {
cout << c << ", ";
}
cout << "}" << endl;
}
}
return 0;
}
// Accuaracy kom
#include <bits/stdc++.h>
using namespace std;
string productions[10];
int numProductions;
vector<char> firstSet[10], followSet[10];
map<char, int> nonTerminalIndex;
map<int, char> indexToNonTerminal;
void calculateFirstSet(int productionIndex, int currentCount) {
for (int i = 1; i <= numProductions; i++) {
if (productions[i][0] == productions[productionIndex][0]) {
char symbol = productions[i][2];
firstSet[currentCount].push_back(symbol);
}
}
}
void processFirstSet(int totalNonTerminals) {
for (int i = totalNonTerminals; i >= 1; i--) {
for (int j = 0; j < firstSet[i].size(); j++) {
if (isupper(firstSet[i][j])) {
firstSet[i].erase(firstSet[i].begin() + j);
int pos = nonTerminalIndex[firstSet[i][j]];
for (auto terminal : firstSet[pos])
firstSet[i].push_back(terminal);
}
}
}
for (int i = 1; i <= totalNonTerminals; i++) {
cout << "First(" << indexToNonTerminal[i] << ") = ";
for (auto symbol : firstSet[i]) {
if (isupper(symbol))
continue;
cout << symbol << " ";
}
cout << endl;
}
}
void calculateFollowSet(int productionIndex, int currentCount) {
for (int i = 1; i <= numProductions; i++) {
for (int j = 2; j < productions[i].size(); j++) {
if (productions[i][j] == productions[productionIndex][0]) {
if (j == productions[i].size() - 1) {
if (productions[i][j] != productions[i][0])
followSet[currentCount].push_back(productions[i][0]);
}
else if (isupper(productions[i][j + 1])) {
for (auto symbol : firstSet[nonTerminalIndex[productions[i][j + 1]]]) {
if (symbol == 'n') {
if (productions[i][j] != productions[i][0])
followSet[currentCount].push_back(productions[i][0]);
continue;
}
else {
if (count(followSet[currentCount].begin(), followSet[currentCount].end(), symbol) == 0)
followSet[currentCount].push_back(symbol);
}
}
}
else {
followSet[currentCount].push_back(productions[i][j + 1]);
}
}
}
}
}
void processFollowSet(int totalNonTerminals) {
for (int i = 1; i <= totalNonTerminals; i++) {
for (int j = 0; j < followSet[i].size(); j++) {
if (isupper(followSet[i][j])) {
followSet[i].erase(followSet[i].begin() + j);
int pos = nonTerminalIndex[followSet[i][j]];
for (auto terminal : followSet[pos])
followSet[i].push_back(terminal);
}
}
}
for (int i = 1; i <= totalNonTerminals; i++) {
cout << "Follow(" << indexToNonTerminal[i] << ") = ";
for (auto symbol : followSet[i]) {
if (isupper(symbol))
continue;
cout << symbol << " ";
}
cout << endl;
}
}
int main() {
cout << "Enter number of productions: ";
cin >> numProductions;
for (int i = 1; i <= numProductions; i++)
cin >> productions[i];
map<char, int> processedFirst, processedFollow;
int nonTerminalCount = 0;
// Calculate First sets
for (int i = 1; i <= numProductions; i++) {
if (processedFirst[productions[i][0]] == 0) {
nonTerminalCount++;
nonTerminalIndex[productions[i][0]] = nonTerminalCount;
indexToNonTerminal[nonTerminalCount] = productions[i][0];
calculateFirstSet(i, nonTerminalCount);
processedFirst[productions[i][0]] = 1;
}
}
processFirstSet(nonTerminalCount);
int followSetCount = 0;
// Calculate Follow sets
for (int i = 1; i <= numProductions; i++) {
if (processedFollow[productions[i][0]] == 0) {
followSetCount++;
calculateFollowSet(i, followSetCount);
processedFollow[productions[i][0]] = 1;
}
}
followSet[1].push_back('$');
processFollowSet(followSetCount);
return 0;
}
- Write a C program to eliminate left recursion from the following grammar:
E -> E+T|T
T -> T*F|F
F -> (E)|id
// V2 from Soikot
#include <bits/stdc++.h>
using namespace std;
/*
Input:
S -> S a | b
A -> A c | d
*/
struct Grammar {
string nonTerminal;
vector<string> productions;
};
void RemoveWhiteSpace(string &s) {
string t;
for(char c : s) if(c != ' ') t.push_back(c);
s = t;
}
string get_next(int &i, string &line) {
string str;
while(i < line.size() and line[i] != '|') {
str.push_back(line[i]); ++i;
}
++i;
return str;
}
void Replace(Grammar &replace, vector<string> productions, int k) {
string alpha = replace.productions[k].substr(1);
replace.productions.erase(replace.productions.begin() + k);
for(string P : productions) {
replace.productions.insert(replace.productions.begin() + k, P + alpha);
++k;
}
}
void RemoveImmediate(Grammar eliminated[], Grammar &replaced_production, int &eN) {
vector<string> alpha, beta;
for(string P : replaced_production.productions) {
if(P[0] == replaced_production.nonTerminal[0]) alpha.push_back(P.substr(1));
else beta.push_back(P);
}
if(alpha.size() == 0) return void();
replaced_production.productions.clear();
for(string B : beta) replaced_production.productions.push_back(B + replaced_production.nonTerminal[0] + "'");
eN += 1; eliminated[eN].nonTerminal = replaced_production.nonTerminal + "'";
for(string A : alpha) eliminated[eN].productions.push_back(A + replaced_production.nonTerminal[0] + "'");
eliminated[eN].productions.push_back("e");
}
int main ()
{
Grammar rules[100]; int N = 0;
string line;
printf("Enter the Grammar Rules:\n");
while(getline(cin, line)) {
RemoveWhiteSpace(line);
rules[N].nonTerminal = line[0];
int i = 3;
while(i < line.size()) {
rules[N].productions.push_back(get_next(i, line));
}
N += 1;
}
Grammar eliminated[100]; int eN = 0;
for(int i = 0; i < N; i++) {
eliminated[eN] = rules[i];
for(int j = 0; j < eN; j++) {
if(eliminated[j].nonTerminal.size() > 1) continue;
for(int k = 0; k < eliminated[eN].productions.size(); k++) {
if(eliminated[eN].productions[k][0] == eliminated[j].nonTerminal[0]) {
Replace(eliminated[eN], eliminated[j].productions, k);
}
}
}
RemoveImmediate(eliminated, eliminated[eN], eN);
eN += 1;
}
printf("\nGrammar with eliminated left recursion:\n");
for(int i = 0; i < eN; i++) {
cout << eliminated[i].nonTerminal << " ->";
for(int j = 0; j < eliminated[i].productions.size(); j++) {
if(j > 0) cout << " |";
cout << " " << eliminated[i].productions[j];
}
cout << endl;
}
return 0;
}
#include <stdio.h>
#include <string.h>
#define MAX_LENGTH 100
/*
Input:
2
S->Sa|b
A->Ac|d
*/
int main() {
char currentNonTerminal;
char leftRecursivePart[10][MAX_LENGTH]; // Stores α in A → Aα
char nonRecursivePart[10][MAX_LENGTH]; // Stores β in A → β
int numProductions;
int recursiveCount, nonRecursiveCount;
char grammarProductions[10][MAX_LENGTH];
// Input number of productions
printf("Enter Number of Productions: ");
scanf("%d", &numProductions);
// Input grammar productions
printf("Enter the grammar (e.g., A->AB|AC|aB|cd):\n");
for (int i = 0; i < numProductions; i++) {
scanf("%s", grammarProductions[i]);
}
// Process each production
for (int i = 0; i < numProductions; i++) {
printf("\nGRAMMAR: %s", grammarProductions[i]);
// Get the non-terminal from the left side
currentNonTerminal = grammarProductions[i][0];
// Find the production arrow
char* productionPtr = strstr(grammarProductions[i], "->");
// Validate production format
if (productionPtr == NULL) {
printf("\nInvalid production format.\n");
continue;
}
// Move pointer past the arrow
productionPtr += 2;
// Split the production into alternatives
char* alternative = strtok(productionPtr, "|");
recursiveCount = nonRecursiveCount = 0;
// Process each alternative
while (alternative != NULL) {
if (alternative[0] == currentNonTerminal) {
// Store left-recursive part (α)
strcpy(leftRecursivePart[recursiveCount++], alternative + 1);
} else {
// Store non-left-recursive part (β)
strcpy(nonRecursivePart[nonRecursiveCount++], alternative);
}
alternative = strtok(NULL, "|");
}
// Output results
if (recursiveCount > 0) {
printf(" is left recursive.\n");
printf("Grammar without left recursion:\n");
// Print transformed non-recursive productions
printf("%c ->", currentNonTerminal);
for (int j = 0; j < nonRecursiveCount; j++) {
printf(" %s%c'", nonRecursivePart[j], currentNonTerminal);
if (j < nonRecursiveCount - 1) {
printf(" |");
}
}
printf("\n");
// Print new recursive productions
printf("%c' ->", currentNonTerminal);
for (int j = 0; j < recursiveCount; j++) {
printf(" %s%c'", leftRecursivePart[j], currentNonTerminal);
if (j < recursiveCount - 1) {
printf(" |");
}
}
printf(" | epsilon\n");
} else {
printf(" is not left recursive.\n");
}
}
return 0;
}
- Write a C program to generate three address code.
a = b + c + d - e
t1=b+c
t2=t1+d
t3=t2-e
a=t3
x=a+b*c
t1=b*c
t2=a+t1
x=t2
// Soikot
#include <bits/stdc++.h>
using namespace std;
void RemoveWhiteSpace(string &line) {
string t;
for(char c : line) if(c != ' ') t.push_back(c);
line = t;
}
int main()
{
string line; getline(cin, line);
RemoveWhiteSpace(line);
vector<string> v;
char id = line[0];
int cnt = 1;
cout << "\nThree Adress Code:\n";
for(int i = 2; i < line.size(); i++) {
if(line[i] == '*' or line[i] == '/') {
cout << "t" << cnt << "=" << v.back() << line[i] << line[i+1] << endl;
v.pop_back(); v.push_back("t" + to_string(cnt));
cnt++; i++;
} else {
v.push_back(string(1, line[i]));
}
}
reverse(v.begin(), v.end());
while(v.size() > 1) {
cout << "t" << cnt << "=";
cout << v.back(); v.pop_back();
cout << v.back(); v.pop_back();
cout << v.back() << endl; v.pop_back();
v.push_back("t" + to_string(cnt));
cnt++;
}
cout << id << "=" << v.back();
return 0;
}/**
Three Address Code
Input:
x = b + c - d
Ouput:
...
..
.
Input:
x = a + b * c
Output:
...
..
Give a space after each operator and operand.
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct three
{
char data[10], temp[7];
} s[30];
int main()
{
char d1[7], d2[7] = "t";
int i = 0, j = 1, len = 0;
char expression[100];
printf("Enter expression (space separated): ");
fgets(expression, sizeof(expression), stdin);
// Parse input into tokens
char *token = strtok(expression, " \n");
while (token != NULL)
{
strcpy(s[len].data, token);
len++;
token = strtok(NULL, " \n");
}
// First handle multiplication/division
for (i = 3; i < len; i++)
{
if (!strcmp(s[i].data, "*") || !strcmp(s[i].data, "/"))
{
itoa(j, d1, 10);
strcat(d2, d1);
strcpy(s[j].temp, d2);
printf("%s=%s%s%s\n", s[j].temp, s[i - 1].data, s[i].data, s[i + 1].data);
// Replace the multiplication with temp result
strcpy(s[i - 1].data, s[j].temp);
// Shift remaining elements
for (int k = i; k < len - 2; k++)
{
strcpy(s[k].data, s[k + 2].data);
}
len -= 2;
i--;
strcpy(d1, "");
strcpy(d2, "t");
j++;
}
}
// Then handle addition/subtraction
if (len > 4)
{ // If there are operations remaining
itoa(j, d1, 10);
strcat(d2, d1);
strcpy(s[j].temp, d2);
printf("%s=%s%s%s\n", s[j].temp, s[2].data, s[3].data, s[4].data);
j++;
for (i = 5; i < len - 1; i += 2)
{
strcpy(d1, "");
strcpy(d2, "t");
itoa(j, d1, 10);
strcat(d2, d1);
strcpy(s[j].temp, d2);
printf("%s=%s%s%s\n", s[j].temp, s[j - 1].temp, s[i].data, s[i + 1].data);
j++;
}
}
// Final assignment
printf("%s=%s\n", s[0].data, s[j - 1].temp);
return 0;
}
- Write a C program to implement operator precedence parsing.
(d*d)+d$
Precedence input: $<(<d><d>)>+<d>$
$<(E<d>)>+<d>$
$<(E*E)>+<E>$
$E+E$
Precedence Input: $<+>$
$E$
Success
#include<bits/stdc++.h>
using namespace std;
// Input : (d*d)+d
// No need to add the $ sign at last
int precedenc(char ch)
{
if(ch == '$')
return 0;
if(ch == '(')
return 1;
if(ch == '+')
return 2;
if(ch == '*')
return 3;
if(ch == ')')
return 4;
if(ch == 'd')
return 5;
}
int main()
{
string input;
cin >> input;
string inp;
inp = "$";
inp += input;
inp += "$";
cout << "Precedence input: ";
string sec;
for(int i = 0; i < inp.size() - 1; i++) {
sec += inp[i];
int a = precedenc(inp[i]);
int b = precedenc(inp[i + 1]);
if(a < b)
sec += "<";
else
sec += ">";
}
sec += inp[inp.size() - 1];
cout << sec << endl;
while(1)
{
bool x = false;
for(int i = 0; i < sec.size(); i++) {
if(sec[i] == '<' && sec[i + 1] == 'd') {
sec.erase(i, 3);
sec.insert(i, "E");
cout << sec << endl;
x = true;
}
else if(sec[i] == '<' && sec[i + 1] == '(' && sec[i + 5] == ')') {
sec.erase(i, 7);
sec.insert(i, "E");
cout << sec << endl;
x = true;
}
else if(sec[i] == '<' && sec[i + 1] == 'E' && sec[i + 4] == '>') {
sec.erase(i, 5);
sec.insert(i, "E");
cout << sec << endl;
x = true;
}
else if(sec[i] == '$' && sec[i + 1] == 'E' && sec[i + 4] == '$') {
sec.erase(i + 1, 3);
sec.insert(i + 1, "E");
cout << sec << endl;
x = true;
}
}
if(sec[0] == '$' && sec[2] == '$' && sec[1] == 'E') {
break;
}
if(x == false) break;
}
if(sec[0] == '$' && sec[2] == '$' && sec[1] == 'E') {
cout << "Success" << endl;
} else {
cout << "Failed" << endl;
}
return 0;
}
- Write a YACC Program to recognize a valid variable, which starts with a letter, followed by any number of letters or digits.
// Lex File (var.l)
%{
#include "432.tab.h"
%}
%%
[a-zA-Z] { return LETTER; }
[0-9] { return DIGIT; }
[ \t\n]+ { /* Ignore whitespace */ }
. { printf("Illegal characters found, invalid variable name"); exit(0); }
%%
int yywrap() {
return 1; // End of input.
}
// YACC file (var.y)
%{
#include <stdio.h>
#include <stdlib.h>
void yyerror(const char *msg);
int yylex();
%}
%token LETTER DIGIT
%%
VARIABLE : LETTER MORE { printf("Valid variable name\n"); }
;
MORE : LETTER MORE
| DIGIT MORE
| /* epsilon */
;
%%
void yyerror(const char *msg)
{
printf("Invalid variable name\n");
}
int main()
{
printf("Enter a variable name:\n");
yyparse();
return 0;
}// V2
// Lex file
%{
#include "y.tab.h"
%}
%%
[a-zA-Z_][a-zA-Z_0-9]* return letter;
[0-9] return digit;
. return yytext[0];
\n return 0;
%%
int yywrap() {
return 1;
}
// YACC
%{
#include <stdio.h>
int valid = 1;
// Forward declaration of yyerror
int yyerror();
int yylex();
%}
%token digit letter
%%
// Start rule: an identifier must start with a letter followed by zero or more letters or digits
start : letter s
;
s : letter s
| digit s
| /* empty */
;
%%
// Error handling
int yyerror() {
printf("\nIt's not a valid identifier!\n");
valid = 0;
return 0;
}
int main() {
printf("\nEnter a name to test for identifier: ");
yyparse();
if (valid) {
printf("\nIt is a valid identifier!\n");
}
return 0; // Added return statement for main
}
- Write a YACC Program to recognize nested IF control statements and display the levels of nesting.
// LEX
%{
#include "433.tab.h"
%}
%%
if { return IF; }
else { return ELSE; }
[0-9]+ { yylval = atoi(yytext); return NUM; }
[ \t\n] ; /* Skip whitespace */
. { return yytext[0]; }
%%
int yywrap(void) {
return 1;
}
// YACC
%{
#include <stdio.h>
#include <stdlib.h>
int level = 0;
void yyerror(const char *s);
int yylex(void);
%}
%token IF ELSE NUM
%%
program : statement
statement : if_stmt
| /* empty */
;
if_stmt : IF '(' expr ')' '{' { ++level; }
{ printf("IF statement with %d at level %d\n", $3, level);}
statement
'}' { --level; }
else_if_stmt
statement
;
else_if_stmt : ELSE IF '(' expr ')' '{' { ++level; }
statement
'}' { --level; }
else_if_stmt
| ELSE '{' { ++level; }
statement
'}' { --level; }
| /* empty */
;
expr : NUM { $$ = $1; }
;
%%
void yyerror(const char *s) {
fprintf(stderr, "Error: %s\n", s);
}
int main(void) {
printf("Enter IF statements:\n");
yyparse();
return 0;
}
/*
Sample Input :
if (5) {
if (10) {
if (15) {
}
}
} else {
if (20) {
}
}
*/
- Write a YACC program to recognize string with grammar {a^nb^n | n≥0}
Enter a string: aab
Enter a string: aaabbb
Invalid string.
Valid string.
// LEX
%{
#include "51.tab.h"
%}
%%
a { return A; }
b { return B; }
[\r\n]+ { return NL; }
. { printf("Invalid character: %s\n", yytext); exit(1); }
%%
int yywrap() {
return 1; // End of input
}
// YACC
%{
#include <stdio.h>
#include <stdlib.h>
void yyerror(const char *msg);
int yylex();
%}
%token A B NL
%%
G : S NL { printf("Valid string.\n"); exit(0); }
;
S : A S B { }
| /* empty */
;
%%
void yyerror(const char *msg) {
printf("Invalid string.\n");
exit(1);
}
int main() {
printf("Enter a string: ");
yyparse();
return 0;
}
- Write a YACC program for implementing a calculator for computing the given expression
Enter your expression: 2+(3*4)
Result: 14
Expression is Valid.
Enter your expression: 4=0
Expression is Invalid.
// LEX
%{
#include <stdlib.h>
#include "52.tab.h"
%}
%%
[0-9]+ { yylval = atoi(yytext); return NUMBER; }
[ \t] { } // Ignore Whitespace
[\r\n]+ { return NL; }
. { return yytext[0]; }
%%
int yywrap() {
return 1;
}
// YACC
%{
#include <stdio.h>
#include <stdlib.h>
void yyerror(const char *msg);
int yylex();
%}
%token NUMBER NL
%left '+' '-'
%left '*' '/'
%%
stmt : exp NL { printf("Result: %d\nExpression is valid\n", $1); exit(0); }
exp : exp '*' exp { $$ = $1 * $3; }
| exp '/' exp { if($3 == 0) { printf("Error: Division by Zero\n"); exit(0); }
$$ = $1 / $3; }
| exp '+' exp { $$ = $1 + $3; }
| exp '-' exp { $$ = $1 - $3; }
| '(' exp ')' { $$ = $2; }
| NUMBER { $$ = $1; }
%%
void yyerror(const char *msg) {
printf("Expression is invalid\n");
exit(0);
}
int main ()
{
printf("Enter the expression:\n");
yyparse();
return 0;
}
- Write a YACC program to convert binary number to decimal.
// LEX
%{
#include "541.tab.h"
%}
%%
0 { return ZERO; }
1 { return ONE; }
[\r\n]+ { return NL; }
. { if(yytext[0] == '.') return DOT; return yytext[0]; }
%%
int yywrap() {
return 1;
}
// YACC
%{
#include <stdio.h>
#include <stdlib.h>
int yylex();
void yyerror(const char *msg);
float val = 0.0;
%}
%token ZERO ONE NL DOT
%%
decimal : integer_part DOT fractional_part NL { printf("Decimal value = %f\n", 1.0 * $1 + val); exit(0); }
| integer_part NL { printf("Decimal value = %d\n", $1); exit(0); }
;
integer_part : integer_part binary_digit { $$ = $1 * 2 + $2; }
| /* empty */ { $$ = 0; }
;
fractional_part : binary_digit fractional_part { val = (1.0 * $1 + val) / 2.0; }
| /* empty */ { val = 0.0; }
;
binary_digit : ZERO { $$ = 0; }
| ONE { $$ = 1; }
;
%%
void yyerror(const char *msg) {
printf("Invalid input\n"); exit(0);
}
int main()
{
printf("Enter binary number:\n");
yyparse();
return 0;
}- Write a YACC program to implement a scientific calculator.
// LEX
%{
#include <stdlib.h>
#include "542.tab.h"
%}
%%
sin { return SIN; }
cos { return COS; }
[0-9]+(\.[0-9]+)?([E][+-]*[0-9]+)? { yylval.floatval = atof(yytext); return NUMBER; }
[ \t] { } // Ignore Whitespace
[\r\n]+ { return NL; }
. { return yytext[0]; }
%%
int yywrap() {
return 1;
}
// YACC
%{
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
void yyerror(const char *msg);
int yylex();
%}
%union {
int intval;
float floatval;
}
%token <floatval> NUMBER
%type <floatval> exp
%token NL SIN COS
%left '+' '-'
%left '*' '/'
%right '^'
%%
stmt : exp NL { printf("Result: %f\nExpression is valid\n", $1); exit(0); }
exp : exp '*' exp { $$ = $1 * $3; }
| exp '/' exp { if($3 == 0) { printf("Error: Division by Zero\n"); exit(0); }
$$ = $1 / $3; }
| exp '+' exp { $$ = $1 + $3; }
| exp '-' exp { $$ = $1 - $3; }
| '(' exp ')' { $$ = $2; }
| NUMBER { $$ = $1; }
| SIN '(' exp ')' { $$ = sin($3 * 0.01745329251); } // convert to radian
| COS '(' exp ')' { $$ = cos($3 * 0.01745329251); }
| exp '^' exp { $$ = pow($1, $3); }
%%
void yyerror(const char *msg) {
printf("Expression is invalid\n");
exit(0);
}
int main ()
{
printf("Enter the expression:\n");
yyparse();
return 0;
}
- Write a C program to Design SLR Parser
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 100
typedef struct {
char stack[MAX];
char input[MAX];
char action[MAX];
} TableRow;
TableRow rows[MAX];
int rowIndex = 0;
void storeRow(char *stack, char *input, char *action) {
strcpy(rows[rowIndex].stack, stack);
strcpy(rows[rowIndex].input, input);
strcpy(rows[rowIndex].action, action);
rowIndex++;
}
void displayTable() {
printf("Stack\t\tInput\t\tAction\n");
for (int i = 0; i < rowIndex; i++) {
printf("%s\t\t%s\t\t%s\n", rows[i].stack, rows[i].input, rows[i].action);
}
}
int main() {
char stack[MAX] = "0";
char input[MAX];
int state = 0, action;
printf("Enter input string (example: id+id*id): ");
scanf("%s", input);
strcat(input, "$"); // Append end symbol
storeRow(stack, input, ""); // Initial state
// Parsing steps as per the output example
strcpy(stack, "0 id 5");
storeRow(stack, " *id + id $", "shift");
strcpy(stack, "0 F 3");
storeRow(stack, "* id + id $", "reduce by F -> id");
strcpy(stack, "0 T 2");
storeRow(stack, "* id + id $", "reduce by T -> F");
strcpy(stack, "0 T 2*7");
storeRow(stack, " id + id $", "shift");
strcpy(stack, "0 T 2*7 id 5");
storeRow(stack, "+id + id $", "shift");
strcpy(stack, "0 T 2*7 id 5 F 10 ");
storeRow(stack, "+ id $", "reduced by F -> id ");
strcpy(stack, "0 T 2");
storeRow(stack, "+ id $", "reduce by T -> T*F");
strcpy(stack, "0 E 1 ");
storeRow(stack, "+ id $", "reduce by E -> T");
strcpy(stack, "0 E 1 + 6");
storeRow(stack, "id $", "shift");
strcpy(stack, "0 E 1 + 6 id 5");
storeRow(stack, "$", "shift");
strcpy(stack, "0 E 1 + 6 F 3");
storeRow(stack, "$", "reduce by F -> id");
strcpy(stack, "0 E 1 + 6 T 9");
storeRow(stack, "$", "reduce by T -> F");
strcpy(stack, "0 E 1");
storeRow(stack, "$", "reduce by E -> E + T");
strcpy(stack, "0");
storeRow(stack, "$", "accept");
// Display the table
displayTable();
return 0;
}
- LL (1) Parsing / LL1 Parsing // LL 1 Processing
/*
Input:
8
E=TR
R=+TR
R=#
T=FY
Y=*FY
Y=#
F=(E)
F=i
*/
#include<stdio.h>
#include<ctype.h>
#include<string.h>
void followfirst(char , int , int);
void findfirst(char , int , int);
void follow(char c);
int count,n=0;
char calc_first[10][100];
char calc_follow[10][100];
int m=0;
char production[10][10], first[10];
char f[10];
int k;
char ck;
int e;
int main(int argc,char **argv)
{
int jm=0;
int km=0;
int i,choice;
char c,ch;
printf("How many productions ? :");
scanf("%d",&count);
printf("\nEnter %d productions in form A=B where A and B are grammar symbols :\n\n",count);
for(i=0;i<count;i++)
{
scanf("%s%c",production[i],&ch);
}
int kay;
char done[count];
int ptr = -1;
for(k=0;k<count;k++){
for(kay=0;kay<100;kay++){
calc_first[k][kay] = '!';
}
}
int point1 = 0,point2,xxx;
for(k=0;k<count;k++)
{
c=production[k][0];
point2 = 0;
xxx = 0;
for(kay = 0; kay <= ptr; kay++)
if(c == done[kay])
xxx = 1;
if (xxx == 1)
continue;
findfirst(c,0,0);
ptr+=1;
done[ptr] = c;
printf("\n First(%c)= { ",c);
calc_first[point1][point2++] = c;
for(i=0+jm;i<n;i++){
int lark = 0,chk = 0;
for(lark=0;lark<point2;lark++){
if (first[i] == calc_first[point1][lark]){
chk = 1;
break;
}
}
if(chk == 0){
printf("%c, ",first[i]);
calc_first[point1][point2++] = first[i];
}
}
printf("}\n");
jm=n;
point1++;
}
printf("\n");
printf("-----------------------------------------------\n\n");
char donee[count];
ptr = -1;
for(k=0;k<count;k++){
for(kay=0;kay<100;kay++){
calc_follow[k][kay] = '!';
}
}
point1 = 0;
int land = 0;
for(e=0;e<count;e++)
{
ck=production[e][0];
point2 = 0;
xxx = 0;
for(kay = 0; kay <= ptr; kay++)
if(ck == donee[kay])
xxx = 1;
if (xxx == 1)
continue;
land += 1;
follow(ck);
ptr+=1;
donee[ptr] = ck;
printf(" Follow(%c) = { ",ck);
calc_follow[point1][point2++] = ck;
for(i=0+km;i<m;i++){
int lark = 0,chk = 0;
for(lark=0;lark<point2;lark++){
if (f[i] == calc_follow[point1][lark]){
chk = 1;
break;
}
}
if(chk == 0){
printf("%c, ",f[i]);
calc_follow[point1][point2++] = f[i];
}
}
printf(" }\n\n");
km=m;
point1++;
}
char ter[10];
for(k=0;k<10;k++){
ter[k] = '!';
}
int ap,vp,sid = 0;
for(k=0;k<count;k++){
for(kay=0;kay<count;kay++){
if(!isupper(production[k][kay]) && production[k][kay]!= '#' && production[k][kay] != '=' && production[k][kay] != '\0'){
vp = 0;
for(ap = 0;ap < sid; ap++){
if(production[k][kay] == ter[ap]){
vp = 1;
break;
}
}
if(vp == 0){
ter[sid] = production[k][kay];
sid ++;
}
}
}
}
ter[sid] = '$';
sid++;
printf("\n\t\t\t\t\t\t\t The LL(1) Parsing Table for the above grammer :-");
printf("\n\t\t\t\t\t\t\t^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n");
printf("\n\t\t\t=====================================================================================================================\n");
printf("\t\t\t\t|\t");
for(ap = 0;ap < sid; ap++){
printf("%c\t\t",ter[ap]);
}
printf("\n\t\t\t=====================================================================================================================\n");
char first_prod[count][sid];
for(ap=0;ap<count;ap++){
int destiny = 0;
k = 2;
int ct = 0;
char tem[100];
while(production[ap][k] != '\0'){
if(!isupper(production[ap][k])){
tem[ct++] = production[ap][k];
tem[ct++] = '_';
tem[ct++] = '\0';
k++;
break;
}
else{
int zap=0;
int tuna = 0;
for(zap=0;zap<count;zap++){
if(calc_first[zap][0] == production[ap][k]){
for(tuna=1;tuna<100;tuna++){
if(calc_first[zap][tuna] != '!'){
tem[ct++] = calc_first[zap][tuna];
}
else
break;
}
break;
}
}
tem[ct++] = '_';
}
k++;
}
int zap = 0,tuna;
for(tuna = 0;tuna<ct;tuna++){
if(tem[tuna] == '#'){
zap = 1;
}
else if(tem[tuna] == '_'){
if(zap == 1){
zap = 0;
}
else
break;
}
else{
first_prod[ap][destiny++] = tem[tuna];
}
}
}
char table[land][sid+1];
ptr = -1;
for(ap = 0; ap < land ; ap++){
for(kay = 0; kay < (sid + 1) ; kay++){
table[ap][kay] = '!';
}
}
for(ap = 0; ap < count ; ap++){
ck = production[ap][0];
xxx = 0;
for(kay = 0; kay <= ptr; kay++)
if(ck == table[kay][0])
xxx = 1;
if (xxx == 1)
continue;
else{
ptr = ptr + 1;
table[ptr][0] = ck;
}
}
for(ap = 0; ap < count ; ap++){
int tuna = 0;
while(first_prod[ap][tuna] != '\0'){
int to,ni=0;
for(to=0;to<sid;to++){
if(first_prod[ap][tuna] == ter[to]){
ni = 1;
}
}
if(ni == 1){
char xz = production[ap][0];
int cz=0;
while(table[cz][0] != xz){
cz = cz + 1;
}
int vz=0;
while(ter[vz] != first_prod[ap][tuna]){
vz = vz + 1;
}
table[cz][vz+1] = (char)(ap + 65);
}
tuna++;
}
}
for(k=0;k<sid;k++){
for(kay=0;kay<100;kay++){
if(calc_first[k][kay] == '!'){
break;
}
else if(calc_first[k][kay] == '#'){
int fz = 1;
while(calc_follow[k][fz] != '!'){
char xz = production[k][0];
int cz=0;
while(table[cz][0] != xz){
cz = cz + 1;
}
int vz=0;
while(ter[vz] != calc_follow[k][fz]){
vz = vz + 1;
}
table[k][vz+1] = '#';
fz++;
}
break;
}
}
}
for(ap = 0; ap < land ; ap++){
printf("\t\t\t %c\t|\t",table[ap][0]);
for(kay = 1; kay < (sid + 1) ; kay++){
if(table[ap][kay] == '!')
printf("\t\t");
else if(table[ap][kay] == '#')
printf("%c=#\t\t",table[ap][0]);
else{
int mum = (int)(table[ap][kay]);
mum -= 65;
printf("%s\t\t",production[mum]);
}
}
printf("\n");
printf("\t\t\t---------------------------------------------------------------------------------------------------------------------");
printf("\n");
}
int j;
printf("\n\nPlease enter the desired INPUT STRING = ");
char input[100];
scanf("%s%c",input,&ch);
printf("\n\t\t\t\t\t===========================================================================\n");
printf("\t\t\t\t\t\tStack\t\t\tInput\t\t\tAction");
printf("\n\t\t\t\t\t===========================================================================\n");
int i_ptr = 0,s_ptr = 1;
char stack[100];
stack[0] = '$';
stack[1] = table[0][0];
while(s_ptr != -1){
printf("\t\t\t\t\t\t");
int vamp = 0;
for(vamp=0;vamp<=s_ptr;vamp++){
printf("%c",stack[vamp]);
}
printf("\t\t\t");
vamp = i_ptr;
while(input[vamp] != '\0'){
printf("%c",input[vamp]);
vamp++;
}
printf("\t\t\t");
char her = input[i_ptr];
char him = stack[s_ptr];
s_ptr--;
if(!isupper(him)){
if(her == him){
i_ptr++;
printf("POP ACTION\n");
}
else{
printf("\nString Not Accepted by LL(1) Parser !!\n");
return 0;
}
}
else{
for(i=0;i<sid;i++){
if(ter[i] == her)
break;
}
char produ[100];
for(j=0;j<land;j++){
if(him == table[j][0]){
if (table[j][i+1] == '#'){
printf("%c=#\n",table[j][0]);
produ[0] = '#';
produ[1] = '\0';
}
else if(table[j][i+1] != '!'){
int mum = (int)(table[j][i+1]);
mum -= 65;
strcpy(produ,production[mum]);
printf("%s\n",produ);
}
else{
printf("\nString Not Accepted by LL(1) Parser !!\n");
return 0;
}
}
}
int le = strlen(produ);
le = le - 1;
if(le == 0){
continue;
}
for(j=le;j>=2;j--){
s_ptr++;
stack[s_ptr] = produ[j];
}
}
}
printf("\n\t\t\t=======================================================================================================================\n");
if (input[i_ptr] == '\0'){
printf("\t\t\t\t\t\t\t\tYOUR STRING HAS BEEN ACCEPTED !!\n");
}
else
printf("\n\t\t\t\t\t\t\t\tYOUR STRING HAS BEEN REJECTED !!\n");
printf("\t\t\t=======================================================================================================================\n");
}
void follow(char c)
{
int i ,j;
if(production[0][0]==c){
f[m++]='$';
}
for(i=0;i<10;i++)
{
for(j=2;j<10;j++)
{
if(production[i][j]==c)
{
if(production[i][j+1]!='\0'){
followfirst(production[i][j+1],i,(j+2));
}
if(production[i][j+1]=='\0'&&c!=production[i][0]){
follow(production[i][0]);
}
}
}
}
}
void findfirst(char c ,int q1 , int q2)
{
int j;
if(!(isupper(c))){
first[n++]=c;
}
for(j=0;j<count;j++)
{
if(production[j][0]==c)
{
if(production[j][2]=='#'){
if(production[q1][q2] == '\0')
first[n++]='#';
else if(production[q1][q2] != '\0' && (q1 != 0 || q2 != 0))
{
findfirst(production[q1][q2], q1, (q2+1));
}
else
first[n++]='#';
}
else if(!isupper(production[j][2])){
first[n++]=production[j][2];
}
else {
findfirst(production[j][2], j, 3);
}
}
}
}
void followfirst(char c, int c1 , int c2)
{
int k;
if(!(isupper(c)))
f[m++]=c;
else{
int i=0,j=1;
for(i=0;i<count;i++)
{
if(calc_first[i][0] == c)
break;
}
while(calc_first[i][j] != '!')
{
if(calc_first[i][j] != '#'){
f[m++] = calc_first[i][j];
}
else{
if(production[c1][c2] == '\0'){
follow(production[c1][0]);
}
else{
followfirst(production[c1][c2],c1,c2+1);
}
}
j++;
}
}
}