FIT2014 Lecture Notes - Lecture 8: Lexeme, Regular Expression
28 Jun 2018
School
Department
Course
Professor
Lecture 8 : Terminology
- A token is a name of pattern
o It may also have an attribute value associated with it
- A lexeme is a sequence of characters that matches the pattern corresponding to a token
- A pattern is a description of the form that the lexemes of a token may take
o Often described using regular expression.
Lexical Analyser
- Read the input one character at a time.
- Splits the input up into token
- Implemented using a FA or NFA
Minimum DFA
- Colour all Final States with one colour and colour all non final states with a different colour.
- Repeat until no new colour is added
o Consider all states with one colour
o If their rows in the transition table do not have the same pattern of colour
o Introduce a new colour for each state that has a different new pattern,
- Give each colour a unique number and use these number to form the transition table.
Document Summary
It may also have an attribute value associated with it. A lexeme is a sequence of characters that matches the pattern corresponding to a token. A pattern is a description of the form that the lexemes of a token may take: often described using regular expression. Read the input one character at a time. Colour all final states with one colour and colour all non final states with a different colour. Repeat until no new colour is added: consider all states with one colour. If their rows in the transition table do not have the same pattern of colour. Introduce a new colour for each state that has a different new pattern,
