プログラミング言語の構文#
導入
教科書3章
講義1回分
前提#
プログラミング言語の基本構成要素として文（statement）と式（expression）がある．文は手続きを表す要素であり，それ単独で完結できる．C言語においては;や}を末尾に持つ要素が文である．式は四則演算などの評価結果となる値を持つ要素である．代入文の右辺の要素は全て式と考えてよい．文と式は入れ子構造を取る．
- 文：
n = i * 2;if (n > 5) return 1;return 1;return 0; - 式：
i * 2i2n > 5n510(1)
- 代入文の左辺
nは式ではない．その理由は後述する例題2を確認せよ．
文と式の違いをよく理解しておくこと．
文脈自由文法#
あらゆるプログラミング言語は厳密な文法規則を持つ．これを構文（syntax）と呼ぶ．プログラミング言語の構文は文脈自由文法（context-free grammar，CF文法）で表現される．
例えば，加算演算子+と乗算演算子*を用いた式（3+4*5等）の構文規則はCF文法を用いて次のように定義できる．
| 記号の名前 | 記号 | 意味 |
|---|---|---|
| 定義 | \(\ra\) | 左辺が右辺で定義 |
| 選択 | \(\mid\) | 「あるいは」の意味 |
| 非終端記号 | \(E\) | プログラム中に直接現れない抽象的な名前 |
| 終端記号 | + * ( ) num(1) | プログラム中に直接現れる記号 |
numは任意の数字列（3や16等）を表すラベルと解釈せよ．単純化のためnumという表現を用いる．
式\(E\)は次のような定義と同等の意味を持つ．
numは式である（例：num）- \(x\)と\(y\)が式であれば\(x\)
+\(y\)，\(x\)*\(y\)，(\(x\))も式である（例：num+num(num)等） - 上記の1と2で与えられたものだけが式である（例：
num-num-numnum++は式ではない）
Quiz
(num+num)*numは式\(E\)に該当するか？
Answer
式である．理由は後述．
式\(E\)の定義\(E \ra E+E \ |\ E*E \ |\ num \ |\ (E)\)は生成規則（production rule）と呼ばれる．終端記号の列，すなわち具体的なプログラム文（num+num等）を生成するための規則である．生成規則を適用して具体的な文に置き換える操作を導出（derivation）と呼び，\(\RA\)で表される．先のクイズの(num+num)*numは以下のように導出される．
導出に成功したことから(num+num)*numは式である．
Quiz
次の3つの式は式\(E\)に該当するか？
num+num+num(num+num+num)num+(num+(num))
Answer
全て該当する．導出を試してみると良い．
文脈自由文法の形式的定義#
文脈自由文法（CF文法）の形式的な定義について考える．CF文法は\(G = \{N, \mathit{\Sigma}, P, S\}\)の4つ組で定義される．先の式の生成規則\(E\)を持つCF文法\(G_0\)は以下のように定義される．
集合\(\Gamma\)に対して\(\Gamma^*\)とは，\(\Gamma\)の要素を0個以上連ねて得られる要素列の集合である．例えば\(\Gamma = \{a, b\}\)のとき，\(\Gamma^*\)はaやb，ab，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を1個か0個だけ取る生成規則は\(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言語と呼ばれる．
Quiz
CF文法\(G_0\)が生成するCF言語\(L(G_0)\)の具体例を考えよ．
Answer
num num+num (num+num)*num num*num*(num+(num))+num等．
例題1#
次のCF文法\(G_1\)は文字aとbから構成される言語を生成する．
\(G_1\)が生成する具体的な言語（終端記号列）はabやaaabbbなどである．aとbの出現数は常に同じで，常にaが先に出現する(1)．
- \(L(G_1) = \{ a^n b^n|n \geq 1\) }
例題2#
次のCF文法\(G_2\)はC言語の一部を生成する．非終端記号\(S\)は文（Statement），\(C\)は条件（Condition），\(E\)は式（Expression）を意味している．
\(G_2\)が生成する言語（終端記号列）の一例を以下に示す．C言語の正しい構文規則に従っていることを確認せよ．
CF言語\(L(G_2)\)はC言語と比較すると以下のような違いがある．
- 変数と数値が
idとnumに抽象化されている - 比較演算が
>のみ，四則演算が+と*のみである forやwhileが存在しない
しかし，ここで重要な点はCF文法によってC言語の一部の構文を定義可能であるということである．実際にC言語の構文やPythonの構文はCF文法を用いて定義されている(1)．
無曖昧な文脈自由文法#
導出列（導出の流れ）は木として表現できる．これを解析木（または導出木や構文木）と呼ぶ．\(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;\(G_0\)で定義した\(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 --- e4[E];
e4 --- num2[num]:::tr;
e2 --- times[#42;]:::tr;
e2 --- e5[E];
e5 --- 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 --- e4[E];
e4 --- num2[num]:::tr;
e2 --- plus[#43;]:::tr;
e2 --- e5[E];
e5 --- num3[num]:::tr;
e3 --- num1[num]:::tr;左の解析木は*が+より高い優先度であることを示しており，一般的な数学的解釈と一致する．一方，右の解析木では+が優先される．このように1つの終端記号列に対して2つ以上の解析木が得られるとき，文法は曖昧（ambiguous）であるという．これまで題材に用いてきた\(G_0\)の生成規則\(E \ra E+E \ |\ E*E \ |\ num \ |\ (E)\)は曖昧である．
文法が曖昧な場合，解析の結果が唯一に定まらなくなる．そのため一部の解析（導出）に失敗した際に，別の解析手順を踏む必要が発生してしまう．これは解析（コンパイル）コストの増大につながる．さらに曖昧な箇所が複数ある場合は組み合わせ爆発にもつながる．
Note
コンパイラの立場になって考えると良い．
もしプログラマが3+4*5という式をプログラム中に記述した際に，(3+4)*5と解釈すべきなのか3+(4*5)と解釈すべきなのかが判断できない．どちらの機械語を生成すべきかがわからない(1)．
3+4*5という式を常に3+(4*5)と解釈できる仕掛けが必要である．
- プログラマに「数式には絶対に括弧をつけろ」というルールを押し付けるのは現実的ではない．守ってくれるとは限らない．
プログラミング言語の文法は無曖昧（unambiguous）であることが望ましい(1)．曖昧な文法は等価かつ無曖昧に書き換えられる場合がある．このとき，その文法は本質的に曖昧でないと呼ぶ．文法\(G_0\)は本質的に曖昧ではない．よって無曖昧に書き換え可能である．具体的には生成規則\(P\)を無曖昧に構成し直す．
- 無曖昧な文法のクラスとしてはLR文法やLL文法が存在するが，この講義では扱わない．3年後期の「言語処理工学A」で取り扱う．
例題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つの性質を満たすよう構成されている．
*は+より優先度が高い（num+num*numはnum+(num*num)と解釈される）+は左結合的である（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）とは同一の演算子が並んでいるときに，どちらの演算を優先するかを示す性質である．左結合では左の演算が優先される．+と*は左結合でも右結合でも結果は同じだが，-や/は結果が変わる(1)．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\)を配置すれば右結合的となる．
Quiz
C言語における右結合の演算子を答えよ．
Answer
代入演算子=が唯一の右結合演算子である．i = j = 100はi = (j = 100)と解釈される．比較演算子== != < > <= >=や 論理演算子&& || !などは全て左結合である．冪乗演算子^は数学的には右結合だがC言語には存在しない．^はC言語ではXOR演算である．
多くのプログラミング言語の構文は\(G_3\)のような工夫を取り入れることにより，無曖昧なCF文法に近づけている．プログラミング言語の構文定義には数多くの非終端記号が用いられているが，曖昧さ除去のために導入されたものも少なくない．
Note
実際のC言語の四則演算式は\(G_3\)と同様の曖昧さ除去が取り入れられている．
無曖昧な文法規則への変換#
生成規則を無曖昧に変換する方法について述べる．
例題4#
6種類の演算子を用いた式を考える．式は次の規則に従う．概ね一般的な手続き言語の規則と同様である．
- 演算子の種類：加減算
+-，乗除算*/，冪乗↑，比較演算> - 演算の優先順位：
↑>*/>+->> - 非結合的な演算：
>(1) - 左結合的な演算：
*/+- - 右結合的な演算：
↑(2)
1>2>3のような>の連続を許さない．2↑2↑3は2↑(2↑3)と解釈．
上記の式を生成する無曖昧なCF文法\(G_4\)は次のように定義できる．
\(G\)から等価で無曖昧な\(G'\)を得る方法を考える．優先順位の低い順で\(i (1 \leq i \leq 5)\)番目の二項演算子を\(\theta_i\)とし，\(\theta_i\)を直接生成する生成規則の左辺を\(E_i\)とするとき，\(G'\)は次のように構成される．
上記の法則を解釈する．前提として優先度と結合性の制御とは，生成される解析木の構造（トポロジ）の作り方と等価である．木の深い位置に設置するほど優先度と結合度が高くなる．
再掲：無曖昧なCF文法\(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;まず優先度については，優先度が低い演算子から順に生成規則を構成する．これにより解析木の浅い位置に低優先度の演算子を，深い位置に高優先度の演算子を配置する．
結合度は再帰的な規則，つまり現在の規則\(E_i\)を演算子の左右のどちらに設置するかで制御できる．左結合の場合は\(E_i\)を左側に，右結合の場合は右側に配置する．再帰的な規則は解析木の深い位置に設置されるため，左に配置すれば演算子は左結合となる．非結合の場合は，再帰的規則\(E_i\)が式中に現れないようにすればよい．
文脈自由文法の表現方法#
CF文法には様々な表現方法が存在する．ここではCF文法の拡張方法や記法について紹介する．
BNF#
BNF（Backus Naur form，バッカスナウア記法）はCF文法を記述するための記法の一つである．BNFは単なる記法であり，その本質はCF文法である．
\(G_3\)に対応するBNFを以下に示す．
再掲：\(G_3\)の定義
CF文法が\(G=(N,\mathit{\Sigma},P,S)\)の4つ組で定義されていたのに対し，BNFでは生成規則\(P\)のみを上記のように列挙する．定義は::=，定義の文末は;，非終端記号は<>で囲むといった記法を採用している．上記の例のようにテキストとして表しやすく，多くのプログラミング言語の構文定義で用いられている．
©
©拡張文脈自由文法#
拡張CF文法（extended CF grammar）とは，CF文法の生成規則の右辺に正規表現を許す文法である．CF文法と同様に\(G=(N,\mathit{\Sigma},P,S)\)の4つ組で与えられる．生成規則の集合\(P\)のみがCF文法と異なる（正規表現が利用できる）．
一例として\(G_3\)に対応する拡張CF文法\(G_3^e\)を示す．なお記号の重複が発生するため(1)，正規表現としてのメタ記号部分をピンク背景文字で表している点に注意せよ．
- 例えば
*は式としての乗算演算子と，正規表現としての繰り返しの2つの意味を持ってしまう．
再掲：\(G_3\)の定義
正規表現中で利用できるメタ記号の一部を以下に示す(1)．
- 正規表現はこの講義では扱わない．2年後期の「基礎工学のための情報学1」や3年前期の「計算理論」で扱う．
| メタ記号 | 意味 | 例 |
|---|---|---|
* | 0回以上の繰り返し | a*はa aa aaaaa |
+ | 1回以上の繰り返し | a+はa aa aaaaa ... |
| | 選択 | a|bはa b |
() | グループ化 | (a|b)cはac bca(/a)*はy a/a a/a/a/a/a ... |
Note
正規表現を覚えておくことを強く推奨する．情報科学の様々な文脈で用いられる一種の共通言語である．少なくとも上記4つのメタ記号を覚えておくと良い．
BNFに正規表現を加えたEBNF（extended BNF，拡張BNF）も存在する．C言語の構文はEBNFによって定義されている．以降の講義でも構文定義にはEBNFを用いる．
構文図式#
構文図式（syntax diagram, あるいはrailroad diagram）とは文字通り構文に対する図式表現である．拡張CF文法の構文を図示化できるため，簡潔で理解しやすいという利点がある．拡張CF文法の本質となる正規表現を図示化したものと解釈しても良い．
拡張CF文法\(G_3^e\)の構文図式を以下に示す．正規表現の記法と併せてその挙動を確認せよ．これまで通り，非終端記号を青色枠■，終端記号を灰色枠■で表現している．
JSONの構文は構文図式で定義されている．
まとめ#
本ページではプログラミング言語の構文について説明した．構文はCF文法によって形式的に定義される．
プログラミング言語の構文は曖昧でないことが望ましい．構文が曖昧とは一つの終端記号列に対して複数の解析木が得られる状況を指す．曖昧な構文は生成規則の書き換えにより，無曖昧に変換できることもある．
実際のプログラミング言語はBNFや拡張CF文法，EBNFなどを用いて定義される．これらは記述ルールの差異があるものの，その本質は共通している．
プログラミング言語の構文は，プログラム記述時の使い勝手だけでなく，文法の曖昧さや演算子の優先度，解析コストの低さなど様々な要素を鑑みて設計されている点をよく認識せよ．
《宿題》#
Homework 約30分 答え
2種類の文字0と1のみで構成される言語を生成するCF文法を答えよ．ただし先頭と末尾は同じ文字とする．
- OK：
01001110101011110 - NG：
0110111000001011001
以下の書式をコピーして回答せよ．\(\Sigma\)はZで代用している．\(\varepsilon\)遷移にはeという文字を使うと良い．
-
PIerre.Lescanne, https://en.wikipedia.org/wiki/John_Backus ↩
-
Eriktj at English Wikipedia, https://en.wikipedia.org/wiki/Peter_Naur ↩