1. return < 0 if first value should come before second value
2. return > 0 if first value should come AFTEr second value
3. 0 if the first and second value are equivalent

cs143.stanford.edu

Lectures

• SU-CS143 APR012025
• SU-CS143 APR032025
• SU-CS143 APR152025
• SU-CS143 APR172025
• SU-CS143 APR242025
• SU-CS143 APR292025
• SU-CS143 MAY062025

Lexing

• What to do: SU-CS143 APR082025
• How to implement it: SU-CS143 APR102025

Logistics

• programming assignments: myth
• psets: gradescope
• labs: myth.stanford.edu
  • /afs/ir/class/cs143
• finals and midterms

Textbook: the purple dragonbook

Structure

• written assignments (2.5*4 = 10%)
• programming assignments (10+10+15+15 = 50%); 4 of them
  • lexer
  • parser
  • semantic analysis parse
  • code generator
• midterm (15%)
• final (25%)

Compiler we will Build

• lexer: strings -> tokens
  • built with Flex FSTs
  • smallest part of the code
• parser: tokens -> AST
  • built with Bison CFGs
  • linear time parsing!
• semantic analysis: AST
  • C++
  • check types + properties
  • fill in types for expressions in the tree
• [PA5: optimization - TBD]
• code generation: AST -> MIPS
  • C++
  • write MIPS
  • yay!

Emphasis: correctness over performance.

Recall that Euler’s Equation exists:

\begin{equation} f(x) = e^{i k \omega x} = \cos (k\omega x) + i \sin(k\omega x) \end{equation}

and, for \(\omega = \frac{2\pi}{L}\), this is still \(L\) periodic!

Next up, we make an important note:

\begin{equation} e^{ik\omega x}, e^{-i k \omega x} \end{equation}

is linearly independent over \(x\).

inner product over complex-valued functions

recall all of the inner product properties. Now, for functions periodic over \([0,L]\) (recall we have double this if the function is period over \([-L, L]\):

A complex number is a type of number. They are usually written as \(a+bi\).

Formally—

\begin{equation} \mathbb{C} = \left\{a+bi\ \middle |\ a,b \in \mathbb{R} \right\} \end{equation}

This set generates solutions to every single polynomial with unique solutions. Its plane looks like \(\mathbb{R}^{2}\).

constituents

an order pair of two elements \((a,b)\) where \(a,b\in \mathbb{R}\).

properties of complex arithmetic

there are 6. For all statements below, we assume \(\alpha = a+bi\) and \(\beta=c+di\), \(\lambda = e+fi\), where \(a,b,c,d,e,f \in \mathbb{R}\) and therefore \(\alpha, \beta,\lambda \in \mathbb{C}\).

\begin{equation} \begin{cases} x_1’ = 5x_1 - 5x_2 \\ x_2’ = 2x_1 -x_2 \end{cases} \end{equation}

This gives rise to:

\begin{equation} A = \mqty(5 & -5 \\ 2 &-1) \end{equation}

Solving the characteristic polynomial gives:

\begin{equation} (5-\lambda)(-1-\lambda) + 10 = \lambda^{2} - 4\lambda +5 \end{equation}

Therefore, our solutions are imaginary!

\begin{equation} \lambda_{1}, \lambda_{2} = 2 \pm i \end{equation}

Aside: we only need to deal with one

Notably, anything that satisfies the original polynomial, its conjugates also satisfies: