DEVHIDE
Login Or Sign up

How can I transform this into a recursive descent parser

275 Views Asked by At

My code is a follows (this code 100% works, it just doesn't use recursive descent)

import java.awt.Component;
import java.awt.FlowLayout;
import java.awt.GridLayout;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Scanner;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JPanel;
import javax.swing.JRadioButton;
import javax.swing.JTextField;

public class FileParser {

    private static Scanner scan;

    private static String getLabel(String labelFile) {

        int i;
        labelFile.trim();

        for (i = 0; i < labelFile.length(); i++) {
            char charVal = labelFile.charAt(i);
            boolean bool = Character.isLetter(charVal);

            if (!bool) {
                break;
            }
        }
        return labelFile.substring(0, i);
    }

    public static void main(String[] args) {

        try {
            File inputFile = new File("X:/Path/To/File/Input.txt");
            String mainStr, mainLabel;
            scan = new Scanner(inputFile);
            if (scan.hasNextLine()) {
                mainStr = scan.nextLine().trim();
                mainLabel = getLabel(mainStr);
                if (!mainLabel.equalsIgnoreCase("Window")) {
                    System.out.println("Incorrect Input file should start with WINDOW");
                    return;
                }
                mainStr = mainStr.substring(mainLabel.length()).trim();
                JFrame mainFrame = (JFrame) addCompnt(mainStr, mainLabel);
                mainFrame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
                mainFrame.setVisible(true);
            } else {
                System.out.println("Error");
            }
        } catch (FileNotFoundException fnfe) {
            System.out.println("File not found");
            fnfe.toString();
        } catch (Exception unk) {
            System.out.println("Unknown Error");
            unk.toString();
        }
    }

    private static ArrayList<Integer> getArray(String arrayStr) throws Exception {

        int x, y;

        ArrayList<Integer> arrayInt = new ArrayList<Integer>();
        for (x = 0; x < arrayStr.length(); x++) {
            for (y = x; y < arrayStr.length() && Character.isDigit(arrayStr.charAt(y)); y++);
            if (x != y) {
                arrayInt.add(Integer.parseInt(arrayStr.substring(x, y)));
            }
            x = y;
        }
        return arrayInt;
    }

    private static Component addCompnt(String compntStr, String compntLabel) throws Exception {

        String inputStr;

        if (compntLabel.equalsIgnoreCase("Window")) {
            compntStr = compntStr.trim();
            JFrame wndwFrame;
            if (compntStr.charAt(0) == '"') {
                compntStr = compntStr.substring(1);
                inputStr = compntStr.substring(0, compntStr.indexOf('"'));
                wndwFrame = new JFrame(inputStr);
                compntStr = compntStr.substring(compntStr.indexOf('"') + 1).trim();
            } else {
                wndwFrame = new JFrame("Missing Window Title");
            }
            if (compntStr.charAt(0) == '(') {
                inputStr = compntStr.substring(0, compntStr.indexOf(')') + 1);
                compntStr = compntStr.substring(inputStr.length()).trim();
                ArrayList<Integer> intStr = getArray(inputStr);
                if (intStr.size() == 2) {
                    wndwFrame.setSize(intStr.get(0), intStr.get(1));
                }
            }
            inputStr = getLabel(compntStr);
            compntStr = compntStr.substring(inputStr.length()).trim();
            JPanel loPanel = new JPanel();
            if (inputStr.equalsIgnoreCase("Layout")) {
                inputStr = getLabel(compntStr);
                compntStr = compntStr.substring(inputStr.length()).trim();
                if (inputStr.equalsIgnoreCase("Flow")) {
                    FlowLayout fLayout = new FlowLayout();
                    loPanel.setLayout(fLayout);
                }
                if (inputStr.equalsIgnoreCase("Grid")) {
                    if (compntStr.charAt(0) == '(') {
                        inputStr = compntStr.substring(0, compntStr.indexOf(')') + 1);
                        compntStr = compntStr.substring(inputStr.length()).trim();
                        ArrayList<Integer> intStr = getArray(inputStr);                                         
                        GridLayout gLayout;
                        if (intStr.size() == 2) {
                            gLayout = new GridLayout(intStr.get(0), intStr.get(1));
                            loPanel.setLayout(gLayout);
                        } else if (intStr.size() == 4) {
                            gLayout = new GridLayout(intStr.get(0), intStr.get(1), intStr.get(2), intStr.get(3));
                            loPanel.setLayout(gLayout);
                        }
                    }
                }
            }                    
            while (true) {                                                                                                  
                if (scan.hasNextLine()) {                                                                                   
                    compntStr = scan.nextLine().trim();                                                                     
                    inputStr = getLabel(compntStr);                                                                         
                    if (inputStr.equalsIgnoreCase("end")) {                                             
                        break;                                                                                              
                    } else {                                                                                                
                        Component nestCompnt = addCompnt(compntStr.substring(inputStr.length()), inputStr);                 
                        if (nestCompnt != null) {                                                                           
                            if (nestCompnt.getClass() == wndwFrame.getClass()) {                                            
                                System.out.println("Window can't be nested inside");                                            
                            } else {                                                                                        
                                loPanel.add(nestCompnt);                                                                
                            }                                                                                               
                        }                                                                                                   
                    }                                                                                                       
                } else {                                                                                                                                                                    
                    break;                                                                                                   
                }
            }
            wndwFrame.add(loPanel);
            return wndwFrame;
        }

        
        if (compntLabel.equalsIgnoreCase("Button")) {
            compntStr = compntStr.trim();
            JButton widgetBttn;
            if (compntStr.charAt(0) == '"') {
                compntStr = compntStr.substring(1);
                inputStr = compntStr.substring(0, compntStr.indexOf('\"'));
                widgetBttn = new JButton(inputStr);
                compntStr = compntStr.substring(compntStr.indexOf('"') + 1).trim();
            } else {
                widgetBttn = new JButton("Missing Button Label");
            }
            return widgetBttn;
        }
        
        if (compntLabel.equalsIgnoreCase("Group")) {
            compntStr = compntStr.trim();
            JRadioButton grpBttn;
            if (compntStr.charAt(0) == '"') {
                compntStr = compntStr.substring(1);
                inputStr = compntStr.substring(0, compntStr.indexOf('\"'));
                grpBttn = new JRadioButton(inputStr);
                compntStr = compntStr.substring(compntStr.indexOf('"') + 1).trim();
            } else {
                grpBttn = new JRadioButton("Missing Group Label");
            }
            return grpBttn;
        }
        
        if (compntLabel.equalsIgnoreCase("Label")) {
            compntStr = compntStr.trim();
            JLabel widgetLabel;
            if (compntStr.charAt(0) == '"') {
                compntStr = compntStr.substring(1);
                inputStr = compntStr.substring(0, compntStr.indexOf('\"'));
                widgetLabel = new JLabel(inputStr);
                compntStr = compntStr.substring(compntStr.indexOf('"') + 1).trim();
            } else {
                widgetLabel = new JLabel("Missing Label");
            }
            return widgetLabel;
        }
        
        if (compntLabel.equalsIgnoreCase("Panel")) {
            compntStr = compntStr.trim();
            JPanel compntPnl = new JPanel();
            inputStr = getLabel(compntStr);
            compntStr = compntStr.substring(inputStr.length()).trim();
            if (inputStr.equalsIgnoreCase("Layout")) {
                inputStr = getLabel(compntStr);
                compntStr = compntStr.substring(inputStr.length()).trim();
                if (inputStr.equalsIgnoreCase("Flow")) {
                    FlowLayout panelFlow = new FlowLayout();
                    compntPnl.setLayout(panelFlow);
                }
                if (inputStr.equalsIgnoreCase("Grid")) {
                    if (compntStr.charAt(0) == '(') {
                        inputStr = compntStr.substring(0, compntStr.indexOf(')') + 1);
                        compntStr = compntStr.substring(inputStr.length()).trim();
                        ArrayList<Integer> gridStrg = getArray(inputStr);
                        GridLayout gLayout;
                        if (gridStrg.size() == 2) {
                            gLayout = new GridLayout(gridStrg.get(0), gridStrg.get(1));
                            compntPnl.setLayout(gLayout);
                        } else if (gridStrg.size() == 4) {
                            gLayout = new GridLayout(gridStrg.get(0), gridStrg.get(1), gridStrg.get(2),
                                    gridStrg.get(3));
                            compntPnl.setLayout(gLayout);
                        }
                    }
                }
            }
            while (true) {
                if (scan.hasNextLine()) {
                    compntStr = scan.nextLine().trim();
                    inputStr = getLabel(compntStr);
                    if (inputStr.equalsIgnoreCase("End")) {
                        break;
                    } else {
                        Component errCompnt = addCompnt(compntStr.substring(inputStr.length()), inputStr);
                        if (errCompnt != null) {
                            if (errCompnt.getClass() == new JFrame().getClass()) {
                                System.out.println("Panel Layout Error");
                            } else {
                                compntPnl.add(errCompnt);
                            }
                        }
                    }
                } else {
                    System.out.println("Error in Panel Layout Nesting");
                    break;
                }
            }
            return compntPnl;
        }
        
        if (compntLabel.equalsIgnoreCase("Textfield")) {
            compntStr = compntStr.trim();
            ArrayList<Integer> textStr = getArray(compntStr);
            JTextField txtFld = new JTextField(textStr.get(0));
            return txtFld;
        }
        
        if (compntLabel.equalsIgnoreCase("Radio")) {
            compntStr = compntStr.trim();
            JRadioButton rdoBttn;
            if (compntStr.charAt(0) == '"') {
                compntStr = compntStr.substring(1);
                inputStr = compntStr.substring(0, compntStr.indexOf('\"'));
                rdoBttn = new JRadioButton(inputStr);
                compntStr = compntStr.substring(compntStr.indexOf('"') + 1).trim();
            } else {
                rdoBttn = new JRadioButton("Missing Radio Label");
            }
            return rdoBttn;
        }
        return null;
    }

}

As stated above, this code works, it doesn't use recursive descent. How can I accomplish that?

Input must follow this form:

language definition

Blue text are tokens (title cases are keywords) Red non-terminal Black punctuation are BNF meta symbols

In the production for...

  • window the string is the name that is to appear on the top border of the window and the two numbers are the width and height of the window

  • layout_type that defines the grid layout, the first two numbers represent the number of rows and columns, and the optional next two the horizontal and vertical gaps

  • widget that defines a...

    • button, the string is the name of the button
    • label, the string is the text that is to be placed in the label
    • text field, the number is the width of the text field

  • radio_button, the string is the label of the button

Using recursive descent, I need to create a Java program that will parse the following input file:

Window "Calculator" (200, 200) Layout Flow:
 Textfield 20;
 Panel Layout Grid(4, 3, 5, 5):
   Button "7";
   Button "8";
   Button "9";
   Button "4";
   Button "5";
   Button "6";
   Button "1";
   Button "2";
   Button "3";
   Label "";
   Button "0";
 End;
End;

The output should produce this:

Output Image

Important to note, this is not a calculator!

I have been trying to implement switch/case for this but I am struggling. Most of the widgets follow the same process.

if (compntLabel.equalsIgnoreCase("Button")) {
            compntStr = compntStr.trim();
            JButton widgetBttn;
            if (compntStr.charAt(0) == '"') {
                compntStr = compntStr.substring(1);
                inputStr = compntStr.substring(0, compntStr.indexOf('\"'));
                widgetBttn = new JButton(inputStr);
                compntStr = compntStr.substring(compntStr.indexOf('"') + 1).trim();
            } else {
                widgetBttn = new JButton("Missing widget Label");
            }
            return widgetBttn;

For my switch case statement I was trying to do something like this:

private static String inputToken(String s) {
    JButton widgetBttn;
    String compntStr; //if only this worked
    switch (s.toUpperCase()) {
        case "Button":
        case "Group":
        case "Label":
        case "Panel":
            compntStr = compntStr.trim();
            if (compntStr.charAt(0) == '"') {
                compntStr = compntStr.substring(1);
                inputStr = compntStr.substring(0, compntStr.indexOf('\"'));
                widgetBttn = new JButton(inputStr);
                compntStr = compntStr.substring(compntStr.indexOf('"') + 1).trim();
            break;
        case "Textfield":
            if (compntLabel.equalsIgnoreCase("Textfield")) {// widget ::= Textfield NUMBER ';'
                compntStr = compntStr.trim();
                ArrayList<Integer> textStr = getArray(compntStr);
                JTextField txtFld = new JTextField(textStr.get(0));
            break;
        case "Radio":
            JRadioButton rdoBttn;
            if (compntStr.charAt(0) == '"') {
                compntStr = compntStr.substring(1);
                inputStr = compntStr.substring(0, compntStr.indexOf('\"'));
                rdoBttn = new JRadioButton(inputStr);
                compntStr = compntStr.substring(compntStr.indexOf('"') + 1).trim();
            break;
        default:
            System.out.println("Missing widget label");
            break;
            }
            return widgetBttn;
    }
}

But I also know this doesn't work.

java recursive-descent
Original Q&A
1

There are 1 best solutions below

3
Gene On

Parsing is not only about reading a correct input successfully, but also finding syntax errors in incorrect input. I did not examine your code closely, but I don't see a stack. There's some wonderful computer science that says you can't correctly parse the grammar you've been given without one (because a Panel is a widget that includes other widgets, which may be Panels and yada yada...). It's mathematically impossible. RD parsers use the runtime stack, but it's also possible to use an explicit one in a slightly different coding of the parser, but then it's not RD.

From an LL(1) grammar, a recursive descent parser is almost a direct translation. Happily you have been given an LL(1) grammar!

By far the cleanest organization for a parser like this is to separate the task of scanning from parsing. Scanning is transforming the input into a stream of "tokens." For your language, the following is usable:

enum Token {
  STRING, NUMBER, // Literals.
  COLON, COMMA, DOT, LP, RP, SEMI, // Characters.
  EOF, NONE, // Meta tokens: Values for end-of-input and "no token." 
  Button, Group, End, Flow, Grid, Label, Layout, Panel, Radio, Textfield, Window, // Words.
};

With this, a reasonable scanner interface looks like this:

final class Scanner {

  private final String input;
  private int pos = 0, lastPos = 0;
  private Token token = Token.NONE;

  Scanner(String input) {
    this.input = input;
    advance();  // Advance to the first token on the input.
  }

  // Use Integer.parseInt(getTokenString()); to fetch NUMBER values.
  String getTokenString() {
    return input.substring(lastPos, pos);
  }

  Token getToken() {
    return token;
  }

  private char getChar() {
    return input.charAt(pos);
  }

  void advance() {
    while (pos < input.length() && Character.isWhitespace(getChar())) {
      ++pos; // skip whitespace
    }
    if (pos >= input.length()) {
      token = Token.EOF;
      return;
    }
    lastPos = pos; // Remember where the token starts.
    // Advance the scanner. All the good stuff happens here. Go for it!
    // When advance() is complete, lastPos should be the index of the first
    // character of the token just found, and pos should be the 
    // one _after_ the last. this.token should be the token itself.
    ...
  }

The start of the test input you described (which incidentally has a syntax error; the final semi needs to be a dot instead), looks like this:

Scanner: Window Window
Scanner: STRING "Calculator"
Scanner: LP (
Scanner: NUMBER 200
Scanner: COMMA ,
Scanner: NUMBER 200
Scanner: RP )
Scanner: Layout Layout
Scanner: Flow Flow
Scanner: COLON :
Scanner: Textfield Textfield
Scanner: NUMBER 20
Scanner: SEMI ;
Scanner: Panel Panel
Scanner: Layout Layout
Scanner: Grid Grid
Scanner: LP (
Scanner: NUMBER 4
Scanner: COMMA ,
Scanner: NUMBER 3
Scanner: COMMA ,
Scanner: NUMBER 5
Scanner: COMMA ,
Scanner: NUMBER 5
Scanner: RP )
Scanner: COLON :
Scanner: Button Button
Scanner: STRING "7"
Scanner: SEMI ;

With a working scanner, you can forget about all the details of identifying tokens. That makes the parser a much simpler beast. A reasonable interface looks like this:

class Parser {
  private final Scanner scanner;

  Parser(Scanner scanner) {
    this.scanner = scanner;
  }

  private void match(Token token) {
    if (scanner.getToken() != token) {
      throw new SyntaxError("Expected a " + token + " and found " + scanner.getTokenString());
    }
    scanner.advance();
  }

  void parse() {
    gui();
    match(Token.EOF); // Make sure there's nothing left of the input.
  }

  // Parse the rule "gui" by recursive descent.
  private void gui() {
    ...
  }

  // More recursive descent methods here: one for each grammar rule.
}

Here are some translations of grammar rules to recursive descent methods to get the idea:

  private void gui() {
    match(Token.Window);
    match(Token.STRING);
    match(Token.LP);
    match(Token.NUMBER);
    match(Token.COMMA);
    match(Token.NUMBER);
    match(Token.RP);
    layout();
    widgets();
    match(Token.End);
    match(Token.DOT);
  }

  private void widgets() {
    widget();
    if (isFirstOfWidget(scanner.getToken())) {
      widgets();
    }
  }
  
  private static boolean isFirstOfWidget(Token token) {
    switch (token) {
    case Button:
    case Group:
    case Label:
    case Panel:
    case Textfield:
      return true;
    default:
      return false;
    }
  }

  private void widget() {
    switch (scanner.getToken()) {
    case Button:
      scanner.advance();  // Same as match(Token.Button);
      match(Token.STRING);
      match(Token.SEMI);
      break;
    case Group:
      scanner.advance(); // Same as match(Token.Group);
      radio_buttons();
      match(Token.End);
      match(Token.SEMI);
      break;
    case Label:
      scanner.advance(); // Same as match(Token.Label);
      match(Token.STRING);
      match(Token.SEMI);
      break;
    case Panel:  
      scanner.advance();  // Same as match(Token.Panel);
      layout();
      widgets();
      match(Token.End);
      match(Token.SEMI);
      break;
    case Textfield:
      scanner.advance();  // Same as match(Token.Textfield);
      match(Token.NUMBER);
      match(Token.SEMI);
      break;
    default:
      throw new SyntaxError("Expected a widget, found: " + scanner.getTokenString());
    }
  }

Using these as patterns, you should be able to work out the rest. The key idea is that each method is responsible for matching exactly the tokens that the corresponding grammar rule defines as correct.

Now this parser actually does nothing except verify correctness of the input by gobbling it and looking for "end of input." The next step in making it useful is to add "action" code that does what you need as each rule is matched. In your case, I guess you'll be positioning Swing widgets.

Enjoy this problem! Parsing languages with computer programs is fun and historic. The theory and practice of language parsing was one of the early great successes of computer science.

Related Questions in JAVA

Related Questions in RECURSIVE-DESCENT

Trending Questions

Popular # Hahtags

javascript python java c# php android html jquery c++ css ios sql mysql r reactjs node.js arrays c asp.net json

Popular Questions

.

Copyright © 2021 Jogjafile Inc.