Une machine de Turing en Ruby - Le parser

La machine de Turing réalisée dans le dernier article était seulement un brouillon, et elle souffre de plusieurs limitations. J’aimerais maintenant faire évoluer le programme en permettant à l’utilisateur de charger un jeu d’instructions quelconque. Pour cela j’aurai besoin d’un parser, qui sera vite écrit grâce à Ruby.

Un jeu d’instruction pour la machine de Turing ressemblera à ceci (si vous avez besoin du code, il est ici):

0 A => 1 R B
1 A => 1 L C
0 B => 1 L A
1 B => 1 R B
0 C => 1 L B
1 C => 1 R HALT

C’est l’algorithme busy beaver à 3 états que j’ai utilisé pour coder la première version de la machine. Il faut écrire un parser qui va transformer ce code source en ce hash Ruby, utilisé en interne par la machine:

{
  ['0', 'A'] => {write: '1', move: 'R', next_state: 'B'},
  ['1', 'A'] => {write: '1', move: 'L', next_state: 'C'},
  ['0', 'B'] => {write: '1', move: 'L', next_state: 'A'},
  ['1', 'B'] => {write: '1', move: 'R', next_state: 'B'},
  ['0', 'C'] => {write: '1', move: 'L', next_state: 'B'},
  ['1', 'C'] => {write: '1', move: 'R', next_state: 'HALT'},
}

Voici le parser, qui est construit autour de la méthode String#split.

module TuringMachine

  class InstructionsParser

    def initialize(raw_instructions)
      @lines = raw_instructions.split("\n")
      @instructions = {}
    end

    def parse
      build_instructions
      @instructions
    end

    private

    def build_instructions
      @lines.each do |instruction|
        keys, value = instruction.split('=>')
        key_symbol, key_state = keys.split
        write, move, next_state = value.split
        @instructions[[key_symbol, key_state]] = {
          write: write, move: move, next_state: next_state
        }
      end
    end

  end

end

On va l’utiliser comme ça:

raw_instructions = IO.read(ARGV[0])
parser = InstructionsParser.new(raw_instructions)
instructions = parser.parse

Je vais expliquer plus en détail. Tout d’abord dans le constructeur, on divise la grande chaîne de caractères en entrée en autant de lignes indépendantes:

@lines = raw_instructions.split("\n")

Puis dans la méthode privée build_instructions, on itère sur chacune des lignes pour construire le hash:

@lines.each do |instruction|

Chaque ligne est d’abord divisé en deux parties, de chaque coté de =>:

keys, value = instruction.split('=>')

La partie des clés (celle de gauche) est à son tour divisé en deux, le symbole sous la tête de lecture et l’état de la machine:

key_symbol, key_state = keys.split

Ensuite c’est au tour de la partie de droite, celle qui représente la prochaine instruction:

write, move, next_state = value.split

Enfin, on ajoute clé et valeur dans le hash:

@instructions[[key_symbol, key_state]] = {
  write: write, move: move, next_state: next_state
}

Pour finir, voici mon premier jeu d’instructions pour une machine de Turing:

0 A => 1 R B
0 B => 0 R C
0 C => 1 R HALT

Ça fait quoi ? Ça écrit 101, tout simplement :

 turing_machine instruction_sets/write101 
  1 0000000000000000000000000000000000000000 A -> 1RB
                       ^
  2 0000000000000000000100000000000000000000 B -> 0RC
                        ^
  3 0000000000000000000100000000000000000000 C -> 1RHALT
                         ^
  4 0000000000000000000101000000000000000000 HALT

Je vous rappelle que vous pouvez consulter le code de la machine de Turing.

Voilà, avec l’aide de String#split il est facile d’écrire un parser simple. Alors bien sûr, ce parser n’est pas vraiment complet, il manque par exemple la gestion des erreurs. Mais il y a des choses plus urgentes à implémenter, comme le mouvement nul, le ruban infini, ou la possibilité de commencer le programme avec un ruban qui contient des données…

À plus tard.