Compilers - Lexical Analysis

Lexical Analysis

convert a text source program into tokens

Syntactic Analysis

Convert a token stream into a arse tree

Semantic Analysis

Enforce semantic rules and convert a parse tree into an intermediate form

whitespaces, comments, lexical

Lexical analysis discards (), discards (), and detects () errors

token

basic building block of a program

tedious, difficult, prone, separate

Lexical Analyzers are (tedious/engaging) to write, (easy/difficult) to extend, error (prone/resilient), and hard to (separate/merge) patterns and processing

Regular Languages

WE want to express the patterns of token classes as (two words)

character, empty, concatenation, alteration, Kleene star

Regular languages include:

a ()

the () string

the () and () of two strings

an RE followed by the (two words) meaning 0 or more repetitions of

a?

means 0 or 1 instance of a in regular expressions

a+

means 1 or more instance of a in regular expressions

\[abc\]

means any 1 instance of a, b, or c

formal language

(two words) categories can be organized in a hierarchy according to the kinds of languages they can describe (and their parsing complexity, required resources, etc. )

terminal, non-terminal, production rules, start symbol

a Grammar specification includes

a set of () symbols

a set of () symbols

a set of (two words)

a () symbol

2,4,3,1

Order the following in descending order

1 regular

3 Context Free

4 Context sensitive

2 Recursively enumerable

recursion

Something that separates RE’s from CFG’s is that there is no () in RE’s

Finite Automaton

(two words) is convertible into scanning program in a simple, mechanical way

alphabet, states, edges, start state, accepting states

A Finite Automaton consists of

a finite set of symbols, known as a/an ()

a finite set of ()

a finite set of () - which go from one state to another, and is labeled with a symbol

One state known as the (two words)

a subset of states known as the (two words)

finite, start, symbol,

An FA scans a () input string by

starting in the () state

For each successive () in the input string, transmitting along an edge from the current state that is labeled with the (same as exactly before)

Or at any time transiting along an accessible edge labeled with ε

all, accept, accepts, rejects

After () symbols are consumed, if the current state is a () state, the FA () the input, otherwise it () the input

Language

a set of strings accepted by a FA is said to be a ()

Infinite

All FA are finite, and any language accepted by an FA can be ()

2, same, epsilon

A deterministic FA demands

No () edges from a state can have the () symbol

No edge is labeled with ()

one, same, epsilon

Non-deterministic FAs

at least () start state has at least two edges going to different other states and bearing the () symbol

At least one edge is labeled with ()

does not

Being non-deterministic (does/does not) increase the descriptive power of a FA

guessing

No computers have good () hardware

e-closure

when converting an NFA to a FA, keeping track of whichever state the NFA might be in at any point is done with

O(n)

the time complexity for a DFA accepting a string is ()

Lexical Analyzer Generator

(three words) is a program that mechanically converts a set of REs into a program

1975

Lex was developed in ()

flex

whats the lexical analyzer that we use in this class

processing routine

in flex, each token category has its own (two words)

regular expressions

in flex, token formats are expressed as (two words)