Help with a Recursive Descent Parser

[Ryan Murphy]

Hi everyone, my name is Ryan. I have been a lurker around here for a while now, but this is my first post here. The reason I am posting is that I have project and I need some help with it. I am currently in an online programming class where we are learning about the differences between languages, and our first project involves writing a program that parses, using recursive descent, a GUI definition language defined in an input file and generates the GUI that it defines. The project includes the grammar for the GUI language as well as the lexical analyzer for the project. With what we have learned so far in the class, I do not feel ready for this project and I am looking for some help to get me started. I want to make clear I am NOT looking for the answer to be handed to me, I am just looking for advice on where I should start and any resources that would be helpful. I appreciate any help that can be given. Thanks and have a good day!

[Carey Brown]

If writing a recursive descent parser by hand is not a part of your requirements, I suggest you look into the ANTLR tool which can generate lexers and parsers in Java.

[Stefan Evans]

I would suggest
- start small/simple with the equivalent of a "Hello World"
- use a test driven approach. Write a test, make it work.

Without knowing more about the assignment, I can't really give more advice than that.
I presume they have given you some libraries/templates to start from and some example input files?

Which bits of the process are you not confident about?
Which bits of the program do you have to write, and which are already there?
e.g. Do you have to open and read the file, or is that done for you?

[Ryan Murphy]

I apologize everyone. I let my lack of confidence cause me to panic before actually thinking things through. I am going to give things a try and come back on here if I run into a specific problem. Sorry for wasting everyone's time.

[Stefan Evans]

No problemo.
And its fully understandable. - just looking at the term: "parsing a GUI Definition language using recursive descent" gave me the shivers.

[Campbell Ritchie]

Welcome to the Ranch

Have you been given a grammar for the language? Have you been given any semantic contents for any of its expressions?

[Ryan Murphy]

HI everyone,

Sorry for the delayed reply; I've been super busy. I am close to getting it working, but I am running into some Problems. I am including the grammar for this project:

gui ::= Window STRING '(' NUMBER ',' NUMBER ')' layout widgets End '.'
layout ::=Layout layout_type ':'
layout_type ::= Flow | Grid '(' NUMBER ',' NUMBER [',' NUMBER ',' NUMBER] ')'
widgets ::= widget widgets | widget
widget ::=
Button STRING ';' |
Group radio_buttons End ';' |
Label STRING ';' |
Panel layout widgets End ';' |
Textfield NUMBER ';'
radio_buttons ::= radio_button radio_buttons | radio_button
radio_button ::= Radio STRING ';'

In the above grammar, the red symbols are nonterminals, the blue symbols are tokens and the black punctuation symbols are BNF metasymbols. Among the tokens those in title case are keywords. The character literals are punctuation tokens.
Below is an explanation of the meaning of some of the symbols in the above productions that should help you understand the actions that are to be performed when each of the productions is parsed:
• In the window production the string is name that is to appear in the top border of the window and the two numbers are the width and height of the window
• In the production for layout_type that define the grid layout, the first two numbers represent the number of rows and columns, and the optional next two the horizontal and vertical gaps
• In the production for widget that defines a button, the string is the name of the button
• In the production for widget that defines a label, the string is text that is to be placed in the label
• In the production for widget that defines a text field, the number is the width of the text field
• In the production for radio_button, the string is the label of the button


This is the code provided by the professor

// CMSC 330
// Project 1
// Duane J. Jarc
// March 25, 2014

// Netbeans under Windows 8

import java.io.*;

// Tnis class provides the lexical analyzer for project 1

class Lexer
{
    private static final int KEYWORDS = 11;
    private StreamTokenizer tokenizer;
    private String punctuation = ",:;.()";
    private Token[] punctuationTokens =
    {
        Token.COMMA, Token.COLON, Token.SEMICOLON, Token.PERIOD, Token.LEFT_PAREN, Token.RIGHT_PAREN
    };

    // Constructor that creates a lexical analyzer object given the source file

    public Lexer(String fileName) throws FileNotFoundException
    {
        tokenizer = new StreamTokenizer(new FileReader(fileName));
        tokenizer.ordinaryChar('.');
        tokenizer.quoteChar('"');
    }

    // Returns the next token in the input stream
    
    public Token getNextToken() throws SyntaxError, IOException
    {
        int token = tokenizer.nextToken();
        switch (token)
        {
            case StreamTokenizer.TT_NUMBER:
                return Token.NUMBER;
            case StreamTokenizer.TT_WORD:
                for (Token aToken : Token.values())
                {
                    if (aToken.ordinal() == KEYWORDS)
                        break;
                    if (aToken.name().equals(tokenizer.sval.toUpperCase()))
                        return aToken;
                }
                throw new SyntaxError(lineNo(), "Invalid token " + getLexeme());
            case StreamTokenizer.TT_EOF:
                return Token.EOF;
            case '"':
                return Token.STRING;
            default:
                for (int i = 0; i < punctuation.length(); i++)
                    if (token == punctuation.charAt(i))
                        return punctuationTokens[i];
        }
        return Token.EOF;
    }

    // Returns the lexeme associated with the current token
    
    public String getLexeme()
    {
        return tokenizer.sval;
    }

    // Returns the numeric value of the current token for numeric tokens
    
    public double getValue()
    {
        return tokenizer.nval;
    }

    // Returns the currebt line of the input file
    
    public int lineNo()
    {
        return tokenizer.lineno();
    }
}

// CMSC 330
// Project 1
// Duane J. Jarc
// March 25, 2014

// Netbeans under Windows 8

// Enumerated type that defines the list of tokens

enum Token {BUTTON, END, FLOW, GRID, GROUP, LABEL, LAYOUT, PANEL, RADIO, TEXTFIELD, WINDOW, 
    COMMA, COLON, SEMICOLON, PERIOD, LEFT_PAREN, RIGHT_PAREN, 
    STRING, NUMBER, EOF};

// CMSC 330
// Project 1
// Duane J. Jarc
// March 25, 2014
// Netbeans under Windows 8

// Class that defines a syntax error

class SyntaxError extends Exception
{
    
    // Constructor that creates a synatx error object given the line number and error

    public SyntaxError(int line, String description)
    {
        super("Line: " + line + " " + description);
    }
}

And this is the parser I built:

import javax.swing.*;
import java.awt.FlowLayout;
import java.awt.GridLayout;
import java.io.IOException;


public class Parser {
	
	Token token;
	Token currentLevel;
	Lexer lexer;
	String textGUI;
	JFrame windowFrame;
	JPanel panel;
	ButtonGroup radioGroup;
	JFileChooser fileChooser;
	JRadioButton radioButton;
	
	public Parser(){
		try {
			fileChooser = new JFileChooser(".");
		    if (fileChooser.showOpenDialog(null) == JFileChooser.APPROVE_OPTION){
		         lexer = new Lexer(fileChooser.getSelectedFile().toString());
		    }
			token = lexer.getNextToken();
			this.parseGUI();
		} catch (SyntaxError | IOException e) {
			e.printStackTrace();
		}
		
	}
	
	public static void main(String[] args){
		new Parser();
	}
		
	public boolean parseGUI() throws SyntaxError, IOException{
		int width;
		int height;
		if(token == Token.WINDOW){
			currentLevel = Token.WINDOW;
			windowFrame = new JFrame();
			token = lexer.getNextToken();
			if(token == Token.STRING){
				windowFrame.setTitle(lexer.getLexeme());
				token = lexer.getNextToken();
				if(token == Token.LEFT_PAREN){
					token = lexer.getNextToken();
					if(token == Token.NUMBER){
						width = (int) lexer.getValue();
						token = lexer.getNextToken();
						if(token == Token.COMMA){
							token = lexer.getNextToken();
							if(token == Token.NUMBER){
								height = (int) lexer.getValue();
								token = lexer.getNextToken();
								if(token == Token.RIGHT_PAREN){
									windowFrame.setSize(width, height);
									token = lexer.getNextToken();
									if(this.getLayout()){
										if(this.getWidgets()){
											if(token == Token.END){
												token = lexer.getNextToken();
												if(token == Token.PERIOD){
													windowFrame.setVisible(true);
													return true;
												}
											}
										}
									}
								}
							}
						}
					}
				}
			}
		}
		return false;
	}
	
	private boolean getLayout() throws SyntaxError, IOException {
		if(token == Token.LAYOUT){
			token = lexer.getNextToken();
			if(this.getLayoutType()){
				if(token == Token.COLON){
					token = lexer.getNextToken();
					return true;
				}
			}
		}
		return false;
	}

	private boolean getLayoutType() throws SyntaxError, IOException {
		int rows;
		int columns;
		int columnGap;
		int rowGap;
		if(token == Token.FLOW){
			if(currentLevel == Token.WINDOW){
				windowFrame.setLayout(new FlowLayout());
			}else{
				panel.setLayout(new FlowLayout());
			}
			token = lexer.getNextToken();
			return true;
		}else if(token == Token.GRID){
			token = lexer.getNextToken();
			if(token == Token.LEFT_PAREN){
				token = lexer.getNextToken();
				if(token == Token.NUMBER){
					rows = (int) lexer.getValue();
					token = lexer.getNextToken();
					if(token == Token.COMMA){
						token = lexer.getNextToken();
						if(token == Token.NUMBER){
							columns = (int) lexer.getValue();;
							token = lexer.getNextToken();
							if(token == Token.RIGHT_PAREN){
								if(currentLevel == Token.WINDOW){
									windowFrame.setLayout(new GridLayout(rows, columns));
								}else{
									panel.setLayout(new GridLayout(rows, columns));
								}
								token = lexer.getNextToken();
								return true;
							}else if(token == Token.COMMA){
								token = lexer.getNextToken();
								if(token == Token.NUMBER){
									columnGap = (int) lexer.getValue();
									token = lexer.getNextToken();
									if(token == Token.COMMA){
										token = lexer.getNextToken();
										if(token == Token.NUMBER){
											rowGap = (int) lexer.getValue();
											token = lexer.getNextToken();
											if(token == Token.RIGHT_PAREN){
												if(currentLevel == Token.WINDOW){
													windowFrame.setLayout(new GridLayout(rows, columns, columnGap, rowGap));
												}else{
													panel.setLayout(new GridLayout(rows, columns, columnGap, rowGap));
												}
												token = lexer.getNextToken();
												return true;
											}
										}
									}
								}
							}
						}
					}
				}
			}
		}
		return false;
	}

	private boolean getWidgets() throws SyntaxError, IOException {
		if(this.getWidget()){
			if(this.getWidgets()){
				return true;
			}
			return true;
		}
		return false;
	}

	private boolean getWidget() throws SyntaxError, IOException {
		int length;
		if(token == Token.BUTTON){
			token = lexer.getNextToken();
			if(token == Token.STRING){
				textGUI = lexer.getLexeme();
				token = lexer.getNextToken();
				if(token == Token.SEMICOLON){
					if(currentLevel == Token.WINDOW){
						windowFrame.add(new JButton(textGUI));
					}else{
						panel.add(new JButton(textGUI));
					}
					token = lexer.getNextToken();
					return true;
				}
			}
		}else if(token == Token.GROUP){
			radioGroup = new ButtonGroup();
			token = lexer.getNextToken();
			if(getRadioButtons()){
				if(token == Token.END){
					token = lexer.getNextToken();
					if(token == Token.SEMICOLON){
						token = lexer.getNextToken();
						return true;
					}
				}
			}
		}else if(token == Token.LABEL){
			token = lexer.getNextToken();
			if(token == Token.STRING){
				textGUI = lexer.getLexeme();
				token = lexer.getNextToken();
				if(token == Token.SEMICOLON){
					if(currentLevel == Token.WINDOW){
						windowFrame.add(new JLabel(textGUI));
					}else{
						panel.add(new JLabel(textGUI));
					}
					token = lexer.getNextToken();
					return true;
				}
			}
		}else if(token == Token.PANEL){
			if(currentLevel == Token.WINDOW){
				windowFrame.add(panel = new JPanel());
			}else{
				panel.add(panel = new JPanel());
			}
			currentLevel = Token.PANEL;
			token = lexer.getNextToken();
			if(getLayout()){
				if(getWidgets()){
					if(token == Token.END){
						token = lexer.getNextToken();
						if(token == Token.SEMICOLON){
							token = lexer.getNextToken();
							return true;
						}
					}
				}
			}
		}else if(token == Token.TEXTFIELD){
			token = lexer.getNextToken();
			if(token == Token.NUMBER){
				length = (int) lexer.getValue();
				token = lexer.getNextToken();
				if(token == Token.SEMICOLON){
					if(currentLevel == Token.WINDOW){
						windowFrame.add(new JTextField(length));
					}else{
						panel.add(new JTextField(length));
					}
					token = lexer.getNextToken();
					return true;
				}
			}
		}
		return false;
	}

	private boolean getRadioButtons() throws SyntaxError, IOException {
		if(getRadioButton()){
			if(getRadioButtons()){
				return true;
			}
			return true;
		}
		return false;
	}

	private boolean getRadioButton() throws SyntaxError, IOException {
		if(token == Token.RADIO){
			token = lexer.getNextToken();
			if(token == Token.STRING){
				textGUI = lexer.getLexeme();
				token = lexer.getNextToken();
				if(token == Token.SEMICOLON){
					radioButton = new JRadioButton(textGUI);
					radioGroup.add(radioButton);
					if(currentLevel == Token.WINDOW){
						windowFrame.add(radioButton);
					}else{
						panel.add(radioButton);
					}
					token = lexer.getNextToken();
					return true;
				}
			}
		}
		return false;
	}
}

Sorry for the length of the file, I just want to give everyone a feel of what I have and the scope of the project. Right now, one problem I know I am having is that my Parser is not properly handling nested Panels.


Placing the below text into a text file:

Window "Testing" (600, 500) Layout Flow:
Button "Test1";
Textfield 20;
Label "Something";
Group
Radio "A";
Radio "B";
Radio "C";
Radio "D";
Radio "E";
Radio "F";
End;
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;
Panel Layout Flow:
Group
Radio "z";
Radio "x";
Radio "y";
Radio "v";
End;
Panel Layout Grid(3, 3):
Button "X";
Button "O";
Button "X";
Button "O";
Button "X";
Button "O";
Button "X";
Button "O";
Button "X";
End;
End;
End.

Should produce the following image:



Instead it produces this:



Any suggestions on what might be the source of the problem?

Thanks!

[Carey Brown]

I don't see the specific problem but it looks like a Panel is not dealing with the End properly and putting the following Panel inside of the first Panel.

[Ryan Murphy]

Thanks for the feedback, I was kinda wondering if that might have had something to do with it. The only question I have is how to I handle keeping track in the parser which panel I am adding to? I think that might be the root of the problem.

[Carey Brown]

Starting at line 212:

        }else if(token == Token.PANEL){
            if(currentLevel == Token.WINDOW){
                windowFrame.add(panel = new JPanel());
            }else{
                panel.add(panel = new JPanel());
            }
            currentLevel = Token.PANEL;
            token = lexer.getNextToken();
            if(getLayout()){
                if(getWidgets()){
                    if(token == Token.END){
                        token = lexer.getNextToken();
                        if(token == Token.SEMICOLON){
                            token = lexer.getNextToken();
                            return true;
                        }
                    }
                }
            }

getWidgets() on line 10 will return false when it encounters END. Maybe leave getWidgets() but remove enclosing if().
I tried to compile your code but there are pieces missing. I'm assuming you omitted them because they were too long.

[Ryan Murphy]

I think I figured out the source of my problem. In between 242 and 243 on my parser class I inserted the following line:

currentLevel = Token.WINDOW;

I retired that and other examples and so far they all seem to be compline correctly. Thanks everyone for the welcome and the help. I look forward to learning more! :-)