$24
Homework Assignment 2 Solution
Code
You'll need the following files to complete the assignment:
Makefile
arith1.c
arith2.c
Problem 1:
Examine arith1.c: It contains an implementation of a simple arithmatic calculator. The following will compile and run a few test cases.
make arith1
./arith1
1 + 2 + 3
./arith1
1 + 2 * 3
The arith1 language is parsed used a recursive-descent parser: It is fairly straightforward to determine the language's grammar from the parser.
In particular:
Using the code, give the complete grammar in BNF form
Is the grammar left or right recursive? How does that affect the associativity of plus and mult?
Problem 1 Answer:
Problem 2:
Using the grammar you extracted in Problem 1 add two new operators, average, "@", and minus, "-" , operators to the arith1 language . The "-" should have the a higher precedence than "+" and lower precedence than "*". The average operator, "@", should have the higher precedence than "*" but still be able to be overridden using parentheses as defined by the grammar. Both operators should have the same associativity as plus and times.
Give the modified grammar.
Problem 2 Answer:
Problem 3:
Write the left derivation for the following expressions according to the modified grammar from Problem 2 -- It may help to draw the parse tree first.
1 + 2 - 2
2 - 3 * 5
10 - 5 @ 2
10 - 7 - 2
NOTE: You should show only one step at a time -- as we did in class -- but you may jump (skip steps) from
number to the actual terminal number.
For example:
number '+' expr
'10' '+' expr
Problem 3 Answer:
Problem 4:
Modify arith1.c and add the new operator that you defined in Problem 2. Pay careful attention to the pattern between the original grammar and the associated function calls in arith1.c. If you have properly adjusted the grammar, it should be a straightforward modification of the original functions with the additional of a couple new function for the new operator. ()
You should pay careful attention to how expressions evaluate; a compile and a correct evaluation of some expressions does not mean you have modified everything correctly. Try the sample cases below.
./arith
1 + 2 - 2
The result is: 1
./arith
2 - 3 * 5
The result is: -13
./arith
5 @ 2
The result is: 3
./arith
10 - 7 - 2
The result is: 5
./arith
10 - 5 @ 2
The result is: 7
Problem 4 Answer:
Problem 5:
Examine arith2.c: It contains another implementation of a simple arithmetic calculator. The following will compile and run a few test cases.
make arith2
./arith2
1 + 2 * 3
./arith2
1 + 2 + 3
The arith2 language is parsed using a slightly different technique, although it is still considered a recursive-descent parser. Pay careful attention to the way while loops are used to parse, instead of pure recursion. Thinking in terms of EBNF (hint: kleene star) may help determine the difference from the previous grammar.
In particular:
Using the code, give the complete grammar in BNF or EBNF form
Is the grammar left or right recursive? How does that affect the associativity of plus and mult?
Problem 5 Answer:
Problem 6:
Using the grammar you extracted in Problem 5 add two new operators to the arith2 language. The first, minus, should have higher precedence than plus, but lower precedence than mult. The second, average, "@", should have higher precedence than mult, but still be able to be overridden using parentheses as defined by the grammar. Both operators should have the same associativity as plus and times.
Give the modified grammar.
Problem 7:
Write the left derivation for the following expressions according to the modified grammar from Problem 6 -- It may help to draw the parse tree first.
a. 1 + 2 - 2
2 - 3 * 5
10 - 5 @ 2
10 - 7 - 2
NOTE: You should show only one step at a time -- as we did in class -- but may jump from number to the
actual terminal number.
For example:
number '+' expr
'10' '+' expr
Problem 7 Answer:
Problem 8:
Modify arith2.c and add the new operators that you defined in Problem 6. Pay careful attention to the pattern between the original grammar and the associated function calls in arith2.c. If you have properly adjusted the grammar, it should be a straightforward modification of the original functions with the additional of a couple new functions for the new operators.
You should pay careful attention to how expressions evaluate; a compile and a correct evaluation of some expressions does not mean you have modified everything correctly. Try the sample cases below.
./arith
1 + 2 - 2
The result is:
1
./arith
2 - 3 * 5
The result is: -13
./arith
10 - 5 @ 2
The result is:
7
./arith
10 - 7 - 2
The result is:
1
You DO NOT have to paste arith2.c in the template file, but you must submit the modified arith2.c file in the tarball that you will create for this assignment.
Problem 8 Answer:
Problem 9:
Write regular expressions to match the following -- You should test your solutions using rubular.
C identifiers: A C identifier must start with an alpha character or an underscore, and may be followed by alphanumeric characters or the underscore.
Strings: A string must start and end with an double quote and may contain any character except the double quote itself; however, you may escape a double quote inside the string using \ -- i.e. "this is \" a string"
Strings over the alphabet {a,b} that contain an even number of b's.
Strings over the alphabet {a,b,c} that contain an odd number of c's.
Samples:
The following are acceptable strings for (3): abb, bab, bbaaa, ababa; the following should be rejected for (3):
abbb, babb, bbabbb.
The following are acceptable string for (4): cabab, ccaaabc, ccc; the following should be rejected for (4):
cababc, ccaaab, bbabcc.
NOTE: Rubular will feed the entire input at each character into the regex. If we have a regex aa* and give rubular the input "baa" it will match "aa". The entire string does not match however, which is correct and how you should view the regular expression. For example, if you were asked to write a regex that one or more a, and match "baa" on rubular then you have done something wrong.
Problem 9 Answer:
Problem 10:
Both _Bool and bool are available in the ISO C standard published in 2011. Briefly explain:
What are they used for?
Why do both exist?
Is one better than the other? Why?
Problem 10 Answer:
Problem 11:
Page 69 cyu 19:
What are pragmas? Why are they processed by the scanner? Briefly, if you are a language designer what are the trade off of providing pragmas in a language?
Problem 11 Answer:
Problem 12:
Operator precedence and associativity are often subtle details that are overlooked when using a language (and require careful treatment when implementing a compiler). One way around this issue is to use prefix or postfix notation. This is not as foreign as you think, every function call is in prefix notation, so pow(2, 3) is just as valid as + 2 3.
Rewrite the expressions a–d below in prefix notation. Assume the following precedences and associativities for the operators:
Binary Precedence Associativity
Operator (3 highest)
^ 3 left
* 2 left
/ 2 left
+ 1 right
The algorithm for rewriting is very straightforward:
Parenthesize the expression fully, using the rules of precedence and associativity.
Within each parenthesized subexpression, move the operator to left of its left operand.
Remove the parentheses.
The operands will have the same order in the resulting expressions (due to the restriction that the operators are NOT commulatative).
w + x ^ y ^ z
w * x * y ^ z
w + x + y / z
w / x * y / z
Problem 12 Answer:
Problem 13:
Repeat Problem 12, but use postfix notation instead.
Problem 13 Answer:
