アンダースタンディング コンピュテーション ―単純な機械から不可能なプログラムまで

112

4

章 能力を高める

4.1.4

　シミュレーション

これで技術的詳細が解決しました。決定性プッシュダウン・オートマトンのシミュレーションを

Rubyで構築してみましょう。すでに難しいところはDFAとNFAをシミュレートするときにやってし

まっているので、あとはPDAに合わせてチューニングするだけです。欠けているところで最も重要な

のは、スタックです。以下に、

Stack

クラスの実装方法の1 つを示します。

class Stack < Struct.new(:contents)

def push(character)

Stack.new([character] + contents)

end

def pop

Stack.new(contents.drop(1))

end

def top

contents.first

end

def inspect

"#<Stack (#{top})#{co

ntents.drop(1).join}>"

end

end

Stack

オブジェクトはスタックの内容を配列に格納し、文字をスタックに積む

#push

操作、文字を

スタックから取り出す

#pop

操作、さらにはスタックのトップにある文字を読む

#top

操作を公開して

います。

>>

stack = Stack.new(['a', 'b', 'c', 'd', 'e'])

=> #<Stack (a)bcde>

>>

stack.top

=> "a"

>>

stack.pop.pop.top

=> "c"

>>

stack.push('x').push('y').top ...