Hatena::ブログ(Diary)

西尾泰和のはてなダイアリー

2013-05-10

文字列の解析

プログラミング言語の処理系は、文字列として与えられたソースコードから意味を汲み取る必要があります。例えば"int x = 1234;"という文字列から、"1234"の部分が整数を意味しているということを理解する必要があります。

どうすればそのようなことができるでしょうか?

最初の一歩として"ab12cd"という文字列を受け取ると"12"を返す関数を作ることを考えてみましょう。

どうすればそのような関数を作れるでしょうか?

素朴に1文字ずつループ

まずはやりたいことをもっと明確に言語化してみましょう。やりたいことは「文字列を頭から1文字ずつ見ていって、0〜9の文字が続いている範囲を取り出したい」です

最初の文字が「0〜9の文字」でなかったら?その時は特に何もせずに次の文字を見れば良い。

次の文字も「0〜9の文字」でなかったら?その時も特に何もせずに次の文字を見れば良い。

次の文字が「0〜9の文字」だったら?これは結果として返すべき文字列の一部ですね。だけどまだreturnしてはいけません。だって次の文字の「0〜9の文字」かもしれませんから。と言うことは「後で結果として返すもの」を溜めておく必要がありますね。resultという名前で呼ぶことにします。

次の文字も「0〜9の文字」だったら?これも結果として返すべき文字列の一部です。これも溜めておく必要があります。

その次の文字が「0〜9の文字」でなかったら?ここでついに「0〜9の文字が続いている範囲」が終わりました!溜めておいた結果を返しましょう。

でも、「文字が『0〜9の文字』でない」という条件は「0〜9の文字が続いている範囲」の前と後と両方で使われていますね。「文字が『0〜9の文字』でない」という条件だけではどう行動するべきかが決まらないわけです。そこで「0〜9の文字が続いている範囲」が見つかったか、まだ見つかっていないのかを条件に含めることにします。これはis_foundという名前で呼ぶことにします。

こういう考え方で作られたPythonのコードが以下になります。

def find_int(string):
    result = ""
    is_found = False
    for char in string:
        print 'char=%r, result=%r, is_found=%r' % (char, result, is_found)
        if char in '0123456789':
            result += char
            is_found = True
        elif is_found:
            return result

    return ''


print find_int("ab12cd")

実行すると次のようになります。

char='a', result='', is_found=False
char='b', result='', is_found=False
char='1', result='', is_found=False
char='2', result='1', is_found=True
char='c', result='12', is_found=True
12


拙著「コーディングを支える技術」の読者から頂いた質問など対して、こんな感じで補足記事を書いて行きたいと思っています。質問・感想はおきがねなくどうぞ。

この解説は拙著の第3章と第4章の間に新しい章として入るのが適当かなと思います。その章のこの後の話の流れとしては

  • is_foundってのが1個あるだけならまだしも、もっと複雑になると分けがわからなくなる、どうしよう。(状態遷移図の導入)
  • 正規表現を使うと楽ちん
  • ネストしたカッコを正規表現で切り出せるか?(正規言語, 文脈自由言語)
  • どうやる?(再帰下降パーサ, yacc)
  • どう表現する?(BNF)

という感じかな。

拙著に関する他のエントリーは「「コーディングを支える技術」著者公式ページ」からたどれるようにします。

投稿したコメントは管理者が承認するまで公開されません。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/nishiohirokazu/20130510/1368196109