… パーザーと構文木 BNFによる文法記述 再帰降下（下降）法 ソースコードとトークン列高級言語のソースコード（今回の例では、1 + 2, (5 - 2)*4 のような算術式です）は、なんらかのテキストストリームから言語処理系に入力されます。ファイル、キーボード、文字列データなどが入力源となるテキストストリームですね。入力テキストストリームは、トークンスキャナーによりトークンの列に変換されます。トークンとは、それ以上は分解できない構文的な“かたまり”のことです。今回扱う算術式で…

…、取り急ぎ。味気ないBNFのみ。補助的な定義 型 ::= 型変数 | 任意のJSON型表現 | 'never' スカラー型 ::= integer型 | number型 | string型 | boolean型 | null型 | 簡易列挙型 | 'anyScalar' /* * スカラーの各型は、型名予約語にオプショナルなスキーマ属性 * never の意味は、出力が存在しないこと（voidとは違う！） * anyScalar の意味は、(number|string|boo…

…。以下、構文記述にはBNFを用います。パイプラインとコマンド式Catyスクリプトは、コマンド言語と式言語のハイブリッドな性格を持ちます。トップレベルの構文要素（ルート非終端記号）を「パイプライン」、セカンドレベルの構文要素を「コマンド式」とします。うーん、ハイブリッドですなー。まずは次の定義をしましょう。 単純コマンド式 ::= スカラーリテラル | コマンド呼び出し | '(' パイプライン ')'単純コマンド式は、コマンド式のビルディングブロックです。スカラーリテラルとコ…

…されます。構文は全部BNFで定義してますが、あまりきれいでも効率的でもありません。BNF以外の文法が適切な部分もあります（演算子による式とか）。説明用なので、ここに書くBNF自体を尊重する必要はありません。型（type）と型表現（type expression）が混同されていますが、構文の話しかしてないので混乱はないと思います、型＝型表現です。意味論の話をするときは、もう少し注意します。以前からの変更点今までモンヤリと記述しただけなので、変更というほどのことではないけど書いて…

…かが確定すれば、次のBNFで「名前」という構文要素を定義できます。 名前 ::= 名前文字+ 上の定義に合致する文字列でも、さらに若干は除外すべきものが出てくるかもしれません。例えば、"." と ".." は通常の意味では使わない（後述）ので、誤解を招かないために禁止したほうがいいでしょう。mafsで使うパス名は常に絶対パスです。 絶対パス ::= 接頭辞? '/' パス主要部 パス主要部 ::= 空文字列 | 名前 ('/' 名前)* '/'? 接頭辞 ::= 名前 接頭辞…

…望もありそうですね。BNF風にするなら、次のようかな。 name ::= (string(minLength = 2, maxLength = 20) | object { "given" : string(minLength = 1, maxLength = 10), "family" : string(minLength = 1, maxLength = 10) } ); 今まで述べてきたような型定義構文は「難しすぎる」という意見もあるでしょうね（僕自身そう思っています）…

…造を明白にするため、BNFまたは再帰方程式でツリーを定義してください。 プログラミング課題 10： 正の数aは前もって与えられた定数として、連立方程式 {x = a*y, y = 1 + x*y, x, yは非負}を近似的に解くプログラムを書いてください。（次の問題も見ておいてね。） 考える課題 11： なぜ、近似的な数値解法の問題がここに紛れ込んでいるのでしょう？（ヒント→「データ型のクレイジー計算」） さて、次の図を眺めながら、後に続く説明を読んでくださいね。（下側の図で…

…うことで、構文定義のBNFは次のようにすべきでした。 式 ::= 加数 ('+' 加数)* 加数 ::= 因数 ('*' 因数)* 因数 ::= 数 | '-' 因数 | '(' 式 ')' あるいは： 式 ::= 加数 | 加数 '+' 式 加数 ::= 因数 | 因数 '*' 加数 因数 ::= 数 | '-' 因数 | '(' 式 ')'さらにあるいは： 式 ::= 加数 ('+' 式)? 加数 ::= 因数 ('*' 加数)? 因数 ::= 数 | '-' 因数 | …

…ある）。ここから先のBNFでは、空白と区切り記号で字句に切り分けた後の構文を記述します。変数と関数： variable ::= name function ::= name '(' args ')'値を表す式： value ::= number | string | boolean | null | variable | function関数の引数： args ::= EMPTY | arg (',' arg)* arg ::= valueさて、構文的には関数呼び出し（fun…

…。JSONを定義するBNFにこだわらずに、Xion構文を直接に書き下してみましょう。次の点に注意してください。 例えば、objectは、JSONのobjectではなくて、taggedObject（XionObject）です。 tagとkey（の名前）として有効な文字列は前もって定義されているとします。 繰り返し記号「*」は、カンマを区切り文字としての繰り返しを表すとします。 アンダスコアから始まる構文要素は、BNF上でだけ使い、構文イベントにはなりません。 [1] objec…

…か言う。 正規表現／BNFは無意識に使う。 文字のコードポイントとエンコードされた表現を、キチンと区別して話す。 「アイオー（Io）」とか「ベータ（Beta）」とか、検索に困る名前のプログラミング言語を知っている。 AWKの語源となった3人の本（著者の一人となっている書籍群）を読んでいる。 バイトオーダや構造体パディングで失敗した経験はある。 その気になれば、きったなーいコードを書ける。 パワーポイントは使わない（使えない？）が、ホワイトボードでの説明はうまい。 デザインパタ…

…“タプルを作る”） BNF（線形文法規則と言っても同じ）で次のように書いた方が馴染みやすいでしょうかね： s ::= ε | a s （εは空列、a∈A, s∈S） これを順次代入で、S0 = O（空）, S1 = I + A×O, S2 = I + A×I, S3 = I + A×(I + A), ... と解いてもいいのだけど（それが正統的）、Waltersは次のクレイジー計算をしてます。 S = I + A×S ↓A×Sを移項して S - A×S = I ↓S = I×…

…（割とよくある形の）BNFで書いておきます。1つの定義を複数行で書くので、定義の最後にセミコロンを付けています object ::= '{' '}' | '{' members '}' ;members ::= string ':' value | members ',' string ':' value ;array ::= '[' ']' | '[' elements ']' ;elements ::= value | elements ',' value ;value …

…シになります。概念的な木ではないので扱いにくいし、パフォーマンスにも悪影響を与えます。開発中のバージョン3では、この問題を解決するために、AST transformatin という機構を入れたようですが、生成規則を汚すので、SableCCの本来の美点をそこねる気がします。JJTreeでは、BNF上で、木に組み入れる構文要素を指定できます。こっちのほうが（記述能力は低いが）汚染度は少ないですね。これ以上詳しい話（があれば、それ）は、キマイラ・サイトのほうに載せるかもしれません。

…じってみたのですが、BNF（構文記述）とJavaコード（アクション）が混じる記述にウンザリ（yaccでも同じです）。JJTreeというツールと一緒に使うと、さほどアクションを書かずに構文木を作ってくるようではありますが。いずれにしても、JavaCCの構文記述は汚い感じがします。しょうがない、がまんすればいいハナシか、と思っていたら、SableCC（http://sablecc.org/）というのを見つました。SableCCでは、アクションを書き込まないので、構文記述がスッキリ…

…に依存するからです。BNFのような実例からはじめたほうが説明としては親切でしょうが、背景を説明しきらないと、どうも落ち着かないのです。再帰代入系（の圏）は、曖昧な形では1995年くらいから漠然と認識してましたが、全体の構造がだいたい分かったのは1999から2000年くらいです（あまり時期を特定できませんが）。しかし、その頃はたぶんうまく説明できなかったでしょう。説明のための適切な言葉を持っていなかったので。トレース付きモノイド圏（traced monoidal categor…