言語処理系のまとめ #1 - 某大学の講義録

そもそも何を勉強させられているのか

今のところは(5/21現在)
字句解析および構文解析
→コンパイラのフロントエンド部分の処理に使われている。

自分たちの書いたソースコードは機械や機械語に落とし込むコンパイラにしてみればただの文字列に過ぎない。それを適切に切り分けて対応した機械語へと翻訳するために、まずは字句解析および構文解析でソースコードの意味を解析する。
字句解析：ソースコードから単語を切り出す(=今回の記事)
構文解析：字句解析で単語を切り出した後、それらの単語から構文規則をチェックする。ついでに内部表現に落とし込む。(=次回以降の記事)

今回の記事はとりあえず字句解析の部分をまとめます。

字句解析

字句解析の一例
例えば下のようなコードがあった時、

int foo ( int a ) {
    int val ;
    if ( a > 0 ) {
        val = 10 * ( a + 3 ) ;
    } else {
        val = 10 * a + 3 ;
    }
    return val ;
}

字句解析によって以下のように単語(=トークン)毎に分割される。
f:id:rei_624:20190521002825p:plain

そして、これらの字句解析は何らかの規則によって分割するパターンを定義する必要がある。(例えばintやifのようにアルファベット複数の文字からなる単語で分割するようにしないと、i,n,tのようにそれぞれで分割されてしまう。)

字句解析のルール

例：<名前>→<英字>{<英字>|<数字>}*
というルールの時。(記号については後で)<名前>は必ず<英字>で始まり、その後ろに0個以上の<英字>または<数字>を繰り返したものと定義される。

 | := または。今回の場合は<英字>または<数字>
{}* := スター閉包。0個以上の{}内の文字の繰り返し
{}+ := 正スター閉包。1個以上の{}内の文字の繰り返し(==スター閉包からεを除いたもの。)

また、上記の例を状態遷移図で表すと以下の図のようになり、ここでは最終的に2に到達する文字列のみが受理され(=<名前>であった)、それ以外は不受理(=<名前>でなかった)と判断される。

f:id:rei_624:20190604112218p:plain

上記の生成規則を満たす例：waseda、masakari

上記を満たす状態遷移図さえ作ることができれば、字句解析器を自動生成することができる。
→字句の表現方法を定義することで状態遷移表を生成する。(=字句をある規則に従った文字列の集合とみなす。)

正規表現

基本的な用語の定義(一部再掲)

アルファベット
・記号(シンボル)の有限集合→{a, b, c, d}など
記号列
・記号の列(0文字以上の記号の連続)→{a, ab, abcd}など
・一つも記号がない記号列をεとする
集合の積
・A,Bを記号列の集合とした時、ABの集合の積は
　→AB={xy|x $\in$ A, y $\in$ B}
$A^*$ (スター閉包)
・0個以上の{}内の文字の繰り返し
$A^+$ (正スター閉包)
・1個以上の{}内の文字の繰り返し(==スター閉包からεを除いたもの。)

正規表現

詳しくは情報数学のスライドか教科書を見てください(オートマトン・言語理論)
ある記号の有限集合 $\mathit{\Sigma}$ 上の正規表現と定義されるもの
・空集合
・{ε}
・aを $\mathit{\Sigma}$ 中のある1要素としたとき、{a}
・ $R$ 、 $S$ をそれぞれ $\mathit{\Sigma}$ 上の正規表現とした時、以下の3つ
　1. $R|S$
　2. $RS$
　3. $R^*$
あとは上記を有限回繰り返して得られる集合のみが $\mathit{\Sigma}$ 上の正規表現である。