Computer Language Engineering Overview

Introduction

Outline Introduction to computer language engineering What are compilers? Why should we learn about them? Anatomy of a compiler

Why Study Compilers? Compilers enable programming at a high level language instead of machine instructions. Malleability, Portability, Modularity, Simplicity, Programmer Productivity Also Efficiency and Performance

Why Study Compilers? Build a large, ambitious software system. See theory come to life. Learn how to build programming languages. Learn how programming languages work. Learn tradeoffs in language design.

Compilers Construction touches many topics in Computer Science Theory Algorithms Graph manipulation, dynamic programming Data structures Symbol tables, abstract syntax trees Systems Allocation and naming, multi-pass systems, compiler construction Computer Architecture Memory hierarchy, instruction selection, interlocks and latencies, parallelism Security Detection of and Protection against vulnerabilities Software Engineering Software development environments, debugging Artificial Intelligence Heuristic based search for best optimizations Finite State Automata, Grammars and Parsing, data-flow

Power of a Language Can use to describe any action Not tied to a context Many ways to describe the same action Flexible

How to instruct a computer How about natural languages? English?? Open the pod bay doors, Hal. I am sorry Dave, I am afraid I cannot do that We are not there yet!! Natural Languages: Powerful, but Ambiguous Same expression describes many possible actions

Programming Languages Properties need to be precise need to be concise need to be expressive need to be at a high-level (lot of abstractions)

1. How to instruct the computer Write a program using a programming language High-level Abstract Description Microprocessors talk in assembly language Low-level Implementation Details

1. How to instruct the computer Input: High-level programming language Output: Low-level assembly instructions Compiler does the translation: Read and understand the program Precisely determine what actions it require Figure-out how to faithfully carry-out those actions Instruct the computer to carry out those actions

Example (input program) int sumcalc(int a, int b, int N) { int i, x, y; x = 0; y = 0; for(i 0; i <= N; i++) { x = x + (4*a/b)*i + (i+1)*(i+1); x = x + b*y; } return x; }

Example (Output assembly code) sumcalc, .-sumcalc .section .Lframe1: .long .LSCIE1:.long .byte .string .uleb128 .sleb128 .byte .byte .uleb128 .uleb128 .byte .uleb128 0x1 .align . .long .quad .quad .byte .long .byte .uleb128 .byte .uleb128 .byte .long .byte .uleb128 .align .size %rbp %rsp, %rbp %edi, -4(%rbp) %esi, -8(%rbp) %edx, -12(%rbp) $0, -20(%rbp) $0, -24(%rbp) $0, -16(%rbp) -16(%rbp), %eax -12(%rbp), %eax .L3 -4(%rbp), %eax 0(,%rax,4), %edx -8(%rbp), %rax %rax, -40(%rbp) , -40(%rbp), %rcx pushq movq movl movl movl movl movl movl movl cmpl jg movl leal leaq movq .LECIE1-.LSCIE1 0x0 0x1 "" 0x1 -8 0x10 0xc 0x7 0x8 0x90 8 .LASFDE1-.Lframe1 .LFB2 .LFE2-.LFB2 0x4 .LCFI0-.LFB2 0xe 0x10 0x86 0x2 0x4 .LCFI1-.LCFI0 0xd 0x6 8 movq cltd idivl movl movl imull movl incl imull addl leaq addl movl movl imull leaq addl leaq incl jmp movl leave ret (%rcx) %eax, -28(%rbp) -28(%rbp), %edx -16(%rbp), %edx -16(%rbp), %eax %eax %eax, %eax %eax, %edx -20(%rbp), %rax %edx, (%rax) -8(%rbp), %eax %eax, %edx -24(%rbp), %edx -20(%rbp), %rax %edx, (%rax) -16(%rbp), %rax (%rax) .L2 -20(%rbp), %eax

From Description to Implementation Lexical analysis (Scanning): Identify logical pieces of the description. Syntax analysis (Parsing): Identify how those pieces relate to each other. Semantic analysis: Identify the meaning of the overall structure. I R Generation: Design one possiblestructure. I R Optimization: Simplify the intendedstructure. Generation: Fabricate the structure. Optimization: Improve the resulting structure.

The Structure of a Modern Compiler Source Code Lexical Analysis Syntax Analysis Semantic Analysis IR Generation IR Optimization Code Generation Machine Code Optimization

The Structure of a Modern Compiler Source Code Lexical Analysis Syntax Analysis Semantic Analysis IR Generation IR Optimization Code Generation Machine Code Optimization

The Structure of a Modern Compiler Source Code Lexical Analysis Syntax Analysis Semantic Analysis IR Generation IR Optimization Code Generation Machine Code Optimization

while (y < z) { int x = a + b; y += x; } Lexical Analysis Syntax Analysis Semantic Analysis IR Generation IR Optimization Code Generation Optimization

while (y < z) { int x = a + b; y += x; } Lexical Analysis Syntax Analysis Semantic Analysis IR Generation IR Optimization Code Generation Optimization

while (y < z) { int x = a + b; y += x; } Lexical Analysis T_While T_LeftParen T_Identifier y T_Less T_Identifier z T_RightParen T_OpenBrace T_Int T_Identifier x T_Assign T_Identifier a T_Plus T_Identifier b T_Semicolon T_Identifier y T_PlusAssign T_Identifier x T_Semicolon T_CloseBrace Syntax Analysis Semantic Analysis IR Generation IR Optimization Code Generation Optimization

while (y < z) { int x = a + b; y += x; } Lexical Analysis T_While T_LeftParen T_Identifier y T_Less T_Identifier z T_RightParen T_OpenBrace T_Int T_Identifier x T_Assign T_Identifier a T_Plus T_Identifier b T_Semicolon T_Identifier y T_PlusAssign T_Identifier x T_Semicolon T_CloseBrace Syntax Analysis Semantic Analysis IR Generation IR Optimization Code Generation Optimization

while (y < z) { int x = a + b; y += x; } While Lexical Analysis Syntax Analysis Sequence Semantic Analysis IR Generation < = = IR Optimization y z x + y + Code Generation Optimization a b y x

while (y < z) { int x = a + b; y += x; } While Lexical Analysis Syntax Analysis Sequence Semantic Analysis IR Generation < = = IR Optimization y z x + y + Code Generation Optimization a b y x

while (y < z) int x = a y += x; } { +b; void While Lexical Analysis Syntax Analysis void Sequence Semantic Analysis IR Generation int < = = bool int IR Optimization int int y z x + y + Code Generation int int int int Optimization a b y x int int int int

while (y < z) int x = a y += x; } { +b; void While Lexical Analysis Syntax Analysis void Sequence Semantic Analysis IR Generation int < = = bool int IR Optimization int int y z x + y + Code Generation int int int int Optimization a b y x int int int int

while (y < z) { int x = a + b; y += x; } Lexical Analysis Loop: x = a + b = x + y _t1 = y < z y Syntax Analysis Semantic Analysis if _t1 goto Loop IR Generation IR Optimization Code Generation Optimization

while (y < z) { int x = a + b; y += x; } Lexical Analysis Loop: x = a + b = x + y _t1 = y < z if _t1 goto Loop y Syntax Analysis Semantic Analysis IR Generation IR Optimization Code Generation Optimization

while (y < z) { int x = a + b; y += x; } Lexical Analysis x = a + b = x + y _t1 = y < z if _t1 goto Loop Loop: y Syntax Analysis Semantic Analysis IR Generation IR Optimization Code Generation Optimization

while (y < z) { int x = a + b; y += x; } Lexical Analysis x = a + b = x + y _t1 = y < z if _t1 goto Loop Loop: y Syntax Analysis Semantic Analysis IR Generation IR Optimization Code Generation Optimization

while (y < z) { int x = a + b; y += x; } Lexical Analysis add $1, $2, $3 Loop: add $4, $1, $4 slt $6, $1, $5 beq $6, loop Syntax Analysis Semantic Analysis IR Generation IR Optimization Code Generation Optimization

while (y < z) { int x = a + b; y += x; } Lexical Analysis add $1, $2, $3 Loop: add $4, $1, $4 slt $6, $1, $5 beq $6, loop Syntax Analysis Semantic Analysis IR Generation IR Optimization Code Generation Optimization

while (y < z) { int x = a + b; y += x; } Lexical Analysis add $1, $2, $3 Loop: add $4, $1, $4 blt $1, $5, loop Syntax Analysis Semantic Analysis IR Generation IR Optimization Code Generation Optimization