Lecture Notes 1/22

Rules for a Regular Expression:

if s & t are regular expressions, then:

  1. s | t
  2. s * t (concatenate)
  3. s*

( continued from last lecture ) NFA for recognizing tokens construct NFAs for each construct of a Regular Expression.

If all tokens of a language are represented by regular expressions $r_1, r_2, r_3, … r_n$, then we can create $N(r_1), N(r_2), … N(r_n)$.

NFA is classified somewhat as a greedy algorithm. Parse trees are created–NFA will then pick the best possible path.

NOTE: Look at CS456Notes02 to see how to minimize a DFA.

Chapter 2 Reading (Not That Important)

Chapter 3 Reading

The lexical analyzer (scanner) reads a stream of characters and outputs a groups of tokens.

NOTE: In most cases, the scanner is the first step of the front end of a compiler.

Attributes of a Token:

  1. Token Type - Parser is more concerned about how the token is an identifier rather than it being a text (lexeme).
  2. Lexeme - In the compiling process, the values of literals and identifers mus tbe accessible.
  3. Line & Column Numbers of Token’s Lexeme - For the sake of error reporting (location of the token within the input would produce meaningful error messages).

Summary