KOI: Some solutions to exercise 1

Please note that these are suggested solutions. There can be other solutions that are also correct.

Question 1

a) ...

b) ...

c)

  1. lexical analysis ("scanning")
  2. syntactic analysis ("parsing")
  3. semantic analysis
  4. intermediate code generation
  5. machine-independent optimization
  6. code generation
  7. machine-dependent optimization

d) ...

e) the symbol table

f) ...

Question 2

A language is defined as the set of all valid sentences ("programs", "inputs", "sequences of tokens") that can be written (or said) in the language.

A grammar for a language is a description, typically using some form of rules, that describes which sentences are valid in the language. The same language can be described by many different grammars.

A parser is a computer program, or part of a computer program, that analyzes its input to determine if it is valid in a certain language. It usually also outputs some representation of the input, for example as a tree structure.

Question 3

Natural languages are usually much larger, much more complex, much more general (can be used for many purposes) and have much fuzzier limits between correct and incorrect usage, than computer languages. Sentences in natural languages can also be much more ambiguous (the same sentence can be interpreted in different ways) than computer programs.

Question 4

a) ...

b) ...

c) ...

Question 5

  1. Scanner
  2. Parser
  3. Program execution
  4. Semantic analysis
  5. Optimizer or semantic analysis
  6. Linker
  7. Semantic analysis

Question 6

  1. Scanner
  2. Semantic analysis
  3. Linker

Question 7

  1. Scanner
  2. Semantic analysis
  3. Semantic analysis (possibly!)
  4. Parser
  5. Semantic analysis

Question 8

  1. Preprocessor
  2. Scanner
  3. Parser
  4. Program execution
  5. Optimizer or semantic analysis
  6. Semantic analysis
  7. Optimizer or semantic analysis
  8. Semantic analysis
  9. Linker

Question 9

Linux is free software, or open source, while the others are not. Linux and macOS are based on, or similar to, Unix, while Windows is not. Linux and (to a lesser extent) Windows run on many different types of hardware, while macOS only runs on Apple computers.

Question 10

ls, rm, cp, cd, mkdir, alias, gcc, gdb, make, ...

Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se) October 27, 2022