Comments
Description
Transcript
2007年度 早稲田大学理工学部CS学科 プログラミング言語論
2007年度 早稲田大学理工学部CS学科 プログラミング言語論 Part 05: 式と演算子 小野 康一 (ONO, Kouichi) [email protected] 式, 演算式 (expression, formula) 算術演算式 (arithmetic expression) 論理演算式 (logical expression, logic formula) 2007年度 早稲田大学 CS学科 プログラミング言語論 演算子 (operator) 何らかのシンボル(記号)によって表現される 演算 基本的には関数記号と同じ いくつかの(0個以上の)引数をとり、それによって何 らかの計算を表現し、(多くの場合において)その計算 の結果としての評価値を持つ 2007年度 早稲田大学 CS学科 プログラミング言語論 (演算子の)引数の個数 (arity) 単項演算子 (unary operator) 否定演算子 (!) 二項演算子 (binary operator) 加算/減算/乗算/除算演算子 (+,-,*,/) 論理積/論理和演算子 (&&,||) 等値演算子 (==) 代入演算子 (=) 三項演算子 (ternary operator) 条件演算子 (?:) 四項演算子 (quadternary operator) 存在する? n項演算子 (n-ary operator) 2007年度 早稲田大学 CS学科 プログラミング言語論 表記法 (notation) 前置記法 (prefix notation) 演算子を最初に置き、その後に引数を配列する表記法 “+ 3 5” 中置記法 (infix notation) 我々が日常で慣れ親しんでいる表記法 “3 + 5” 後置記法 (postfix notation) 引数を先に配列し、最後に演算子を配置する表記法 “3 5 +” 2007年度 早稲田大学 CS学科 プログラミング言語論 前置記法 たとえば * + 2 3 6 において、加算演算子(+)の引数は “2” と “3” であり、乗算演算子(*)の引数は “+ 2 3” と “6” である これは、中置記法で表すと ( 2 + 3 ) * 6 となる 前置記法では括弧は必要ない 2007年度 早稲田大学 CS学科 プログラミング言語論 前置記法による式の評価 前頁の式 * + 2 3 6 において、仮に、これらの演算子がCall-byValueであるとすると、この式は + 2 3 の演算結果を求めて(仮にrとする)、それを用 いて * r 6 の演算結果を求める計算を表していることに なる 2007年度 早稲田大学 CS学科 プログラミング言語論 前置記法: この式の評価値は? 整数の算術演算子として、加算演算子(+)、減 算演算子(-)、乗算演算子(*)、除算演算子 (/)があるとする。なお、除算演算子は剰余を 切り捨てた整数値を返すとする また、評価戦略はCall-by-Valueであるとす る この時、以下の式の評価値は何になるか? * 2 - 8 / + 6 5 / 9 4 2007年度 早稲田大学 CS学科 プログラミング言語論 前置記法による四則演算式のBNF 前置記法で整数の四則演算を表現する算術 演算式の構文規則をBNFで表すと、以下のよ うになる <expr> ::= <op> <expr> <expr> | <digits> <op> ::= + | - | * | / <digits> ::= <digit> | <digits> <digit> <digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 2007年度 早稲田大学 CS学科 プログラミング言語論 後置記法 たとえば 3 5 + 2 / において、加算演算子(+)の引数は “3” と “5” であり、除算演算子(/)の引数は “3 5 +” と “2” である これは、中置記法で表すと ( 3 + 5 ) / 2 となる 後置記法では括弧は必要ない 2007年度 早稲田大学 CS学科 プログラミング言語論 後置記法による式の評価 前頁の式 3 5 + 2 / において、仮に、これらの演算子がCall-byValueであるとすると、この式は 3 5 + の演算結果を求めて(仮にsとする)、それを用 いて s 2 / の演算結果を求める計算を表していることに なる 2007年度 早稲田大学 CS学科 プログラミング言語論 後置記法: この式の評価値は? 整数の算術演算子として、加算演算子(+)、減 算演算子(-)、乗算演算子(*)、除算演算子 (/)があるとする。なお、除算演算子は剰余を 切り捨てた整数値を返すとする また、評価戦略はCall-by-Valueであるとす る この時、以下の式の評価値は何になるか? 9 4 2 3 + * 6 – 5 / / 2007年度 早稲田大学 CS学科 プログラミング言語論 後置記法による四則演算式のBNF 後置記法で整数の四則演算を表現する算術 演算式の構文規則をBNFで表すと、以下のよ うになる <expr> ::= <expr> <expr> <op> | <digits> <op> ::= + | - | * | / <digits> ::= <digit> | <digits> <digit> <digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 2007年度 早稲田大学 CS学科 プログラミング言語論 「ポーランド記法」/「逆ポーランド記法」 前置記法のことをポーランド記法(Polish Notation)、 後置記法のことを逆ポーランド記法(Reverse Polish Notation/RPN, あるいはInverse (Inverted) Polish Notation/IPN)とも呼ぶ この場合の “Polish” は、「ポーランド人(の)」と訳す 方が適切であり、「(逆)ポーランド記法」という訳語は、 ある種のごまかしを含んでいるといえる この “Polish” はポーランド人全体ではなく、論理学 者 Jan Łukasiewicz/ヤン・ウカシェヴィチ(ポーラン ド/1878.12.21-1956.02.13)を指している。彼は 前置記法による数式表現を提唱した 2007年度 早稲田大学 CS学科 プログラミング言語論 Jan Łukasiewiczの表記法 それならば、“Polish”などと書かずに、 Łukasiewicz Notationと命名するのがスジ だが、そうはならなかった コンピュータの技術はUSが主流であり(あとは UKくらい)、北米と西欧圏以外の研究業績は 軽んじられることが時々ある。これもそのケー スかもしれない この講義では、「(逆)ポーランド記法」のような 呼び方はせず、「前置記法」「後置記法」とする 2007年度 早稲田大学 CS学科 プログラミング言語論 前置記法と欧米系言語 前置記法で書かれた式は、欧米系の自然言語で読 み下すと、素直な表現になりやすい たとえば + 3 5 は、 addition of 3 and 5 のように読み下せる。あるいは / + 3 5 2 は、たとえば英語を用いて、 division of addition of 3 and 5 with 2 のように読み下せる(自然言語なので前置詞などの 係りの範囲が曖昧になりがちであり、正確さは失われ るが) 2007年度 早稲田大学 CS学科 プログラミング言語論 後置記法と日本語 後置記法で書かれた式は、日本語で読み下すと、素 直な表現になりやすい たとえば 3 5 + は、 3と5を足す のように読み下せる。あるいは 3 5 + 2 / は、 3と5を足し(て、それを)2で割る のように読み下せる(当然、日本語も自然言語であり、 係り受けなどが曖昧になりがちであり、正確さには欠 ける) 2007年度 早稲田大学 CS学科 プログラミング言語論 中置記法 後置記法が日本語と親和性が高いとはいえ、 やはり我々は、後置記法による式表現をいきな り見せられると、すぐに読み取ることが難しい 人間は、慣れている表現の方がどうしてもとっ つきやすいので、中置記法による式表現の方が 読み取りやすいように感じる しかし、中置記法による式を読み取るには、「そ の演算子の引数となる項は、式中のどの部分 なのか」を判別する必要がある 2007年度 早稲田大学 CS学科 プログラミング言語論 中置記法による式の解釈に必要な概念 中置記法による式の解釈において、「その演算 子の引数となる項は、式中のどの部分なのか」 を判別可能にするために、以下の概念が必要 になる 優先順位 (precedence) 結合性 (associativity/association) 括弧 2007年度 早稲田大学 CS学科 プログラミング言語論 中置記法における演算子の優先順位 中置記法による式では、個々の演算子に優先 順位 (precedence) があらかじめ定められて いる 複数の演算子を用いて書かれた式では、優先 順位の高い演算子が近くの項を引数に取る 2007年度 早稲田大学 CS学科 プログラミング言語論 優先順位の例 たとえば、加減算演算子(+,-)よりも、乗除算演算子 (*,/)の方が優先順位が高い。よって、 2 * 3 + 5 は、括弧を補って優先順位を明示すると ( 2 * 3 ) + 5 となる。また、 2 + 3 * 5 は 2 + ( 3 * 5 ) となる。 ( 2 + 3 ) * 5 とはならない 2007年度 早稲田大学 CS学科 プログラミング言語論 中置記法における演算子の結合性 中置記法による式では、等しい優先順位を持つ演算 子が連続する場合に、どちらの演算子が先に各項と 結合するか(各項を引数に取るか)があらかじめ定め られている 左側の演算子が先に結合する場合、その演算子は 左結合性(left associativity/association)を持つ といい、右側の演算子が先に結合する場合、その演 算子は右結合性(right associativity/association)を持つという ほとんどの演算子は左結合性を持つ 2007年度 早稲田大学 CS学科 プログラミング言語論 結合性の例 たとえば、加減算演算子(+)と減算演算子(-) は、優先順位が等しく、左結合性を持つ。この 演算子が連続する式 7 - 4 + 6 は、 ( 7 - 4 ) + 6 となる。 7 – ( 4 + 6 ) とはならない 2007年度 早稲田大学 CS学科 プログラミング言語論 右結合性を持つ演算子 多くのプログラミング言語において、ほとんどの演算子 は左結合だが、一部の演算子は右結合性を持つ たとえば、代入演算子や冪(べき)乗演算子など 2007年度 早稲田大学 CS学科 プログラミング言語論 右結合性を持つ演算子の例 代入演算子 C/C++/Javaは代入演算子(“=”)を持つ。言い換えると、これ らの言語では、代入文は式でもあり、したがって評価値を持つ。 ということは、代入文を式の中に書いたり、関数の引数として 与えることができる、ということである Pascalなどの言語は代入演算子を持たない。それらの言語 は、代入記号(Pascalでは“:=”)はあるが、それは演算子では ない。つまり、それらの言語では、代入文は式ではない 冪乗演算子 Fortranでは “**”、Basicでは “^” C/C++/Javaは冪乗演算子を持たない(関数ライブラリやク ラスライブラリで冪乗を計算する関数が提供されている) 2007年度 早稲田大学 CS学科 プログラミング言語論 代入演算子 代入演算子(=)は、一般に、右結合性を持つ たとえば、C/C++/Javaにおいて、 int a = 10; int b = 20; a = b = 30; というプログラムの最後の代入文は、括弧を補うと a = ( b = 30 ); と同じ意味になる 変数aには、 b = 30 という式(代入文は式でもある)の評価値が代入されるが、 この式の評価値は30である。よって、変数aには30が代 入される 2007年度 早稲田大学 CS学科 プログラミング言語論 冪乗演算子 冪乗演算子は、一般に、右結合性を持つ そうではない言語もある。たとえばCOBOLでは、 冪乗演算子は左結合性を持つ たとえば、Fortranにおいて、 2 ** 3 ** 4 という式は、 2 ** ( 3 ** 4 ) となる。 ( 2 ** 3 ) ** 4 ではない 2007年度 早稲田大学 CS学科 プログラミング言語論 括弧 中置記法で、演算子の優先順位や結合性に沿わな い式を表現するためには、括弧を用いる必要がある たとえば 2 + 3 * 6 という式において、乗算演算子(*)の引数となる項は “3” と “6” であり、加算演算子(+)の引数となる項は “2” と “3 * 6” である。これを、加算演算子の引数と なる項が “2” と “3”、乗算演算子の引数となる項が “2 + 3” と “6” となるように表現するには、括弧を用 いる必要がある。たとえば、 ( 2 + 3 ) * 6 のように表現する 2007年度 早稲田大学 CS学科 プログラミング言語論 中置記法による四則演算式のBNF 中置記法で整数の四則演算を表現する算術 演算式の構文規則をBNFで表すと、以下のよ うになる <expr> ::= <expr> <asop> <term> <term> ::= <term> <mdop> <factor> <factor> ::= <digits> | ( <expr> ) <asop> ::= + | <mdop> ::= * | / <digits> ::= <digit> | <digits> <digit> <digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 2007年度 早稲田大学 CS学科 プログラミング言語論 この構文規則はいい加減? 前頁の構文規則だと、数値が“0”で始まること を許す 123 + 098 - 0000 奇妙な表現ではあるが、現実のプログラミング 言語でもそのような数値の表現は許されてい るので、構文規則を厳格化することはしない 「厳格な」構文規則を考えてみたい人はBNF の練習のつもりでやってみるとよいだろう 2007年度 早稲田大学 CS学科 プログラミング言語論 中置記法による式の構文解析木 expr 構文解析木 (構文木) term syntax tree mdop factor term (parse tree) factor * digits 例: ( 2 + 3 ) * 6 ( expr ) digit asop term expr 6 expr + factor term 非終端記号 digits nonterminal symbol factor digit digits 2 3 digit 終端記号 terminal symbol 2 2007年度 早稲田大学 CS学科 プログラミング言語論 抽象構文木 構文木には、非終端記号も終端記号もすべて含まれているので、 構造を解析するには有用 しかし、式の評価や変換のためには、構文木を作るよりも、抽象構 文木 (abstract syntax tree/AST)を作る方が有用 区別のために構文木を具象構文木(concrete syntax tree/CST)と呼ぶことがある 抽象構文木は、表記法から独立したデータ表現になる 例: ( 2 + 3 ) * 6 * + 2 6 3 2007年度 早稲田大学 CS学科 プログラミング言語論 抽象構文木を用いた式の評価 抽象構文木は再帰的なデータ構造なので、評価も再 帰的な計算アルゴリズムになる int eval(Node tree) { if (treeが数値) // treeが 2 のような場合 return treeの数値 Operator op = tree.getOperator(); Node tree1 = tree.getArg(1); * Node tree2 = tree.getArg(2); int r1 = eval(tree1); int r2 = eval(tree2); + return op.apply(r1,r2); } 3 2 2007年度 早稲田大学 CS学科 プログラミング言語論 6 抽象構文木を用いた式の変換 抽象構文木は表記法から独立したデータ構造になっている したがって、ある表記法で書かれた式を別の表記法に変換したい 場合には、一旦、式から抽象構文木を作成し、その木を再び別の 表記法で書き下せばよい 抽象構文木を、とある表記法で書き下すためには、木になってい るすべてのデータを一通り辿る必要がある (式の変換に限らず)木構造になっているデータを一通り辿ること を、「木のtraverse(横断,走査)」という * + 2 6 3 2007年度 早稲田大学 CS学科 プログラミング言語論 木のtraverse 辿る順序 (traverse order) にはいくつかある pre-order post-order in-order * + 2 6 3 2007年度 早稲田大学 CS学科 プログラミング言語論 pre-order traverse 木をroot nodeから再帰的に辿る 最初に、現在着目しているnodeを訪れる 続いて、そのnodeのsubtreeを左から辿る pre-order traverseで訪れた順序で出力すると、 prefix notationの式になる (1) * * + 2 3 6 (2) + (3) 2 (5) 6 (4) 3 2007年度 早稲田大学 CS学科 プログラミング言語論 post-order traverse 木をroot nodeから再帰的に辿る 最初に、現在着目しているnodeのsubtreeを左から辿る 最後に、そのnodeを訪れる post-order traverseで訪れた順序で出力すると、 postfix notationの式になる (5) * 2 3 + 6 * (3) + (1) 2 (4) 6 (2) 3 2007年度 早稲田大学 CS学科 プログラミング言語論 in-order traverse 木をroot nodeから再帰的に辿る 最初に、現在着目しているnodeの最左のsubtreeを辿る 次に、そのnodeを訪れる 続いて、そのnodeの2番目以降のsubtreeを左から辿る in-order traverseで訪れた順序で出力すると、infix notationの式になる?? (4) * 2 + 3 * 6 (2) + (1) 2 (5) 6 (3) 3 2007年度 早稲田大学 CS学科 プログラミング言語論 in-order traverseによる中置記法 in-order traverseで訪れた順序で出力すると、infix notationにはなるが、正しい式ではない 出力されるべき式は 2 + 3 * 6 ではなく ( 2 + 3 ) * 6 (4) * のはず 括弧を適切に補う必要がある (2) + (5) 6 (1) 2 (3) 3 2007年度 早稲田大学 CS学科 プログラミング言語論 括弧をどのように補うか? 抽象構文木には括弧に対応するnodeがない ので、適切に補う必要がある naiveな方法: 全部に括弧をつける (4) * (2) + (1) 2 (5) 6 (3) 3 2007年度 早稲田大学 CS学科 プログラミング言語論 “naive” 日本語では、「ナイーヴ」が「繊細な」といった 印象の語として用いられることがあるが、英語 だとnaiveはあまりいい意味で用いられない 英語でも「純真な」「素朴な」といった意味もあるが、 大抵は「世間知らずの」「ばか正直な」という意味 で用いられる コンピュータ用語で「naive way (naiveな方 法)」と言うと、「ばか正直なやり方」「あまり深く 考えていないやり方」「工夫のないやり方」と いった意味になる 2007年度 早稲田大学 CS学科 プログラミング言語論 naiveな括弧の付け方 木をroot nodeから再帰的に辿る 最初に、開き括弧(“(”)を出力する 現在着目しているnodeの最左のsubtreeを辿る 次に、そのnodeを訪れる(Æそのnodeを出力する) 続いて、そのnodeの2番目以降のsubtreeを左から辿る 最後に、閉じ括弧(“)”)を出力する このやり方だと以下の式が出力される (4) * (((2) + (3)) * (6)) (2) + (1) 2 (5) 6 (3) 3 2007年度 早稲田大学 CS学科 プログラミング言語論 括弧の付け方 naiveなやり方によって出力される式 (((2) + (3)) * (6)) は、出力されるべき式 ( 2 + 3 ) * 6 と意味は同じ(括弧が冗長なだけ) しかし、不要な括弧は出力しないように抑制させたい 要/不要の条件は何か? (4) * (2) + (1) 2 (5) 6 (3) 3 2007年度 早稲田大学 CS学科 プログラミング言語論 括弧の付け方 (cont’d) 括弧の要/不要は、優先順位と結合性から判断 親子の関係にある二つのnode a, bがともに演算子で あると仮定(親nodeがa、子nodeがb) aよりbの優先順位が高い場合は不要、低い場合は必要 優先順位が等しい場合、結合性から判断 a 左結合性の場合 bがaの左の子nodeなら不要 右結合性の場合 bがaの右の子nodeなら不要 b 2007年度 早稲田大学 CS学科 プログラミング言語論 式のparse 式の文字列を字句解析してトークン列にする 前置記法: “* + 2 3 6” Æ “*” “+” “2” “3” “6” 後置記法: “2 3 + 6 *” Æ “2” “3” “+” “6” “*” 中置記法: “(2+3)*6” Æ “(” “2” “+” “3” “)” “*” “6” トークン列を元に、抽象構文木を作成する * + 2 6 3 2007年度 早稲田大学 CS学科 プログラミング言語論 式のparse: 前置記法 トークン列からトークンを取り出す トークンが演算子シンボルの場合、演算子nodeを作 成し、残りのトークン列から、その演算子のarityの数 だけ、treeを作成して演算子nodeの子nodeにする トークンが数値シンボル/変数シンボルの場合、数値 node/変数nodeを作成する * * + 2 3 6 + 2 6 3 2007年度 早稲田大学 CS学科 プログラミング言語論 式のparse: 後置記法 トークン列からトークンを取り出す トークンが演算子シンボルの場合、演算子nodeを作 成し、スタックから、その演算子のarityの数だけ、 nodeをpopして演算子nodeの子nodeにして、演算 子nodeをスタックにpushする トークンが数値シンボル/変数シンボルの場合、数値 node/変数nodeを作成して、そのnodeをスタックに * pushする 2 3 + 6 * + 2 6 3 2007年度 早稲田大学 CS学科 プログラミング言語論 式のparse: 中置記法 まずは単純な式だけを考える 括弧はなし すべての演算子の優先順位が同じ すべての演算子は左結合性 加減算演算子(+,-)のみと仮定 2 + 3 – 4 + 5 parse中の木の状態を保持する変数が あればよい + 4 + 2 2007年度 早稲田大学 CS学科 プログラミング言語論 5 3 式のparse: 中置記法 (cont’d) 少し複雑な式を考える 括弧はなし 演算子の優先順位は2種類 すべての演算子は左結合性 加減算演算子(+,-)と乗除算演算子(*,/)と仮定 2 + 3 * 4 - 5 parse中の木の状態を保持する変数と 5 乗除算演算子による木を保持する変数 + の2つがあればよい * 2 3 2007年度 早稲田大学 CS学科 プログラミング言語論 4 式のparse: 中置記法 (cont’d) フルスペックの式を考える 括弧はあり 演算子の優先順位は2種類 すべての演算子は左結合性 2 * ( 3 / ( 4 - 5 ) ) parse中の木の状態を保持する変数と 乗除算演算子による木を保持する変数 * の2つがあればよい / 開き括弧があったら、対応する閉じ 2 括弧までを部分トークン列として切り出し 3 て、再帰的に処理する 4 2007年度 早稲田大学 CS学科 プログラミング言語論 5 式の評価 / 命令列への変換 式の評価、もしくは、式から命令列への変換を 考える 評価/変換のためには、「まずどの演算をやっ て、次にどの演算をやるか」という評価順序/ 実行順序が決定されている必要がある 抽象構文木が作成されていて、かつ、評価戦 略が決まっていれば、評価順序/実行順序は 決定される、ように思える。が、しかし… 2007年度 早稲田大学 CS学科 プログラミング言語論 評価順序/実行順序 中置記法による以下の式 ( 2 + 3 ) * 6 から、右下の抽象構文木が作成される 評価戦略がCall-by-Valueのようなstrict evaluationならば、最内評価なので、 “2 + 3” の 演算の後で、(その評価結果をrとして) “r * 6” の 演算の順序になることが決定される * + 2 6 3 2007年度 早稲田大学 CS学科 プログラミング言語論 評価順序/実行順序 では、以下の式はどうか ( 2 + 3 ) * ( 7 – 1 ) 最内評価だと、 “2 + 3” と “7 - 1” の演算の後で、 (評価結果をr,sとして) “* r s” の演算の順になる しかし、 “2 + 3” と “7 - 1” のどちらが先になるか (つまり、 “*” の左右どちらの引数を先に評価する か)は、評価戦略、優先順位、結合性では決まらない * その言語の仕様で、評価順序が 定義されている必要がある + 2 3 2007年度 早稲田大学 CS学科 プログラミング言語論 7 1 演算子/関数の引数の評価順序 C/C++の言語仕様は演算子の引数の評価順序を 定めていない 演算子の引数だけでなく、関数の引数についても、評価順 序は言語仕様で決められていない Javaでは、(演算子/関数ともに)左側の引数(左辺 項)から先に評価することが言語仕様に明確に定義さ れている つまり、評価順序がどのようになるかは、言語仕様の 問題であり、式の表記法とは無関係 中置記法だから評価順序を決める必要があるというわけで はなく、前置記法や後置記法であったとしても評価順序を 決める必要がある 2007年度 早稲田大学 CS学科 プログラミング言語論 C/C++における引数の評価順序 C/C++の言語仕様では、演算子/関数の引数の評 価順序は決められていない 処理系依存 左側の引数(左辺項)を先に評価する処理系も、右側の引 数(右辺項)を先に評価する処理系も、ともに言語仕様を満 たす 例外として、以下は左辺項から評価されることが決められ ている 論理演算子 “&&”, “||” 条件演算子 “?:” カンマ演算子 “,” 2007年度 早稲田大学 CS学科 プログラミング言語論 引数の評価順序と副作用 評価順序が処理系依存であることが問題 になるのは、以下の条件を満たす式が書 かれた場合 ある演算子の引数として、ある変数に対し て副作用を及ぼす項が与えられて、かつ、 その演算子の他の引数にその変数を参照 する項が与えられた時 2007年度 早稲田大学 CS学科 プログラミング言語論 引数の評価順序と副作用: 例 たとえば、以下のCプログラムを考える int m = 10; int n = m * m++; このCプログラムは、乗算演算子 “*” の引数として、左辺 項に “m”、右辺項に “m++” がそれぞれ与えられている Cの言語仕様において“*”の引数の評価順序は決められ ていない 左辺項から先に評価する処理系だと、nの値は100になる 右辺項から先に評価する処理系だと、nの値は110になる どちらもCの言語仕様に対して整合している 2007年度 早稲田大学 CS学科 プログラミング言語論 引数の評価順序と副作用: 代入文 C/C++では、代入演算子(=, +=など)も演算 子なので、左辺式のLHVの評価と右辺式の RHVの評価のどちらを先にするかも処理系依存 である 2007年度 早稲田大学 CS学科 プログラミング言語論 引数の評価順序と副作用: 代入文 たとえば、以下のCプログラムを考える int a[10] = { 0 }; int i; for (i = 0; i < 5; a[i] = i++); このCプログラムは、代入演算子 “=” の引数として、左辺 項に “a[i]”、右辺項に “i++” がそれぞれ与えられている Cの言語仕様において“=”の引数の評価順序は決められて いない 左辺項から先に評価する処理系だと、配列aの値は {0,1,2,3,4,0,0,0,0,0}になる 右辺項から先に評価する処理系だと、配列aの値は {0,0,1,2,3,4,0,0,0,0}になる どちらもCの言語仕様に対して整合している 2007年度 早稲田大学 CS学科 プログラミング言語論 Cにおける式の評価順序 ANSI/ISOによる標準化C言語(いわゆるC89)以前においては、 実行効率向上のために、数学上の変形規則(結合則などの算術 規則)が満たされるなら評価順序を変更することが許されていた つまり、以下の式 x * y * z は、乗算演算子 “*” が左結合であるため、 ( x * y ) * z と同じだが、数学的には、以下の結合則が成り立つ ( x * y ) * z = x * ( y * z ) よって、コンパイラは x * ( y * z ) の方が実行効率が上がると判断できるなら、そのように式を変形 してもよい C89以降では許されていない 2007年度 早稲田大学 CS学科 プログラミング言語論 後置記法による式の評価 これまで述べたように、式の評価には、評価順序、つ まり「どこから計算するか」を決定する必要があり、そ のためには、以下の情報が必要になる 抽象構文木 (もしくは、それに相当する情報) 評価戦略 演算子/関数の引数の評価順序 後置記法による式は、わざわざ構文解析して抽象構 文木を作成しなくても、スタックマシンを使って評価す ることができる 2007年度 早稲田大学 CS学科 プログラミング言語論 スタックマシン (stack machine) スタックをメモリとして持つ計算機(もしくは計 算モデル) 実際のハードウェアとしてのマシンを指すこともあ るし、また、「フォン・ノイマン・アーキテクチャ」型計 算機上にソフトウェアで実現(シミュレート)したもの (仮想スタックマシン)を指すこともある スタックへのデータの出し入れ(push,pop操 作)と、スタック中のデータを用いた演算・ス タック操作の組み合わせで動作する 2007年度 早稲田大学 CS学科 プログラミング言語論 スタックマシンによる算術演算式の評価 トークン列から1つずつトークンを順に取り出し、ス タックを用いて演算する トークンが数値および変数の場合は、そのままスタッ クのtopに積む トークンが演算子の場合は、そのarityの数だけス タックから要素を取り出し、演算子を適用して評価結 果を求めて、それをスタックのtopに積む strict evaluation、かつ、左から評価、を仮定している すべてのトークンの処理が終わったときのスタックの 状態が、その式全体の演算結果になる 算術演算式の場合は、スタックに1つだけ要素が入った状 態になり、その要素が評価結果になる 2007年度 早稲田大学 CS学科 プログラミング言語論 スタックマシンによる式の評価の例 以下の後置記法による算術演算式を評価す る 2 3 + 6 * 2 3 2 3 2 + 6 5 2007年度 早稲田大学 CS学科 プログラミング言語論 6 5 * 30 スタックマシンの利点 以下は基本的に、ソフトウェアによる仮想ス タックマシンを想定している 処理系をコンパクトに作ることができる 組み込み装置など、メモリに制約がある機械に搭 載しやすい スタック操作を実装するだけなので、異なる アーキテクチャの機械で容易に実装できる 2007年度 早稲田大学 CS学科 プログラミング言語論 後置記法にもとづくプログラミング言語 FORTH Charles (Chuck) H. Mooreにより1968年に開発 さまざまなスタック指向言語を派生 Java VMはFORTHの仮想スタックマシンの仕様をベース にしている (つまり、Java VMも仮想スタックマシン) Intel 80x87 浮動小数点コプロセッサのアーキテクチャは FORTHベース PostScript プリンタ記述言語(Printer Description Language/PDL)としてAdobeにより1984年に開発 Appleのプリンタ(LaserWriter)に採用 PDF (Portable Document Format)のベースになって いる 2007年度 早稲田大学 CS学科 プログラミング言語論 FORTH: SWAP演算子 サンプルプログラム 3 2 4 SWAP – 5 * + 3 2 3 2 4 3 - 2 3 5 2 3 5 2 3 4 * 4 2 3 10 3 2007年度 早稲田大学 CS学科 プログラミング言語論 SWAP 2 4 3 + 13 FORTH: ROT演算子 サンプルプログラム 1 2 3 4 ROT – * + 1 2 1 4 3 2 1 ROT 2 4 3 1 - 2 1 2 3 1 3 * 3 2 1 6 3 2007年度 早稲田大学 CS学科 プログラミング言語論 4 4 3 2 1 + 9 FORTH: DUP演算子 サンプルプログラム 2 DUP * 3 DUP * + 2 DUP 2 3 4 DUP 3 3 4 * 2 2 9 4 * 3 4 + 13 2007年度 早稲田大学 CS学科 プログラミング言語論 3 4 PostScript サンプルプログラム 出力結果 Sa mp le /Times-Roman findfont 200 scalefont setfont 100 100 moveto 60 rotate (Sample) show showpage 2007年度 早稲田大学 CS学科 プログラミング言語論