Click here to Skip to main content
12,293,601 members (61,914 online)
Rate this:
 
Please Sign up or sign in to vote.
See more: Java
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 28-Nov-12 6:29am
Edited 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! :)
ryanb31 28-Nov-12 13:47pm
   
What?
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 1

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

package com.factor;
 
/**
 * Application class for factorisation project.
 */
public class FactorApplication {
    public void main(String[] args) {
        // code goes here.
    }
}
  Permalink  
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 2

/* 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;
	}
 
	 
}
  Permalink  

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

  Print Answers RSS
Top Experts
Last 24hrsThis month


Advertise | Privacy | Mobile
Web02 | 2.8.160525.2 | Last Updated 1 Apr 2016
Copyright © CodeProject, 1999-2016
All Rights Reserved. Terms of Service
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100