Programming Languages

Question 1

What is a BNF and what it consists of?

Answer 1

BNF stands for Backus-Naur-Form and it is a formal mathematical way of describing a language (syntax of the language).

In general it consists of:

• set of terminal symbols (RHS only)
• set of non-terminal symbols (either RHS or LHS)
• set of production rules of the form LHS ::= RHS

Question 2

What a two base components of a compiler?

Answer 2

1. Analyzer. Performs:
   - lexical analysis (aka lexer, tokenizer)
   - syntactic analysis
   - semantic analysis
2. Synthesizer. Performs:
   - intermediate code generation
   - optimization
   - code generation

Question 3

Describe compiler’s analyzer steps?

Answer 3

Lexical analysis: translates sequence of characters into sequence of tokens

Syntactical analysis: translates sequence of tokens into a parse tree. Also builds the symbol table

Semantical analysis: traverses the parse tree and performs global checks, e.g. type checking, actual-parameter correspondence.

Question 4

Describe compiler’s synthesizer steps?

Answer 4

Intermediate code generation: traverses the parse tree and generates “abstract machine code”, e.g. triple, quadruples.

Optimization: performs control and data flow analysis., remove redundant ops, move loop invariant ops outside loop

Code generation: Translates intermediate code to actual machine code.

Question 5

Describe what generally the lexer/tokenizer outputs?

Answer 5

Two main outputs: token and value.

Token is an integer code for each lexical class: identifier,
number, keyword, operator, punctuation, etc.

Value is the actual instance. For identifier it is a string, for a number it is its numeric value, etc.

Question 6

What are two main parsing strategies?

Answer 6

Top-down (recursive-descent parsing) and Bottom-up parsing. The deterministic bottom-up parser is strictly more powerful than the top-down parser, but harder to understand and build manually.

Question 7

What is a language recognizer?

Answer 7

Recognizer is a computer program that outputs either Yes or No answer indication whether an input string does belong to a language L defined by a grammar G.

Parser, on the other hand, enhances the parsing tree built by the recognizer with attributes and semantic actions.

Question 8

What are higher order functions?

Answer 8

Higher order functions are the one which take another function as argument or returns it as an output.

Such functions promote code re-use and are useful in translating advanced forms of control such as Python generators.