Created
April 7, 2017 07:54
-
-
Save DarinM223/81e5308846cd0366275cc5c82eef2d4e to your computer and use it in GitHub Desktop.
Simple parser from a context free grammar
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| package parser; | |
| import java.io.IOException; | |
| import java.io.Reader; | |
| import java.io.Writer; | |
| import static java.util.Objects.requireNonNull; | |
| /** | |
| * A translator that converts simple arithmetic expressions into postfix form. | |
| * | |
| * The context free grammar is: | |
| * | |
| * expr -> expr + term { print('+') } | |
| * | expr - term { print('-') } | |
| * | term | |
| * | |
| * term -> 0 { print('0') } | |
| * | 1 { print ('1') } | |
| * ... | |
| * | 9 { print('9') } | |
| * | |
| * After applying left-recursion-eliminating transformation to prevent infinite recursion the grammar is: | |
| * | |
| * expr -> term rest | |
| * | |
| * rest -> + term { print('+') } rest | |
| * | - term { print('-') } rest | |
| * | e | |
| * | |
| * term -> 0 { print('0') } | |
| * | 1 { print('1') } | |
| * ... | |
| * | 9 { print('9') } | |
| */ | |
| public class Parser { | |
| private final Reader input; | |
| private final Writer output; | |
| private int lookahead; | |
| public Parser(Reader input, Writer output) throws IOException { | |
| this.input = requireNonNull(input); | |
| this.output = requireNonNull(output); | |
| this.lookahead = this.input.read(); | |
| } | |
| /** | |
| * Implements the expr case of the transformed grammar. | |
| * The expr case is: `expr -> term rest`. | |
| * That means that that first the term() method is called to handle the | |
| * term case then the rest() method is called to handle the rest case. | |
| * @throws IOException | |
| */ | |
| public void expr() throws IOException { | |
| this.term(); | |
| this.rest(); | |
| } | |
| /** | |
| * Implements the term case of the transformed grammar. | |
| * The term case is: `i { print('i') }` with i being a digit from 0 to 9. | |
| * This means that if the lookahead character i is a digit, then read the next char by calling | |
| * match(i) and then write out i into the output input. | |
| * @throws IOException | |
| */ | |
| public void term() throws IOException { | |
| if (Character.isDigit((char) this.lookahead)) { | |
| int lookahead = this.lookahead; | |
| match(lookahead); | |
| output.write(lookahead); | |
| } else { | |
| throw new Error("Syntax error"); | |
| } | |
| } | |
| /** | |
| * Implements the rest case of the transformed grammar. | |
| * The rest case is: | |
| * ` rest -> + term { print('+') } rest | |
| * | - term { print('-') } rest | |
| * | e ` | |
| * This means that if the lookahead character is a '+' or '-' then it will | |
| * read the next character, call the term() case, print out '+' or '-', then recursively call | |
| * the rest() case. If the lookahead character is not a '+' or '-' it does nothing. | |
| * | |
| * This code could be written exactly like the grammer by recursively calling rest() over and over | |
| * but rewriting the logic to use an infinite loop will make it less likely to overflow the stack. | |
| * The rewritten logic loops forever and only breaks out if the lookahead character is not a '+' or '-'. | |
| * @throws IOException | |
| */ | |
| public void rest() throws IOException { | |
| while (true) { | |
| switch (lookahead) { | |
| case '+': | |
| this.match('+'); | |
| this.term(); | |
| this.output.write('+'); | |
| break; | |
| case '-': | |
| this.match('-'); | |
| this.term(); | |
| this.output.write('-'); | |
| break; | |
| default: | |
| return; // Break out of the loop if not '+' or '-'. | |
| } | |
| } | |
| } | |
| /** | |
| * Checks if the character passed in matches the lookahead character and | |
| * reads the next character into the lookahead. | |
| * @param ch | |
| * @throws IOException | |
| */ | |
| public void match(int ch) throws IOException { | |
| if (lookahead == ch) { | |
| lookahead = this.input.read(); | |
| } else { | |
| throw new Error("Syntax Error"); | |
| } | |
| } | |
| } |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| package parser; | |
| import java.io.*; | |
| public class Postfix { | |
| public static void main(String[] args) throws IOException { | |
| InputStreamReader reader = new InputStreamReader(System.in); | |
| ByteArrayOutputStream outputStream = new ByteArrayOutputStream(); | |
| OutputStreamWriter writer = new OutputStreamWriter(outputStream); | |
| Parser parse = new Parser(reader, writer); | |
| parse.expr(); | |
| writer.close(); // Close and flush output stream writer. | |
| String output = outputStream.toString(); | |
| System.out.println("Output generated by parser: " + output); | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment