コンパイラ 作りながら学ぶ第3章

3.1 バッカス記法

　バッカス記号とは，ALGO60という1960年に初めて国際的な組織で開発されたプログラミング言語の構文である．ALGO60の構文がバッカス記法で明確に定義されて以来，多くのプログラミング言語は，バッカス記法やそれを拡張した記法で記述されるようになった．バッカス記法で，「識別子」または「名前」と呼ばれるものを定義すれば次のようになる．

<数字> ::=0|1|2|3|4|5|6|7|8|9
<英字> ::= a|b|...|y|z
<名前> ::= <英字>|<名前><英字>|<名前><数字>

　ここで，＜＞で囲まれたものを構文要素と呼ぶ．上か一行目は，＜数字＞は0～9のどれかで表される，という意味を表している．同様にして二行目は，英字はa～bのどれかのアルファベットで表される，という意味になる．三行目は，名前は＜英字＞か＜名前＞＜英字＞か＜名前＞＜英字＞のいづれかで表されるという意味になる．例えば，＜名前＞aに英字sを付け加えた，asも＜名前＞となる．さらにこれに＜数字＞2を付け加えたas2も名前となる．つまり，最初の文字が英字で，あとは英字or数字で構成される文字列を＜名前＞と定義している．これを｛｝という要素の繰り返しを表す記号で表現すると以下のようになる．

＜名前＞　→　＜英字＞{＜英字＞｜＜数字＞}

これは，英字または数字の繰り返しで表現される一文字以上の文字列を表す．これに空を意味するεを加えて｛ε｜＜英字＞｜＜数字＞｝とするとゼロ文字以上の繰り返しとなる．

＜文＞　→　＜主部＞＜述部＞
＜主部＞　→　＜名詞＞＜助詞＞
＜述部＞　→　＜動詞＞
＜名詞＞　→　私|君|犬
＜助詞＞　→　は|が|も
＜動詞＞　→　遊ぶ|泳ぐ|走る

　次に，日本語の一部を，バッカス記法で定義してみる．これ以降「:=」の代わりに「→」を用いる．上の構文では，＜文＞の定義を，主部と述部で構成されるものとし，さらにその主部は名詞と助詞で構成され，述部は動詞で構成さる．さらに，名詞は「私or君or犬」で構成され，助詞は，「はorがorも」で構成され，動詞は「遊ぶor泳ぐor走る」で構成されることを表している．「私は泳ぐ」という文の構成を図で表すと以下のようになる．

上図は木構造となっている．「文」がその木の根であり，「私」「は」などの具体的な単語は，葉に相当する．このような具体的は，単語は末端に現れることから終端記号と呼ばれ，それ以外のものは非終端記号と呼ばれる．

3.2 構文図式

構文規則を図式で表現すると直感的に理解しやすくなる．それは構文図式と呼ばれている．
下図は，$|\alpha_1|\alpha_2|...|\alpha_n|$を表す構文図式です．

下図は，$\alpha_1 \alpha_2 \cdots \alpha_n$を表す構文図式です．

下図は，{$\alpha$}を表す構文図式です．

3.3 文法と言語の形式的定義

任意個の記号の列を記号列という．例えば，アルファベット{a,b,c,d}からなる記号列には，a, c, ba, abc, bbcddなどがある．xとyが記号列であるとき，それを連結した$xy$も記号列である．$A,B$を記号列の集合とするとき

AB= \{xy|x\in A, y\in B\}

で$A$と$B$の積$AB$を定義する．また，集合のべき乗を次のように定義する．
$$A^1 = A, ; A^2 = AA=AA^1,; A^3 = AAA = AA^2,;\cdots A^n = AA^{n-1}$$これを使ってAの閉包$A^*$，正の閉包$A^+$を定義する．

A^+ =\bigcup_{i=1}^{\infty} A^i,\quad A^*=\bigcup_{i=0}^{\infty} A^i

これらの記号や用語を使って文法と言語定義する．前節まで構文規則と呼んでいたものは，ここでは生成規則あるいは書き換え規則と呼ばれ一般に次の形をしている．
$$U\to x$$ここで$U$は記号であり，$x$は記号列を表す．$U$を生成規則の左辺，$x$を生成規則の右辺と呼ぶ．ここで文法と呼んでいるものは正確には文脈自由文法と呼ばれる．3.1で$A\to \alpha |\beta$と表現されていたものは，$A\to \alpha, A\to \beta$という二つの生成規則をまとめた略記法である．

文脈自由文法の定義と例

G=\{P,S\}

文脈自由文法$G$は生成規則の集合$P$と記号$S$の組として定義される．$S$は開始記号，出発記号と呼ばれる．文脈自由文法$G=\{P,S\}$において$P$の生成規則の左辺に現れる記号を非終端記号と呼び，右辺にだけ現れる記号を端記号と呼ぶ．また，生成規則に現れる記号の集合を語彙と呼ぶ．非終端記号の集合を$N$,終端記号の集合を$T$，語彙を$V$と表す.$N,T$の代わりに，$V_n, V_T$と書くこともある．

\begin{align}
G1=&\{\;P,E\;\}\\
P=\{\;&E\to E+T\\
&E\to T\\
&T\to T*F\\
&T\to F\\
&F\to (E)\\
&F\to a\\
&F\to b\\
&F\to c\;\}
\end{align}

このとき$V_n,V_T,V$は次のようになる．

\begin{align}
&V_n = \{E,T,F\}\\
&V_T = \{+,*,(,),a,b,c\}\\
&V=\{E,T,F,+,*,(,),a,b,c\}
\end{align}

文法が与えられたとき，それから得られる分野言語を次に定義する．
[定義]
文法$G=\{P,S\}$において，$x,y\in V^* ,;U\to u\in P$のとき$v,w\in V^*$が

v=xUy, \; w=xuy

であるならば$v$は$w$を直接生成するといい，

v\Rightarrow w

と書く．このとき$w$は$v$に直接還元されるという．$v$から直接生成を何回かした結果$w$が得られたとき，$v$は$w$を生成するという．

[定義]
$v=u_0 \Rightarrow u_1 \Rightarrow \cdots \Rightarrow u_n = w(n\geq 0)$となる$u_i \in V^*(0\leq i \leq n)$が存在するならば$v$は$w$を生成するといい，$w$は$v$に還元されるという．このとき，$n>0$ならば,$v\xrightarrow{+}$と書き，$n\geq 0$ならば$v\xrightarrow{*}$ と書く．

[定義]
文法$G=\{P,S\}$において，$x\in V^{*}$で$S\xrightarrow{*}x$ならば$x$を文形式と呼ぶ．$x\in V_{T}^{*}$で$S\xrightarrow{*}x$ならば$x$を文と呼ぶ．$G$の集合を$G$の言語と呼び$L(G)$と書く．

3.4 解析木

前節の文法$G1$の文$ab$が開始記号$E$から生成される様子を図示すると次のようになる．

この図を得るためには，開始記号から始めて順次，非終端記号$U$をそれにたいして使われた規則$U\to a$に対して

で置き換えていけばよい．できあがった木の末端（葉と呼ばれる）の記号を左から順次にたどって並べたものが文となる．例えば文$a+bc$は以下の構文木となる．

これらの図は文がどのような生成規則から生成されたのかを示している．すなわち，その分の構造を示している．コンパイラは，$a+b*c$のような文が与えられたとき，その構造を調べること，すなわち上記のずを求めることをする．その仕事は構文解析と呼ばれ，その結果得られる上記のような木は解析木と呼ばれる．
解析木は文の構造を示すものであるので，あたえられた文に対してその解析木が一意に定まらないと困る．例えば，次の文法を考えてみる．

\begin{align}
G2= &{P2,E}\\
P2=\{&E\to E+E\\
&E\to E*E\\
&E\to(E)\\
&E\to a\\
&E\to b\\
&E\to c \}
\end{align}

この文法の文としても$a+bc$は得られる．($G1$と$G2$の言語は同じで，$L(G1)=L(G2)$である）．しかし文法$G2$の文としての$a+bc$に対しては，次のように2通りの解析木が得られる．


このようにある文の解析木が2とおり以上存在すれば，その文はあいまいであるという．あいまいな文を生成できる文法はあいまいな文法であるという．例えば，文法$G2$の文$a+b*c$はあいまいである．したがって$G2$はあいまいな文法である．