What are the advantages to using nondeterminism when writing compilers? The disadvantages?

What are the advantages of using a table driven algorithm for some task in a compiler, over writing code that does the task directly? Disadvantages?

Suppose language L8 has 8 levels of operator precedene, and variant language L4 has 4 levels. L8 and L4 are otherwise identical, and have the same set of operators. What are the implications of this distinction for the programmer using L8 and L4 and compilers for these languages?

Show that the following grammar is LL(1)

  s => AaAb|BbBa
  A => epsilon
  B => epsilon

What actions does an LR shift reduce parser take when it makes a reduction?

Both LL(k) and LR(k) grammars see only k symbols of input as lookahead. However, LR parsers are more powerful than LL parsers. Briefly explain why this is so.

Your friend in the next office wrote the C++ compiler you use for extended PL/0 compiler development. He comes to you and says he has just found a bug in his compiler, and that under some circumstances division of two integers will produce a slightly wrong result. What impact does this have on your extended PL/0 compiler? On your users?

What is regression testing, and how is it used for writing compilers?

Why should the compiler writer not attempt to convert floating point literals to the computer's internal representation?

Show the reduced deterministic finite state machine that recognizes this regular expression. Think before you dive in.

(AB((AB)*|epsilon)(C|epsilon)|epsilon)

Suppose we further extend PL/0's if/then/else/end statement, so that the then and else clauses can appear in any order. A particular kind of clause can appear only 1 or fewer times.

• Draw the railroad diagram(s) that capture these syntactic requirements
• Is the language still LL(1)? (Why?)
• What implication would these changes have on the APT constructor?

Suppose we wanted to modify part or all of the PL/0 compilation system to support some new requirements. For each of the requirements listed below briefly describe what part of the compilation system would have to be modified to support that change, and what those changes would entail. (Consider each question independently.)

• Generate assembly code for a new target machine.
• Introduce a string data type.
• Prove that the PL/0 program will always terminate.
• Allow numbers to be specified in octal radix if the first digit is a 0.
• Introduce a built-in global variable to all PL/0 programs that is named 'radix', is of type 1..10, and determines the radix used to interpret numbers.
• Enforces a requirement that expressions in PL/0 cannot be parenthesized more than one level deep. For example, "1*(2+a)" is legal, but "1*(2+(a))" would not be legal.
• The PL/0 compiler is not to use any dynamic storage allocation.

I'm a hot shot compiler writer with these problems and resources:

• Do all of my work on a Sun SPARC
• Have SPARC binary named ucc that compiles C into UIR, which is a universal intermediate representation for C programs.
• Have SPARC binary named lex to translate scanner specs to equivalent scanners encoded in C
• Have SPARC binary named yacc to translate parser specs to eqiuvalent parsers encoded in C
• Have programming language called FOO, and have to write the FOO compiler
• Must write FOO in extended PL/0
• Customer wants to compile + execute FOO on a MIPS
• Have scanners specs FOO.l and 0.l for FOO and PL/0
• Have parser specs FOO.y and 0.y for FOO and PL/0