Lexical Analysis with Regular Expressions - Wellesley College
Lexical Analysis with
Regular Expressions
Thursday, October 23, 2008
Reading: Stoughton 3.14, Appel Chs. 1 and 2
CS235 Languages and Automata
Department of Computer Science
Wellesley College
Lecture Overview
Lexical analysis = breaking programs into tokens is the first stage
of a compiler.
The structure of tokens can be specified by regular expressions.
The ML-Lex tool can automatically derive a lexical analyzer from
a description of tokens specified by regular expressions.
To use ML-Lex, we¡¯ll need to learn a few more ML features:
? sum-of-product data structures
? mutable cells
Lexical Analysis
22-2
Compiler Structure
Abstract
Syntax
Tree (AST)
Source
Program
Lexer
Tokens
(a.k.a. Scanner,
Tokenizer)
(character
stream)
Parser
Type
Checker
Intermediate Representation
Front End
(CS235)
Semantic
Analysis
Middle
Stages
(CS251/
CS301)
Global Analysis
Information
(Symbol and
Attribute Tables)
Intermediate Representation
Optimizer
Intermediate Representation
Back End
(CS301)
(used by all phases
of the compiler)
Code
Generator
Machine code or byte code
Lexical Analysis
22-3
Front End Example
if (num > 0 && num
0
return
&&
0
num
;
int
val scale = fn : int -> figure -> figure
val it = () : unit
- map perimeter [Square 1, Rectangle(2,3), Triangle(4,5,6)];
val it = [4,10,15] : int list
- map (scale 10) [Square 1, Rectangle(2,3), Triangle(4,5,6)];
val it = [Square 10,Rectangle (20,30),Triangle (40,50,60)] : figure list
Lexical Analysis
22-9
We Can Define our Own List Data Type
(* contents of the file mylist.sml *)
datatype 'a mylist = Nil | Cons of 'a * ('a mylist)
fun sum Nil = 0
| sum (Cons(n,ns)) = n + (sum ns)
fun map f Nil = Nil
| map f (Cons(x,xs)) = Cons(f x, map f xs)
- use "mylist.sml";
[opening mylist.sml]
datatype 'a mylist = Cons of 'a * 'a mylist | Nil
val sum = fn : int mylist -> int
val map = fn : ('a -> 'b) -> 'a mylist -> 'b mylist
val it = () : unit
- sum (Cons(1, Cons(2, Cons(3, Nil))));
val it = 6 : int
- map (fn x => x*2) (Cons(1, Cons(2, Cons(3, Nil))));
val it = Cons (2,Cons (4,Cons (6,Nil))) : int mylist
Lexical Analysis
22-10
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- pattern matching using regular expressions university of cambridge
- cs 2112 lab 7 regular expressions department of computer science
- chapter regular expressions text normalization edit distance
- regular expression the university of edinburgh
- regular expression regex universitetet i oslo
- 5hjxodu suhvvlrqv fkhdw vkhhw mit
- lexical analysis with regular expressions wellesley college
- lecture 18 theory of computation regular expressions and dfas
- regular expressions in programming stony brook university
- jflex regular expressions h sc
Related searches
- lexical words with friends cheat
- regular expressions js
- using regular expressions in java
- regular expressions tutorial
- regular expressions in java
- java regular expressions tutorial
- lexical analysis code
- lexical analysis example
- lexical analysis in java
- lexical analysis pdf
- lexical analysis c
- lexical analysis definition