PPPUC++ #8.333333.....

c++ reading
6.3.2 Tokens
  • と言うわけでようやくトークンに来ました
    • 実はオレオレバージョンは最初boost::spirit でおもむろに書きだしてしまい, definition(const まで打ったところで、「はっ」となって直したとか言うのは内緒*1
      • ただ、スタックなしバージョンとしては、このバージョンも最後まで書くべきだったかも。あとでやるかも
  • 先読み(look ahead)が必要ということ, しかし、ツッコム(barge ahead)前にまだいくつかヌケが。。。
    1. まず現時点(cin)でも複数行にまたがるのはOK
    2. どうやって'+'とか'-'とか探す？
    3. '*'がどこにあったかをどう記憶する？
    4. 順序をどうやって実装する？
  • まず 4 は置いとく
  • tokenize time!
  • 3種類のトークンが必要
    1. 浮動小数点数 ( 3.14, 0.274e2, ...)
    2. 演算子 (+,-, *, /, %) え？%も？？？
    3. 括弧
  • どうやってトークンを表現するか？　文字列中の場所を指定する方法は？　→　ダメ。ぐちゃぐちゃになる。
    • まず、数値とかそのまま文字列で持つのがダメ。複数行だと大変
      • ってそうかな？　前者は分かるけど後者は別に問題じゃない気が。まあ重箱の隅ですが
  • てわけで、(kind, value) のペアで覚えとくのが良さそう。
  • で class type!!
  • class とはよーするにユーザー定義型だよ、と。
    • DateとかMatrixとかBignumとか、言語仕様にも標準ライブラリにもない型ってのはあるのだけれど、それを入れてしまうとカオス
    • だからC++は他のモダンな言語と同じくユーザー定義型を用意してるのです！　(Mr.Sは C++がモダンだと言いたいようです)
      • つーか、その程度のものなら多くのモダンな言語ではモロにあるような。。。。（重箱の隅ごめんなさいごめんなさい）
6.3.3 Implementing tokens
  • どう実装すっか？
  • さっきの三種類を表せれば良いわけです。「種類」を示す物と値がある場合の「値」をパックした物
class Token {
public:
  char kind;
  double value;
};
    • 余段ですが僕はこのclass {}最後のセミコロンが許せない人です＜バカ
    • あとstructで教えないのは publicを強調したいのと最初はclassという用語を馴染ませたいからなのかな？
  • 演算子を直接 char で '+', '-' ... とか入れていく、という方針。数値はkind= '8'　なんでやw
    • avoid any magi(ry
  • ユーザー定義型にはメンバ関数も入れれるので、と、いきなりコンストラクタ&初期化子＆オーバーロードを出してます。大丈夫か初心者向け
class Token {
public:
  char kind;        // what kind of token
  double value;     // for numbers: a value
  Token(char ch)    // make a Token from a char
    : kind(ch), value(0) { }
  Token(char ch, double val) // make a Token from a char and a double
    : kind(ch), value(val) { }
};
    • 正直デフォルト引数で一行にまとめた方が最初はわかりやすいんじゃないかと思います。。。
  • コンストラクタについては 9.4.2& 9.7で詳細やります
6.3.4 Using tokens
  • つかっていこう!
  • Token get_token()みたいな関数を用意して、この結果をvectorにトークンを蓄積していく、という戦略
    • こうやってまず全読み、あとから解析
  • よーしじゃあ '*'の処理書いちゃうぞー、、、、と、アレ？　これだけではダメですねー。＊優先どうする？　括弧なんか対応しようがない
    • で、結局こうしたからって、何とかなるのかな？　というわざとらしい自問自答の後、この手じゃダメだ、と気がつくと言うお芝居。
  • こういった事は無意味でなんか無くて、むしろ問題を理解していく仮定としては悪くない、というのがMr.Sの意見みたいです（僕も同感です）。
    • 調査前、設計前などにこうした、無計画でバカっぽい（これ重要）小さな実験を行う事は、問題に直に触れ、人間の最大の武器である「感覚」レベルに問題を刷り込む、という重要なフェーズだと思います。
6.3.5 Back to the drawing board
  • で、さっきみたいにドつぼにハマらないよう、再考！（try not to dash ahead with another "half-baked solution"という表現が気に入りました）。
  • やってみて一つ気付いた事。単一の式を受けて、即finishはイケテナイ。いくら性能が上がったとはいえ、プログラムの起動は重い操作。
    • 実際に触ってみる事でユーザー視点でものを見ることに成功！　という事例ですね
    • 新たな疑似コードはwhile()でくくられただけ。
while(not_finished) {
  read_a_line
  calulate  // do the work
  write_result
}
  • さて上を見ながら疑問点を抽出します
    1. どうやって構成要素に分けるか＞Tokenize!
    2. 式の終端はどうする。＞もちろん 改行！　（この「もちろん」はくせ者。もちろんなんて理由は無い）
    3. 文字列で表された数値を 数値型に変換する方法は？ ＞ Tokenizeの一部になる
    4. 最大の難関、優先順位をどうするか＞　うーーーん？
    5. 入出力ともに浮動小数点にすべきか？＞あたりめー
    6. 変数を許すか？　＞　うーむ。いやそれより先にすべき事がある！　（実は7.8章でやるそうですが、これをやると問題が２倍くらいにふくれあがるそうです）
      • えーそうかなー, ひょっとしてmapもつかっちゃあかんの？　と思ったけど、確かにまともなパーサジェネなりライブラリの助けなしに作ろうとすると、変数名切り出すだけでもかなりホネですね
  • "Feature creep"に気をつけろ！ 　解析関数つけてみよか、ループ構文つけてみようか、ソルバルーチンも、グラフも、、、などなどの無限ループに陥る罠。
    • ってどっかで聞いたような。キノコ本だっけ？
  • プログラマ的には 1, 3, 4がやっかいものだそうな。
  • 結局、先人の知恵を拝借せえという話。キミ、50年もの年月を一朝で超えられるものかね、は、は、は、とか
    • 試行錯誤礼賛ちゃったんかー

6.4 Grammer

  • 先人の知恵によると、まずは
    1. Tokenに変換
    2. 文法を定義
    3. 文法に従ってToken列を解析する
  • ここではよくあるタイプの文法なんだけど
Expression:
  Term
  Expression "+" Term // addtion
  Expression "-" Term // subtraction
 :
 :
  • とゆーよーにいきなりLL(0)ではウマく行かないように左再帰しているアタリが心憎い（というかわざとらしい） さすが Mr.S
  • パッと見、文法なんて何の役に立つのよ？　という感じがするかも
    • かつて私もそうでした（ by オビ=ワン)
  • でも、よーく考えると、自分たちが何かを認識するときも、無意識下では同じ事をやっている
    • というのをトップルールExpressionから始めて〜　というのをしばし例示
    • ごめんなさい眠いので飛ばします_o_
6.4.1 A detour: English grammar
  • 遠回りねえ・・・
    • C++ swim and birds rules!!! とか書きたくなってくるくらいには面倒くさいです
    • って思ったら本書にもs/swim/fly/で書いてあったw
6.4.2 Writing a grammar
  • フィオ「良い文法書くための第一条件を教えて？経験？」 ビョルコ「 そうだな。経験だな」フィオ「がーーーーーん」
    • あんまりダァ・・・
  • まあ、しかし、簡単なのなら、以下の方法がわかればオK
    1. どうやってトークンと規則(の表記)を区別するか
    2. どうやってある規則を他の規則に連結するか
    3. どうやってorを表現するか
    4. 繰り返しをどう表現するか
    5. どれがスタート規則なのか
  • トークンのことを終端記号、規則の事を非終端記号と言ったり、と用語は様々（確かに）
  • ここでは,以下のように。。。
    • トークンは "（二重引用付）でくくりまくり
    • スタート規則は一番最初の行にしまくり
    • or は複数行に続けて書きまくり
  • というわけで例は {}でくくられて カンマセパレートなリストの例。
    • いきなり左再帰を無くしてるアタリが詰めがアマい（違
6.5 Turning a grammar into code

この章で一番の山場

  • 文法の実装方法は多数あるけれど、最も単純なものをここでは使います
    • 1つの規則を1つの関数で表し、トークンはToken型で表す、という方法
      • そういえば 索引にも Recursive Descentの項は無かったんだけど、名無しアルゴリズムで通すのかな？？？
6.5.1 Implementing grammar rules
  • 以下の４関数をユーティリティ関数として。
    1. get_token()　：　cin使ってトークンを切り出す
    2. expression() ： + , - で構成される式への対応。 term() と get_token() を呼び出します。
    3. term()　　　　： *, / で構成される式への対応。primary(), get_token()を呼び出します。
    4. primary()　　： 数値と括弧への対応。expression()と get_token()を呼び出します。
  • (改めて primary()からexpression()へのアークを想像して、これがあるから複雑な式に対応できるんだよな。とか。当たり前なんだけど、ちょっとワクワクしてきました)
  • 何気にこの例での「役割分担」させ方を, 一般的な問題の単純化へのヒントにするよう促す Noteがあります。つくづく教科書として良い本だなー
  • さて、これらの関数は何をするヒトゾ？
    • 各関数は文法規則に則って、その順番で対応する関数を呼ぶべし
    • トークンのところはトークンチェックすべし
    • ・・・こんだけ　^^
  • 返り値どうしよう？
    • 結局欲しいのは最終的な計算結果。途中は実は計算機に限れば必要ない
    • 解析結果のごちゃごちゃに対応しなくても良いんだ！
    • これはイイ！　というわけで、doubleを返します。
  • しかしハバな人もいます。get_token()です。この人はToken型を返す訳でそうはいかない
  • というわけで最終的なプロトタイプ宣言は
    1. Token get_token()
    2. double expression()
    3. double term()
    4. double primary()

となります

6.5.2 Expressions

まずは expression

Expression:
  Term
  Expression '+' Term
  Expression '-' Term
  • cultivate -- 耕す。はぐくむ。鍛える　... ちぃおぼえた
  • 最初なのでいくつか間違いをいれてある。こういうちょっとした差分の例から覚えていくのは良い方法
6.5.3 Expressions: first try
  • Expression '+' Term　という規則から expression()を呼んで、'+'('-')を確認して, それから term()を呼ぶのだ
double expression()
{
    double left = expression();
    Token t = get_token();
    switch (t.kind) {
    case '+':
        return left + term();
    case '-':
        return left - term();
    default:
        return left;
    }
}
    • アレレ、これでは無限ループ以前に不正文字でも答え返しちゃわないか？？？と思ったけど、おそらく get_token()が小姑か、あるいはさっき言ってた意図的な間違いか。
  • まあ前述の通り、これはいきなり最初の行で愉快に悪の無限再帰呼び出しになってしまうので動きませんが、役に立つ再帰呼び出しについては 8.5.8でやるそうです
6.5.2.2 Expressions: second try

何回トライするのかなwktk

  • Termの方がExpressionより小さい集合なわけだから、Termをまず見てから、それから Expressionかどうかを調べれば良い
    • ひっくりかえせ！
  • と言う感じ
  • すると今度は上手く行った
    • かのように見えるw　加算である限りは
    • 減算では右結合なので 1-2-3 が 1-(2-3)となり =2 となってしまうおいおい
  • こういうバグは実に危険。なぜなら、バグが見つかったり見つからなかったりするから
    • ハイゼンバグに比べたら再現性のあるバグなんて・・・
  • 結局、不用意に文法を変えてしまうような変更を行ったためこうなったとの事。
  • また、新世界の神になる、という第三の選択肢をちらつかせる　ドSさん（嘘
6.5.2.3 Expressions: third time lucky
  • いったいどうしたら
    • 根本的に文法変えてしまう。
  • 繰り返しを使って '+'|'-' Termを反復させる。
  • そう、必要なのは first tryから expressionを消し飛ばす事だったはず
    • というわけで expression()をループにて表現してみましたー、というのがここでの話
    • 個人的にはthird tryの最初のコード(共通部分くくりだして get_token()呼び出しを一回にしている)方が、僕には読みやすいのだけれど Mr.S的には混乱するだけだからcaseに分けてコピペせよとのこと。うーむ。
6.5.3 Terms
  • これはほとんど同じ
Term:
 Primary
 Term '*' Primary
 Term '/' Primary
 Term '%' Primary
  • しかし'%'。これはfloatを対象にすると演算が未定義。
    • そうだよねえやっぱ
    • というわけで、これを実装するには
      1. 両方とも整数である事を確認してから答。どちらかが整数で無い場合はエラー
      2. あきらめて仕様から抜く（潔い）
    • この問題は"浮動小数点にしよか？　YES!!!"という無策（？）が生んだ結果。いわゆる 'feature creep!!' 。てなわけで更なる犠牲にならないためにも今回は潔い方で
  • あとは ZERO DIVIDEエラーね。

6.5.4 Primary expressions

Primary:
  Number
  '(' Expression ')'
  • 一見ややこしいけどやることは単純
    • そのままコーディングするだけ。

*1:なにせexampleと全く一緒になってしまいますし・・・