Class 06: Introduction to Lexical Analysis and Regular Expressions

Held: Monday, 2 February 2004

Summary: Today we begin our consideration of lexical analysis through a visit to the regular expressions that are typically used to denote lexemes, the basic building blocks of languages.

Related Pages:

• EBoard.
• Class outline 6.

Notes:

• Does anyone have questions on phase 1 of the project?
• Does anyone need a group?
• Don't forget to vote.
• New draft virtual community policies to be posted.
• In most cases, I make printable versions of my Web pages (without the links and history) available with a .pdf suffix.

Overview:

• What is a language?
• The process of lexical analysis
• Hand-coding a lexical analyzer
• Lexical analyzer generators
• Regular expressions

What is a Language?

• Before we go much further in the class, we should decide what constitutes a language.
  • You should have a sense of some possible definitions from the readings.
• If we ignore some issues with meaning, we can say that a language is simply a collection of utterences (the valid sayings in the language).
  • I say meaning rather than semantics because semantics is used for things like the valid use of variables.
• In the early parts of the course, you should keep this set of strings model in mind.

An Introduction to Lexical Analysis

• Lexical analysis is traditionally the first real step in compilation. During lexical analysis, one identifies the simple tokens (also called lexemes) that make up a program.
• What are these tokens? Things like identifiers, particular keywords, symbols, and such.
  • Some tokens have associated semantic values, such as the name of an identifier or the value of an integer.
• During the tokenizing phase, a compiler converts a sequence of characters (sometimes thought of as a sequence of bytes or integers) to a sequence of tokens.
• During this conversion we often eliminate unnecessary components, such as whitespace (spaces, tabs, newlines) and comments.
  • However, there are reasons to preserve some related information, such as the line number (used in printing error messages).
• There are many techniques for writing lexical analyzers (sometimes called lexers), including
  • Hand coding
  • Relying on lexical analyzer generators
  • Relying on parser generators
• In general, it's best to use a lexical analyzer generator because it gives you the best performance.

Writing Lexical Analyzers by Hand

• Let's think about how we might write a program (in C, Java, or the language of your choice) to do lexical analysis for a simple language.
  • Numbers are sequences of digits.
  • Words are sequences of characters and digits.
  • Whitespace is ignored (but you cannot have whitespace in the middle of word).
  • Comments are in the standard C slash-star-star-slash format.
  • The operators +,-,*,/ are permitted.
  • Everything else is invalid.
• The goal of the program is to be as efficient as possible. Hence, we don't want to reread a character if we don't have to.
• Here's a start of something in pseudocode

  token readToken
    skip over whitespace and comments
    if the next character is a digit, read and return a number
    if the next character is a character, read and return a word
    if the next character is an operator, return it
    otherwise, crash and burn
  

• We'll think about the various parts in more detail

Generating Lexical Analyzers

• As you may have noted, some parts of a lexical analyzer are tedious to write (and sometimes even hard to get right).
  • It would be nice to automate the process.
• Lexical analyzer generators typically take as input a description of the various tokens in the language.
• They output code that will read characters from some input and then generate tokens.
• Often, lexers operate on a demand-driven basis: when you ask for the next token, they read enough input to get it.
• They may also provide a peekToken operation.

Regular Expressions

• Regular expressions are mechanisms used to describe tokens.
• Each regular expression describes a language: a set of valid tokens.
  • We'll denote the set of utterances (i.e., the langauge) a regular expression, re, denotes by L(re).
• Regular expressions can only describe relatively simple languages, but they permit very efficient membership tests and matching.
• Problem: need a language to describe regular expressions, but we're only now learning how to describe languages, which leads to an interesting problem in recursion.
  • We'll use an informal description of regular expressions.
• Like all languages, the language of regular expressions is based on an underlying alphabet, Sigma.
• There is a special symbol, epsilon, not in Sigma.
  • epsilon is written as the greek letter epsilon
  • L(epsilon) is the set of the empty string, { "" }.
• Any single symbol in Sigma is a regular expression.
  • The regular expression for that symbol is that symbol
  • For each symbol s in Sigma, L(s) = { s }.
• The Concatenation of any two regular expressions is a regular expression denoting the combinations of strings from those two regular expressions.
  • If R and S are regular expressions, the concatenation of R and S is written (R.S)
  • L((R.S)) = { concat(x,y) | x in L(R), y in L(S) }
• The concatenation of any two strings is the two strings written in sequence with no intervening space.
  • concat("hello", "world") = "helloworld"
• epsilon is the identity string for concatenation
  • concat(epsilon,s) = concat(s,epsilon) = s
• We sometimes will want shorthand
  • (R.R) may also be written as (R)²; ((R.R).(R)) as (R)³; and so on and so forth.
• The Alternation of any two regular expressions is a regular expression denoting strings in the language of either regular expresion.
  • If R and S are regular expressions, the alternation of R and S is written (R|S).
  • L((R|S)) = L(R) union L(S)
• If R is a regular expression, then the Kleene Star of R is a regular expression.
  • If R is a regular expression, the Kleene star of R is written (R*).
  • L((R*)) = L(epsilon) union L((R)¹) union L((R)²) ...