Lecture 19: Recursive-Descent Parsing: Predictive Parsing
Lecture 19: Recursive-Descent Parsing: Predictive Parsing
The Turing Machine simulator used in the lecture is availble here. It's a Java applet so a Java runtime environment needs to be installed to use it. The source code for the applet is also available via the website, so it is posisble to run the simulator locally.
The following Turing Machine program for recognising words a^nb^nc^n where n >= 1 was developed by Thorsten Altenkirch It is simpler than the one in the lecture notes. The notation is slightly different from that used in the lecture: the first two fields gives the current state and the current tape symbol, the next three gives the new state, the tape symbol to replace the current type symbol by, and whether to move the read/write head left (<) or right (>). An underscore (_) is used as the blank symbol. As this particular simulator does not have any designated accepting states, we take the machine stopping in a configuration with a "Y" as the only non-blank symbol on the tape to mean success, and the machine stopping in any other configuration to mean reject.
1,a,2,#,> 2,a,2,a,> 2,#,2,#,> 2,b,3,#,> 3,b,3,b,> 3,#,3,#,> 3,c,4,#,< 4,#,4,#,< 4,b,4,b,< 4,a,5,a,< 4,_,6,_,> 5,a,5,a,< 5,#,1,#,> 6,#,6,_,> 6,_,7,_,> 7,_,8,Y,>Be aware that there might be a slight problem with the end of line character when pasting the code into the applet.