編譯原理-詞法分析(文件)
【正文】 corresponds to the regular expression rs r … r … s … ε NFA for a regular expression r Choice among Alternatives ? We added a new start state and a new accepting state using εtransitions. ? This machine accepts L(r|s) = L(r) U L(s). r … s … ε ε ε ε Repetition ? This machine corresponds to r*. r … ε ε ε ε Example ? Translate the regular expression ab|a into a NFA. a b a b ε a ε ε ε ε Example ? letter(letter|digit)* letter digit letter digit letter ε ε ε ε ε ε ε ε ε From NFA to DFA ? We need some method for eliminating εtransitions and multiple transitions from a state on a single input character. ? Eliminating εtransitions involves the construction of εclosures. ? Eliminating multiple transitions involves keeping track of the set of the states instead of single states. ε Closure ? εclosure of a single state s is the set of states reachable by zero or more εtransitions. We denote this set by s. ? εclosure of a state always contains the state itself. Example ? a* ? 1 = {1, 2, 4} ? 2 = {2} ? 3 = {2, 3, 4} ? 4 = {4} ε ε a ε ε 1 2 3 4 εClosure of Set of States ? εclosure of a set of states is defined as the union of εclosures of each individual state. ? If S = {s1, s2,…s n} is a set of states, then S = s1 U s2 U … U s n ? In the previous example we had 1 = {1, 2, 4} and 3 = {2, 3, 4} Let S = {1, 3} S = {1, 3} = 1 U 3 = {1, 2, 4} U {2, 3, 4} = {1, 2, 3, 4} The Subset Construction ? Given NFA M. ? Need to construct a corresponding DFA M?. 1. Compute εclosure of the start state of M。 end while。 ch:=next input character。 end switch。 state:=2。 break。 {go to state 3 without advancing the input} accept。 ? The function putes additional attributes as well. ? The string of input characters is not passed as a parameter, but is kept in a buffer provided by the system facilities. Regular Expression Operations Operation Metacharacter 1. Choice among alternatives | 2. Concatenation 3. Repetition or “closure” * Choice among Alternatives ? Let r and s be regular expressions. ? r|s is a regular expression that matches any string that matched either by r or by s. ? L(r|s) = L(r) U L(s) ? Examples: – a|b matches either a or b. L(a|b) = {a,b}. – a|ε matches either a or ε. L(a|ε) = {a, ε}. – L(a|b|c|d) = {a, b, c, d} Concatenation ? Examples: ab matches the only string ab. (a|b)c matches either ac or bc. ? Given two sets of string S1 and S2, the concatenated set of strings S1S2 is the set of string of S1 appended by all the strings of S2. ? Example: S1={aa, b} and S2={a, bb} S1S2={aaa, aabb, ba, bbb} ? L(rs) = L(r)L(s), where r and s are two regular expressions. Repetition ? Also called (Kleene) closure. ? r* matches any finite concatenation of strings, each of which matches r. ? Example: a* matches ε, a, aa, aaa, aaaa, … ? L(r*) = L(r)* ? Example: L((a|bc)*) = L(a|bc)* = {a, bb}* ={ε, a, bb, aa, abb, bbbb, aaa, aabb, abba, abbbb, bbabb, bbbba, bbbbbb,…} Precedence of Operations ? Repetition ? Concatenation ? Alternative ? Example: a|cb* is interpreted as a|(c(b*)) ? Parentheses are used to indicate the precedence as usual. Highest Lowest Names for Regular Expressions ? Often,it is helpful to use regular definitions of names. ? Example: digit=0|1|2…|9 ? The name bees a metasymbol and should be distinguished from the string (digit in the example). ? We can use names in regular expressions like digit digit* Example ? Σ = {a, b, c} ? Find a regular expression for the strings of Σ that contain exactly on
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1