次: , 上: Concepts


1.1 言語と文脈自由文法

Bisonが言語を解析するためには、その言語が 文脈自由文法(context-free grammar)で記述されている必要があります。 すなわち、1個以上の文法グループ(syntactic groupings)を定め、 その文法グループを部品から組み立てる規則を与える必要があります。 たとえば、C言語では、ある種のグループは「式」と呼ばれます。 式を作る規則の1つは、 「1つの式とは、別の式にマイナス記号を付けたものでもよい」かもしれません。 別の規則は、「1つの式とは、整数でもよい」かもしれません。 ここから解るように、規則はしばしば再帰的になりますが、 再帰を始めるための少なくとも1個の規則が必要です。

このような規則を人間が読めるように表現する、もっとも一般的な形式的な方法は、 バッカス-ナウア記法(Backus-Naur form)略して“BNF”です。 これは、Algol 60言語を定義するために開発されました。 BNFで表現された任意の言語は、文脈自由言語です。 Bisonへの入力は、本質的には、機械可読なBNFです。

すべての文脈自由言語をBisonで扱えるわけではありません。 LALR(1)だけを扱えます。 簡単に説明すると、ちょうど1個のトークンを先読みすることによって、 入力文字列の任意の部分を解析できる必要があるということです。 厳密に説明すると、これはLR(1)文法の説明で、 LALR(1)には簡単に説明できない追加の制限があります。 しかし、LALR(1)になれないLR(1)文法は、現実にはまれです。 より詳しい説明は See Mysterious Reduce/Reduce Conflicts

ある言語についての形式文法的な規則では、 文法的な単位またはグループを記号(symbol)と呼びます。 文法規則に従って小さい部分から組み立てられた記号を 非終端記号(nonterminal symbol)といい、 終端記号(terminal symbol)またはトークン型(token type)と呼ばれる ものに分解できます。 本書では、1個の終端記号に対応する入力の一部分をトークン(token)、 1個の非終端記号に対応する入力の一部分をグループ(grouping)と呼びます。

何が終端記号で何が非終端記号かを示すために、 例としてC言語を使います。 Cのトークンは、識別子、定数(数値または文字列)、さまざまな予約語、 算術演算子、区切り記号です。 C言語の終端記号には、「識別子」、「数値」、「文字列」、そして、 予約語、演算子、区切り記号のそれぞれに対する記号、 すなわち、「if」、「return」、「const」、「static」、「int」、「char」、 「プラス記号」、「開きブレース」、「閉じブレース」、「カンマ」、 などが含まれます (これらのトークンは文字に分解できますが、 それは文法の問題ではなく、字句解析の問題です)。

次の例は、トークンに分解されたCの関数です。

     int             /* 予約語 `int' */
     square (x)      /* 識別子, 開きかっこ, */
                     /* 識別子, 閉じかっこ */
          int x;     /* 予約語 `int', 識別子, セミコロン */
     {               /* 開きブレース */
       return x * x; /* 予約語 `return', 識別子, */
                     /* アスタリスク, 識別子, セミコロン */
     }               /* 閉じブレース */

Cの文法的なグループには、式、文、宣言、関数定義が含まれます。 これらは、Cの文法で、非終端記号、「式」、「文」、「宣言」、 「関数定義」として表されます。 完全な文法では、上記の4つの意味を表現するために、 それぞれの非終端記号について、数十個の追加の言語構築が必要です。 上記の例で、関数定義は、宣言と文を含みます。 文の中で、それぞれの`x'は式であり、 `x * x'も式です。

それぞれの非終端記号には、それがより単純な構成要素からどのように作られるか 示すために、文法規則が必要です。 たとえば、Cの文の1つであるreturn文について、 文法規則を形式ばらずに書くと、次のようになります。

「文」は、キーワード「return」、「式」、「セミコロン」から 作ることができる。

Cの各種の文について、「文」には多くの他の規則があるでしょう。

1つの非終端記号が、言語の全体を表現するように、 特別なものとして識別される必要があります。 これを開始記号(start symbol)と呼びます。 コンパイラでは、これは完全な入力プログラムを意味します。 C言語では、非終端記号「定義と宣言の並び」が、この働きをします。

たとえば、`1 + 2'は有効なCの式で、 Cのプログラムの有効な一部分ですが、 Cプログラム全体としては無効です。 したがって、Cの文脈自由文法では、「式」は開始記号でないとわかります。

Bison構文解析器は、入力としてトークンの列を読み、 文法規則を使ってトークンをグループにします。 もし入力が有効であれば、最終的な結果として、トークンの列全体が 文法の開始記号である1つのグループの記号に還元されます。 もしわれわれがCの文法を使うならば、入力全体は 「定義と宣言の列」の必要があります。 もしそうでなければ、構文解析器が文法エラーを報告します。