Compiler Theory

• Analysis and Synthesis
• Lexemes and Tokens Source Code => Immediate Representation (IR) Abstract Syntax Tree is one of the IRS, The semantics is implied by the tree structure

Input - source code Output - Intermediate Representation + Symbol Table

Phases

• Lexical Analysis - Grouping of words into lexical units (lexemes)
• Syntax Analysis (Parsing) - checks if the program is syntatically correct (syntax tree) (AST, Syntax Tree, Symbol Tree)

Parsing Algorithms - Top Down Parsing - Recursive Descent Parsing, Predictive Parsing, LL - Bottom Up Parsing - LR Parsing, LR, SLR etc. - Semantic Analysis - Checks is semantically consistent with the language definition (Uses Symbol Table). (Checks if each operator is applied to operators of compatible types, Checks if variables are declared, implicit Type conversion)

Symbol Table

Keeps information regarding identifiers in the program. Entities are created and maintained by lexical/syntax analysis.

Code generation

Generation of code from the intermediate representation. Traverse the tree, visit node and generate instruction

Machine code generated from IR (along with code optimizations)

Intermediate Code Generation

AST can be converted to a low level IR.

3-address code (Maximum three operands per instruction)

Input - x = sum + i*10;

t1 = i * 10 t2 = sum + t1 x = t2

LD R1, i MUL R1, #10 LD R2, sum ADD R1, R2 ST x, R1

Type of code generated depend on the types of operands

Lexical Analyzer

Forms meaningful lexical units called lexemes Generates for each lexeme, a token that is composed of a name and optional attribute value (entity)

Token Recognition

Modeled using state transition diagram - Lexemebegin - Forward

Backus-Naur Form

<expression> ::= <expression> + <expression>
            | <id>
            | <num>

Context Free Grammar

G = (N, T, P, S)

N -> set of Non terminals (Variables) T -> set of Terminals (Basic) P -> Production/Grammar rules S -> start symbol

A -> a

A is non terminal, a is string of zero of more terminals and non terminals

A -> head, a -> body

Derivation

Derivation of string begins with the start symbol. Replaces a non terminal with the body of a production for that non terminal

Sentential Form

S =>* a, we say a is a sentential form, which may contain both terminals and non terminals and may be empty

Sentence

A sentence is a sentential form with no non-terminals

• Leftmost derivations
• Rightmost derivations

Parse Tree

A Parse tree is a graphical representation of a derivation

• Root is labelled as the start symbol
• Each leaf is terminal or epsilon
• Each interior node is non-terminal

Ambiguous Grammar

A grammar that produces more than one parse tree for some sentence

Top-Down Parsing

Construct Parse tree, starting from the root and creating nodes in preorder.

Non Terminal -> choose production, add children Terminal -> match with the next input token

Bottom Up Parsing

Construct parse tree bottom-up, starting from the leaves. Parent node A added to a set of nodes matching the body a of production A->a