Syntax

Question 1

What is the difference between syntax, semantics, and pragmatics?

Answer 1

Syntax: What makes correct phrases of different types, Lexicon = what makes correct words, Phrase-level syntax = what makes correct phrases out of words

Semantics: What phrases of different types mean

Pragmatics: What is the force of phrases of different types when used

Question 2

What is a Context Free Grammar (CFG)?

Answer 2

A context-free grammar is 
G = (NT, T, R, S) Where:
NT is a finite set of nonterminals
T is a finite set of terminals
R is a finite set of production rules
S is the starting nonterminal. is an element of NT and corresponds to the syntactic category of a full sentence

Another name for a CFG is Backus-Naur form (BNF)

Question 3

In a CFG what is a derivation sequence for a string?

Answer 3

A sequence of production rules followed to get from the starting nonterminal to the desired string

Question 4

In a CFG what is a Derivation tree?

Answer 4

A tree for a string w where the leaves are labelled with terminals, the root is the start nonterminal and each parent branches according to some production rule.

Question 5

What is an unambiguous grammar?

Answer 5

A grammar that for each string, there is only one derivation tree

Question 6

Name a few examples of well-formedness requirements on programs that can not be captured with CFGs

Answer 6

1. An identifier must be declared before its use
2. The number of parameters of a call of a function agrees with the number of parameters of its definition
3. The type of expression assigned to a variable must be compatible with the variable’s type
4. A variable must be assigned before it is used

Question 7

Compilation is done in a cascade of phases, name those phases:

(Not very important for the exam…)

Answer 7

1. Lexical analysis:
   break a string down into a sequence of tokens
2. Syntactical analysis:
   build a derivation tree
3. Semantic analysis
   Check that the tree is ok from the contextual perspective
4. Generation of intermediate forms
5. Optimization
6. Code generation