Showing posts with label Java Program. Show all posts
Showing posts with label Java Program. Show all posts
Program to eliminate unit productions from given CFG (context free grammar). - Java program
Write
a program to eliminate unit productions from given CFG.
Program:
package engineeringway;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
public class engineeringway {
/**
* @param args the
command line arguments
*/
public static void
main(String[] args) throws FileNotFoundException, IOException {
// TODO code
application logic here
BufferedReader
in = new BufferedReader(new FileReader("E://sid//input4.txt"));
String str;
List<String> list = new ArrayList<String>();
while((str = in.readLine()) != null){
list.add(str);
}
String[] stringArr = list.toArray(new String[0]);
int i=0;
int j=0;
int c=0;
for(i=0;i<stringArr.length;i++){
System.out.println(stringArr[i].length());
if(stringArr[i].length()==3){
c++;
}
}
StringBuilder[] pro1=new StringBuilder[c];
StringBuilder[] pro2=new StringBuilder[stringArr.length];
for(i=0;i<stringArr.length;i++){
pro2[i] = new StringBuilder("");
pro2[i].append(stringArr[i]);
System.out.println("-"+pro2[i]);
if(stringArr[i].length()==3){
pro1[j] = new StringBuilder("");
System.out.println(stringArr[i]);
pro1[j].append(stringArr[i]);
j++;
}
}
System.out.print("\n");
int count=0;
for(int b=0;b<pro1.length;b++)
{
String
b1;
b1=pro1[b].toString().trim();
String
c1=b1.substring(b1.length() - 1);
char ch = c1.charAt(0);
//System.out.println(ch);
if(ch>='A' &&ch<='Z'){
System.out.println(pro1[b]);
count++;
for(int q=0;q<pro2.length;q++){
char first=pro2[q].toString().charAt(0);
System.out.println(first);
if(ch==first){
//for(int r=0;r<pro2[q].length();r++)
//{
System.out.println(pro2[q].substring(2));
String
sub=pro2[q].substring(2);
for(int r=0;r<pro2.length;r++){
if(pro2[r].length()==3 &&
pro2[2].toString().charAt(0)==ch){
String
h=pro2[r].toString().replaceAll(String.valueOf(pro2[2].toString().charAt(0)),sub pro2[r].replace(0, pro2[r].length(), h
)} }
} }
}
}
for(int r=0;r<pro2.length;r++){
System.out.println(pro2[r]);
}
if(count==0){
System.out.println("Unit production doesn't
exist");
}
else{
System.out.println("Unit production exist");
}
}
}
Output:
Program to find out FIRST () and FOLLOW() from given set of production rules. - Java program
Write a program to find out FIRST () and
FOLLOW() from given set of production rules.
S→ABa|bcA
A→cBc|є
B →cdA| ad
Program:
/*
* To change this
license header, choose License Headers in Project Properties.
* To change this
template file, choose Tools | Templates
* and open the
template in the editor.
*/
package prac_5cd;
import java.io.*;
public class Prac_5CD {
static char
nonterminal[],terminal[];
static int
ntlen,tlen;
static String
grammar[][],first[],follow[];
public static void
main(String[] args) throws IOException {
String
nt,t;
int i,j,n;
BufferedReader
br=new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter the non-terminals");
nt=br.readLine();
ntlen=nt.length();
nonterminal=new
char[ntlen];
nonterminal=nt.toCharArray();
System.out.println("Enter the terminals");
t=br.readLine();
tlen=t.length();
terminal=new
char[tlen];
terminal=t.toCharArray();
System.out.println("Specify the grammar(Enter 9 for epsilon
production)");
grammar=new
String[ntlen][];
for(i=0;i<ntlen;i++)
{
System.out.println("Enter the number of productions for
"+nonterminal[i]);
n=Integer.parseInt(br.readLine());
grammar[i]=new
String[n];
System.out.println("Enter the productions");
for(j=0;j<n;j++)
grammar[i][j]=br.readLine();
}
first=new String[ntlen];
for(i=0;i<ntlen;i++)
first[i]=first(i); //calling
first funcction for every non-terminal
System.out.println("First Set");
for(i=0;i<ntlen;i++)
System.out.println(removeDuplicates(first[i]));
follow=new
String[ntlen];
for(i=0;i<ntlen;i++)
follow[i]=follow(i); //calling follow function for every non -terminal
System.out.println("Follow Set");
for(i=0;i<ntlen;i++)
System.out.println(removeDuplicates(follow[i]));
}
static String first(int i)
{
int
j,k,l=0,found=0;
String
temp="",str="";
for(j=0;j<grammar[i].length;j++) //number of productions
{
for(k=0;k<grammar[i][j].length();k++,found=0) //when nonterminal has
epsilon production
{
for(l=0;l<ntlen;l++) //finding nonterminal
{
if(grammar[i][j].charAt(k)==nonterminal[l]) //for nonterminal in first
set
{
str=first(l);
if(!(str.length()==1 && str.charAt(0)=='9')) //when epsilon
production is the only nonterminal production
temp=temp+str;
found=1;
//str.replace("9", "");
break;
}
}
if(found==1)
{
if(str.contains("9")) //here epsilon will lead to next
nonterminal’s first set
continue;
}
else //if
first set includes terminal
temp=temp+grammar[i][j].charAt(k);
break;
}
}
return temp;
}
static String follow(int i)
{
char pro[],chr[];
String
temp="";
int
j,k,l,m,n,found=0;
if(i==0)
temp="$";
for(j=0;j<ntlen;j++)
{
for(k=0;k<grammar[j].length;k++) //entering grammar matrix
{
pro=new
char[grammar[j][k].length()];
pro=grammar[j][k].toCharArray();
for(l=0;l<pro.length;l++) //entering each production
{
if(pro[l]==nonterminal[i]) //finding the nonterminal whose follow set is
to be found
{
if(l==pro.length-1) //if it is the last terminal/non-terminal then
follow of current non-terminal
{
if(j<i)
temp=temp+follow[j];
}
else
{
for(m=0;m<ntlen;m++)
{
if(pro[l+1]==nonterminal[m]) //first of next non-terminal otherwise
(else later…)
{
chr=new
char[first[m].length()];
chr=first[m].toCharArray();
for(n=0;n<chr.length;n++)
{
if(chr[n]=='9') //if first includes epsilon
{
if(l+1==pro.length-1)
temp=temp+follow(j); //when non-terminal is second last
else
temp=temp+follow(m);
}
else
temp=temp+chr[n]; //include whole first set except epsilon
}
found=1;
}
}
if(found!=1)
temp=temp+pro[l+1]; //follow set will include terminal(else is here)
}
}
}
}
}
return temp;
}
static String removeDuplicates(String str)
{
int i;
char ch;
boolean seen[] =
new boolean[256];
StringBuilder sb =
new StringBuilder(seen.length);
for(i=0;i<str.length();i++)
{
ch=str.charAt(i);
if
(!seen[ch])
{
seen[ch] = true;
sb.append(ch);
}
if(str.contains("9"))
{
str.replace("9", "");
}
}
return
sb.toString();
}
}
Output:
Write a Program to Implement Recursive Decent Parser. - java program
Aim:
Write a Program to
Implement Recursive Decent Parser for the given grammar:
E→TA
A→+TA | є
T→FB
B→*FB | є
F→(E) | id
Parse the string:
1) id + id * id
2) (id + id) * (id + id)
3) (id + id * id)
Program:
package dharmik_cd4;
import java.util.Scanner;
/**
*
* @author dharmik
*/
public class Dharmik_CD4 {
static String
given;
static char l;
static int i=0;
public static void
main(String[] args) {
Scanner in =
new Scanner(System.in);
String s = in.nextLine();
given = s;
l=given.charAt(i);
i++;
E();
if(l=='$'){
System.out.println("Successful");
}else{
System.out.println("Error in given string");
}
}
static void E(){
T();
A();
}
static void T(){
F();
B();
}
static void A(){
if(l=='+'){
match('+');
T();
A();
}
else{
}
}
static void F(){
if(l=='('){
match('(');
E();
match(')');
}else
if(l=='i'){
match('i');
match('d');
}else{
System.out.println("Error1");
System.exit(0);
}
}
static void B(){
if(l=='*'){
match('*');
F();
B();
}
else{
}
}
static void
match(char t){
if(l==t){
l=given.charAt(i);
i++;
if(i>given.length()){
System.out.println("Error");
}
}
else{
System.out.println("Error");
}
}
}
Output:
 |
 |
Subscribe to:
Posts
(
Atom
)