形式言語理論

言語$L$の文法$G$とは、文が$L$に属すかどうか判定する規則である。

終端記号の集合

言語$L$の文字の集合。ただし、文字を直接扱うと煩雑なため、トークン(文字を組み合わせた単語のようなもの)の集合を使うことが多い。

非終端記号の集合

終端記号とは重ならない記号の集合。

開始記号

非終端記号の中の一つ。

規則の集合

規則は「左辺→右辺」の形をしている。左辺と右辺は、終端記号と非終端記号からなる列。

例えば、数値と四則演算から成る式の文法は次のようになる。ただし、数値は$n$というトークンで表す。

• 終端記号の集合{n,+,-,*,/}
• 非終端記号の集合$\{E,T\}$
• 開始記号$E$
• 規則の集合{E → E+E, E → E-E, E → T, T → T*T, T → T/T, T → n}

文法が与えられた時、次の手順によって文(終端記号の列)が生成できれば、その文は言語に属する。

1. 開始記号だけからなる列を考える。
2. ある規則の左辺と一致する部分があれば、その部分をその規則の右辺で置き換える。
3. 列の中に非終端記号が含まれなくなるまで繰り返す。

この列を、その文の導出列と呼ぶ。文から導出列を作り出すことをparseすると言う。

すべての規則の左辺が非終端記号1個であるような文法を、文脈自由文法と言う。そうでない文法を、文脈依存文法と言う。