MTHSC 865 HW03

3385 days ago by spotuku

# Homework 3, HW03 # Srikanth Potukuchi # 08/30/2012-09/01/2012 
       

A simple example of scaning a string

def find_digits(s): ''' Prints each substring of s which is a set of consecutive digits. This is a Mealy implementation of the FSA. Daniel D. Warner August 21, 2010 ''' n = len(s) start = finis = -1 for i in range(0,n): if s[i] in '0123456789': # We have seen a digit if start == -1: start = finis = i finis += 1 #print finis else: # We have seen a nondigit if -1 < start: print s[start:finis] start = finis = -1 else: # We reached the end of the string if -1 < start: print s[start:] 
       
find_digits('onetwothree') find_digits('1') find_digits('123') find_digits('abc456xyz') find_digits('abc123xyz456') find_digits('0123456789') 
       
1
123
456
123
456
0123456789
1
123
456
123
456
0123456789

The following blocks set up and run the VFN

Define the character codes.

def char_code(ch): if ch in ' \t': return 0 if ch in '.': return 1 if ch in '+-': return 2 if ch in '0123456789': return 3 if ch in 'EeDd': return 4 return 5 
       
for ch in 'A z0.+-9E\td': print ch, char_code(ch) 
       
A 5
  0
z 5
0 3
. 1
+ 2
- 2
9 3
E 4
	0
d 4
A 5
  0
z 5
0 3
. 1
+ 2
- 2
9 3
E 4
	0
d 4

Define the State Transition Function.

''' Define the state transition function for the VFN FSA. The arguments are the current state and the input character code. The value returned is the new state. The forward transitions are defined by the state transition diagram in the file VFN.pdf. Srikanth Potukuchi 08/30/2012-09/01/2012 ''' # The states are 0,1,2,3,4,5,6,7,8 corresponding to s0,Decpt,Sign,Integer,Mantissa,Decimal,Exp,Signed Exp,Float # Input character codes are 0,1,2,3,4 corresponding to [],[.],[+-],[0-9],[EeDd] VFN_f = ((0,1,2,3,0,0,0,0,0), (0,0,0,0,4,0,0,0,0), (0,1,0,3,0,0,0,0,0), (0,0,0,3,0,5,6,0,0), (0,0,0,0,4,0,6,0,0), (0,0,0,0,4,0,6,0,0), (0,0,0,0,0,0,0,7,8), (0,0,0,0,0,0,0,0,8), (0,0,0,0,0,0,0,0,8), ) for t in VFN_f: print t 
       
(0, 1, 2, 3, 0, 0, 0, 0, 0)
(0, 0, 0, 0, 4, 0, 0, 0, 0)
(0, 1, 0, 3, 0, 0, 0, 0, 0)
(0, 0, 0, 3, 0, 5, 6, 0, 0)
(0, 0, 0, 0, 4, 0, 6, 0, 0)
(0, 0, 0, 0, 4, 0, 6, 0, 0)
(0, 0, 0, 0, 0, 0, 0, 7, 8)
(0, 0, 0, 0, 0, 0, 0, 0, 8)
(0, 0, 0, 0, 0, 0, 0, 0, 8)
(0, 1, 2, 3, 0, 0, 0, 0, 0)
(0, 0, 0, 0, 4, 0, 0, 0, 0)
(0, 1, 0, 3, 0, 0, 0, 0, 0)
(0, 0, 0, 3, 0, 5, 6, 0, 0)
(0, 0, 0, 0, 4, 0, 6, 0, 0)
(0, 0, 0, 0, 4, 0, 6, 0, 0)
(0, 0, 0, 0, 0, 0, 0, 7, 8)
(0, 0, 0, 0, 0, 0, 0, 0, 8)
(0, 0, 0, 0, 0, 0, 0, 0, 8)

Define the output function.

''' Define the output function for the VFN FSA. The arguments are the current state and the input character code. The value returned is the action code. Srikanth Potukuchi 08/30/2012-09/01/2012 ''' VFN_g = ((0,1,2,3,0,0,0,0,0), (0,0,0,0,4,0,0,0,0), (0,1,0,3,0,0,0,0,0), (0,0,0,3,0,5,6,0,0), (0,0,0,0,4,0,6,0,0), (0,0,0,0,4,0,6,0,0), (0,0,0,0,0,0,0,7,8), (0,0,0,0,0,0,0,0,8), (0,0,0,0,0,0,0,0,8), ) for t in VFN_g: print t 
       
(0, 0, 0, 0, 0, 0)
(0, 0, 0, 0, 0, 0)
(0, 0, 0, 0, 0, 0)
(0, 1, 0, 3, 4, 5)
(0, 0, 0, 3, 4, 5)
(0, 0, 0, 3, 4, 0)
(0, 0, 0, 0, 0, 0)
(0, 0, 0, 0, 0, 0)
(0, 0, 0, 3, 0, 5)
(0, 0, 0, 0, 0, 0)
(0, 0, 0, 0, 0, 0)
(0, 0, 0, 0, 0, 0)
(0, 1, 0, 3, 4, 5)
(0, 0, 0, 3, 4, 5)
(0, 0, 0, 3, 4, 0)
(0, 0, 0, 0, 0, 0)
(0, 0, 0, 0, 0, 0)
(0, 0, 0, 3, 0, 5)

Define the VFN FSA.

def find_VFN(s): ''' Prints each substring of s which is a VFN (a valid fortran number). This routine should always print the longest VFN that is possible. The rules for a VFN are: 1. white space (spaces and tabs) should be ignored 2. a VFN is a string of 1 or more digits 3. a VFN may optionally contain a decimal point at the beginning, end, or interior of the string of digits 4. a VFN may optionally have a sign (+,-) as a prefix 5. a VFN may optionally have an exponent term as a suffix 6. an exponent term consists of one of (e, E, d, D) followed by an optional sign (+,-) followed by one or more digits. Daniel D. Warner August 31, 2009 Modified by Srikanth Potukuchi 09/01/2012 ''' global VFN_f n = len(s) state = 0 # pointers start = finis = posib = -1 # Scan the string for k in range(0,n): ch = s[k] # Get the character cc = char_code(ch) # Get the character code action = VFN_g[state][cc] # Get the output action state = VFN_f[state][cc] # Evaluate the state transition function print ch,cc,action,state # Process the output action 
       
find_VFN('1') print '' find_VFN('1 2 3. 4 5') print '' find_VFN('2+ 2. -.2 + 2e0- 2.E0') print '' find_VFN('+1+.2++3++.4++..5e-6+7e.8+.9') print '' 
       
1 3 0 3

1 3 0 3
  0 0 0
2 3 0 3
  0 0 0
3 3 0 3
. 1 1 1
  0 0 0
4 3 0 3
  0 0 0
5 3 0 3

2 3 0 3
+ 2 0 0
  0 0 0
2 3 0 3
. 1 1 1
  0 0 0
- 2 0 2
. 1 0 1
2 3 0 3
  0 0 0
+ 2 0 2
  0 0 0
2 3 0 3
e 4 4 0
0 3 0 3
- 2 0 0
  0 0 0
2 3 0 3
. 1 1 1
E 4 0 0
0 3 0 3

+ 2 0 2
1 3 0 3
+ 2 0 0
. 1 0 1
2 3 0 3
+ 2 0 0
+ 2 0 2
3 3 0 3
+ 2 0 0
+ 2 0 2
. 1 0 1
4 3 0 3
+ 2 0 0
+ 2 0 2
. 1 0 1
. 1 0 0
5 3 0 3
e 4 4 0
- 2 0 2
6 3 0 3
+ 2 0 0
7 3 0 3
e 4 4 0
. 1 0 1
8 3 0 3
+ 2 0 0
. 1 0 1
9 3 0 3
1 3 0 3

1 3 0 3
  0 0 0
2 3 0 3
  0 0 0
3 3 0 3
. 1 1 1
  0 0 0
4 3 0 3
  0 0 0
5 3 0 3

2 3 0 3
+ 2 0 0
  0 0 0
2 3 0 3
. 1 1 1
  0 0 0
- 2 0 2
. 1 0 1
2 3 0 3
  0 0 0
+ 2 0 2
  0 0 0
2 3 0 3
e 4 4 0
0 3 0 3
- 2 0 0
  0 0 0
2 3 0 3
. 1 1 1
E 4 0 0
0 3 0 3

+ 2 0 2
1 3 0 3
+ 2 0 0
. 1 0 1
2 3 0 3
+ 2 0 0
+ 2 0 2
3 3 0 3
+ 2 0 0
+ 2 0 2
. 1 0 1
4 3 0 3
+ 2 0 0
+ 2 0 2
. 1 0 1
. 1 0 0
5 3 0 3
e 4 4 0
- 2 0 2
6 3 0 3
+ 2 0 0
7 3 0 3
e 4 4 0
. 1 0 1
8 3 0 3
+ 2 0 0
. 1 0 1
9 3 0 3
find_VFN('123456789e123456789E123456789d123456789D123456789e123456789E123456789d12') print '' find_VFN('123456789z123456789E123456789x123456789D123456789/123456789E123456789=12') print '' find_VFN('1234.6789e1234.6789E1234.6789d1234.6789D1234.6789e1234.6789E1234.6789d12') print '' find_VFN('1234.6789]1234.6789E1234.6789@1234.6789D1234.6789R1234.6789E1234.6789%12') print '' find_VFN('1234..789e1234..789E1234..789d1234..789D1234..789e1234..789E1234..789d12') print '' find_VFN('1234..789]1234..789E1234..789@1234..789D1234..789R1234..789E1234..789%12') print '' find_VFN('1234.6789.1234.6789.1234.6789.1234.6789.1234.6789.1234.6789.1234.6789.12') print '' find_VFN('1evaluate234.6789]1234.6789.1234.6789@1234.6789.1234.6789R1234.6789.1234.6789%12') print '' find_VFN('123...789e123...789E123...789d123...789D123...789e123...789E123...789d12') print '' find_VFN('123...789]123...789E123...789@123...789D123...789R123...789E123...789%12') print '' find_VFN('123456789012345678901234567890123456789012345678901234567890123456789012') print '' find_VFN('12345678901234567890123456789012345678901234567890123456789012345678901.') 
       
WARNING: Output truncated!  
full_output.txt



1 3 0 3
2 3 3 3
3 3 3 3
4 3 3 3
5 3 3 3
6 3 3 3
7 3 3 3
8 3 3 3
9 3 3 3
e 4 4 0
1 3 0 3
2 3 3 3
3 3 3 3
4 3 3 3
5 3 3 3
6 3 3 3
7 3 3 3
8 3 3 3
9 3 3 3
E 4 4 0
1 3 0 3
2 3 3 3
3 3 3 3
4 3 3 3
5 3 3 3
6 3 3 3
7 3 3 3
8 3 3 3
9 3 3 3
d 4 4 0
1 3 0 3
2 3 3 3
3 3 3 3
4 3 3 3
5 3 3 3
6 3 3 3
7 3 3 3
8 3 3 3
9 3 3 3
D 4 4 0
1 3 0 3
2 3 3 3
3 3 3 3
4 3 3 3
5 3 3 3
6 3 3 3
7 3 3 3
8 3 3 3
9 3 3 3
e 4 4 0
1 3 0 3
2 3 3 3
3 3 3 3
4 3 3 3
5 3 3 3
6 3 3 3
7 3 3 3
8 3 3 3
9 3 3 3

...

3 3 3 3
4 3 3 3
5 3 3 3
6 3 3 3
7 3 3 3
8 3 3 3
9 3 3 3
0 3 3 3
1 3 3 3
2 3 3 3
3 3 3 3
4 3 3 3
5 3 3 3
6 3 3 3
7 3 3 3
8 3 3 3
9 3 3 3
0 3 3 3
1 3 3 3
2 3 3 3
3 3 3 3
4 3 3 3
5 3 3 3
6 3 3 3
7 3 3 3
8 3 3 3
9 3 3 3
0 3 3 3
1 3 3 3
2 3 3 3
3 3 3 3
4 3 3 3
5 3 3 3
6 3 3 3
7 3 3 3
8 3 3 3
9 3 3 3
0 3 3 3
1 3 3 3
2 3 3 3
3 3 3 3
4 3 3 3
5 3 3 3
6 3 3 3
7 3 3 3
8 3 3 3
9 3 3 3
0 3 3 3
1 3 3 3
2 3 3 3
3 3 3 3
4 3 3 3
5 3 3 3
6 3 3 3
7 3 3 3
8 3 3 3
9 3 3 3
0 3 3 3
1 3 3 3
. 1 1 1
WARNING: Output truncated!  
full_output.txt



1 3 0 3
2 3 3 3
3 3 3 3
4 3 3 3
5 3 3 3
6 3 3 3
7 3 3 3
8 3 3 3
9 3 3 3
e 4 4 0
1 3 0 3
2 3 3 3
3 3 3 3
4 3 3 3
5 3 3 3
6 3 3 3
7 3 3 3
8 3 3 3
9 3 3 3
E 4 4 0
1 3 0 3
2 3 3 3
3 3 3 3
4 3 3 3
5 3 3 3
6 3 3 3
7 3 3 3
8 3 3 3
9 3 3 3
d 4 4 0
1 3 0 3
2 3 3 3
3 3 3 3
4 3 3 3
5 3 3 3
6 3 3 3
7 3 3 3
8 3 3 3
9 3 3 3
D 4 4 0
1 3 0 3
2 3 3 3
3 3 3 3
4 3 3 3
5 3 3 3
6 3 3 3
7 3 3 3
8 3 3 3
9 3 3 3
e 4 4 0
1 3 0 3
2 3 3 3
3 3 3 3
4 3 3 3
5 3 3 3
6 3 3 3
7 3 3 3
8 3 3 3
9 3 3 3

...

3 3 3 3
4 3 3 3
5 3 3 3
6 3 3 3
7 3 3 3
8 3 3 3
9 3 3 3
0 3 3 3
1 3 3 3
2 3 3 3
3 3 3 3
4 3 3 3
5 3 3 3
6 3 3 3
7 3 3 3
8 3 3 3
9 3 3 3
0 3 3 3
1 3 3 3
2 3 3 3
3 3 3 3
4 3 3 3
5 3 3 3
6 3 3 3
7 3 3 3
8 3 3 3
9 3 3 3
0 3 3 3
1 3 3 3
2 3 3 3
3 3 3 3
4 3 3 3
5 3 3 3
6 3 3 3
7 3 3 3
8 3 3 3
9 3 3 3
0 3 3 3
1 3 3 3
2 3 3 3
3 3 3 3
4 3 3 3
5 3 3 3
6 3 3 3
7 3 3 3
8 3 3 3
9 3 3 3
0 3 3 3
1 3 3 3
2 3 3 3
3 3 3 3
4 3 3 3
5 3 3 3
6 3 3 3
7 3 3 3
8 3 3 3
9 3 3 3
0 3 3 3
1 3 3 3
. 1 1 1