Reference no: EM134533

Question 1. Given the productions.

S-> Sa | aaA | AbS

A-> acA

a) List the parse table. Is the grammar LL(1) in this form? If no, why not?

b) If not, rewrite the grammar until it is LL(1), proven. If you cannot accomplish this, why? Either way, show the appropriate sets leading to your decision.

Question 2. Given the LL(1) grammar

S-> aS | B

B-> bBa | Cb

C-> c |d

Assume scanner ( ) and error ( ) functions return the next token and abort processing, respectively. Write a complete LL(1) recursive-descent parser in C- like pseudo code without rewriting the grammar.

Question 3. In your grammar there is no function call. Suppose we want to change function calls so that they evaluate to some returned data, and this data could be used the same way as variables are used in expressions (not left of assignment). For example, you could write x = 2 + F1(5) * 3 which, assuming that F1(5) returns 10, should put 32 into x.

Show changes needed in syntax and explain semantics of function call.

Question 4. Write a program would read two numbers and then print all numbers between the first and the second, inclusive. For example, on input 2 and

Question 5 the program would print 2 3 4 5 (output one per line from the virtual machine).

Question 5. Given the production:

S-> aSAc | Acb

A-> bbb| empty

Implement a complete pseudo code for a recursive descent parser. Assume scanner ( ) function returns the next token and error ( ) aborts processing with an error message. Do not forget the main program. This grammar is LL(1) so no don't modify.

Question 6. Given

S -> SabC | abC | aCa

C -> ccC | c | empty | D

D -> dd

Rewrite the grammar as LL(1) if possible or otherwise argue why it is not possible. Prove that it is indeed LL(1), after the modifications, showing only the sets that are needed and using them for your proof.

Question 7. Suppose you have a language where a valid program is a sequence of assignments, with each ending with a semicolon. An assignment has syntax and semantics as in our language. Expressions can use variables and integers. Variables are not defined just used. There are two predefined variables READ and WRITE. READ evaluates to the standard input value, WRITE doesn't evaluate to anything but it prints to the output the value being assigned to it. Expressions are as follow: binary -,+,*,/,^, and unary!. Expression can be parenthesized, which overrides any precedence.

Precedence is set as: weakest are + and -, then *, then /, then ^, then the unary. Associativity is right to left for + and -, and left to right for all others. Write the unambiguous CFG grammar.

Example statements

x:=READ+5;

WRITE:=x;

x=y+x/(x*5);

Question 8. Suppose you have a language where a valid program is a sequence of statements and nothing else. Every statement ends with semicolon. A statement is either input READ(variable) or assignment

variable = expression, where expression is C-like expression involving ( ) and +,-,*,/ all arithmetical binary operators except - which is both unary and binary, and no other operators. Associativity is set so that all operators are left to right except * which is right to left, Precedence is set so that ( )

overrides anything, the rest, from the strongest to the weakest are:

unary minus

+ and -, the same

* and /, the same.

There are no numbers nor anything else. Variables are not defined.

Example program:

READ(x);

READ(y);

x=y+x/(x*y);

Design unambiguous CFG. Make sure to state what the tokens are.

Question 9. Our project grammar uses input statement which reads input into a variable before it can be used. For example, to read a value and multiply by 10 we must do the following:

READ,x;

y = = x*10;

Suppose that we also want to allow the following:

y = = READ*10;

to do exactly the same semantics except the value is not stored in x. This change should apply to other cases as well, for example we want to be able to say:

IF (READ > 0) THEN ... #meaning if the input is greater than 0

y= =10+READ*READ ... # multiply two inputs, add 10, put result in y

Again, the original syntax/semantics should be preserved and this should be an additional way to accomplish something. Show the grammar to allow that. Prove that it is LL(1).

Question 10. Write a valid C-program that would read an input and then compute and output its factorial. Are there limitations of this program? Be very specific.

Question 11. Given the production:

S-> aSAb | Ab

A-> bbb

implement a complete pseudo code for a recursive descent parser. Assume scanner ( ) returns the next token.

Question 12. Give all needed first and follow sets needed to check if the grammar is LL(1). Is it?:

S -> aA | BB

A -> aaA | empty

B -> bB | Cd

C -> cA | dC

Question 13. A function returns a number, takes no arguments, and its body is a block. Functions are defined exactly like variables in the grammar except that function name is follow by a block. Show the grammar. Is the resulting grammar LL(1)?

Question 14. A function definition must be before the program token, and functions cannot be nested (exactly like in C). Every function has a return type (no void) and one argument. Function call is like in C, with an expression for the argument and the function call itself is an expression. Show the grammar. Examples

int fun1(long x)

begin

/* same as in any block*/

end;

long fun2(int x)

begin

/** ... */

end;

program xxx(void)

begin

int x;

x=fun1(5+2)*10;

end;

Question 15. Design unambiguous grammar to parse expressions involving +, -, *, / and unary -. Unary minus is strongest, followed by * and /(same precedence, right associative), then +, left associative, then finally -, left associative. Do not use any other operators, and use only number tokens.

Question 16. Assume function f ( ) has local variables a, b, and function g is nested inside of f ( ) and has local variable a. There is also a global variable c.

a) show the complete memory space for the program when it begins execution

b) show the stack after f ( ) is called, which subsequently calls g ( ), which calls itself once.

c) assume we have three statements in g ( )

stat1: c=10;

stat2: a=20;

stat3: b=30;

how would they be translated by the compiler: explain in words.

Question 17. Show the grammar for:

a) allow global variables placed just before the first begin - these variables are optional and are listed separated by commas. For example:

program

int x,y,z;

begin {etc.}

b) also allow functions. Each function takes any number of arguments and always returns an integer. Parameter list is C-like, and the return statement (followed by an expression) is mandatory. Functions can be called in place of any expression. Functions are defined with a block, which is the same as the begin-end block in our grammar. Functions are defined separately, as in C but before the main program. Assume we have a multi-pass compiler so that prototypes is not an issue. The following is an example program

int sum(int a, b) {paramater list is same as for globals}

begin

int c;

return a+b;

end;

program

int x,y;

begin

readI(x);

readI(y);

z:=10+sum(x,y+1);

writeI(z);

end.

Question 17. Given the program (like Pascal, with nested functions)

int x, y; {global}

function A

begin

int z; {z is in A}

function B {B is defined inside A}

begin

int x; {x is in B}

function C {C is inside B}

begin

int x; {x is in C}

z:=10:

x:=100;

y:=1000;

C(); {recursive call on C}

end; {end of C}

C();

end; {end of B}

B(); { A calls B}

end; {end of A}

a) show ARs (activation Records) for A, B, C (show only local data, static and dynamic link}

b) What is in the persistent data space?

c) assume call to A() is done somewhere. Then, show that contents of the stack during the 3rd recursive call to C(). Make sure to fill out all info on the stack.

d) How would the left-hand-side variables in C()be translated by the compiler (explain in words, separately for each variable).

Question 18. Given the grammar, with lower case terminals and upper case nonterminals, and S the initial nonterminal

S -> aS | aA | bA

A -> Aa | ABb | cA

B -> bB | bdB | c

a) remove left recursion as needed, showing the modified grammar

b) left-factorize as needed what you get in a), showing the new grammar

c) Is the resulting grammar LL(1)? Argue piece by piece why it is or why it is not, showing all (and only the necessary) First and Follow sets.

Question 19. Assume the following static program structure, show the static chains and display when exactly five ARs are on the stack, assuming procedure A is called first.

proc A

begin /* proc A */

proc B

begin /* proc B */

proc C

begin /* proc C */

call A

end /* proc C */

call C

end /* proc B */

proc D

begin /* proc D */

call B

end /* proc D */

call D

end /* proc A */

Question 20. Write grammar for a language where:

- there is no name for the program

- variables are defined as var varName, varName;

variables are optional

all variables in a block are listed in the same declaration

if var keyword is placed then at least one varName must follow (but may be more than one)

these variables can be found in any <block> and not just <programBlock>

if variables are present in a block, they must precede executable statements

- <stat> can also be a function call (function name followed by single parenthesized expression)

- functions are defined below the program (after end.) one at a time.

each function is defined as function fName(var argName)

followed by <block> {just plain <block>, not <programBlock>}

Write only CFG (not the scanner rules) assuming tokes as in the project (plus var keyword and minus int keyword)

Here is an example parsable program:

program

begin

var x, y, z;

x:=y+10;

printIt(x+y);

begin

var w;

w:=20;

printIt(w);

end;

end.

function printIt(var a)

begin

writeI(a);

end

function notNeeded(var a)

begin

a:=0;

end