2019年10月6日
[ 前の資料 | 講義ホームページ・トップ ]
2019年度用に改訂予定
プログラミング言語の仕様は,なんとなくプログラムを書いている間はわざわざ目を通す機会はあまりないが,その言語についての正確な知識を得るためには有益である.その意味で言語仕様は辞書のようなものである.1 ただし,コンパイラを作る者にとっては,言語仕様を読む技能は必要不可欠といえる.言語仕様は大きくわけて,次の2つのことが書いてある.
これに加えて多くの言語仕様では,各処理系が提供すべき標準ライブラリについての記述が加えられていることも多い.この章では,いくつかの言語の仕様を具体的に見て,特に言語の構文についての記述を概観していく.
プログラミング言語の構文論は多くの現代的な言語の場合, 字句文法(lexical grammar) と 構文文法(syntactic grammar) にわけて与えられる.字句構造は,どういった文字の並びがその言語の「単語」になりうるか(この「単語」を トークン(token) ということがある)を与えているもので,構文構造は,どういったトークンの並びがプログラムたりうるかを規定している.この二段構えの構成はコンパイラの構造と密接に関連している.コンパイラは通常,入力ファイルを,字句解析(lexical analysis) 処理によってトークン列に変換し,それを, 構文解析(syntactic analysis) 処理によって抽象構文木と呼ばれるプログラムの構成を表現するデータに変換する.(その後,様々な処理を経てターゲットプログラムが出力されるが,それはこの講義の範囲ではない.)また,どういった文字列がプログラムたりうるか,という意味では型に関する制約も構文論の一部といえるが,通常のコンパイラの実装では,構文解析と型検査は別フェーズの処理であることもあり,構文に関する仕様とは見做されないことも多い.
字句文法や構文文法を定義する際には通常,BNF (Backus-Naur form) またはその拡張が使われる.これは,本質的には文脈自由文法の生成規則であるが,生成規則の右辺に,選択を表す |
,グループ化をするための括弧 ((...)
),一回以上の繰り返しを表す +
,0回以上の繰り返しを表す *
,0または1回の出現(オプション)を表す ?
や [...]
などを使う.例えば,以下は OCaml における識別子を定義する BNF である.(OCaml では \(\{\}\) で0回以上の繰り返しを, \(\{\}^+\) で1回以上の繰り返しを表す,という(やや標準的ではない?)記法を採用している.)
\(ident ::= ( letter \mid\)
_
\() \{ letter \mid \texttt{0} \ldots \texttt{9} \mid\)_
\(\mid\ \texttt{'} \}\) \(letter ::= \texttt{A} \ldots \texttt{Z} \mid \texttt{a} \ldots \texttt{z}\)
これで識別子が,英文字か_
で始まり,英数字か_
か'
が続く文字列であることがわかる.
このレベルでは,以下のことが定義される.
//
のように,ある記号から行末までをコメントとして扱ういわゆる一行コメントと,C言語やJava の /* ... */
,OCaml の (* ... *)
のように開始記号と終端記号の間を全てコメントとして扱うブロックコメントがある.ブロックコメント中に再び開始記号が現れた時の扱い(開始記号と同じ数の終端記号が現れるまでコメントとして扱うかどうか)は言語によって異なるので注意した方がよい.
また,文法とは別に,長さ,大文字小文字の使い分け,などについての慣習・ローカルルールが 命名規則(naming convention) として設けられていることも多い.識別子は英語などの自然言語から由来することも多いので,英語(のように空白が単語の区切りになる言語)で複数の単語にわたるフレーズを識別子とする場合,単語をアンダースコア(_
)でつなぐか,ハイフン(-
)でつなぐか,単語の先頭を大文字にして(空白なしで)つなぐか,などが決められていることも多い.それぞれスネークケース(snake_case
),チェインケース(chain-case
),キャメルケース(camelCase
)などと呼ばれる.
==
などといった記号列でトークンになるものを定める.
トークンの区切り方に複数の可能性がある場合,多くの場合,(ファイルの先頭から見て)できるだけ長く文字列をとってトークンになるように区切る,という方法が採用される.例えば C 言語では &&
も &
も演算子だが,&&
を &
がふたつ並んだものではなく,&&
でひとつのトークンとして扱う.&&&
であれば,(どうせ構文エラーだが) &&
と &
が並んだものとして扱うだろう.
既に述べたように予約語は識別子として使えない例外的な文字の並びである.例えば Java, C言語, OCaml では for
は予約語であり,変数の名前として使うことができない.予約語と関連する用語として キーワード(keyword) がある.これは,言語の構文を表すための特別な文字列で,これらの言語で for
はキーワードでもある.多くの言語で予約語とキーワードはほとんど一致するが,いくつか例外もある.
goto
構文があるわけではないが識別子として使えない.上の意味では,予約語ではあるがキーワードではないということになるのだが,Java 言語仕様の用語では,ここでいう予約語も全て「キーワード」と呼んでいる.Java言語仕様3章 Lexical Structureを見てみよう.
OCaml reference manual 6.1節 Lexical conventionを見てみよう.
言語仕様ドラフト N1256の 6.4 Lexical elements を見てみよう.
言語仕様第五版R5RS の Chapter 2 Lexical Conventions と Section 7.1.1 Lexical structure を見てみよう.
ここで与えられるのは,どういったトークンの列が,式,文,関数定義などといったプログラムの構成要素となるかである.また,この段階で,構文・演算子の結合順位---例えば C 言語での *x++
という表現が,
x
にポインタ参照 (*
演算子) を施した先のオブジェクトの中を1増やす (++
演算子),のではなく,x
を1増やして(++
演算子)から,(増やす前の) x
の指す先を参照する(*
演算子) 表現であること---が決定される.+
など.)
if
相当の〈式1〉?
〈式2〉:
〈式3〉という構文があり,三項演算子(ternary operator)としばしば呼ばれるが,これはミックスフィックス演算子の一例である.
C言語の *
や &
のように,ひとつの記号が前置演算子になったり中置演算子になる場合もある.
先程の *x++
のような,ひとつの式(x
)の前後に演算子が置かれた場合に,どちらを優先させて結合するかを決めるのが演算子の 優先順位(precedence) または 結合の強さ である.強いものほど優先させて結合する.この例であれば「後置演算子++
は前置演算子 *
よりも結合が強い」という.
ここまで,演算子は何らかの記号・文字列であることを暗黙のうちに仮定していて話を進めてきたが,言語によっては,専用のトークンが存在しない演算(子)もありえる.典型例が,ふたつの式を並置する OCaml の関数適用(f x
など)である.この場合でも,f x + 1
が f (x + 1)
のことなのか,(f x) + 1
のことなのかを決定するために優先順位を定める必要がある.
複数の演算子が等しい優先順位を持つこともある.同じ(優先順位の)中置演算子が,ある式の前後に置かれた場合に,どちらを優先するかを決定するのが, 結合性(associativity) であり, 右結合(right associative) と 左結合(left associative) のふたつがある.右結合の場合 〈式1〉〈演算子1〉〈式2〉〈演算子2〉〈式3〉は〈式1〉〈演算子1〉(〈式2〉〈演算子2〉〈式3〉)と解釈され,左結合の場合 〈式1〉〈演算子1〉〈式2〉〈演算子2〉〈式3〉は(〈式1〉〈演算子1〉〈式2〉)〈演算子2〉〈式3〉と解釈される.例えば +
と -
は(C言語でも Java でも OCaml でも)左結合演算子で,1 + 2 - 4 + 5
は ((1 + 2) - 4) + 5
のことである.
いくつかの言語では,プログラマが新しい演算子を優先度・結合性とともに定義することができる.
以降のケーススタディでは,式の構文がどのように指定されているかを中心に見ていくが,優先順位や結合性の指定の仕方の違いに注目しよう.また,仕様では,構文と同時に,意味(動作)も織り交ぜて記述されていることが多い.
OCaml reference manual 6.7節 Expressionsを見てみよう.
OCaml の場合,全ての種類の式が,ひとつの非終端記号 (expr) に関する生成規則で記述されており,優先順位や結合性は別途表になっている.また,OCaml でも新しい演算子を定義することができるが,優先度・結合性は演算子の先頭の記号の種類で最初から決まっていて,プログラマが決められない.融通が利かないようにも思えるが,優先度をプログラマが決められるようにすると,同じ字面の式でもプログラム毎に式の意味が変わったりするので,それはそれで紛らわしい.
Java言語仕様15章 Expressionsを見てみよう.Java では,沢山の非終端記号を導入して生成規則を工夫することで優先順位や結合性を表現している.
以下は,乗算・除算と加算・減算についての文法規則の抜粋である.UnaryExpression は別に定義されている前置演算子式のための非終端記号の名前である.ここから,*
, /
, %
が +
, -
よりも優先度が高く,左結合になっていることが(よく考えると)読み取れる.
MultiplicativeExpression:
UnaryExpression
MultiplicativeExpression * UnaryExpression
MultiplicativeExpression / UnaryExpression
MultiplicativeExpression % UnaryExpression
AdditiveExpression:
MultiplicativeExpression
AdditiveExpression + MultiplicativeExpression
AdditiveExpression - MultiplicativeExpression
言語仕様ドラフト N1256の 6.5 Expressions を見てみよう.
C言語でも,優先順位や結合性は,沢山の非終端記号を導入して生成規則を工夫することで与えている.
言語仕様第五版R5RS の Chapter 4 Expressions と Section 7.1.2〜7.1.6 を見てみよう.
Scheme の場合は,演算子の優先度などの概念がそもそもない.構文毎に syntax (プリミティブ, 4.1節), library-syntax (プリミティブではなく,マクロと呼ばれる機能によって別の構文に展開されて処理される構文で,derived expression とも呼ばれる.4.2節) に分かれている.
間違ったプログラム(そもそもプログラムでないような入力も含めて)についてできるだけ漏れなく挙げ,その場合に何が起こるべきかを記述するのも言語仕様の重要な役割である.エラーにも,以下にあげるようないくつかの種類がある.
大きくわけて,プログラムを言語処理系に与えてから実行が始まる前に検出されるエラー,いわゆるコンパイル時エラー2と,実行の最中に検出されるエラー(実行時エラー)に大別される.
字句解析と構文解析の段階で発生する静的エラーである.言語処理系について学ぶとわかるが,大抵のプログラミング言語の構文解析は,前から順に読んでいき,行き詰まったら即座に(その先は読まずに)止まってしまうアルゴリズムで作られていることもあり,エラーメッセージは不親切であることが多い(つまり,「ここで期待する単語・記号が来なかった」程度しか教えてくれない.)
(静的)型エラー ((static) type error) は,静的型付き言語で,呼び出す関数が要求する引数の型と実引数の型があわない,など,型についての制約を満たせないことに起因する静的エラーである.
実行時エラーにも様々な原因があるが,メモリが足りなくなったなどのいくつかの特殊な場合を除くと,ほとんどの原因は,以下のような,ある操作を行おうとしたが,その対象となるデータが想定外のものであった,というものである.
これらは,ある意味でデータの分類に関するエラーで,実行時型エラーと呼ばれることも多い.Java, OCaml などの実行前に型検査がある言語では,型検査に通ったプログラムについては,こういった値の分類についての実行時型エラーは発生しないことが理論的に保証されている(ことになっている).このような,「一部の実行時エラーを実行前に全て検知できる型システムを持つ」言語を 強く型付けされる言語(strongly typed language) という.C言語も実行前に型検査を行うが,検査がザルで何かのエラーが防げる保証があるわけではない.
強く型付けされる言語でも,
null
ポインタだった.といった,その言語の型の分類能力を越えたところで発生するエラーを防ぐことはできない.強く型付けされる言語は,バグを仕込まないための強力なサポートをしてくれるが,型の表現力に相対的な能力しかないことには注意したい.(型の表現力をあげてより多くのエラーを防ごう,という試みはプログラミング言語研究の一分野である.)
実行時エラーが発生した場合に,実際に何が起こるかは言語によってまちまちである.モダンな言語では例外機構の枠内で記述されている場合も多いが,C言語では以下に述べる未定義動作(undefined behavior)として定義している場合も多い.4 また,同じ原因のエラーでも言語によって対処がまちまちなこともある.例えば整数演算のオーバーフローなどは C では undefined だが,OCaml では全く無視される.
通常,「動作が未定義」とは言語仕様にぬけがあって,プログラムがどのように実行されるかが不明な場合をさすが,一部の言語(C言語が代表)では, 未定義動作(undefined behavior) という用語をわざわざ導入している.C言語における未定義動作の定義は何でもあり—anything goes—であり,無理矢理実行を続けてもよい(その後どうなるかは,神,もとい,OS・ハードウェアのみぞ知る)し,実行時エラーとして実行を中断してもよい.5
未定義動作がどういう場合に発生するかわかるくらいなら,きちんと実行を中断させるようにしろ,というのは尤もな指摘だが,エラーを検知するためのコストを払いたくない場合もある.例えば配列アクセスで添字が大きすぎる場合,C言語では未定義動作だが,検知するためには配列にはそのサイズ情報を付加し,読み書きの際には添字チェックを行う必要がある.最適化である程度省くことができるかもしれないが,そのような余計なコストがかかる可能性があるくらいなら,効率を重視して無視(これも未定義動作のうちである)してしまえ,というのがC言語系の言語の設計思想である.ここはトレードオフでもあるが,C言語がよく使われていた時代に比べ,未定義動作のリスクも大きくなってきている.特に不正な領域を読み書きできてしまうことによって発生するセキュリティの問題は深刻である.(効率はある程度諦めて実行時にエラーを検出しよう,という研究や,型システムを工夫して未定義動作が発生するのを未然に防ごう,という研究が1990年代後半から盛んになった.Rust などの新しい低水準言語は,そういった研究の賜物である.)
未定義動作と紛らわしいのが 未指定動作(unspecified behavior) である.これは,いくつかの可能性があるがどれを選ぶかは処理系次第,というもので,例えば C, OCaml, Scheme では,関数呼び出しで実引数が複数ある場合に,それらの評価順序は未指定動作となっていて,どの順番で実行されるかわからないので,特定の評価順序に依存したプログラムは書くべきではない.
ちなみに,Java はどのプラットフォームでも同じように動作することを目指して設計されているので,基本的に未定義動作や未指定動作は(意図しない仕様の記述漏れを除いて)存在しない.
Java は言語仕様 Chapter 1 のわりと早いうちに「コンパイル時エラー」についての記述がある.実行時のエラーは例外機構に組込まれており Chapter 11 に記述されている.
OCaml はエラーについてのまとまった記述はあまりない.
C 言語については 3.4.3 undefined behavior, 3.4.4 unspecified behavior に定義があるので,一度読んでみるとよいだろう.
Scheme についても R5RS の 1.3.2 Error situations and unspecified behavior という節がある.
[ 前の資料 | 講義ホームページ・トップ ]
初心者が調べるのに使ってみても,説明に使われている言葉の意味がわからなくて結局なんだかわからないという点も含めて.↩
コンパイラを使う場合は翻訳段階で発生するのでコンパイル時エラーでよいが,実行にコンパイラを使わない場合にも発生するので他の用語がほしいところだ.↩
言語によっては,数値への自動変換を試みて,それが成功すればエラーとはならない(もしくは,どんな値でも数値に変換できてしまう)ものもある.↩
「未定義として定義」とはこれいかに.↩
極端な場合,プログラムを実行したユーザのファイルを全て削除されたとしても文句はいえない.(そんなCコンパイラしかなかったら,とても気をつけてプログラムを書くでしょうね.)↩
Copyright 五十嵐 淳, 2016, 2017, 2018, 2019