2016年度「プログラミング言語」配布資料 (8)

五十嵐 淳 (京都大学大学院情報学研究科 通信情報システム専攻)

2016年12月11日

[ 前の資料 | 講義ホームページ・トップ | 次の資料 ]

under construction2017年版に向け改訂中

プログラミング言語の仕様は,なんとなくプログラムを書いている間はわざわざ目を通す機会はあまりないが,その言語についての正確な知識を得るためには有益である.その意味で言語仕様は辞書のようなものである.1 コンパイラを作る者にとっては,言語仕様を読む技能は必要不可欠といえる.言語仕様は大きくわけて,次の2つのことが書いてある.

  • どんな文字列がその言語のプログラムたりえるか,という 構文論(syntax) について
  • プログラムがどんな動作をするか,という 意味論(semantics) について

これに加えて多くの言語仕様では,標準ライブラリについての記述が加えられていることも多い.この章では,いくつかの言語の仕様を具体的に見て,特に言語の構文についての記述を概観していく.

プログラミング言語の構文論

プログラミング言語の構文論は多くの現代的な言語の場合, 字句文法(lexical grammar)構文文法(syntactic grammar) にわけて与えられる.字句構造は,どういった文字の並びがその言語の「単語」になりうるか(この「単語」をトークンということがある)を与えているもので,構文構造は,どういったトークンの並びがプログラムたりうるかを規定している.この二段構えの構成はコンパイラの構造と密接に関連している.コンパイラは通常,入力ファイルを,字句解析(lexical analysis) 処理によってトークン列に変換し,それを, 構文解析(syntactic analysis) 処理によって抽象構文木と呼ばれるプログラムの構成を表現するデータに変換する.(その後,様々な処理を経てターゲットプログラムが出力されるが,それはこの講義の範囲ではない.)また,どういった文字列がプログラムたりうるか,という意味では型に関する制約も構文論の一部といえるが,通常のコンパイラの実装では,構文解析と型検査は別フェーズの処理なこともあり,構文に関する仕様とは見做されないことも多い.

字句文法や構文文法を定義する際には通常,BNF (Backus-Naur form) またはその拡張が使われる.これは,本質的には文脈自由文法の生成規則であるが,生成規則の右辺に,選択を表す |,グループ化をするための括弧 ((...)),一回以上の繰り返しを表す +,0回以上の繰り返しを表す *,0または1回の出現(オプション)を表す ?[...]などを使う.例えば,以下は OCaml における識別子を定義する BNF である.(OCaml では \(\{\}\) で0回以上の繰り返しを, \(\{\}^+\) で1回以上の繰り返しを表す,という(やや標準的ではない?)記法を採用している.)

\(ident ::= ( letter \mid \texttt{_} ) \{ letter \mid \texttt{0} \ldots \texttt{9} \mid \texttt{_} \mid\ \texttt{'} \}\)
\(letter ::= \texttt{A} \ldots \texttt{Z} \mid \texttt{a} \ldots \texttt{z}\)

これで識別子が,英文字か_で始まり,英数字か_'が続く文字列であることがわかる.

字句文法

このレベルでは,以下のことが定義される.

空白文字
空白文字(blank characters)は,トークン間の区切りを明示する役割は果たすが,構文解析の段階では無視する(トークンに表れない)ことが多い.この講義で扱った言語では,スペース,タブ,改行文字は一括して空白文字として扱われ全て構文解析の段階では無視されるので,改行をスペースに置き換えたり,その逆をしてもプログラムとしては全く同じく扱われる.(字句・構文解析技術が成熟していなかった頃の)古いプログラミング言語では,行が特殊な意味を持つものも多い.また,逆に最近の言語(Haskell, Pythonなど)では,ひと固まりの処理(C言語, Java での {} で表されるブロック)などを表すために,括弧などの記号ではなく,字下げ(行頭からの空白の)量を利用するものもあり,そういった言語ではスペースと改行は厳密に区別される.また,エディタ上では何も表示されないのに空白文字ではない,という文字(典型的にはいわゆる全角スペース)もありうるので注意が必要である.
コメント
コメントも通常,空白と同じく構文解析の段階では無視される.コメントには,C言語や Java の // のように,ある記号から行末までをコメントとして扱ういわゆる一行コメントと,C言語やJava の /* ... */,OCaml の (* ... *) のように開始記号と終端記号の間を全てコメントとして扱うブロックコメントがある.ブロックコメント中に再び開始記号が現れた時の扱い(開始記号と同じ数の終端記号が現れるまでコメントとして扱うかどうか)は言語によって異なるので注意した方がよい.
識別子と予約語
識別子(identifier) はもの(変数や型,クラス,コンストラクタ)の名前として使える文字列である.多くの言語では,識別子で使える文字は英数字が中心だが,それ以外の記号についてはわりとまちまちである.また一部の文字列は 予約語(reserved word) といって,識別子として使うことはできない.

また,文法とは別に,長さ,大文字小文字の使い分け,などについての慣習・ローカルルールが 命名規則(naming convention) として設けられていることも多い.識別子は英語などの自然言語から由来することも多いので,英語(のように空白が単語の区切りになる言語)で複数の単語にわたるフレーズを識別子とする場合,単語をアンダースコア(_)でつなぐか,ハイフン(-)でつなぐか,単語の先頭を大文字にするかなどのを決めることも多く,それぞれスネークケース,チェインケース,キャメルケースなどと呼ばれる.

各種定数
整数,浮動小数点数,文字,文字列などの定数の表記を定める.これらは種類毎に整数定数のトークン,浮動小数点数のトークン,文字定数のトークン,文字列定数のトークンとなる.
その他記号
その他,括弧や == などといった記号列でトークンになるものを定める.

トークンの区切り方に複数の可能性がある場合,多くの場合,(ファイルの先頭から見て)できるだけ長く文字列をとってトークンになるように区切る,という方法が採用される.例えば C 言語では &&& も演算子だが,&&& がふたつ並んだものではなく,&& でひとつのトークンとして扱う.&&& であれば,(どうせ構文エラーだが) &&& が並んだものとして扱うだろう.

予約語とキーワード

既に述べたように予約語は識別子として使えない例外的な文字の並びである.例えば Java, C言語, OCaml では for は予約語であり,変数の名前として使うことができない.予約語と関連する用語として キーワード(keyword) がある.これは,言語の構文を表すための特別な文字列で,これらの言語で for はキーワードでもある.多くの言語で予約語とキーワードはほとんど一致するが,いくつか例外もある.

  • Java では const, goto は予約語だが,特に goto 構文があるわけでもなく,キーワードではない.未来の言語拡張でキーワードになる事態に備えて,まさに「予約」している.
  • FORTRAN のようにキーワードが識別子として使える言語もある.キーワードが識別子になると通常構文解析がややこしくなるので,現代的な言語では避けられる.

ケーススタディ: Java

Java言語仕様3章 Lexical Structureを見てみよう.

ケーススタディ: OCaml

OCaml reference manual 6.1節 Lexical conventionを見てみよう.

ケーススタディ: C

言語仕様ドラフト N1256の 6.4 Lexical elements を見てみよう.

構文文法

ここで与えられるのは,どういったトークンの列が,式,文,関数定義などといったプログラムの構成要素となるかである.また,この段階で,構文・演算子の結合順位---例えば C 言語での *x++ という表現が,

  • 変数 x にポインタ参照 (*演算子) を施した先のオブジェクトの中を1増やす (++演算子),のではなく,
  • 変数 x を1増やして(++演算子)から,(増やす前の) x の指す先を参照する(*演算子)
    表現であること---が決定される.
前置演算子(prefix operator)
式の前に置いて,より大きな式を構成するような演算子.
中置演算子(infix operator)
ふたつの式の間に置いて,より大きな式を構成するような演算子.(+ など.)
後置演算子(postfix operator)
式の後に置いて,より大きな式を構成するような演算子.
ミックスフィックス演算子(mixfix operator)
ふたつ以上の部分からなる演算子.Java や C では〈式1〉の値が真なら〈式2〉の値,偽なら〈式3〉の値になる,というOCamlの if 相当の〈式1〉?〈式2〉:〈式3〉という構文があり,三項演算子(ternary operatorとしばしば呼ばれるが,これはミックスフィックス演算子の一例である.

C言語の *& のように,ひとつの記号が前置演算子になったり中置演算子になる場合もある.

先程の *x++ のような,ひとつの式(x)の前後に演算子が置かれた場合に,どちらを優先させて結合するかを決めるのが演算子の 優先順位(precedence) または 結合の強さ である.強いものほど優先させて結合する.この例であれば「後置演算子++は前置演算子 * よりも結合が強い」という.

ここまで,演算子は何らかの記号・文字列であることを暗黙のうちに仮定していて話を進めてきたが,言語によっては,専用のトークンが存在しない演算(子)もありえる.典型例が,ふたつの式を並置する OCaml の関数適用(f x など)である.この場合でも,f x + 1f (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

OCaml reference manual 6.7節 Expressionsを見てみよう.

OCaml の場合,全ての種類の式が,ひとつの非終端記号 (expr) に関する生成規則で記述されており,優先順位や結合性は別途表になっている.また,OCaml でも新しい演算子を定義することができるが,優先度・結合性は演算子の先頭の記号の種類で最初から決まっていて,プログラマが決められない.融通が利かないようにも思えるが,優先度をプログラマが決められるようにすると,同じ字面の式でもプログラム毎に式の意味が変わったりするので,それはそれで紛らわしい.

ケーススタディ: Java

Java言語仕様15章 Expressionsを見てみよう.Java では,優先順位や結合性は,沢山の非終端記号を導入して生成規則を工夫することで与えている.

以下は,乗算・除算と加算・減算についての文法規則の抜粋である.UnaryExpression は別に定義されている前置演算子式のための非終端記号の名前である.ここから,*, /, %+, - よりも優先度が高く,左結合になっていることが(よく考えると)読み取れる.

MultiplicativeExpression:
  UnaryExpression
  MultiplicativeExpression * UnaryExpression
  MultiplicativeExpression / UnaryExpression
  MultiplicativeExpression % UnaryExpression
  
AdditiveExpression:
  MultiplicativeExpression
  AdditiveExpression + MultiplicativeExpression
  AdditiveExpression - MultiplicativeExpression

ケーススタディ: C

言語仕様ドラフト N1256の 6.5 Expressions を見てみよう.

C言語でも,優先順位や結合性は,沢山の非終端記号を導入して生成規則を工夫することで与えている.

エラー

コンパイル時エラー(構文エラー,型エラー),コンパイル時警告,実行時エラー(例外,未定義動作),未指定動作


[ 前の資料 | 講義ホームページ・トップ | 次の資料 ]


  1. 初心者が調べるのに使ってみても,説明に使われている言葉の意味がわからなくて結局なんだかわからないという点も含めて.


Copyright 五十嵐 淳, 2016, 2017