Its DFA time! Deterministic Finite Automata + regular expression (complexity). See programmatically compiling RegEx to DFA.

Another review of the compiler

Compiler Front End

Lexer => Parser => Semantic Analysis; usually language specific.

Compiler Mid End

Optimizer; usually shared across many languages.

Compiler Back End

Codegen

parser

parser does parsing

parser: takes sequence of tokens from the lexer and produce AST of the program. General goal is to distinguish between valid and invalid strings of tokens.

Importantly, we don’t really emit errors from parsing; instead we just do it at the layer below and above.

and also abstract syntax tree and top-down parsing

error handling

Recall! Our compiler should detect non-valid programs and to translate valid ones.

Good error handler should report errors accurately and clearly; recovering from an error quickly, and not slow down compilation of valid code.

Bottom-Up Parsing

Bottom-Up Parsing is more general than top-down parsing (i.e., it doesn’t require left factorization, etc.)

This is generally the preferred method. Key insight: we reduce strings into increasingly higher level symbols

Sketch

Because of the Properties of Bottom-Up Parsing, we can….

initialization

• split the string into two pieces
• right substring has terminals, not yet examined
• left substring has terminals and non-terminals

We begin by splitting to the left since we begin with no non-terminals.

semantic analysis