KOI: Exercise 1: Basics, phases and Linux

You can do this exercise in any size group you wish. Don't worry if you find some of the questions difficult to answer, since they may be intended to initiate a discussion rather than have a single correct answer.

There might also be more questions than you have time to answer, but do as many as you can.

Preparations

Before this exercise you should have:

Question 1

When writing a computer program it is a good idea to divide it into modules, at least if it isn't very small. This is no less true for compilers. We have made an attempt to divide the compiler into modules, and we came up with this list:
  1. code generation
  2. debugger
  3. editor
  4. intermediate code generation
  5. lexical analysis ("scanning")
  6. linking
  7. machine-dependent optimization
  8. machine-independent optimization
  9. semantic analysis
  10. symbol table
  11. syntactic analysis ("parsing")

a) Some of these modules are usually called phases. What is a phase?

b) Another term used in the compiler context is pass. What is the difference between a phase and a pass?

c) In the list above, the modules have been ordered alphabetically. List the phases in the correct order, for example by drawing a number of squares connected with arrows.

d) The input to the compiler, and to the first phase, is the source program as text (that is, a sequence of characters), while the output from the compiler, and from the last phase, is the target program, typically as assembly language or machine language. What are the input and output of each phase? You can write them at the arrows between the squares from the question above.

e) One of the modules is part of the compiler, but isn't a phase. Which one?

f) Some of the listed modules are not part of the compiler, but are used or exist in connection to the compiler. Add them to the figure with the phases.

Question 2

What is the difference between a parser, a grammar and a language?

Question 3

What are some important differences between a natural language, such as Swedish or English, and a computer language, such as C, XML or SQL?

Question 4

Chose a programming language that you are familiar with, such as C, C++ or Java, and give concrete examples (that is, with snippets of source code) of examples of errors that can be detected in:

a) the lexical analysis ("the scanner")

b) the syntactic analysis ("the parser")

c) the semantic analysis

Question 5

We are writing a program to help schoolchildren train addition. The user should enter two numbers and their sum, and the program will answer if it was correct or wrong. Two examples, with the user's input underlined: 

En övning i addition!
Ange två tal och deras summa: 10 29 39
Rätt!


En övning i addition!
Ange två tal och deras summa: 20 30 60
Nej, 20 + 30 blir 50!

We have written the program in C, but we made some mistakes, and when we try to build (that is, compile and link) and run the program, we will get the error and warning messages that are shown. In which of the compiler phases, or at other times, are each of these errors and warnings detected?

(Some of the errors may have to be fixed before we can continue the build an get the other errors.)

The program Messages
#include <stdio.h>

int main(void) {
  int a, b, summan;

  printf("En övning i addition!\n)
  printf("Ange två tal och deras summa: ");
  scanf("%d", &a);
  scanf("%d", b);
  scanf("%d", &gissning);
  if (gissning == summan)
    printf("Rätt!\n");
  else
    print("Nej, %d + %d blir %d!\n",
          a, b, summan);
  return "0";
}






(1) warning: missing terminating " character
(2) error: expected ';' before 'printf'

(3) Segmentation fault (core dumped)
(4) error: 'gissning' undeclared
(5) warning: 'summan' is used uninitialized


(6) undefined reference to 'print'

(7) warning: returning 'char *' from a function with return type 'int'

Question 6

The C program below contains some mistakes. When we try to build (that is, compile and link) and run the program, we will get the error and warning messages that are shown. In which of the compiler phases, or at other times, are each of these errors and warnings detected?

(Some of the errors may have to be fixed before we can continue the build an get the other errors.)

The program Messages
#include <stdio.h>

int main(void) {
    int a;
    int 2a;

    printf("Hej!\n");
    printg("Ange ett tal: ");

    scanf("%d", &a);
    printf("Talet = %d\n", a);

    return 0;
}





(1) error: invalid suffix "a" on integer constant


(2) warning: implicit declaration of function 'printg'
(3) error: undefined reference to `printg'

Question 7

The C program below contains some mistakes. When we try to build (that is, compile and link) and run the program, we will get the error and warning messages that are shown. In which of the compiler phases, or at other times, are each of these errors and warnings detected?

(Some of the errors may have to be fixed before we can continue the build an get the other errors.)

The program Messages
#include <stdio.h>

int main(void) {
  int i = 17;
  float f = 3.14;
  char c = 'x';
  char* s = "foo;

  s = f;
  printf("f = %f\n", i);

  c s;
  return;
}







(1) missing terminating " character

(2) error: incompatible types in assignment
(3) warning: double format, different type arg (arg 2)

(4) error: syntax error before "s"
(5) warning: `return' with no value, in function returning non-void

Question 8

The C program below contains some mistakes. When we try to build (that is, compile and link) and run the program, we will get the error and warning messages that are shown. In which of the compiler phases, or at other times, are each of these errors and warnings detected?

(Some of the errors may have to be fixed before we can continue the build an get the other errors.)

The program Messages
#inglude <stdio.h>

int main(void) {
    int x, y, z, t;

    printf("Ange x: );
    scanf("%d", &x);
    printf("Ange y: ")
    scanf("%d", y);
    t = x + y;
    u = x + y;
    printf("z = %d\n", z);
    f(8);

} // main

(1) error: invalid preprocessing directive #inglude




(2) warning: missing terminating " character

(3) error: expected ';' before '}' token
(4) Segmentation fault (core dumped)
(5) warning: variable 't' set but not used
(6) error: 'u' undeclared
(7) warning: 'z' is used uninitialized
(8) warning: implicit declaration of function 'f'
(9) undefined reference to 'f'

Question 9

What are some important differences between Linux, Windows and macOS (which is what Apple now calls the OS previously known as Mac OS X)?

Question 10

Which are the most useful commands that you can give in a shell in Linux?

There are solutions to some of the questions, but try to solve them yourself first.

Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se), September 8, 2023