Hatena::Groupxn--272ax3f

スクリプト言語の作り方15日

スクリプト言語の作り方15日

プレゼンテーション

字句解析を手で書く

15.1 オートマトンに直す

  • [0-9]+ => [0-9][0-9]*
  • 図 15.1 は [0-9][0-9]* と等価なオートマトン
    • 丸のことを"状態"という
    • 矢印にそって移動できる。"遷移する"という。
  • 有限個の丸で構成できなければいけない
  • 34+41を一致するか調べてみよう
f:id:r_kurain:20121004192235j:image

もう一つのオートマトンの例

/\s*([0-9][0-9]*|[A-Za-z][A-Za-z0-9]*|=|==)/
図15.2 にオートマトン f:id:r_kurain:20121004192236j:image

汎用的な書き換え

15.2 オートマトンのプログラム

  • リスト 15.2 がオートマトンを実装した例
  • 先の正規表現だけに対応できる
  • read() を呼ぶだびに、一致する文字列が返る
  • while が輪っか状の矢印に対応して
  • if が 次の丸への遷移を示す

15.3 正規表現の限界

/\( ( [^()]++ | (?R) )* \)/