Program 1 - Instructions

program   stmt_list $$ stmt_list   stmt_list stmt stmt_list   stmt stmt   id := expr stmt   read id  stmt   write expr stmt   if condition then stmt_list fi condition   expr relation expr  expr   term expr   expr add_op term term   factor  term   term mult_op factor factor   ( expr ) | id  add_op   +  add_op   - mult_op   *  mult_op   / 

NOTE_1: an id can be considered any single character and number can be considered any single digit. This just follows the idea that "if it's not a keyword, it must be an identifier." NOTE_2: The $$ just means "The top of the stack" which -- in practical terms -- just means the end of the file!  YOU MAY ASSUME THAT ALL INPUT IS COMPLETELY SPACE DELIMITED (just so you don't have to alter the Lexer) AND ALL LOWER CASE (though making the parser case-insensitive would be trivial).

Instructions:

Modify the sample code (above) to parse "Programs" based upon the grammar above

NOTE that only the Parser and Token classes should require any changes; you may make other alterations if desired, but only these two files actually need to be changed.

The parser should "accept" valid "programs" and generate the .DOT (Graphviz) "code" necessary to draw a full parse tree.

The parser should "reject" invalid "programs" with a descriptive error message; this message should be part of output tree.

The program should accept a filename from the "Command Line" as illustrated in the example.

Submit

• The modified parser code which incorporates the changes described above.
  • If using Netbeans, Eclipse, or any other IDE, I only want the contents of the source folder (Parser.java and Compiler.java), not the whole project.
  • The code should be complete. ie., all code necessary to compile and run it should be included... even if you only changed the Parser.java file.
• Please do NOT include any code that is not relevant to the project. (Partial samples, etc.)
  • (In other words: all of the necessary code and only the necessary code).

  • ParserExample; import java.util.ArrayList; import java.util.Arrays; import java.util.List; /* GRAMMAR FOR PROCESSING SIMPLE SENTENCES:  ::=       ::=    |   ::=     ::=   | <>  ::=    | <>  ::=   |   ::=   | <> // *** Terminal Productions (Actual terminals omitted, but they are just the valid words in the language). ***  ::= ','  ::= '.' | '!'  ::= ...adjective list...  ::= ...adverb list...  ::= ...article list...  ::= ...conjunction list...  ::= ...noun list...  ::= ...preposition list...  ::= ...verb list.... */ /** * The Syntax Analyzer * */ class Parser { // The lexer which will provide the tokens private final LexicalAnalyzer lexer; private final CodeGenerator codeGenerator = new CodeGenerator(); /** * The constructor initializes the terminal literals in their vectors. * * @param lexer The Lexer Object */ public Parser(LexicalAnalyzer lexer) { this.lexer = lexer; } /** * Begin analyzing... * * @throws MockCompiler.ParseException */ public void analyze() { try { // Generate header for our output codeGenerator.writeHeader(); // Start the actual parsing. Sentence("PARSE TREE"); // "PARSE TREE" is just the root node. // generate footer for our output codeGenerator.writeFooter(); // The footer for the compiled output // For graphically displaying the output. // CodeGenerator.openWebGraphViz(); } catch (ParseException ex) { System.err.println("Syntax Error: " + ex); } } //  ::=      protected void Sentence(String from) throws ParseException { final String nodeName = codeGenerator.buildNodeName(""); codeGenerator.addNonTerminalToTree(from, nodeName); NP(nodeName); VP(nodeName); NP(nodeName); PP(nodeName); Sentence_Tail(nodeName); } //  ::=   |  void Sentence_Tail(String from) throws ParseException { final String nodeName = codeGenerator.buildNodeName(""); codeGenerator.addNonTerminalToTree(from, nodeName); if (isCurrentToken(TOKEN.CONJUNCTION)) { CONJ(nodeName); Sentence(nodeName); } else { EOS(from); } } //  ::=    void NP(String from) throws ParseException { final String nodeName = codeGenerator.buildNodeName(""); codeGenerator.addNonTerminalToTree(from, nodeName); ART(nodeName); ADJ_LIST(nodeName); NOUN(nodeName); } //  ::=   | <> void ADJ_LIST(String from) throws ParseException { final String nodeName = codeGenerator.buildNodeName(""); if (isCurrentToken(TOKEN.ADJECTIVE)) { codeGenerator.addNonTerminalToTree(from, nodeName); ADJ(nodeName); ADJ_TAIL(nodeName); } } //  ::=    | <> void ADJ_TAIL(String from) throws ParseException { final String nodeName = codeGenerator.buildNodeName(""); if (isCurrentToken(TOKEN.ADJ_SEP)) { codeGenerator.addNonTerminalToTree(from, nodeName); ADJ_SEP(nodeName); if (isCurrentToken(TOKEN.ADJECTIVE)) { ADJ_LIST(nodeName); } else { raiseException(TOKEN.ADJECTIVE, from); } } } //  ::=   |  void VP(String from) throws ParseException { final String nodeName = codeGenerator.buildNodeName(""); codeGenerator.addNonTerminalToTree(from, nodeName); if (isCurrentToken(TOKEN.ADVERB)) { ADV(nodeName); } VERB(nodeName); } //  ::=   | <> void PP(String from) throws ParseException { final String nodeName = codeGenerator.buildNodeName(""); if (isCurrentToken(TOKEN.PREPOSITION)) { codeGenerator.addNonTerminalToTree(from, nodeName); PREP(nodeName); NP(nodeName); } } ///////////////////////////////////////////////////////////////////////////////////// // For the sake of completeness, each terminal-token has it's own method, // though they all do the same thing here. In a "REAL" program, each terminal // would likely have unique code associated with it. ///////////////////////////////////////////////////////////////////////////////////// //  void EOS(String from) throws ParseException { ProcessTerminal(TOKEN.EOS, from); } //  void ADJ(String from) throws ParseException { ProcessTerminal(TOKEN.ADJECTIVE, from); } //  void ADV(String from) throws ParseException { ProcessTerminal(TOKEN.ADVERB, from); } //  void ART(String from) throws ParseException { ProcessTerminal(TOKEN.ARTICLE, from); } //  void CONJ(String from) throws ParseException { ProcessTerminal(TOKEN.CONJUNCTION, from); } //  void NOUN(String from) throws ParseException { ProcessTerminal(TOKEN.NOUN, from); } //  void PREP(String from) throws ParseException { ProcessTerminal(TOKEN.PREPOSITION, from); } //  void VERB(String from) throws ParseException { ProcessTerminal(TOKEN.VERB, from); } //  void ADJ_SEP(String from) throws ParseException { ProcessTerminal(TOKEN.ADJ_SEP, from); } //////////////////////////////////////////////////////////////////////////// // Terminal: // Test it's type and continute if we really have a terminal node, syntax error if fails. void ProcessTerminal(TOKEN terminal, String from) throws ParseException { final String terminalID = codeGenerator.buildNodeName("<" + terminal.name() + ">"); if (!isCurrentToken(terminal)) { raiseException(terminal, from); } else { codeGenerator.addNonTerminalToTree(from, terminalID); codeGenerator.addTerminalToTree(terminalID, lexer.getLexeme()); lexer.advanceToken(); } } // The code below this point is just a bunch of "helper functions" to keep the // parser code (above) a bit cleaner. // Simple Wrapper around current token. private boolean isCurrentToken(TOKEN token) { return token == lexer.getToken(); } // Handle all of the errors in one place for cleaner parser code. private void raiseException(TOKEN expected, String from) throws ParseException { final String template = "SYNTAX ERROR: '%s' was expected but '%s' was found."; String err = String.format(template, expected.toString(), lexer.getLexeme()); System.out.printf("\t\"%s\" -> {\"%s\"};%n}%n", from, err); throw new ParseException(err); } static class ParseException extends Exception { public ParseException(String errMsg) { super(errMsg); } } } /** All Of the Tokens Used by the parser **/ enum TOKEN { ARTICLE("a", "the"), CONJUNCTION("and", "or"), NOUN("dog", "cat", "rat", "house", "tree"), VERB("loves", "hates", "eats", "chases", "stalks"), ADJECTIVE("fast", "slow", "delicious", "furry", "sneaky", "lazy", "tall"), ADJ_SEP(","), ADVERB("quickly", "secretly", "silently"), PREPOSITION("of", "on", "around", "with", "up"), EOS(".", "!"), START, EOF, OTHER; private final List lexemeList; private TOKEN(String... tokenStrings) { lexemeList = new ArrayList<>(tokenStrings.length); lexemeList.addAll(Arrays.asList(tokenStrings)); } public static TOKEN fromLexeme(final String string) { // Just to be safe... String lexeme = string.trim(); // An empty string should mean no more tokens to process. if (lexeme.isEmpty()) { return EOF; } // Search through ALL lexemes looking for a match with early bailout. for (TOKEN t : TOKEN.values()) { if (t.lexemeList.contains(lexeme)) { // early bailout. return t; } } return OTHER; } }