Started out by changing the grammar given into LL(1) grammar:
- Firstly i broke "exp op exp" into terms and factors, to address priority of ** over /
- Then rearranged the symbols to address the associaivity of the operators(term/exp ->(/ right assosiative))(term ** factor -> (** right-assosiative))
- Then i eliminated left-recursion
- I did left- factoring
- Then i calculated FIRST, FOLLOW, FIRST+ just like in the lectures
- Made the Lookahead table
I used the template given for the TernaryEvaluator, Main.java, ParseError.java and the way i read from the stdin in Exp_evaluator.java is identical to that template.
- Helpers: made helper functions to make my life easier for checking symbols
- To check for "**" as its not one character i just checked insade the appropriate functions if everytime we see one star there is another one afterwards
- At first i made all routines boolean so i am sure it recognises the syntax correctly(true) and doesnt accept incorrect expressions(parse error).
- Then i changed them to string so i could construct the given string recursively correctly(without applying the operator rules yet)
- Finally i applied the operations of ** and /:
- **: In term2() : I just add to the end of the string to be returned by term2(), the string that is returned from factor() twice (which is basically b for "a ** b")
- /: In exp(): I check the if the string returned from exp2() is a suffix of the string returned from term() and if so, we apply / operation with a helper function doSlash(String a, String b).
- I already solved associativity from the step where i turned the grammar into LL(1), which is discussed in the "Grammar change" part of the README.
- Firstly i found the Terminals of the language by looking at the examples:
- "+", "(", ")", "{", "}", ",", "if", "else","prefix", "suffix",
- And then the non-terminals so i could bring it into context free grammar, which i wrote in part2_grammar.txt
I got the boilerplate from the tutorials given in the website.
- I wrote the terminals i found from the grammar
- I created 2 new macros, identifier and string_lit , which were written according to the examples given.(my string only gets a-zA-Z and space and my identifiers get a-zA-Z and underscore)
I wrote the .cup file for the parser based on the examples given.
- I declared the terminals that i wrote in the lexical rules of the lexer
- Also the non-terminals that i made all of them strings as we are buildng a compiler so i want to create one big string which will actually be a java source code.
- Added precedence for the concatenation
- I wrote the grammar rules and their results as strings of java code
- For the suffix and prefix functions i just produced the java obj.startsWith(x) and obj.endsWith(x)
- For the if-else conditionals i prefered to output a ternary expression so i could then easily return them and use them as expressions: ((exp.startsWith("com")) ? exp1 : exp2)
- I tried different grammars that ended up showing me the message "Warning : *** Reduce/Reduce conflict found in state #42" so i had to keep trying to eliminate these conflicts. Of course one of them was the one discussed on piazza about differentiating between a function declaration and a call. At first i tried to use the "hack" but i encountered an issue. Because i had distinct non-terminals for arguments(call) and parameters(declaration) , so i guess the parser couldnt decide which was what before finding the "){" token.
- So i decided to use the first fix of changing my grammar.
- I separated the expressions inside functions and the expressions at top level of the program, and removed the rule that let the program have a plain identifier on its own
- Now the parser knows if it sees an identifier inside a function call (foo(x)) that x couldnt have been delcared in the program so now it is sure it's a declaration of a function.
- I also had to break the args rule into out_args and args.
- because if we are inside a function that was already called with an argument we can use that argument with its identifier as an argument in a new call inside that function. But as said on the other bullet we cant do that on a top level. for example:
foo(x){
fun(x); //we should be allowed to do this
}
foo("Compilers")
Also i made the ParserRunner.java that calls the parser, just like the Main given in the example files
After some debugging with the generated java program and some changes in the parser.cup file i ran it with the examples and got the exact program that ran the examples!
- cd Part2
- add the input to input.txt
- make
- make execute < input.txt > Main.java
- javac Main.java
- java Main
