import java.awt.*; import java.applet.*; import java.util.Stack; import java.lang.String; import java.util.Vector; public class Parsing extends Applet{ // Fields protected Stack Backtrack_Store; protected Stack Previous_Steps; //for printing step_by_step protected Backtrack_row curr_backtrack; protected boolean parse_found; protected int exp_rule_number; protected int how_many_results; protected int which_result; protected Row current_row; protected String due_symbol; protected String state; protected String recognized_word; protected String all_recogn_words; protected boolean print_at_once; //print all information parallel to parsing protected boolean prev_step_possible; protected boolean renew_init_values; protected boolean restore_this_step; protected boolean has_to_do_backtracking; protected String this_step; protected String previous_step; protected Vector previous_rules; protected String this_stack; protected String previous_stack; //dynamic Array to store information during parsing process protected Vector parse_info = new Vector(100, 50); protected Vector good_rules = new Vector(30); //for storing used expansion rules - to create parse result protected String[][] all_results; //demostrating elements protected Button butt_back; protected Button butt_startover; protected Button butt_evrthing; protected Button next_step; protected Button prev_step; protected Button results_butt; protected Label parse_in_steps; protected List my_rules_copy; protected Panel panel_for_input; protected Panel butt_panel; protected ScrollPane treepanel; protected Panel northpanel; protected TextArea parse_table; protected TextArea stack_table; protected TreeCanvas myTree; public void init(){ setBackground(Color.white); Backtrack_Store = new Stack(); Previous_Steps = new Stack(); parse_in_steps = new Label(" PARSE STEP BY STEP "); parse_in_steps.setForeground(Color.red); //Organize Layout of demonstrating elements parse_table = new TextArea(); parse_table.setEditable(false); parse_table.setBackground(new Color (255, 255, 200)); parse_table.setFont(new Font("Courier", Font.PLAIN,12)); stack_table = new TextArea(); stack_table.setEditable(false); stack_table.setBackground(new Color(255, 255, 200)); //light yellow stack_table.setFont(new Font("Courier", Font.PLAIN,12)); treepanel=new ScrollPane(); treepanel.setBackground(new Color(230, 230, 230)); //light blue? panel_for_input= new Panel(); butt_panel = new Panel(); northpanel=new Panel(); northpanel.setBackground(new Color(230, 230, 230)); //light blue? butt_back = new Button("Back to Input"); butt_startover = new Button("Start Over"); butt_evrthing = new Button("Parse At Once"); next_step = new Button("Next Step"); prev_step = new Button("Previous Step"); butt_back.setBackground(new Color(230, 230, 230)); butt_startover.setBackground(new Color(230, 230, 230)); butt_evrthing.setBackground(new Color(230, 230, 230)); next_step.setBackground(new Color(230, 230, 230)); prev_step.setBackground(new Color(230, 230, 230)); results_butt = new Button("Constructed Tree"); my_rules_copy = new List(FirstFrame().myRules.my_rules.countItems()+1, false); my_rules_copy.setBackground( new Color(230, 230, 230)); GridBagLayout gbl = new GridBagLayout(); GridBagConstraints gbc = new GridBagConstraints(); setLayout(gbl); gbc.gridy = 0; gbc.gridx = 0; gbc.weightx = 1; gbc.fill=GridBagConstraints.HORIZONTAL; gbl.setConstraints(my_rules_copy,gbc); add(my_rules_copy); gbc.gridy = 0; gbc.gridx = 1; gbc.weightx = 1; gbc.gridwidth = GridBagConstraints.RELATIVE; gbc.fill=GridBagConstraints.NONE; gbl.setConstraints(panel_for_input,gbc); add(panel_for_input); gbc.gridy = 0; gbc.gridx = 2; gbc.weightx = 0; gbc.gridwidth = GridBagConstraints.REMAINDER; gbc.fill=GridBagConstraints.NONE; gbl.setConstraints(butt_panel,gbc); add(butt_panel); GridBagLayout gbl_buttons = new GridBagLayout(); GridBagConstraints gbc_buttons = new GridBagConstraints(); butt_panel.setLayout(gbl_buttons); gbc_buttons.gridy = 0; gbc_buttons.gridx = 0; gbc_buttons.weightx = 1; gbc_buttons.weighty = 1; gbc_buttons.fill=GridBagConstraints.NONE; gbl_buttons.setConstraints(butt_back,gbc_buttons); butt_panel.add(butt_back); gbc_buttons.gridy = 0; gbc_buttons.gridx = 1; gbc_buttons.weightx = 1; gbc_buttons.weighty = 1; gbc_buttons.fill=GridBagConstraints.NONE; gbl_buttons.setConstraints(butt_startover,gbc_buttons); butt_panel.add(butt_startover); gbc_buttons.gridy = 1; gbc_buttons.gridx = 0; gbc_buttons.weightx = 1; gbc_buttons.weighty = 1; gbc_buttons.gridwidth=2; gbc_buttons.fill=GridBagConstraints.NONE; gbl_buttons.setConstraints(butt_evrthing,gbc_buttons); butt_panel.add(butt_evrthing); gbc_buttons.gridy = 2; gbc_buttons.gridx = 0; gbc_buttons.weightx = 3; gbc_buttons.weighty = 1; gbc_buttons.gridwidth = GridBagConstraints.REMAINDER; gbc_buttons.gridheight = GridBagConstraints.RELATIVE; gbc_buttons.fill=GridBagConstraints.BOTH; gbl_buttons.setConstraints(parse_in_steps,gbc_buttons); butt_panel.add(parse_in_steps); gbc_buttons.gridy = 3; gbc_buttons.gridx = 0; gbc_buttons.weightx = 1.5; gbc_buttons.weighty = 1; gbc_buttons.gridwidth = GridBagConstraints.RELATIVE; gbc_buttons.gridheight = GridBagConstraints.REMAINDER; gbc_buttons.fill=GridBagConstraints.NONE; gbl_buttons.setConstraints(next_step,gbc_buttons); butt_panel.add(next_step); gbc_buttons.gridy = 3; gbc_buttons.gridx = 1; gbc_buttons.weightx = 1.5; gbc_buttons.weighty = 1; gbc_buttons.gridwidth = GridBagConstraints.REMAINDER; gbc_buttons.gridheight = GridBagConstraints.REMAINDER; gbc_buttons.fill=GridBagConstraints.NONE; gbl_buttons.setConstraints(prev_step,gbc_buttons); butt_panel.add(prev_step); gbc.gridy = 1; gbc.gridx = 0; gbc.gridwidth = GridBagConstraints.REMAINDER; gbc.gridheight = GridBagConstraints.REMAINDER; gbc.weightx = 0; gbc.weighty = 1; gbc.fill=GridBagConstraints.BOTH; Panel bottom = new Panel(); gbl.setConstraints(bottom,gbc); add(bottom); GridBagLayout gbl_bottom = new GridBagLayout(); bottom.setLayout(new GridLayout(1,2)); Panel drawpanel = new Panel(); Panel tablepanel = new Panel(); bottom.add(tablepanel); bottom.add(drawpanel); tablepanel.setLayout(new GridLayout(2,1)); tablepanel.add(parse_table); tablepanel.add(stack_table); drawpanel.setLayout(new BorderLayout()); drawpanel.add("North",northpanel); drawpanel.add("Center",treepanel); } //connection established with the first screen (lexicon, rules, input) public LexRulesInput FirstFrame(){ return MainFrame().myLexRulesInput; } public DemoParser MainFrame(){ return (DemoParser) getParent(); } protected void set_init_values(){ renew_init_values=false; has_to_do_backtracking=false; restore_this_step=false; prev_step_possible=false; //it will be first step in step by step procedure parse_found = false; exp_rule_number = 0; current_row = new Row(1, new_due_symbol(FirstFrame().myRules.my_rules.getItem(0)).trim(), "state at start", 1); due_symbol = current_row.derivation; //the left symbol in "derivation" of the current row state = "initial"; all_results=new String[10][]; how_many_results=0; which_result=0; all_recogn_words=new String(); //clear old stuff my_rules_copy.clear(); good_rules.removeAllElements(); parse_info.removeAllElements(); Backtrack_Store.removeAllElements(); parse_table.setText(""); stack_table.setText(""); Previous_Steps.removeAllElements(); northpanel.removeAll(); northpanel.add(new Label("Parse tree", Label.CENTER)); northpanel.validate(); treepanel.removeAll(); treepanel.validate(); previous_step=new String(); previous_stack=new String(); previous_rules=new Vector(); //renew content of the rules' list for (int i=0; i < FirstFrame().myRules.my_rules.countItems(); i++){ my_rules_copy.addItem("R-"+ String.valueOf(i+1) +" "+ FirstFrame().myRules.my_rules.getItem(i)); } my_rules_copy.validate(); //set initial value of demonstrating elements parse_table.appendText("WORKING TABLE\nStep Derivations Explanation Position\n"); parse_table.appendText(current_row.toString()+"\n"); } //POSSIBLE ACTIONS public boolean action(Event evt, Object whatAction){ if(evt.target == butt_back){ //change the frame (show the first frame) FirstFrame().myInput.clean_old_stuff(); panel_for_input.removeAll(); previous_step=new String(); previous_stack=new String(); previous_rules=new Vector(); MainFrame().myCardLayout.first(MainFrame()); return true; }else if(evt.target == butt_evrthing){ print_at_once=true; set_init_values(); stack_table.setText("BACKTRACKING STORE\nBack to Derivations Alternative Rule Position\n"); while(! state.equals("end_of_job")){ do_piece_of_parsing(); print_stack(Backtrack_Store, stack_table); } renew_init_values=true; print_at_once=false; return true; }else if(evt.target == next_step){ if(renew_init_values){ set_init_values(); } if(restore_this_step){ parse_table.setText(this_step); stack_table.setText(this_stack); redraw_tree(make_set_of_rules(good_rules)); restore_this_step=false; prev_step_possible=true; }else if(! state.equals("end_of_job")){ previous_step=new String(parse_table.getText()); previous_stack=new String(stack_table.getText()); previous_rules=new Vector(); previous_rules=(Vector) good_rules.clone(); prev_step_possible=true; do_piece_of_parsing(); //rewrite stack table stack_table.setText("BACKTRACKING STORE\nBack to Derivations Alternative Rule Position\n"); print_stack(Backtrack_Store, stack_table); }else if(state.equals("end_of_job")){ treepanel.removeAll(); } return true; }else if(evt.target == prev_step){ //only one step back is possible if(prev_step_possible && !print_at_once){ this_step=new String(parse_table.getText()); this_stack=new String(stack_table.getText()); parse_table.setText(previous_step); stack_table.setText(previous_stack); redraw_tree(make_set_of_rules(previous_rules)); restore_this_step=true; prev_step_possible=false; }else{ //keep warning for 1 sec long startTime=System.currentTimeMillis(); parse_in_steps.setText(" NEXT STEP FIRST!!!"); while(System.currentTimeMillis() < startTime+3000){ } parse_in_steps.setText(" PARSE STEP BY STEP"); } return true; }else if(evt.target == results_butt){ redraw_tree(all_results[which_result]); which_result++; if(how_many_results>1){ results_butt.setLabel(" Next tree "); } if(which_result==how_many_results){ if(how_many_results>1){ results_butt.setLabel("Constructed Trees"); }else{ results_butt.setLabel("Constructed Tree"); } which_result=0; } return true; }else if(evt.target == butt_startover){ set_init_values(); return true; }else return false; } //////////////////////////////////////////////////////////////////////////////// //The parsing programm itself - make the job!/////////////////////////////////// //////////////////////////////////////////////////////////////////////////////// //continue till: 1. derivation="" (is empty); 2. current_row.word_number = //// // = all_input_items.length (all words processed!); 3.Backtrack_store is empty// //////////////////////////////////////////////////////////////////////////////// //Methods //check state => actions => state changed => check again //make InputPositionOutOfBoundsException? protected void do_piece_of_parsing(){ //if backtracking has to be done - left from the last step - do it if (has_to_do_backtracking) { backtracking(); has_to_do_backtracking=false; }else{ String status=due_symbol_status(); if(status.equals("empty")){ //all input items are succesfully recognized if(current_row.word_number > FirstFrame().myInput.how_many_items){ parse_found=true; how_many_results++; create_output(); save_result(all_results, good_rules); show_results(how_many_results); if(Backtrack_Store.empty()){ parse_table.appendText("\n One parse found, no other (store empty)\n\n"); parse_info.addElement("\n One parse found, no other (store empty)\n"); show_results(how_many_results); state="end_of_job"; }else{ //separate comments and backtracking in printing step by step parse_table.appendText("\n Parse found,\n but we can try other versions\n\n"); parse_info.addElement("\n Parse found,\n but we can try other versions\n"); has_to_do_backtracking=true; } }else if(current_row.word_number <= FirstFrame().myInput.how_many_items){ if(!Backtrack_Store.empty()){ //separate comments and backtracking in printing step by step parse_table.appendText("\n Parse doesn't cover the whole sentence, backtracking\n\n"); parse_info.addElement("\n Parse doesn't cover the whole sentence, backtracking\n"); has_to_do_backtracking=true; }else{ parse_table.appendText("\n Backtracking is not possible, store is empty\n\n"); parse_info.addElement("\n Backtracking is not possible, store is empty\n"); if(parse_found){ parse_table.appendText("No more parses found\n\n"); parse_info.addElement("No more parses found\n"); }else{ parse_table.appendText("No parse found for this sentence\n\n"); parse_info.addElement("No parse found for this sentence\n"); } show_results(how_many_results); state="end_of_job"; } } //else System.out.println("InputPositionOutOfBoundsException"); }else if(status.equals("non_terminal")){ //if(status.equals("empty")) expansion(); }else{ //due_symbol is terminal if(!recognition()){ if(!Backtrack_Store.empty() ){ //separate comments and backtracking in printing step by step parse_table.appendText("\n Backtracking is possible, trying...\n\n"); parse_info.addElement("\n Backtracking is possible, trying...\n"); has_to_do_backtracking=true; }else{ //if(!Backtrack_Store.empty() ) parse_table.appendText("\n Backtracking is not possible,\n store is empty\n\n"); parse_info.addElement("\n Backtracking is not possible,\n store is empty\n"); if(parse_found){ parse_table.appendText("No more parses found\n\n"); parse_info.addElement("No more parses found\n"); }else{ parse_table.appendText("No parse found for this sentence\n\n"); parse_info.addElement("No parse found for this sentence\n"); } show_results(how_many_results); state="end_of_job"; } //if(!Backtrack_Store.empty() ) } //if(!recognition()) } //if(status.equals("empty")) } } //expansion: two functions: 1)expands with given rule and 2)makes new row //in the parsing table protected void expansion(){ current_row=new Row(current_row.row_number+1, substitute_in_derivation(current_row.derivation, expand_with()), due_symbol + " expanded by R-"+String.valueOf(exp_rule_number+1), current_row.word_number); //select this rule in rule's list my_rules_copy.select(exp_rule_number); //organize printing //add information on the screen and into the parse_info parse_table.appendText(current_row.toString()+"\n"); parse_info.addElement(current_row); //keep the rule used for expansion good_rules.addElement(new Good_Rule(current_row.row_number, FirstFrame().myRules.my_rules.getItem(exp_rule_number))); redraw_tree(make_set_of_rules(good_rules)); due_symbol=new_due_symbol(current_row.derivation); exp_rule_number=0; } protected String expand_with(){ //if no rule from backtracking, check from zero if(exp_rule_number==0){ while(! due_symbol.equals(FirstFrame().myRules.restore_left(FirstFrame().myRules.my_rules.getItem(exp_rule_number)))){ exp_rule_number++; } } //if there is an alternative, put it in stack (rules are ordered! -> rule_number+1) if(exp_rule_number+1 < FirstFrame().myRules.my_rules.countItems() && due_symbol.equals(FirstFrame().myRules.restore_left(FirstFrame().myRules.my_rules.getItem(exp_rule_number+1)))){ curr_backtrack = new Backtrack_row(current_row.row_number, current_row.derivation, exp_rule_number+1, current_row.word_number); Backtrack_Store.push(curr_backtrack); } return(FirstFrame().myRules.restore_right(FirstFrame().myRules.my_rules.getItem(exp_rule_number))); } //recognition: two functions: 1)recognizes terminal and 2)makes new row //in the parsing table protected boolean recognition(){ if(recognized()){ current_row=new Row(current_row.row_number+1, cut_terminal(current_row.derivation), "recognized "+due_symbol+" ("+recognized_word+") ", current_row.word_number+1); //add information on the screen and into the parse_info parse_table.appendText(current_row.toString()+"\n"); parse_info.addElement(current_row); //keep the rule used for expansion good_rules.addElement(new Good_Rule(current_row.row_number, due_symbol+" --> "+recognized_word)); all_recogn_words+=recognized_word+" "; redraw_tree(make_set_of_rules(good_rules)); due_symbol=new_due_symbol(current_row.derivation); return true; }else{ current_row=new Row(current_row.row_number+1, due_symbol, "not recognized, backtracking?", current_row.word_number); //add information on the screen and into the parse_info parse_table.appendText(current_row.toString()+"\n"); parse_info.addElement(current_row); return false; } } protected boolean recognized(){ boolean recognized=false; int index=current_row.word_number; index=index-1; //if input is exhausted (shorter than derivation), return false if(FirstFrame().myInput.all_input_items[index]==null){ return false; } //check all parts of speech for current terminal for(int j=0; (j=0 && current_row.row_number < ( (Good_Rule) good_rules.elementAt(i)).row_number){ good_rules.removeElementAt(i); //delete bad rule i--; //keep going back } } // this function updates information in parse_info // and on the screen (parse_table) protected void correct_info_and_output(){ //while the row number is wrong - remove the row and the line int line_to_remove=parse_info.size()-1; //remove comments first while( !(parse_info.elementAt(line_to_remove) instanceof Row)){ remove_line( (String) parse_info.elementAt(line_to_remove)); parse_info.removeElementAt(line_to_remove); line_to_remove--; } //remove spare rows while( line_to_remove>=0 && current_row.row_number <= ((Row) parse_info.elementAt(line_to_remove)).row_number){ remove_line( ((Row)parse_info.elementAt(line_to_remove)).toString()); parse_info.removeElementAt(line_to_remove); line_to_remove--; } } protected void remove_line(String line){ String curr_text = parse_table.getText(); //find the line at the end of the text int line_to_remove = curr_text.lastIndexOf(line); //get rid of the last line String text_cut = curr_text.substring(0, line_to_remove); //put the cut text parse_table.setText(text_cut); } //replace the due symbol (first left symbol in derivation) //with the right part of the found good rule protected String substitute_in_derivation(String derivation, String found_rule){ derivation=derivation.trim()+" "; found_rule=found_rule.trim()+" "; int next_blank=derivation.indexOf(" "); return (found_rule+derivation.substring(next_blank)).trim(); } //the fatherst left symbol in new string is new due symbol protected String new_due_symbol(String derivation){ derivation=derivation.trim()+" "; int next_blank=derivation.indexOf(" "); derivation=derivation.substring(0,next_blank); derivation=derivation.trim(); return derivation; } protected String cut_terminal(String derivation){ derivation=derivation.trim()+" "; int next_blank=derivation.indexOf(" "); derivation=derivation.substring(next_blank).trim(); return derivation; } protected String due_symbol_status(){ if(due_symbol.equals("")){ return "empty"; }else if(is_left()){ return "non_terminal"; }else return "terminal"; } //check whether a due_symbol is non_terminal (is found on the left side of the rules protected boolean is_left(){ boolean found_left=false; due_symbol=due_symbol.trim(); for(int i=0; i < FirstFrame().myRules.my_rules.countItems(); i++){ if(FirstFrame().myRules.restore_left(FirstFrame().myRules.my_rules.getItem(i)).equals(due_symbol)){ found_left=true; } } return found_left; } protected void save_result(String[][] all_results, Vector good_rules){ //find empty place for new set of rules int i=0; while(all_results[i] != null){ i++; } //make space for new set of rules; all_results[i]=new String[good_rules.size()]; all_results[i]=make_set_of_rules(good_rules); } /////////////////////////////////////////////////////////////////////////// //Show the parsing process (layout, tables, trees) - demonstration part /// /////////////////////////////////////////////////////////////////////////// protected void show_results(int how_many_results){ northpanel.removeAll(); if(how_many_results==0){ northpanel.add(new Label("No parse found!", Label.CENTER)); }else{ northpanel.add(results_butt); if(how_many_results>1){ results_butt.setLabel("Constructed Trees"); } } northpanel.validate(); } protected String[] make_set_of_rules(Vector good_rules){ String[] rules=new String[good_rules.size()]; for(int i=0; i