第 4 回文脈自由文法

本日の内容

4-1. 文脈自由文法
4-2. 構文解析木
4-3. 文法を解釈するプログラム

このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。

4-1. 文脈自由文法

ここからは正規文法で取り扱えないような言語を取り扱うため、正規文法より強力な文法の記述法を学びます。

文法とルール

本講義で文法とは言語を定義するようなもの一般を意味してました。しかし、通常、文法と呼ばれるものはもう少し形式が存在します。英文法や国文法では、単語が品詞に分類でき、さらに文において品詞の並び方が数通りに定められているという手法で定義されます。例えば英語では、文は次の5文型になると言われています。

S+V: 例: I ski. It rains. I have returned. This class has begun.
S+V+C: 例: This is a pen. I am a student. You look tired.
S+V+O: 例: I love you. I am studying programming.
S+V+O+O: 例: I teach you theories of programming.
S+V+O+C: 例: I find you asleep.

ここで S は主語、 Vは述語、Cは補語、Oは目的語です。

正規表現などはこのような表現ではありませんでした。今回は、上記のように、文が特定の品詞の組み合わせでできているというような文法表示を取り扱います。このような表現による文法表現のしかた、正規文法との関係、プログラミングについて学びます。なお、このような表現は、プログラミング言語や通信プロトコルの仕様の記述などにも利用されます。そのため、利用価値が高いものです。

バッカス・ナウア記法

文法の与え方にはさまざまな方法がありますが、ここではバッカス・ナウア記法を取り上げます。バッカス・ナウア記法は、非終端記号の集合 V_N、終端記号の集合 V_T、ルール P、開始記号 S∈V_N の 4 つ組 $G = (V_{N}, V_{T}, P, S)$ で表します。

バッカス・ナウア記法では生成する文字列を作るアルファベットを終端記号と言います。終端記号の集合を $V_{T}$ で表します。一方、それに属さない記号を非終端記号と言います。非終端記号の集合を $V_{N}$ で表します。ルールは左辺に一つの非終端記号、右辺は非終端記号と終端記号の列で表します。通常は左辺と右辺は ::= や → という記号で結びます。そして最後に一つ非終端記号を開始記号として指定します。このルールで左辺に一つだけ非終端記号がある文法を文脈自由文法と言います。

このように定義した文法において、つぎのような手順により記号列を生成します。

開始記号を左辺に含むルールを一つ選ぶ
開始記号をそのルールの右辺に置き換える
置き換えたものの中から非終端記号を一つ選ぶ
その非終端記号を左辺に含むルールを一つ選ぶ
その非終端記号を右辺に置き換える
すべてが終端記号なら終了、そうでなければ 3 に戻る

簡単のため、左辺が同じルールは、右辺を |(縦棒) で区切って列挙することで一つにまとめることにします。

文法の例

以下に簡単な文法の例を示します。

G=({文, 主語, 述語, 補語, 名詞句, 動詞, 代名詞, 冠詞, 名詞}, {This, is, a, pen}, P, 文)

P の定義

文 → 主語述語補語
主語 → 名詞句
述語 → 動詞
補語 → 名詞句
動詞 → is
名詞句 → 代名詞 | 冠詞名詞
代名詞 → This
冠詞 → a
名詞 → pen

このようなルールから、 This is a pen という記号列が導けます。

このように終端記号と言っても一文字であるとは限りません。通常は意味のあるひとまとまりの語句(トークン)毎に文法を考えます。

括弧の処理

正規文法では取り扱えなかった括弧も、このバッカスナウア記法では比較的簡単に扱えます。単純な括弧のみの言語は次のように書けます。

例4-1


S→ε
S→SS
S→(S)

演習4-1

上記の文法にさらに [](角括弧)も使えるようにしなさい

正規文法

バッカス・ナウア記法において、指定できるルールを「非終端記号→終端記号, 非終端記号 → 終端記号非終端記号」だけに制限した文法を正規文法といいます。

例4-2

a*: S→ε, S→aS
[abc]: S→a,S→b,S→c
(abc|asd): S→aA, A→bB, B→c, A→sC, C→d
.*(a|b): (アルファベットが { a, b, c } の時) S→aS, S→bS, S→cS, S→a, S→b

定理: 文脈自由文法に制限を与えた正規文法と、前回与えた正規文法は等価である

まず、このルールから非決定性オートマトンを構成できることを示します。各非終端記号をそれぞれ一つのオートマトンの状態とします。そして、開始記号である非終端記号を表す状態を開始状態とします。また、別に終了状態を作っておきます。 A→bC 型の遷移規則に関しては、状態 A から入力 b で状態 C に遷移するようにします。一方、 A→b 型の遷移規則に関しては状態 A から入力 b で終了状態に遷移するようにします。この様に構成するとすべてのルールは非決定性オートマトンの遷移規則に変換できます。さらに、構成した非決定性オートマトンがもとの文脈自由文法と同じ言語を受理することが明かです。

逆に非決定性オートマトンがすべてこの文脈自由文法に変換できることを示すことで、最終的に両者が等価であることを示します。これは、上記の変換が一対一で行えることから、逆もまた可能であることを示せば充分です。つまり、任意の非決定性オートマトンに対して、状態 A から入力 b で状態 C に遷移するなら、非終端記号 A と C と終端記号 b に対して A→bC というルールを対応付ければ良いということです。なお、受理状態への遷移に関しては、受理状態からεの入力を加えれば良いです。つまり A→bC というルールで C が受理状態なら、さらに C→ε を加えます。

以上により、この表記法と、以前に定義した正規表現が等価であることが示せました。

演習4-2

整数をこのバッカス・ナウア記法による正規文法により表現しなさい。

4-2. 構文解析木

一般のバッカス・ナウア記法による記号列の生成では、一つの非終端記号が複数の非終端、終端記号に対応します。そして、それに含まれる非終端記号がまた複数の非終端、終端記号に対応します。この導出の流れを図にすると、一つの非終端記号が複数の非終端、終端記号に対応するので、木の構造になります。

A→bCD というルールの場合
ルールの図示

根は開始記号になり、葉は終端記号、葉以外の頂点は非終端記号になります。与えられた記号列に対して、それの生成手順に対応した木を構文解析木と言います。例えば、上の This is a pen という記号列は次のような構文解析木を持ちます。

一つの記号列について、複数の構文解析木を持つ文法をあいまいであると言います。あいまいな文法はコンピュータで機械的に処理することができません。因みに英語はあいまいです。次の文章の解釈はなんと 4 通りあります。

Time flies like an arrow.

これは、動詞として Time, flies, like の三通りが考えられ、しかも Time が動詞の時は、 like an arrow の前が名詞になるので副詞句の他に形容詞句になる可能性があるからです。

動詞	like an arrow	訳
Time	副詞句	矢のように蝿の所要時間を計りなさい
Time	形容詞句	矢に似ている蝿の所要時間を計りなさい
flies	副詞句	時間は矢のように飛ぶ
like		時間蝿は一本の矢が好きである

英語の場合、前後の文章や蝿、矢などに関する知識などを利用してふさわしい訳を選ぶ必要があります。

演習4-3

自然言語の構文解析はとても難しいです。次の日本語の構文解析木を書きなさい。

これはペンです
すもももももももものうち
きしゃのきしゃはきしゃできしゃした
きしゃできしゃしたのはきしゃのきしゃです(汽車で帰社したのは貴社の記者です)。

演習4-4

次の日本語を、前後関係などで構文を意識して、英訳しなさい

わたしはうなぎです。

これは、料理屋で注文を確認された時に、発言した言葉です。
私の娘は男だった。

これは孫の誕生を話題にしている人同士の会話です。

足し算の文法

足し算だけの数式を解釈する文法を考えます。最初に次の文法を考えます。

文法 G₀

=({和},{数, +}, P₀, 和)

和 \to 数 + 数

この文法では、 1+1 のような式は解釈できますが、 1+2+3 は駄目です。そこで、足し算がいくつつながっていても解釈可能な文法を考えます。数式は、一般に左から右へ解釈します。したがって、 1+2+3 は 1+2 を解釈した後、その和に対して +3 を加えたものを新しい和とします。つまり、次のようなルールが必要になります。

和 \to 和 + 数

このルールがあれば、一番左の項以外はこれで解釈できます。一番左の項はそれだけで和とみなせば 1+2+3 を解釈できます。

文法 G₁

=({和},{数, +}, P₁, 和)

\begin{matrix} 和 \to 和 + 数 \\ 和 \to 数 \end{matrix}

なお、次のようにしてしまうと和の優先順序を指定できず、あいまいになります。

文法 G_1x

=({和},{数, +}, P_1x, 和)

\begin{matrix} 和 \to 和 + 和 \\ 和 \to 数 \end{matrix}

演習4-5

括弧を加えるにはどうしたら良いか考えなさい。

4-3. 文法を解釈するプログラム

さて、文法からそれを解釈するプログラムを作る手法を学びます。なお、構文解析のことをparse、構文解析をするプログラムなどを parserといいます。

素朴な解析法

バッカス・ナウア記法の素朴な解析法として次のようなものがあります。すべての非終端記号に対して、関数を作ります。そして、左辺の非終端記号を関数呼び出しとし、右辺は関数の内部処理とします。そして、終端記号に対しては文字を認識し、非終端記号に関しては、それに対応した関数を(再帰的に)呼び出します。例えば、 A→bCD で A,C,D が非終端記号、 b が終端記号だった時、関数 A を次のように作ります(あらかじめ文字を一つ読んでおきます)。


private boolean A(){
   if(記号 b を認識できたら){
     次の文字を読み込む
     if(C()){
       if(D()){
         return true;
       }
     }
   }
   return false;
}


def A():
    if 記号 b を認識できたら:
        次の文字を読み込む
        if C():
            if D():
                return True
    return False

そして非終端記号 C, D に対しても同様に関数を作ります。このようにすると構文木通りに関数が呼び出されて、与えられた記号列を処理できる場合があります。しかし、実際は一つの非終端記号から複数の導出規則が存在します。例えば、下の例では状態 S で文字 a を読み込んだ時、 A か B のどちらを導出するかはすぐには決められません。

S→A|B
A→ab
B→ac

素朴な方法としては、適当に導出規則を選び、途中で失敗したら別の導出規則を選ぶ方法が考えられます。これをバックトラックと言います。確かにこの方法でも構文解析できますが、しかし、キューを実装しているように、途中の入力を全て覚える必要があります。また、考え得る全ての構文木を一つ一つ生成しては比較するようなものなので、効率が悪いです。

例4-3

A()||B() は A() を実行して true が返ってきたら B() は実行されず true になります。 A() が false が返されたときだけ、 B() が実行されて、その値が返されます。


import java.io.*;
class Parser {
    public Parser(Reader r){
	reader = new BufferedReader(r);
    }
    final private BufferedReader reader;
    public boolean S() throws IOException{
	if(A() || B()){ // A がだめなら B
	    return true;
	}else{
	    return false;
	}
    }
    private boolean A() throws IOException{
	reader.mark(2); // 2 文字読んだあと戻す可能性がある
        if(reader.read()=='a' && reader.read()=='b'){
          return true;
        }
        reader.reset();
	return false;
    }
    private boolean B() throws IOException{
	reader.mark(2);
        if(reader.read()=='a' && reader.read()=='c'){
          return true;
        }
        reader.reset();
	return false;
    }
}
class Rei {
    public static void main(String[] arg) throws IOException{
	Parser parser = new Parser(new InputStreamReader(System.in));
	if(parser.S()){
	    System.out.println("Ok");
	}else{
	    System.out.println("NG");
	}
    }
}


class Parser:
    def __init__(self, string):
        self.list= list(string)
        self.pointer = 0
    def __iter__(self):
        return self
    def __next__(self):
        if self.pointer >= len(self.list):
            raise StopIteration()
        result = self.list[self.pointer]
        self.pointer += 1
        return result
    def mark(self):
        self.m = self.pointer
    def reset(self):
        self.pointer = self.m
def S():
    if A() or B():
        return True
    else:
        return False
def A():
    reader.mark()
    if next(reader)=='a' and next(reader)=='b':
        return True
    reader.reset()
    return False
def B():
    reader.mark()
    if next(reader)=='a' and next(reader)=='c':
        return True
    reader.reset()
    return False;

reader = Parser(input())
if S():
    print("Ok")
else:
    print("NG")

バックトラックを避け、効率良く構文解析するためにはどのようなことが考えられるでしょうか? 一つの考え方として、次に読み込む記号から必ず導出規則が一つ決定できるような文法が与えられたとします。そのような文法では文字を読み込みながら if 文でどちらの導出規則を選択できるため、バックトラックを行わずに済みます。この、どんな非終端記号に対しても、入力を左から読んでいき、次の先頭の文字を読むだけで一意に導出が可能な文法を LL(1)文法と言います。 (Left to Right, Leftmost derivation)

左再帰性の除去

さて、足し算の文法をプログラムで表現する手法を考えます。まず、前回の足し算の文法は以下の通りです。

文法 G₁

=({和},{数, +}, P₁, 和)

\begin{matrix} 和 \to 和 + 数 \\ 和 \to 数 \end{matrix}

この文法は LL(1) ではありません。つまり、この文法では上で述べたように、文字を読んでも次の導出規則を決めることはできません。なぜならば、入力列に対して $和 \to 和 + 数$ というルールを適応するには、その先頭部分が「和」の形になっているかどうかを調べる必要があります。そして、そのためにはその先頭部分が「和」の形になっているかどうかを調べる必要があります。このように解釈が巡回してしまい、結論にはたどり着けません。つまり、左辺と同じ非終端記号が右辺の先頭に来ていると、入力列を順に読む構文解析ができなくなります。これを左再帰性と言います。

この左再帰性は次のようにすれば除去できます。例えば、次のような左再帰性を持つ生成規則があったとします。

A \to A α | β

A は非終端記号で、α と β は非終端記号、終端記号からなる列を表し、β は A で始まらないとします。これは β, βα, βαα, ... という列を表します。この時、次のように書き直すと左再帰性がなくなります。

\begin{matrix} A \to β A' \\ A' \to α A' | ε \end{matrix}

上の足し算を解釈する文法G₁の左再帰性を除去すると次のようになります。

文法 G₂

=({和, 和'},{数, +}, P₂, 和)

\begin{matrix} 和 \to 数 和' \\ 和' \to + 数 和' | ε \end{matrix}

さて、数式を計算させ、答えを求めたい場合、数式の最後を明白にする記号として、 = を入力するというルールを追加します。このルールを含めた文法 G₁, G₂ をそれぞれ G₁', G₂' とします。

文法 G₁'

=({和, 始},{数, +, =}, P₁', 始)

\begin{matrix} 始 \to 和 = \\ 和 \to 和 + 数 \\ 和 \to 数 \end{matrix}

文法 G₂'

=({始, 和, 和'},{数, +, =}, P₂', 始)

\begin{matrix} 始 \to 和 = \\ 和 \to 数 和' \\ 和' \to + 数 和' | ε \end{matrix}

再帰的下向き構文解析法

文法に対して、左辺から右辺への導出が、次の一文字を読むだけで決定できれば、その文法をLL(1) 文法と言います。これは、開始記号から導出を始め、一番左の非終端記号を次の入力文字から導出ルールを一意に決められれば良いというルールです。各非終端記号 A に対して、その導出規則が A→α と A→β であったと仮定します。この時、 Director(A,α) を A→α において、この規則により一番左側に導出される可能性のある終端記号の集合とします。この時、どの非終端記号 A に対して、 Director(A,α)∩Director(A,β)=∅という関係が全ての A からの導出規則について成立すれば、得られた終端記号列から一意にプログラムで構文解析ができます。


private boolean A(){
  if(文字∈Director(A,α)){
    return αの処理が成功したか;
  }else if(文字∈Director(A,β)){
    return βの処理が成功したか;
  }...

  return false;
}


def A():
    if 文字∈Director(A,α):
        return αの処理が成功したか
    elif 文字∈Director(A,β):
        return βの処理が成功したか
    ...
    return False
}

ここで、Director 内で重複する終端記号はありませんので、文字はどこか一つの Director にだけ属するだけです。そのため、 α の処理などが失敗してもバックトラックの必要がありません。

さて、このような Director 集合の計算方法を与えます。なおプログラムの処理では次の一文字を読んで次の動きを決めます。そのため、終了判定を行うには終了したことがわかるように、入力文字が終ったことを示す特殊な文字を考えることがあります。

LL(1)文法は次のように形式化できます。 α は非終端記号、終端記号からなる列とします。また A は非終端記号とします。この時 First(α), Follow(A), Director(A,α) を次のように定義します。

First(α):: 導出ルールの右辺 α に対して、 α から導出可能な列の先頭になりうる終端記号の集合。もし、α から ε へ導出可能なら、ε も含めます。
Follow(A):: 非終端記号 A に対して、開始記号から導出をした時に、 A の直後になりうる終端記号の集合。
Director(A,α):: 各導出規則 A → α に対して、 Director(A,α) = First(α) 但し、 α から ε へ導出可能ならFollow(A) も含めます。この様に定義することで A→α の導出で、先頭に来る終端記号の候補を得ることができます。

例4-4

文法 G₂'についてこれらを計算すると次のようになります。

\begin{matrix} First (和 =) = {数} \\ First (数 和') = {数} \\ First (+ 数 和') = {+} \\ First (ε) = {ε} \\ Follow (始) = {ε} \\ Follow (和) = {=} \\ Follow (和') = {=} \\ Director (始, 和 =) = {数} \\ Director (和, 数 和') = {数} \\ Director (和', + 数 和') = {+} \\ Director (和', ε) = {=} \end{matrix}

このように各非終端記号に対して、その生成規則を示す Director 同士に共通部分がない文法を LL(1) 文法と言います。 G₂' は計算した Director に共通部分がないので LL(1) 文法です。実際、Director(和',⋅) は {+} と {=} なので共通部分はありません。

参考

なお G₁' についても同様に計算すると次のようになります。

\begin{matrix} First (和 =) = {数} \\ First (和 + 数) = {数} \\ First (数) = {数} \\ Follow (始) = {ε} \\ Follow (和) = {=} \\ Director (始 和 =) = {数} \\ Director (和 和 + 数) = {数} \\ Director (和 数) = {数} \end{matrix}

このように非終端記号「和」に対して、 Director(和, ・) に重複がありますので、 LL(1)文法ではありません。

LL(1) 文法は、先に示した素朴な関数呼出による構文解析に対して、次に来るものを判断して構文規則を変えることで構文解析ができるようになります。

各非終端記号に対応した関数を作ります。ここでは A とし、作る関数を A() とします。

Director(A,・)に応じてプログラムを書きます。 Director(A, B)={x,y}, Director(A, zuCw)={z} の時、次のようになります。


import java.util.Arrays;
private boolean isContained(char c, char[] set){
// set はソートされている必要あり
  return Arrays.binarySort(set,c)>=0;
}

private boolean A(){
   if(isContaind(文字,new char[]{'x','y'}){
     return B();
   }else if(isContaind(文字, new char[]{'z'}){
     次の文字を読む;
     if(文字 == 'u'){
       次の文字を読む;
       if(C()){
         if(文字 == 'w'){
           return true;
         }
       }
     }
   }
   return false;
}


def A():
    if 文字 in {'x','y'}:
        return B()
    elif 文字 in {'z'}:
        次の文字を読む
        if 文字 == 'u':
            次の文字を読む
            if C():
                if 文字 == 'w':
                    return True
    return False

例4-5

G₂' は LL(1) 文法なので、プログラムで構文解析できます。同様に Director により次のように計算できます(わかりやすいように日本語を使ってますので、このままでは動きません)。


private static boolean 始(){
   if(次 == 数){ // Director(始,和=)={数}
      if(和()){
        if(次 == '='){
          return true;
        }
      }
   }
   return false;
}
private static boolean 和(){
   if(次==数){ // Director(和,数和')={数}
      次を読む;
      if(和'()){
        return true;
      }
   }
   return false;
}
private static boolean 和'(){
   if(次=='='){ // Director(和',ε)
     return true;
   }else if(次=='+'){ // Director(和',+数和')
     次を読む;
     if(次==数){
       次を読む;
       if(和'()){
         return true;
       }
     }
   }
   return false;
}  
public static void main(String[] arg){
  次を読む;
  if(始()){
    System.out.println("Ok");
  }else{
    System.out.println("NG");
  }
}


def 始():
    if 次 == 数: # Director(始,和=)={数}
        if 和():
            if 次 == '=':
                return True
   return False

def 和():
    if 次==数: # Director(和,数和')={数}
        次を読む
        if 和'():
            return True
   return False

def 和'():
    if 次=='=': # Director(和',ε)
        return True
    elif 次=='+': # Director(和',+数和')
        次を読む
        if 次==数: 
            次を読む
            if 和'():
                return True
    return False

次を読む;
if 始():
    print("Ok")
else:
    print("NG")

例4-6

上記のプログラムにおいて、「次==数」の判定方法が自明ではありません。これまでのまとめとして、数字一桁の足し算の式を受理する(形を認識するだけで計算しない)プログラムを示します。文字を読み込むタイミングが、 Director の要素の判定時ではなく、判定を通った後の実際のルールの解釈時であることに注意します。


import java.io.*;
class Parser {
    final private Reader reader;
    public Parser(Reader r) throws IOException{
	reader = r;
	c = reader.read();
    }
    private int c;
    public boolean s() throws IOException{
	System.err.println("called s.");
	if(Character.isDigit(c)){
	    if(wa1()){
		if(c=='='){
		    c = reader.read();
		    return true;
		}
	    }
	}
	return false;
    }
    private boolean wa1() throws IOException{
	System.err.println("called wa1.");
	if(Character.isDigit(c)){
	    c = reader.read();
	    if(wa2()){
		return true;
	    }
	}
	return false;
    }
    private boolean wa2() throws IOException{
	System.err.println("called wa2.");
	if(c=='='){
	    return true;
	}
	if(c=='+'){
	    c = reader.read();
	    if(Character.isDigit(c)){
		// 足し算の処理
		c = reader.read();
		if(wa2()){
		    return true;
		}
	    }
	}
	return false;
    }
}
class Rei {
    public static void main(String[] arg) throws IOException{
	final Reader r = new InputStreamReader(System.in);
	final Parser parser = new Parser(r);
	if(parser.s()){
	    System.out.println("accept");
	}else{
	    System.out.println("reject");
	}
    }
}


class Reader:
    def __init__(self, string):
        self.l = list(string)
        self.p = 0

    def read(self):
        if self.p >= len(self.l):
            raise StopIteration()
        result = self.l[self.p]
        self.p += 1
        return result
        
class Parser:
    def __init__(self, r):
        self.reader = r
        self.c = self.reader.read()
    def s(self):
        print("called s.")
        if self.c.isdecimal():
            if self.wa1():
                if self.c=='=':
                    return True
        return False
    def wa1(self):
        print("called wa1.")
        if self.c.isdecimal():
            self.c = self.reader.read()
            if self.wa2():
                return True
        return False

    def wa2(self):
        print("called wa2.")
        if self.c=='=':
            return True
        if self.c=='+':
            self.c = self.reader.read()
            if self.c.isdecimal():
		# 足し算の処理
                self.c = self.reader.read()
                if self.wa2():
                    return True
        return False

r = Reader(input())
parser = Parser(r)
if parser.s():
    print("accept")
else:
    print("reject")

なお Pascal というプログラミング言語は LL(1) 言語です。したがって、 LL(1) は制限がきついですが、そこそこ実用的な文法まで表現できます。

トークンの切り出し

例4-3 では各関数で文字を読んでいました。このような処理の仕方はこれまでのプログラムは構造が異なっています。以下に構造を抽象的に示します。

前回までのプログラム


public static void main(String[] arg){
  前処理;
  while(文字を読みつづける){ // 読み込みは一ヶ所
    文字列の組み立て処理;
    文字列が完成したら出力;
  }
  後処理;
}


前処理
for 文字 in list(文字列):
    文字列の組み立て処理
    文字列が完成したら出力
後処理

今回のプログラム


class Parser { 
  private boolean 非終端記号1(){
    if(トークン∈Director(非終端記号1,α)){
       return α の処理;
    }else if(トークン∈Director(非終端記号1,β)){
       return β の処理;
    }...
    return false;
  }
  private boolean 非終端記号2(){
    トークンの列に応じて他の非終端記号を呼び出す;
    return true;
  }
...
}
/*
  α や β の処理中で文字を読み、終了判定も考慮される。
*/

class Rei {
  public static void main(String[] arg){
     if(開始記号()){
       System.out.println("受理");
     }else{
       System.out.println("拒否");
     }
  }
}


class Parser:
    def 非終端記号1(self):
        if トークン in Director(非終端記号1,α):
            return α の処理
        elif トークン in Director(非終端記号1,β):
            return β の処理
        ...
        return False
    def 非終端記号2(self):
        トークンの列に応じて他の非終端記号を呼び出す
        return True
...

# α や β の処理中で文字を読み、終了判定も考慮される。

if 開始記号():
    print("受理")
else:
    print("拒否")

プログラムの基本的なテクニックとして、入力、出力、処理を分割すると言う考え方があります。長きに渡って使ってきた、「ループの冒頭で文字を読み、終了条件を判定し、ループの中で出力作業を行う」というのは、確かにプログラミングの定石の一つではあります。しかし、今回のように複数の関数で共通のストリームから入力を読むという処理を付加することができません。

以前、オートマトンも主プログラムのループ内で処理してましたが、これを改め、呼び出すと字句が得られる関数を作ると便利です。字句を取り出す関数を getword と呼ぶことにします。これは正規表現の文字列を取り出す group メソッドのような働きをするものです。また、さらに今回は、「演算子」「数字」など複数の種類の字句を一つの getword で取り出す必要があります。つまり、getword の返すものは字句の種類と、実際の字句を示す文字列であるとします。

字句の定義はそれぞれの種類で別々にオートマトンで定義できれば、開始状態からε遷移により分岐すれば一つにまとめられます。これで最長一致により入力から字句を取り出すことを考えます。このとき、主プログラム中の入力ループによる字句の取り出しとは違い、次のふたつの問題があります。

字句の終端をどう判定するか？
ファイルの終端の処理をどうするか？

字句の終端の判定は、基本的には字句に含まれない文字を読み込んだ時になります。ここで、関数としては値を返して処理を主プログラムに戻すことになるのですが、問題は「字句に含まれない文字」の取扱いです。この文字は次の字句に含まれる可能性があります。したがって、関数が終了しても、次に関数が呼び出されたときに処理できるよう、関数自体がオブジェクトのように記憶領域を持ちその文字から処理を開始できるようにします。なお、この考え方は、入力がキューである場合は、関数が記憶領域を持たなくても、読み過ぎた入力を元に戻すという操作で実現できます。

次にファイルの終端の処理です。ファイルの終端を検出した場合、入力処理は終了ですが、そこで字句の検出も終了し、関数としては返すべき値があることも考えられます。つまり、ファイルの終端に達しても、関数は字句を戻すことがありえます。この場合も、関数がファイルの終端を記憶しながら、字句を返し、次の呼出で、字句を返せないことを示せばよいです。

このように、字句解析では、最長一致をするために、字句に含まれない次の文字を読んだ後、次の呼出でもう一度読み出す必要があります。

坂本直志 <[email protected]>
東京電機大学工学部情報通信工学科

第 4 回 文脈自由文法

本日の内容

4-1. 文脈自由文法

文法とルール

バッカス・ナウア記法

文法の例

P の定義

括弧の処理

例4-1

演習4-1

正規文法

例4-2

定理: 文脈自由文法に制限を与えた正規文法と、前回与えた正規文法は等 価である

演習4-2

4-2. 構文解析木

演習4-3

演習4-4

足し算の文法

文法 G0

文法 G1

文法 G1x

演習4-5

4-3. 文法を解釈するプログラム

素朴な解析法

例4-3

左再帰性の除去

文法 G1

文法 G2

文法 G1'

文法 G2'

再帰的下向き構文解析法

例4-4

参考

例4-5

例4-6

トークンの切り出し

前回までのプログラム

今回のプログラム

第 4 回文脈自由文法

定理: 文脈自由文法に制限を与えた正規文法と、前回与えた正規文法は等価である

文法 G₀

文法 G₁

文法 G_1x

文法 G₁

文法 G₂

文法 G₁'

文法 G₂'