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

導入

教科書3章

講義1回分

前提#

プログラミング言語の基本構成要素として文（statement）と式（expression）がある．文は手続きを表す要素であり，それ単独で完結できる．C言語においては;や}を末尾に持つ要素が文である．式は四則演算などの評価結果となる値を持つ要素である．代入文の右辺の要素は全て式と考えてよい．文と式は入れ子構造を取る．

n = i * 2;
if (n > 5) return 1;
return 0;

1. 代入文の左辺nは式ではない． その理由は後述する例題2を確認せよ．

文と式の違いをよく理解しておくこと．

文脈自由文法#

あらゆるプログラミング言語は厳密な文法規則を持つ．これを構文（syntax）と呼ぶ．プログラミング言語の構文は文脈自由文法（context-free grammer，CF文法）で表現される．

例えば，加算演算子+と乗算演算子*を用いた式（3+5*4等）の構文規則はCF文法を用いて次のように定義できる．

1. \(num\)は任意の数字列（3や16等）を表すラベルと解釈せよ． 単純化のため\(num\)という表現を用いる．

式\(E\)は次のような定義と同等の意味を持つ．

1. numは式である（num）
2. \(x\)と\(y\)が式であれば\(x\)+\(y\)，\(x\)*\(y\)，(\(x\))も式である（num+num (num)等）
3. 上記の1と2で与えられたものだけが式である（num-num +num num++は式ではない）

先の式\(E\)の定義\(E \ra E+E \ |\ E*E \ |\ num \ |\ (E)\)は生成規則（production rule）と呼ばれる．終端記号の列，すなわち具体的なプログラム文（num+num等）を生成するための規則である．生成規則を適用して具体的な文に置き換える操作を導出（derivation）と呼び，\(\RA\)で表される．先のクイズの(num+num)*numは以下のように導出される．

導出に成功したことから(num+num)*numは式であるといえる．

文脈自由文法の形式的定義#

CF文法の形式的な定義について考える．CF文法は\(G = \{N, \mathit{\Sigma}, P, S\}\)の4つ組で定義される．先の式の生成規則\(E\)を持つCF文法\(G_0\)は以下のように定義される．

集合\(\Gamma\)に対して\(\Gamma^*\)とは，\(\Gamma\)の要素を0個以上連ねて得られる要素列の集合である．例えば\(\Gamma = \{a, b\}\)のとき，\(\Gamma^*\)はaやb，abaaabb，などを含む．厳密には\(\Gamma^*={\{\varepsilon\} \cup \Gamma \cup \Gamma^2 \cup \cdots = \{\varepsilon\} \cup (\cup_{i=1}^\infty \Gamma^i)}\)である．\(\varepsilon\)は空語である．

生成規則が\(A \ra \varepsilon\)のとき，これを\(\varepsilon\)遷移と呼ぶ．\(\varepsilon\)は空語であり，\(\varepsilon x = x = x \varepsilon\)が成立する．例えば，終端記号aを0個か1個だけ取る生成規則は\(A \ra a|\varepsilon\)のように記述される．

任意の記号列\(\alpha, \beta, \gamma \in (N \cup \mathit{\Sigma})^*\)と生成規則\(A \ra \alpha\)に対して，導出とは\(\beta A \gamma \RA \beta \alpha \gamma\)と書く．さらに複数回の導出\(\alpha_1 \RA \alpha_2,~ \alpha_2 \RA \alpha_3,~ \cdots,~ \alpha_n \RA \alpha_{n+1}\)に対しては，\(\alpha_1 \RA^* \alpha_{n+1}\)と省略できる．これを\(n\)回の導出，あるいは\(n\)回の生成規則の適用と呼ぶ．

文法\(G\)が生成する終端記号の集合（すなわち言語）を\(L(G)\)と書く．\(L(G)\)はCF言語と呼ばれる．

例題1#

次のCF文法\(G_1\)は文字aとbから構成される文を生成する．

\(G_1\)が生成する具体的な終端記号列はabやaaabbbなどである．aとbの出現数は常に同じで，常にaが先に出現する(1)．

1. \(L(G_1) = \{ a^n b^n|n \geq 1\) }

例題2#

次のCF文法\(G_2\)はC言語の一部の文を生成する．

\(G_2\)が生成する終端記号列の一例を以下に示す．C言語の正しい構文規則に従っていることを確認せよ．

id = num;
id = num + num;
if (id + num > id) {
    id = id + num;
}
id = id;

CF言語\(L(G_2)\)はC言語と比較すると以下のような違いがある．

• idやnumが抽象化されている
• 比較演算が>のみ，四則演算が+のみである
• forやwhileが存在しない

しかし，ここで重要な点はCF文法によってC言語の一部の構文を定義可能であるということである．実際にC言語の構文やPythonの構文はCF文法を用いて定義されている．

無曖昧な文脈自由文法#

導出列（導出の流れ）は木として表現できる．これを解析木（または導出木や構文木）と呼ぶ．\(G_0\)に対する導出列\(E \RA^* num + num\)は次の解析木となる．視認性のため，非終端記号を青色枠■，終端記号を灰色枠■ で表現している．

%%{init: {'flowchart': {'curve': 'linear', 'nodeSpacing': 10, 'rankSpacing': 30, 'padding': 5}}}%%
graph LR
  classDef tr fill:#f6f6f6,stroke:#c0c0c0;
  e1[E];
  e1 --- e2[E];
  e1 --- plus[#43;]:::tr;
  e1 --- e3[E];
  e2 --- num1[num]:::tr;
  e3 --- num2[num]:::tr;

先のクイズの(num+num)*numの解析木は次のとおり．

%%{init: {'flowchart': {'curve': 'linear', 'nodeSpacing': 10, 'rankSpacing': 30, 'padding': 5}}}%%
graph LR
  classDef tr fill:#f6f6f6,stroke:#c0c0c0;
  e1[E];
  e1 --- e2[E];
  e1 --- times[#42;]:::tr;
  e1 --- e3[E];
  e2 --- lb["("]:::tr;
  e2 --- e4[E];
  e2 --- rb[")"]:::tr;
  e4 --- e5[E];
  e4 --- plus[#43;]:::tr;
  e4 --- e6[E];
  e5 --- num1[num]:::tr;
  e6 --- num2[num]:::tr;
  e3 --- num3[num]:::tr;

\(E\)からnum+num*numを導出する場合，以下2つの解析木が考えられる．導出列，すなわち導出の方法が2つ存在するといえる．

%%{init: {'flowchart': {'curve': 'linear', 'nodeSpacing': 10, 'rankSpacing': 30, 'padding': 5}}}%%
graph LR
  classDef tr fill:#f6f6f6,stroke:#c0c0c0;
  e1[E];
  e1 --- e3[E];
  e1 --- plus[#43;]:::tr;
  e1 --- e2[E];
  e2 --- num2[num]:::tr;
  e2 --- times[#42;]:::tr;
  e2 --- num3[num]:::tr;
  e3 --- num1[num]:::tr;

%%{init: {'flowchart': {'curve': 'linear', 'nodeSpacing': 10, 'rankSpacing': 30, 'padding': 5}}}%%
graph LR
  classDef tr fill:#f6f6f6,stroke:#c0c0c0;
  e1[E];
  e1 --- e2[E];
  e1 --- times[#42;]:::tr;
  e1 --- e3[E];
  e2 --- num2[num]:::tr;
  e2 --- plus[#43;]:::tr;
  e2 --- num3[num]:::tr;
  e3 --- num1[num]:::tr;

左の解析木は*が+より高い優先度であることを示しており，一般的な数学的解釈と一致する．一方，右の解析木では+が優先される．このように1つの終端記号列に対して，2つ以上の解析木が得られるとき，文法は曖昧（ambiguous）であるという．これまで題材に用いてきた\(G_0\)の生成規則\(E \ra E+E \ |\ E*E \ |\ num \ |\ (E)\)は曖昧なCF文法である．

文法が曖昧で多義的な場合，解析の結果が唯一に定まらなくなる．そのため一部の解析（導出）に失敗した際に，別の解析手順を踏む必要が発生してしまう．これは解析（コンパイル）コストの増大につながる．さらに曖昧な箇所が複数ある場合は組み合わせ爆発にもつながる．

プログラミング言語の文法は無曖昧（unambiguous）であることが望ましい(1)．やむを得ず曖昧な文法が採用される場合は，複数の解析木のうちどれを選択するかをあらかじめ定めておく必要がある．

1. 無曖昧な文法のクラスとしてはLR文法やLL文法が存在するが，この講義では扱わない． 3年後期の「言語処理工学A」で取り扱う．

曖昧な文法を等価かつ無曖昧に書き換えられる場合がある．このとき，その文法は本質的に曖昧でないと呼ぶ．文法\(G_0\)は本質的に曖昧ではない．よって無曖昧に書き換え可能である．

例題3#

\(G_0\)に対する等価で無曖昧なCF文法\(G_3\)は以下のように定義される．

\(G_3\)におけるnum+num*numの解析木はただ一つである．

%%{init: {'flowchart': {'curve': 'linear', 'nodeSpacing': 10, 'rankSpacing': 30, 'padding': 5}}}%%
graph LR
  classDef tr fill:#f6f6f6,stroke:#c0c0c0;
  e1[E1]
  e1 --- e2[E1];
  e2 --- e3[E2];
  e3 --- e4[F];
  e4 --- num1[num]:::tr;
  e1 --- plus[#43;]:::tr;
  e1 --- e5[E2];
  e5 --- e6[E2];
  e6 --- e7[F];
  e7 --- num2[num]:::tr;
  e5 --- times[#42;]:::tr;
  e5 --- e8[F];
  e8 --- num3[num]:::tr;

\(G_3\)の生成規則は2つの演算子*と+について次の3つの性質を満たすよう構成されている．

1. *は+より優先度が高い（num+num*numはnum+(num*num)と解釈される）
2. +は左結合的である（num+num+numは(num+num)+numと解釈される）
3. *は左結合的である（num+num+numはnum+(num+num)と解釈される）

優先度（precedence）とは複数種類の演算子が並んでいるときに，どの演算を優先するかを示す性質である．一般的な数学的解釈では*と/は+と-より優先度が高い．C言語をはじめ，多くのプログラミング言語は同様の優先度を採用している．

CF文法では複数の生成規則を組み合わせることで，演算子の優先度を表現する．\(G_3\)では\(E_1 \ra E_1 + E_2 \ |\ E_2\)が+，\(E_2 \ra E_2 * F \ |\ F\)が*の生成規則である．ポイントは\(E_1\)の生成規則の中に\(E_2\)が出現する点である．これにより\(E_2\)の*が木の深い方に配置され，*が+より高い優先度を持つことになる．

結合性（associativity）とは同一の演算子が並んでいるときに，どちらの演算を優先するかを示す性質である．左結合では左の演算が優先される．+と*は左結合でも右結合でも結果は同じだが，-や/は結果が変わる．C言語では四則演算は全て左結合であり，100/2/2は(100/2)/2と解釈される．

\(G_3\)に対して，同一演算子+が並ぶ式num+num+numを与えた場合の解析木は次のとおりである．左結合となっていることを確認せよ．

%%{init: {'flowchart': {'curve': 'linear', 'nodeSpacing': 10, 'rankSpacing': 30, 'padding': 5}}}%%
graph LR
  classDef tr fill:#f6f6f6,stroke:#c0c0c0;
  e1[E1]
  e1 --- e2[E1];
  e1 --- plus1[#43;]:::tr;
  e1 --- t1[E2];
  e2 --- e3[E1];
  e2 --- plus2[#43;]:::tr;
  e2 --- t2[E2];
  e3 --- t3[E2];
  t3 --- f1[F];
  f1 --- num1[num]:::tr
  t2 --- f2[F];
  f2 --- num2[num]:::tr
  t1 --- f3[F];
  f3 --- num3[num]:::tr

生成規則\(E_1 \ra E_1 + E_2\)において，自分自身を再帰的に呼び出す終端記号\(E_1\)が演算子の左側に出現している点が重要である．これにより左側の演算子を木の深い方へ配置する．逆に\(E_1 \ra E_2 + E_1\)のように右側に\(E_1\)があれば右結合的となる．

多くのプログラミング言語の構文は\(G_3\)のような工夫を取り入れることにより，無曖昧なCF文法に近づけている．プログラミング言語の構文定義には数多くの非終端記号が用いられているが，曖昧さ除去のために導入されたものも少なくない．

<additive-expr> ::= <multiplicative-expr>
                  | <additive-expr> + <multiplicative-expr>
                  | <additive-expr> - <multiplicative-expr>

<multiplicative-expr> ::= <cast-expr>
                        | <multiplicative-expr> * <cast-expr>
                        | <multiplicative-expr> / <cast-expr>
                        | <multiplicative-expr> % <cast-expr>

無曖昧な文法規則への変換#

簡単な式（num+num*num等）を題材に，生成規則を無曖昧に変換する方法について述べる．

例題4#

6種類の演算子を用いた式を考える．式は次の規則に従う．概ね一般的な手続き言語の規則と同様である．

1. 1>2>3のような>の連続を許さない．
2. 2↑2↑3は2↑(2↑3)と解釈．

上記の式を生成する無曖昧なCF文法\(G_4\)は次のように定義できる．

\(G\)から等価で無曖昧な\(G'\)を得る方法を考える．優先順位の低い順で\(i (1 \leqq i \leqq 5)\)番目の二項演算子を\(\theta_i\)とし，\(\theta_i\)を直接生成する生成規則の左辺を\(E_i\)とするとき，\(G'\)は次のように構成される．

上記の法則を解釈する．前提として優先度と結合性の制御とは，生成される解析木の構造（トポロジ）の作り方と等価である．木の深い位置に設置するほど優先度と結合度が高くなる．

%%{init: {'flowchart': {'curve': 'linear', 'nodeSpacing': 10, 'rankSpacing': 30, 'padding': 5}}}%%
graph LR
  classDef tr fill:#f6f6f6,stroke:#c0c0c0;
  e1[E1]
  e1 --- e2[E1];
  e2 --- e3[E2];
  e3 --- e4[F];
  e4 --- num1[num]:::tr;
  e1 --- plus[#43;]:::tr;
  e1 --- e5[E2];
  e5 --- e6[E2];
  e6 --- e7[F];
  e7 --- num2[num]:::tr;
  e5 --- times[#42;]:::tr;
  e5 --- e8[F];
  e8 --- num3[num]:::tr;

まず優先度については，優先度が低い演算子から順に生成規則を構成することで，解析木の浅い位置に低優先度・深い位置に高優先度が配置されるようにする．

結合度は再帰的な規則，つまり現在の規則\(E_i\)を演算子の左右のどちらに設置するかで制御できる．左結合の場合は\(E_i\)を左側に，右結合の場合は右側に配置する．再帰的な規則は解析木の深い位置に設置されるため，左に配置すれば演算子は左結合となる．非結合の場合は，再帰的規則\(E_i\)が式中に現れないようにすればよい．

CF文法の表現方法#

CF文法には様々な表現方法が存在する．ここではCF文法の拡張方法や記法について紹介する．

BNF#

BNF（Backus Naur form，バッカスナウア記法）はCF文法を記述するための記法の一つである．BNFは単なる記法であり，その本質はCF文法である．

\(G_3\)に対応するBNFを以下に示す．

<E1> ::= <E1> + <E2> | <E2> ;
<E2> ::= <E2> * <F>  | <F> ;
<F>  ::= (<E1>) | num ;

CF文法が\(G=(N,\mathit{\Sigma},P,S)\)の4つ組で定義されていたのに対し，BNFでは生成規則\(P\)のみを上記のように列挙する．定義は::=，定義の文末は;，非終端記号は<>で囲むといった記法を採用している．上記の例のようにテキストとして表しやすく，多くのプログラミング言語の構文定義で用いられている．

拡張文脈自由文法#

拡張CF文法（extended CF grammer）とは，CF文法の生成規則の右辺に正規表現を許す文法である．CF文法と同様に\(G=(N,\mathit{\Sigma},P,S)\)の4つ組で与えられる．生成規則の集合\(P\)のみがCF文法と異なる（正規表現が利用できる）．

一例として\(G_3\)に対応する拡張CF文法\(G_3^e\)を示す．なお記号の重複が発生するため(1)，正規表現としてのメタ記号部分をピンク背景文字で表している点に注意せよ．

1. 例えば*は式としての乗算演算子と，正規表現としての繰り返しの2つの意味を持ってしまう．

正規表現中で利用できるメタ記号の一部を以下に示す(1)．

1. 正規表現はこの講義では扱わない． 2年後期の「基礎工学のための情報学1」や3年前期の「計算理論」で扱う．

BNFに正規表現を加えたEBNF（extended BNF，拡張BNF）も存在する．C言語の構文はEBNFによって定義されている．以降の講義でも構文定義にはEBNFを用いる．

構文図式#

構文図式（syntax diagram, あるいはrailroad diagram）とは文字通り構文に対する図式表現である．拡張CF文法の構文を図示化できるため，簡潔で理解しやすいという利点がある．拡張CF文法の本質となる正規表現を図示化したものと解釈しても良い．

拡張CF文法\(G_3^e\)の構文図式を以下に示す．正規表現の記法と併せてその挙動を確認せよ．これまで通り，非終端記号を青色枠■，終端記号を灰色枠■ で表現している．

JSONの構文は構文図式で定義されている．

まとめ#

本ページではプログラミング言語の構文について説明した．構文はCF文法によって形式的に定義される．

プログラミング言語の構文は曖昧でないことが望ましい．構文が曖昧とは一つの終端記号列に対して複数の解析木が得られる状況を指す．曖昧な構文は生成規則の書き換えにより，無曖昧に変換できることもある．

実際のプログラミング言語はBNFや拡張CF文法，EBNFなどを用いて定義される．これらは記述ルールの差異があるものの，その本質は共通している．

プログラミング言語の構文は，プログラム記述時の使い勝手だけでなく，文法の曖昧さや演算子の優先度，解析コストの低さなど様々な要素を鑑みて設計されている点をよく認識せよ．

《宿題》#

G = (
  N = {???},
  Z = {0,1},
  P = {???},
  S = ???
)