Exercises 1: Introduction, abstract and concrete syntax

Programming Languages 2010

1. The following C code has around six errors (some of them depend on what you count as an error). Locate the errors and explain at which compiler phase they are (or should be) revealed.

    /* this is a buggy hello world program
  
    int main ()
    {
      int i ;
      int j = k + 1 ;
      int a[] = {1,2,3}
      j = a + 6 ;
      a[4] = 7 ;
      printf("hello world\n) ; 
    }

2. Decode the following representation of a JVM program to show (a) the corresponding assembly code and (b) a Java expression from which it can be obtained.

    0001 0000 1111 1111 0001 0000 0010 0000
    0110 0100 0001 0000 0000 1001 0110 1000

Use the key in lecture 1. All codes are found in the on-line JVM specification

3. Consider the context-free grammar

    SWhile. Stm  ::= "while" "(" Exp ")" Stm ;
    SExp.   Stm  ::= Exp ";" ;
    EAss.   Exp  ::= Ident "=" Exp ;
    EGt.    Exp1 ::= Exp2 ">" Exp2 ;
    EIdent. Exp2 ::= Ident ;
    EInt.   Exp2 ::= Integer ;
    _.      Exp  ::= Exp1 ;
    _.      Exp1 ::= Exp2 ;
    _.      Exp2 ::= "(" Exp ")" ;

Show the parse tree and abstract syntax tree of the string

    while (x > y) y = x = 3 ;

4. Write an unambiguous context-free grammar for nonnegative numbers in the decimal notation (0,1,2,...,2007,...). Show the syntax tree of the number 2007.

5. Write a grammar for a subset of unix shell scripts:

• a script is a sequence of command lines
• a command line is either of
  • a single command
  • a pipe: a sequence of commands separated by |
  • any of the above followed by optional one or both of the redirections (< or > followed by a file name)

• a command is a command name followed by an optional sequence of options and an optional sequence of arguments
• an option is - followed by an identifier
• a command name is an identifier
• an argument is a file name

You don't have to specify the structure of identifiers and file names, but can use the basic categories Ident and File.