Click here to Skip to main content
15,882,055 members
Please Sign up or sign in to vote.
1.00/5 (2 votes)
See more:
SQL
A predictive parser (a top-down parser without backtracking) insists  that the grammar must be left-factored.

    grammar  a new equivalent grammar suitable for predictive parsing

stmt  if  expr  then  stmt  else  stmt    |
         if  expr  then  stmt


when we see  if, we cannot now which production rule to choose to  re-write stmt in the derivation.


A  abB | aB | cdg | cdeB | cdfB

A  aA’ | cdg | cdeB | cdfB
A’  bB | B

A  aA’ | cdA’’
A’  bB | B
A’’  g | eB | fB


please i need coures code of left factoring by java
this program checked in tha string if the left factoring in the string find it and
remove it
Posted
Updated 1-Apr-16 11:07am
Comments
joshrduncan2012 28-Nov-12 12:36pm    
"I need" doesn't work here. What have you tried? Where are you stuck? Can you show us your attempt in solving this problem?
Sergey Alexandrovich Kryukov 28-Nov-12 12:36pm    
"I need... code" is not a question. Any particular problem? and please format the code properly, if you want to ask the question. It's not readable right now.
--SA
joshrduncan2012 28-Nov-12 14:50pm    
Nice answer SA! :)
ZurdoDev 28-Nov-12 13:47pm    
What?

I've started you off, just fill in the blanks:

Java
package com.factor;
 
/**
 * Application class for factorisation project.
 */
public class FactorApplication {
    public void main(String[] args) {
        // code goes here.
    }
}
 
Share this answer
 
Java
/* lhs : left hand side
 * rhs : right hand side 
 * LF : left factoring 
 * f_count: factoring count that is used to count factor out , i.e X0, X1 , X2  
 * pro: production 
 * cfg: context-free-grammar that refers to the entered grammar by user
 */

public class Lab_6_Left_factoring_ {
	public static String cfg_Left_factored="";
	public static String cfg="A--> abB | aB | cdg | cdeB | cdfB\n" +""; // you can add more productions by only adding \n at the end of the productions. 
	public static String Not_LF="";

	public static boolean left_factoring=false;
	public static int f_count =0;
	public static void main(String[] args) {
		
		System.out.println("Context free grammar is \n" + cfg + "\n ----------------------------------------------------------");
		check_factor(cfg);
		System.out.println("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~");
		 System.out.println("The result of left factoring is \n"  ); // productions that don't need to be left factored out. 
		    System.out.println(Not_LF);
		    System.out.println("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~");
		System.out.println("\t\t\t\t\t\t\t\t Coded by RNR");
		System.out.println("\t\t\t\t\t\t contact info: rebaz.najeeb@koyauniversity.org");
		System.out.println("\t\t\t\t\t\t\t\t\t 2016");
}
		
public static void check_factor(String cfg) {

String lines [] = cfg.split("\\\n");
for (String line: lines) {
	
        line= line.replaceAll("\\s+", "");  // just to remove all white spaces from a line
        
		String productions [] = line.split("-->",0); // to split the a line at a time into right hand side and left hand side productions according to --> 
		String lhs = productions [0];
		String rhs = productions[1];
		System.out.println("\n*** Left hand side: " + lhs ) ;
		System.out.println("------------------------------------------");
		System.out.println("*** Right hand side: " + rhs);
		System.out.println("------------------------------------------");
		System.out.println("");
		
		String [] rhs_productions = rhs.split("\\|") ; // split right hand side for productions based on | 
		
		left_factoring=false;
		
		for (int i=0;i<rhs_productions.length-1;i++) {
			for(int j=i+1;j<rhs_productions.length;j++) {
				
				if (rhs_productions[i].charAt(0)==rhs_productions[j].charAt(0) && (!rhs_productions[i].equals("epsilon")) ) {
					left_factoring=true;
				}
			
				
			}
			}
	
		if(left_factoring) {
		System.out.println(" This Grammar needs left factoring!!");
		System.out.println("");
		
	//	Arrays.sort(rhs_productions); // just to sort the array alphabetically 
		String common_prefix="";
		common_prefix=find_common_prefix(rhs_productions);
		
		System.out.println("--- common prefix is "+ common_prefix);
		System.out.println("------------------------------------------");
		left_factor_out (lhs , common_prefix,  rhs_productions ); // to remove left factoring
	
		}
		else {
			Not_LF+=line +"\n";
        System.out.println("This grammar does not need left factoring");
        System.out.println("");
        
           }
        }
	}



	private static void left_factor_out(String lhs,  String common_prefix,
			String[] rhs_productions) {
		cfg_Left_factored=lhs+"-->"; // rewrite the productions without left factoring
		for(String pro:rhs_productions) {
			if(!pro.startsWith(common_prefix) ) { 
				cfg_Left_factored+=pro+"|";
			}
			
		}
		cfg_Left_factored+=common_prefix + "X"+ f_count + "\n"; 
		cfg_Left_factored+="X"+ f_count + "--> ";
		for(String pro:rhs_productions) {
			
			if(pro.startsWith(common_prefix) ) { 
				if( pro.substring(1 , pro.length()).length() ==0) {
					
					cfg_Left_factored+="epsilon"+"|";
				}
				else {
					cfg_Left_factored+=pro.substring(1 , pro.length() )+"|";				}
				
			}
			
		}
		cfg_Left_factored=cfg_Left_factored.substring(0, cfg_Left_factored.length()-1); // to remove last | symbol at the end 
		System.out.println("left factored out \n" + cfg_Left_factored);
        if(left_factoring){
        	f_count++;
	check_factor(cfg_Left_factored);
	
		}
       
	}
	
	public static String find_common_prefix(String[] rhs_productions) {
	    String common_prefix = "";
	    for (int i=0;i<rhs_productions.length-1;i++) {
	    	
			for(int j=i+1;j<rhs_productions.length;j++) {
				if (rhs_productions[i].charAt(0) == rhs_productions[j].charAt(0) ) {
					common_prefix=rhs_productions[i].charAt(0)+"";
					break;
				}
				
			}
			if(common_prefix.length()>0) // initially length of common_prefix is 0 , once the a common prefix is found , we don't need the first for to keep looping 
					break;	 // this break correspond to stop first loop for(int =i.....)  
			}
	    
	    return common_prefix;
	}

	 
}
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900