コンテンツにスキップ

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

教科書3章 導入 講義1回分

前提#

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

C言語の適当なプログラム
n = i * 2;
if (n > 5) return 1;
return 0;
  • 文：n = i * 2; if (n > 5) return 1; return 1; return 0;
  • 式：(1) i * 2 i 2 n > 5 n 5 1 0
  1. 代入文の左辺 n は式ではない．

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

構文規則#

あらゆるプログラミング言語は厳密な文法規則を持つ．これを構文（syntax）と呼ぶ．構文はBNF（Backus Naur form，バッカスナウア記法）などを用いて定義される．

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

\[ \Ebr::=\Ebr + \Ebr \quad | \quad \Ebr * \Ebr\quad | \quad num \quad | \quad(\ \Ebr\ ) \]
記号の名前 記号 意味
定義 \(::=\) 左辺が右辺で定義
選択 \(\mid\) 「あるいは」の意味
非終端記号 \(\Ebr\) プログラム中に直接現れない抽象的な名前
終端記号 + * ( ) \(num\)(1) プログラム中に直接現れる記号
  1. \(num\)は任意の数字列（3や16等）を表すラベルと解釈せよ． 単純化のため\(num\)という表現を用いる． BNFを用いて厳密に定義すると\(\langle num \rangle ::= 0|1|2|..|9|\langle num \rangle^*\)である．

式\(\Ebr\)は次のように機能的に定義されたことと同じ意味を持つ．

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

Quiz

(num+num)*numは式\(\Ebr\)に該当するか？

Answer

式である．理由は後述．

文脈自由文法#

形式言語理論ではBNFは文脈自由文法（context-free grammer，CF文法）と呼ばれる．BNFとCF文法は同じものであるが，記法が少々異なる．以降ではCF文法を用いてプログラミング言語の構文を考える．

CF文法では定義\(::=\)は代わりに\(\ra\)が用いられる．先の\(\Ebr\)は次のように表現される．

\[ E \ra E + E \quad | \quad E * E \quad | \quad num \quad | \quad (E) \]

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

\[ \displaylines{ & \textsf{導出の流れ}& //\ \textsf{適用した生成規則} \\ E & \RA E*E & //\ E \ra E*E\\ & \RA (E)*E & //\ E \ra (E)\\ & \RA (E+E)*E & //\ E \ra E+E\\ & \RA (num+E)*E & //\ E \ra num\\ & \RA (num+num)*E & //\ E \ra num\\ & \RA (num+num)*num & //\ E \ra num\\ } \]

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

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

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

\[ \displaylines{ G_0=(&N &=& \{E\}, &//\ \textsf{非終端記号の集合}\\ &\mathit{\Sigma} &=& \{num,+,*,(,)\},&//\ \textsf{終端記号の集合}\\ &P &=& \{E \ra E+E \ |\ E*E \ |\ num \ |\ (E)\},&//\ \textsf{生成規則}\\ &S &=& E\quad) &//\ \textsf{開始記号}\\ } \]

集合\(\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言語と呼ばれる．

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=(\ N = \{S\}, \quad \mathit{\Sigma} = \{a,b\}, \quad P = \{S \ra aSb\ |\ ab\}, \quad S \ ) \]

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

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

例題2#

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

\[ \displaylines{ G_2=(& N &=& \{S,C,E\},\\ & \mathit{\Sigma} &=& \{id,num,+,(,),if,'\{','\}',;,>,=\},\\ & P &=& \{\\ & & & \quad S \ra id = E; \ |\ SS \ |\ '\{'S'\}' \ |\ if(C)S, & //\ \textrm{Statement} \ \textsf{文}\\ & & & \quad C \ra E>E, & //\ \textrm{Condition} \ \textsf{条件}\\ & & & \quad E \ra num\ |\ id\ |\ E+E & //\ \textrm{Expression} \ \textsf{式}\\ & & & \},\\ & S & ) } \]

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

G2が生成する終端記号列の一例
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の構文はBNFや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;

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

Note

生成規則\(E \ra (E)\)があるため数学的に曖昧ではない終端記号列（num+(num*num)等）を生成することも可能ではある．しかし，ここでの問題は複数の解析木を作れることそのものにある．

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

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

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

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

例題3#

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

\[ \displaylines{ G_3=( & N &=& \{E,T,F\},\\ & \mathit{\Sigma} &=& \{num,+,*,(,)\},\\ & P &=& \{\\ & & & \quad E \ra E + T \ |\ T,\\ & & & \quad T \ra T * F \ |\ F,\\ & & & \quad F \ra (E) \ |\ num\\ & & & \},\\ & E & ) } \]

\(G_3\)における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];
  e2 --- e3[T];
  e3 --- e4[F];
  e4 --- num1[num]:::tr;
  e1 --- plus[#43;]:::tr;
  e1 --- e5[T];
  e5 --- e6[T];
  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. *は左結合的である

結合性（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[E]
  e1 --- e2[E];
  e1 --- plus1[#43;]:::tr;
  e1 --- t1[T];
  e2 --- e3[E];
  e2 --- plus2[#43;]:::tr;
  e2 --- t2[T];
  e3 --- t3[T];
  t3 --- f1[F];
  f1 --- num1[num]:::tr
  t2 --- f2[F];
  f2 --- num2[num]:::tr
  t1 --- f3[F];
  f3 --- num3[num]:::tr

生成規則\(E \ra E + T\)において，自分自身を再帰的に呼び出す終端規則\(E\)が演算子の左側に出現している点が重要である．逆に\(E \ra T + E\)のように右側に\(E\)があれば右結合的となる．

Quiz

C言語における右結合の演算子を答えよ．

Answer

代入演算子=が右結合である．i = j = 100はi = (j = 100)と解釈される．比較演算子== != < > <= >=や 論理演算子&& || !などは全て左結合である．

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

Note

実際のC言語の四則演算式は\(G_3\)と同様の曖昧さ除去が取り入れられている．

C言語の四則演算式の定義（BNF）
<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)
  • 左結合的な演算：* / + -
  • 右結合的な演算：↑(2)
  1. 1=2=3のような=の連続を許さない．
  2. 2↑2↑3は2↑(2↑3)と解釈．

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

\[ \displaylines{ G_4=( & N &=& \{E_1,E_2,E_3,E_4,E_5\}, \\ & \mathit{\Sigma} &=& \{=,+,-,*,/,\uparrow,(,),num\}, \\ & P &=& \{\\ & & & \quad E_1 \ra E_2 = E_2 \ |\ E_2, \\ & & & \quad E_2 \ra E_2 + E_3 \ |\ E_2 - E_3 \ |\ E_3, \\ & & & \quad E_3 \ra E_3 * E_4 \ |\ E_3 / E_4 \ |\ E_4, \\ & & & \quad E_4 \ra E_5 \uparrow E_4 \ |\ E_5, \\ & & & \quad E_5 \ra (E_1) \ |\ num \\ & & & \},\\ & S &=& E_1\ )\\ } \]

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

\[ \displaylines{ \theta_i \textsf{が非結合的ならば}\quad E_i \ra E_{i+1} & \theta_i & E_{i+1} & | & E_{i+1} \\ \theta_i \textsf{が左結合的ならば}\quad E_i \ra E_i & \theta_i & E_{i+1} & | & E_{i+1} \\ \theta_i \textsf{が右結合的ならば}\quad E_i \ra E_{i+1} & \theta_i & E_i & | & E_{i+1} \\ } \]

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

再掲：無曖昧な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[E]
  e1 --- e2[E];
  e2 --- e3[T];
  e3 --- e4[F];
  e4 --- num1[num]:::tr;
  e1 --- plus[#43;]:::tr;
  e1 --- e5[T];
  e5 --- e6[T];
  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文法と同様に\(G=(N,\mathit{\Sigma},P,S)\)の4つ組で与えられる．生成規則の集合\(P\)のみがCF文法と異なる（正規表現が利用できる）．(1)

  1. BNFに正規表現を加えた拡張BNF（extended BNF，EBNF）も存在する．

例題5#

拡張CFの一例として，\(G_3\)に対応する拡張CF文法\(G_5\)を示す．ただし，減算-を追加し，乗算*を除算/に入れ替えている(1)．

  1. 説明の簡単化のためである． -は+との選択を表すためであり，*は正規表現の記号との衝突ためである．
再掲：\(G_3\)の定義
\[ \displaylines{ G_3=( & N &=& \{E,T,F\},\\ & \mathit{\Sigma} &=& \{num,+,*,(,)\},\\ & P &=& \{\\ & & & \quad E \ra E + T \ |\ T,\\ & & & \quad T \ra T * F \ |\ F,\\ & & & \quad F \ra (E) \ |\ num\\ & & & \},\\ & E & ) } \]
\[ \displaylines{ G_5=( & N &=& \{E,T,F\},\\ & \mathit{\Sigma} &=& \{num,+,/,-,(,)\},\\ & P &=& \{\\ & & & \quad E \ra T((+|-)T)*, & //\ \textsf{右辺に正規表現} \\ & & & \quad T \ra F(/F)*, & //\ \textsf{右辺に正規表現} \\ & & & \quad F \ra '('E')' \ |\ num \\ & & & \},\\ & E & ) } \]

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

  1. 正規表現はこの講義では扱わない． 2年後期の「基礎工学のための情報学1」や3年前期の「計算理論」で扱う．
メタ記号 意味 例
* 0回以上の繰り返し a*はa aaaaa ...
+ 1回以上の繰り返し a+はa aaaaa ...
| 選択 a|bはa b
() グループ化 (a|b)cはac bc
c(/c)*はc c/c c/c/c/c/c ...

構文図式#

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

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

本ページで見てきたように，構文定義はBNFやCF文法，拡張CF文法（正規表現）など様々な方法が存在する．C言語とJavaはBNFによって定義されており，Pythonは拡張BNFとPEGによって定義されている．これらはいくつかの記述ルールの差異があるものの，その本質は共通している．

まとめ#

本ページではプログラミング言語の構文について説明した．構文はBNFやCF文法，拡張CF文法などにより形式的に定義可能である．また構文は構文図式を用いて図示化可能である．

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

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

《宿題》#

Homework 約30分 答え

2種類の文字0と1のみで構成される言語を生成するCF文法を答えよ．ただし先頭と末尾は同じ文字とする．

  • OK：0 1 00 11 101 01011110
  • NG： 01 10 11100 0001011001

以下の書式をコピーして回答せよ．\(\Sigma\)はZで代用している．\(\varepsilon\)遷移にはeという文字を使うと良い．

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

回答フォーム