一个sed写的图灵机

cjaizss

还在加班，不断修改、编译数字电路
无聊中在这里看一个图灵机
该图灵机用sed编写，源码如下：

1. 
   
2. #! /bin/sed -f
   
3. #
   
4. # turing.sed -- emulate a Turing machine
   
5. #
   
6. # Christophe Blaess <[email]ccb@club-internet.fr[/email]>
   
7. # [url]http://perso.club-internet.fr/ccb/[/url]
   
8. 
   
9. # See text file for information about Turing Machine script.
   
10. 
    
11. # Read all the instructions, and add a final newline.
    
12. :read
    
13. N
    
14. $!b read
    
15. G
    
16. 
    
17. # Delete comments extending from a '#' to the end of the line.
    
18. s/#[^\n]*\n//g
    
19. s/#.*$//g
    
20. 
    
21. # Use a colon to separate the instructions.
    
22. s/\n/:/g
    
23. 
    
24. # Is there an initial tape ?
    
25. /|/ s/\(.*\)|\([^:]\)\([^:]*\):\(.*\)/|\2|\3:\1\4/
    
26. 
    
27. # else insert a blank one.
    
28. /|/!s/\(.*\)/| |:\1/
    
29. 
    
30. # Reserve the storage place at the beginning of the pattern space,
    
31. # then set the current state to zero.
    
32. s/\(.*\)/0x\1/
    
33. 
    
34. # Start the machine !
    
35. :loop
    
36.         # Display only the tape and the state.
    
37.         h
    
38.         # (comment out the next two lines to see internal data when
    
39.         #  debuging TM script)
    
40.         s/:.*//
    
41.         s/^\(.\)./(\1) /
    
42.         p
    
43.         g
    
44. 
    
45.         # Check the content of the current cell.
    
46.         /|[^:|]|/!{
    
47.                 s/.*/Internal error in the Turing machine/
    
48.                 q
    
49.         }
    
50. 
    
51.         # Store in second position the symbol read on the tape
    
52.         s/^\(.\).\(.*\)|\(.\)|\(.*\)/\1\3\2|\3|\4/
    
53. 
    
54.         # Have we reached a final state ?
    
55.         /^\(.\).*:\1/!{
    
56.                 s/\(.\).*/Final state \1 reached... end of processing/
    
57.                 q
    
58.         }
    
59. 
    
60.         # Is there an instruction for this state and this cell content ?
    
61.         /^\(..\).*:\1/!{
    
62.                 s/^\(.\)\(.\).*/No instruction for state \1 and cell \2/
    
63.                 q
    
64.         }
    
65. 
    
66.         # Look for the new content to write.
    
67.         /^\(..\).*:\1[^:|]/!{
    
68.                 s/.*/I can't write this symbol on the tape!/
    
69.                 q
    
70.         }
    
71.         s/^\(..\)\(.*\)|.|\(.*\):\1\(.\)/\1\2|\4|\3:\1\4/
    
72. 
    
73.         # Look for the direction of movement.
    
74.         /^\(..\).*:\1.[ LRlr]/!{
    
75.                 s/.*/Movement must be specified as L, R or space/
    
76.                 q
    
77.         }
    
78.         # Clear the substitute flag that we will use later.
    
79.         t nop
    
80.         :nop
    
81.         /^\(..\).*:\1. / {
    
82.                 # Direction = ' ' -> Don't move the head
    
83.                 b end_move
    
84.         }
    
85.         /^\(..\).*:\1.[Ll]/ {
    
86.                 # Move the head to the left if the tape is long enough,
    
87.                 s/^\(..\)\(.*\)\(.\)|\(.\)|/\1\2|\3|\4/
    
88.                 t end_move
    
89.                 # else extend the tape with an empty cell.
    
90.                 s/|\(.\)|/| |\1/
    
91.                 b end_move
    
92.         }
    
93. 
    
94.         # Move the head to the right, if the tape is long enough,
    
95.         s/|\(.\)|\([^:]\)/\1|\2|/
    
96.         t end_move
    
97.         # else extend the tape with an empty cell.
    
98.         s/|\(.\)|/\1| |/
    
99. 
    
100.         :end_move
     
101. 
     
102.         # Check the new state,
     
103.         /^\(..\).*:\1..[^:|]/!{
     
104.                 s/.*/I can't use this symbol as new state/
     
105.                 q
     
106.         }
     
107.         # then switch the machine state
     
108.         s/^\(.\)\(.\)\(.*\):\1\2\(..\)\(.\)/\5\2\3:\1\2\4\5/
     
109. 
     
110.         # Garbage collector : cut the blank portions of the tape,
     
111.         # on the left,
     
112.         s/\(..\) */\1/
     
113.         # then on the right.
     
114.         s/\(..\)\([^:]\) *:/\1\2:/
     
115. 
     
116.         b loop
     
117. 
     
118. ###### end of the script
     

复制代码

[ 本帖最后由 cjaizss 于 2008-5-29 21:39 编辑 ]

cjaizss

改一下标题，呵呵

nicolas.shen

曲高和寡

linux_kaige

我使用的sed，一般也不超过3、5行。。。