# CS 131: Programming Languages and Compilers

ShanghaiTech University - Spring 2021

Last updated

ShanghaiTech University - Spring 2021

Last updated

Introduction

Definition

A **Compiler **is "A program that takes a source-code program and translates it into an equivalent program in target language"

String

A **String **is a sequence of characters.

Alphabet: A finite set of symbols （ASCII characters）

String has words and sentences

Suppose s is banana

**Prefix:**前缀ban banana

**Suffix:**后缀banana, ana

**Substring:**子字符串**Subsequence**:子字符bnan, nn

Not all Strings of chars in the Alphabet is in the certain Language, only those who satisfy the Grammar rules.

Below is **Operations **and **Examples**.

Type 0: Turing Machine Recursive Enumerable Gramma

Type 1: Context-sensitive Grammar （CSG）

Type 2: Context-free Grammar (CFG,上下文无关文法），

*mostly recursive*Type 3: Right-linear Grammar Regular Expressions (RE,正则表达式），

*non-recursive*

Expressiveness: Type 0 > Type 1 > Type 2 > Type 3

Phases

Lexical Analyzer （词法分析器）

Reads the source program character by character and returns the **tokens **of the source program

分析并把 identifiers 放入符号表

利用正则表达式来分析 tokens

利用有限自动机来分析 Token 以完成词法分析

词法分析器 = 读入（scanning） + 词法分析（lexical analysis）

Token

Describes a pattern of characters having some meaning in the source program (such as identifiers, operators, keywords, numbers, delimiters and so on)

e.g., identifiers, operators, numbers

A **Lexeme （词素） **is an instance of a Token, along with its unique attributes.

e.g.

`17`

INT

Token.value = 17

Regular Expression （正则表达式）

我们利用**正则表达式**来 描述 **Tokens **匹配 **Tokens**

**正则表达式**是左结合的，从左向右匹配的**正则表达式**是一个**Type-3 Grammar Rule**

e.g.

Integers:

Digit = [0-9]*

Integer = Digit Digit*

Identifier

letter = [a-zA-Z]

identifier = letter （letter + digit）*

Whitespace

WS = ('\n' + '\t' + ' ')+

Examples

Even Binary number

1[0+1]*0 | 0

Finite Automata （有限自动机）

Transition Diagram

当一个 Token 被识别：

如果是关键字，那么会返回

**Token of the keyword**如果是符号表里的 ID，那么返回

**entry of symbol table**如果符号表没有这个ID，那么加入ID并返回新的

**entry of symbol table**

Finite automata

A **recognizer **for a language is a program that takes a string x, and answers “yes” if x is a sentence of that language, and “no” otherwise.

We call the recognizer of the tokens as a **finite automaton**.

**Example**

**Start Arrow****State****Transition Edge****Accepting State**:同心圆，接受并结束，状态3**Death State:错误**状态，未定义的 transition 指向该状态Transition table:

注意 empty string 可以被某些自动机接收

NFA

Non-Deterministic Finite Automata （NFAs） **easily **represent regular expression, but are **less precise.**

**Accept s: **an Accepting State that spells out **s**.

An NFA is a mathematical model that consists of:

S, a

**finite**set of**states***move*, a**transition function**

DFA

Deterministic Finite Automata （DFAs） require **more complexity** to represent regular expressions but offer **more precision**.

**Accept s: **an Accepting State that spells out **s*** and ***ONLY and ONLY ONE ***path*.

Implementation of Lexers

One Token, A *Recognizer. There are 4 ways. (r stands for RE)*

RE to NFA

Algorithm is called **Thompson's Construction**.

There are some requirements on such construction:

REMEMBER to assign unique names to all states

Properties of the resulting NFA:

Exactly 1 Start State & 1 Accepting State

States do not have multiple outgoing edges with the same input symbol

RE to DFA

**[Step 1]**: We make Augmented RE: concatenate with symbol # (meaning "finish").

e.g. (a+b)*a#

Ensures at least one operator in the RE

**[Step 2]:** Build syntax tree for this Augmented RE:

All other operators are inner nodes

**[Step 3]:** Compute `nullable()`

,` firstpos()`

& `lastpos()`

for ALL nodes.

`firstpos(n)`

: Function returning the set of positions where the*first*Symbol can be at, in the*sub-RE*rooted at`n`

`lastpos(n)`

: Function returning the set of Positions where the*last*Symbol can be at, in the sub-RE rooted at`n`

**[Step 4]:** Compute `followpos()`

for Leaf positions

`followpos(i)`

: Function returning the set of positions *which can follow* position i in the generated String

**[Step 5]:** Construct the DFA.

Calculate \epsilon-Closure

Implement NFA as Recognizer

Implement DFA as Recognizer

Convert NFA to DFA

Algorithm is called **Subset Construction(子集构造法)**, since we make subset of States in original NFA into a single State in resulting DFA

Minimize DFA

Start State of the minimal DFA is the one containing original Starting State

Other Issues for Lexers

Look ahead

Comment Skip

Symbol Table

Syntax Analyzer （句法分析）

如果说词法分析这一步提供了可供计算机识别的**词**，那么句法分析是为了理解句子结构。

通常这一步会生成 **parse tree**, **parse tree** 用以描述句法结构。

Difference with Lexical Analyzer

The syntax analyzer deals with

**recursive**constructs of the languageBoth do similar things; But the lexical analyzer deals with simple

**non-recursive**constructs of the language.The lexical analyzer recognizes the smallest meaningful units （

**tokens**） in a source program.The syntax analyzer works on the smallest meaningful units （

**tokens**） in a source program to recognize meaningful structures （**sentences**） in our programming language.

Parse Tree Abstraction

A **Parse Tree / Syntax Tree (语法树) **is a graphical representation of the structure of a program, where leaf nodes are Tokens.

CFG （上下文无关文法）

A** Context-free Grammar (CFG)** is a** Type-2** Grammar rule, which serves the construction of a Parse Tree from a streamof Tokens. We use a set of Production Rules to characterize a CFG

A **Terminal (终结符号)** is a Token; A **Non-terminal (非终结符号) **is a syntactic variable.

The Start Symbol is the first one of Non-terminals; Usually represents the whole program

A **Production Rule (生成规则)** is a law of production, from a Non-terminal to a sequence of Terminals & Non-terminals.

May be

*recursive*The procedure of applying these rules to get a sentence of Terminals is called

**Sentential Form**/**Derivation**

Derivation Directions（派生文法）&Ambiguity（二义性）

Corresponds to

*Top Down Parsing*

Corresponds to

*Bottom Up Parsing*, in reversed manner

A CFG is **Ambiguous** when it produces more than one Parse Tree for the same sentence. Must remove Ambiguity for apractical CFG, by:

Enforce

*Precedence (优先级)*and*Associativity (结合律)*Grammar Rewritten

Top-Down Parsers

Construction of the parse tree starts at the root, and proceeds towards the leaves.

Recursive Predictive Parsing

Non-Recursive Predictive Parsing （

**LL Parsing**）. （**L**-left to right;**L**-leftmost derivation）语法构架能力弱

Implement

Left Recursion Elimination (消除左递归)

Top Down Parsing

**CANNOT**handle Left-recursive GrammarsCan be eliminated by rewriting

For *Immediate* Left Recursions (Left Recursion that may appear in a single step), eliminate by:

Implementing Recursive-descent Parsing

Left Factoring: Produce LL(1) Grammar

LL(1) means Only 1 Token Look-ahead ensures which Pruduction Rule to expand now.

To convert LL(1) to a CFG, for each Non-terminal :

|| LL(1) || < || CFG ||, so not all Grammar can be convert to LL(1)

Such Grammar will have an entry with multiple Production Rules to use in the Parsing Table, thusWill be inappropriate for Predictive Parsing

Implementing Recursive Predictive Parsing

This part stongly suggest to see https://www.josehu.com/assets/file/compilers.pdf for better understanding.

Parsing Table Construction

This part stongly suggest to see https://www.josehu.com/assets/file/compilers.pdf for better understanding.

Implementing LL(1) Parsing

This part stongly suggest to see https://www.josehu.com/assets/file/compilers.pdf for better understanding.

Bottom-Up Parsers

Construction of the parse tree starts at the leaves, and proceeds towards the root.

Bottom-up parsing is also known as

**shift-reduce parsing****LR Parsing**– much general form of shift-reduce parsing:**LR**,**SLR**,**LALR**(**L**-left to right;**R**-rightmost derivation)

IR

Thanks

[Guanzhou HU's Notes](https://www.josehu.com/)

TAs: 季杨彪, 杨易为, 尤存翰

$st$ is the concatenation of $s$and $t$

$s \epsilon = \epsilon s = s$

$\epsilon$is the empty string

$s^0 = \epsilon$

$\mid s \mid$ is the length of s

A **Language** is a set of Strings over a fixed **Alphabet **$\Sigma$, constructed using a specific Grammar.

e.g. $\{\varepsilon, 0,01,011,0111, \ldots\}$

Alphabet $={0,1}$ and using Grammar rule $\mathrm{RE}=01^{*}$ , we can specify the above example Language, while $01$ isn't.

A **Grammar** $G$** **is the description of method （*rules*） of how to construct a certain Language over a certain Alphabet

每个**正则表达式** $r$ 描述一个语言 $L(r)$

$r$被叫做 **regular set**

$\Sigma$, the symbols of the **input alphabet**

move(state, symbol) $\to$ sets of states

A state $s_0 \in S$, the **start state**

$F \subseteq S$, a set of **final** or **accepting states**

$\epsilon$**move: ε- transitions** are allowed in NFAs. In other words, we can move from one state to another one without consuming any symbol

The $\epsilon$-Closure of $S = S \cup \{$ All States that can go to without consuming any input $\}$

**Does not allow **$\epsilon$**move, ** for every $s \in S$, there is ONLY ONE decision for every input *Symbol.*

No $\epsilon$-closure !!!

$r \to NFA \to Recognizer$

$r \to NFA \to DFA \to Recognizer$

$r \to DFA \to Recognizer$

$r \rightsquigarrow DFA \to Minimized ~ DFA \to Recognizer$

$N(s)$and $N(t)$CANNOT have any intersections

# of States in NFA $\leq 2 \times$(# of Symbols + # of Operators) in $r$

States have at most 2 outgoing $\epsilon$ edges

$\epsilon$, # and $a \in \Sigma$ all are at leaves

Non-$\epsilon$ leaves get its position number, increasing from left $\to$ right

`nullable(n)`

: Function judging whether the *sub-RE* rooted at `n`

can generate $\epsilon$

Conduct a *Post-order* *Depth First Traversal* on the syntax tree, and do the following oprations when leaving $\cdot$ / * nodes:

$c{1} \cdot c{2}:$ For all $i \in$ `lastpos(c1)`

, `followpos(i)`

= `followpo(i)`

$\cup$ `firstpos(c2)`

$c^{*}:$ For all $i \in$ `lastpos(c)`

, `followpos(i)`

$=$ `followpos(i)`

$\cup$ `firstpos(c)`

A State $S$in resulting DFA is an Accepting State iff # node $\in S$

Start State of the resulting DFA is $S_0$

Performance of NFA-type Recognizers: Space $O(|r|)$; Time $O(|r| \times |s|)$

Performance of DFA-type Recognizers: Space $O(|2^{|r|})$; Time $O(|s|)$

A State $S$ in resulting DFA is an Accepting State iff $\exists s \in S, s$ is an Accepting State in original NFA

Start State of the resulting DFA is $S_0$

A State S in the minimal DFA is an Accepting State iff $\exists s \in S$, s is an Accepting State in original DFA

A Sentence is a string of Terminals such that Start Symbol $S \Rightarrow{ }^{+} s$

e.g. $A \rightarrow \alpha A \mid \beta$, where $A$ is a Non-terminal and $\alpha, \beta$ are Terminals

$|$ Context-free Languages $|>|$ Regular Languages $|$, e.g. $\{(^{i})^{i}: i \geq 0 \}$.

**Left-most Derivation** **(左递归)**$\left(\Rightarrow_{l m}\right)$ means to replace the leftmost Non-terminal at each step.

If $\beta A \gamma \Rightarrow \operatorname{lm} \beta \delta \gamma$, then NO Non-terminals in $\mathcal{\beta}$

**Right-most Derivation** $(\Rightarrow r m)$means Replace the rightmost Non-terminal at each step.

If $\beta A \gamma \Rightarrow_{r m} \beta \delta \gamma$, then NO Non-terminals in $\gamma$

e.g. $* > +$ , then $+$ gets expanded first

Eliminate Left Recursion $\to$ Recursive-descent Parsing

Eliminate Left Recursion $\to$ Left Factoring $\to$Recursive Predictive Parsing

Eliminate Left Recursion $\to$Left Factoring $\to$Construct Parsing Table $\to$Non-recursive Predictive Parsing

$A \Rightarrow^{+} A_{\alpha}$: Left Recursion

state

a

b

0

{0,1}

{0}

1

--

{2}

2

--

{3}