# Lexical Analysis

## 正则表达式

Atomic reg: for every a in $\Sigma$ , Epsilon: $\epsilon$

Compound reg: $r+s,rs,r^*$

Transition diagrams (a graph representation of reg)

## 自动机

Deterministic, DFA( widely used in lexical analyzers ); Non-Deterministic NFA

Two algorithm:

• Reg=>NFA=>DFA
• Reg=>DFA (more complicated)

## Reg => NFA

Allows $\epsilon$ transitions, move to another state without consuming any symbol.

Crafting every symbols one by one with $L(\epsilon),L(a),L(s)\cup L(t)$

## NFA => DFA

Calculate $\epsilon$ passing and construct all possible subsets and corresponding input symbol.

Rename each subset and reassemble with input symble.

## Reg => DFA

Evaluate firstpos, latpos, nullable. Draw trees and construct DFA.

Abstractive and a little complicated, needs reviewing according to tutorial in youtube.

Forgot.

• Panic Mode
• Phrase Level

# Context free language and parsing

## Eliminate ambiguity

• Grammar rewrite
• Enforce precedence and associativity

## Top-down parsing

### Recursive-descent paring

Backtracking, general, not efficient

Eliminate left recursion:

• Immediate recursions
• All left recursions

### Predictive parsing

No backtracking, efficient, LL(k)

Left-factoring

### Construct LL(1) parsing table

For each rule $A\rightarrow \alpha$ :

• terminal a in FIRST($\alpha$)? Add $A\rightarrow \alpha$ to M[A,a]
• $\epsilon$ in $FIRST(\alpha)$? Add $A\rightarrow \alpha$ to M[A,b] for all terminals b in $FOLLOW(A)$
• $\epsilon$ in $FIRST(\alpha)$? and \$in$FOLLOW(A)$? Add$A\rightarrow \alpha$to M[A,\$]
• All undefined entries are errors

Not a LL(1) grammar and error recovery.

## Bottom-up parsing

### Operator precedence parsing

Not much impression, maybe not important.

### Construct LR(0) parsing table

Long journey, need tutorial on youtube

### SLR(1) parsing table

Cautions to ambiguous grammar (left/right associative)

# Intermediate represnetation

• Abstract syntax trees

• Directed acyclic graphs

AST合并同值节点

• Control flow graphs

• Single static assignment

• Stack machine code