advertisement

advertisement

Information about Cs419 lec5 lexical analysis using dfa

advertisement

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

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. From Wikibooks, ... Since, however, this section is about using JavaCC to generate a token manager, ...

Read more

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

Read more

• 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

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. ... that groups the input characters into lexical ... learn how to build efficient scanners using regular expressions and ...

Read more

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

Read more

## Add a comment