Cs419 lec5 lexical analysis using dfa

100 %
0 %
Information about Cs419 lec5 lexical analysis using dfa

Published on February 20, 2014

Author: hussiensharaf

Source: slideshare.net

WELCOME TO A JOURNEY TO CS419 Dr. Hussien Sharaf Computer Science Department dr.sharaf@from-masr.com

FINITE AUTOMATA FA Its goal is to act as a recognizer for specific language/pattern.  Any problem can be presented in form of decidable problem that can be answered by Yes/No.  Hence FA (machine with limited memory) can solve any problem.  FA used to be hard wired devices like controller of a lift.  Dr. Hussien M. Sharaf 2

IMPLEMENTATION OF FINITE AUTOMATA IN CODE  1. 2. Possible ways: Use the position in the code (nested within tests) to maintain the state implicitly. Use a variable to maintain the current state and write transitions as doubly nested case statements inside a loop, where the first case statement tests current state and the nested second level tests the input character, given the state or vice versa. Dr. Hussien M. Sharaf 3

EXAMPLE FOR METHOD 1 The position in the code to maintain the state Implicitly. Dr. Hussien M. Sharaf 4

CODE 1 Dr. Hussien M. Sharaf 5

EXAMPLE FOR METHOD 2  A variable to maintain the current state. Dr. Hussien M. Sharaf 6

CODE 2 Dr. Hussien M. Sharaf 7

DETERMINISTIC FINITE AUTOMATA DFA There is a fixed number of states and the DFA can only be in one state at a time. DFA = “a 5-tuple “ (Q, Σ, , q0, F) Q: {q0, q1, q2, …} is set of states. Σ: {a, b, …} set of alphabet. (delta): A transition function, which is a total function from Q x Σ to Q, this function:    Takes a state and input symbol as arguments. Returns a single state. : Q x Σ→Q q0 Q is the start state. F Q is the set of final/accepting states. Dr. Hussien M. Sharaf 8

TRANSITION FUNCTION  : Q x Σ→Q  Maps from domain of (states, letters) to range of states.  (q0, a) (q2, b) q2 (q1, b) Dr. Hussien M. Sharaf q1 q3 9

EXAMPLE1.1   Build an FA that accepts at two a’s followed by one b L = {aab} S1 - S2 a b b S3 a a S5 Dr. Hussien M. Sharaf b a,b S4 + S1 S2 S3 S4 a S2 S3 S5 S5 b S5 S5 S4 S5 10

EXAMPLE1.2 Build a DFA that accepts only aab  DFA that is not well defined.  S1 - a S2 a S3 b S4 + S1 S2 S3 S4 Dr. Hussien M. Sharaf a S2 S3 ? ? b ? ? ? ? 11

EX2  (a+b)* ± a, b Dr. Hussien M. Sharaf 12

FA ACCEPTING NOTHING 1. FA with no final states b a a,b 2. FA with disconnected graph. Start state does not have a path to the final state. b + a Dr. Hussien M. Sharaf a,b b 13

EX3  All words with even count of letters. ((a+b)(a+b))* a, b 1± 2 a, b Dr. Hussien M. Sharaf 14

EX4.1  All words that start with “a” a(a+b)* b a,b b 2 2 1- 1- a 3+ a,b a 3+ a,b Does not accept all inputs Dr. Hussien M. Sharaf 15

EX4.2  All words that start with “a” a(a+b)* a,b b 2 a,b 1- a 3+ a,b 4+ Special accept state for string “a”, might give better performance in hardware implementation Dr. Hussien M. Sharaf 16

ASSIGNMENT2 Compilers_DFA_Sheet_2.pdf  Deadline is 7 March-2013  Dr. Hussien M. Sharaf 17

EX5  All words that start with triple letter (aaa+bbb)(a+b)* a 2 a a 3 1- 6+ b Dr. Hussien M. Sharaf 4 b 5 a,b b 18

EX6 + a - a,b a,b b b 5 {aa, ba, baba, aaaa, bbba, abba, aaabaa, …} All words with even count of letters and ends with “a”. (a+b)a ((a+b)a (b(a+b)a)* )* Dr. Hussien M. Sharaf 19

EX7 a,b - {aa, ba, baba, aaaa, ab, bb, bababa, aaba, …} All words with even count of letters having “a” in an even position from the start, where the first letter is letter number one. (a+b)a((a+b)a)* Dr. Hussien M. Sharaf 20

EX8  COMPILERS CONSTRUCTION PAGE 50 Consider the following FA: •Accepts identifiers where symbols are not acceptded with error handling. •An identifier must start with a letter. letter [a-zA-Z] Other =~letter Other# = ~(letter|digit) Dr. Hussien M. Sharaf — other letter letter digit Other# error any 21

EX9 COMPILERS CONSTRUCTION PAGE 52  Integer constants digit — digit digit other other error Dr. Hussien M. Sharaf 22

EX10 COMPILERS CONSTRUCTION PAGE 52  Decimal/floating constants digit — digit digit other . other digit digit other error Dr. Hussien M. Sharaf 23

THANK YOU Dr. Hussien M. Sharaf 24

Add a comment

Related presentations

Related pages

Lexical Analysis | LinkedIn

Lexical Analysis. Articles, experts, jobs, and more: get all the professional insights you need on LinkedIn. Sign up Get more personalized results when you ...
Read more

Compiler Construction/Lexical analysis - Wikibooks, open ...

Compiler Construction/Lexical analysis. From Wikibooks, ... Since, however, this section is about using JavaCC to generate a token manager, ...
Read more

Lexical analysis - Wikipedia, the free encyclopedia

... lexical analysis is the process of converting a sequence of ... using 'token' interchangeably to ... The lexical syntax is usually a regular ...
Read more

Lexical Analysis (Tokenizing) - Computational Geometry Lab ...

• The lexical analyzer may ... to NFA to DFA • DFAs are easy to implement – Using a switch ... we write a RE • The lexical analysis generator ...
Read more

Lexical analysis test 2 - Documents

Cs419 lec5 lexical analysis using dfa Comments. RECOMMENDED. Lexical analysis Test. Lexical Analysis Test II. Lexical Analysis TEST. Lexical Analysis.
Read more

2 Lexical Analysis - Leonidas Fegaras

2 Lexical Analysis. ... that groups the input characters into lexical ... learn how to build efficient scanners using regular expressions and ...
Read more

Lexical Analysis - Compiler - C Programming - c4learn.com

... takes place using different ... 1.Analysis Phase : Lexical analysis Syntax ... Lexical Analysis Identifies Different Lexical Units in a ...
Read more