top page > computer > programming > algorithm > parse > rg.html
更新日:
文責: 重城良国

正規文法

ウィキペディアの正規文法の説明

正規文法とは

ざっくり言えば「文字列のくりかえしだけで作成できる文法」である。文脈自由文法より狭い範囲の文法であり、正規文法で表現できる文法はすべて文脈自由文法でも表現可能である。

正規表現で表現可能な文法はこの範囲である。

右正規文法

書き換え規則で書くと以下のようになる文法。

A -> a
A -> aB
A -> ε

規則の左側に要素をつけ加えていくことで生成される文法。再帰的な定義を使用することで単純なくりかえしが表現できる。

左正規文法

書き換え規則で書くと以下のようになる文法。

A -> a
A -> Ba
A -> ε

規則の右側に要素をつけ加えていくことで生成される文法。

正規文法の左と右

左正規文法と右正規文法とは表現できる文法の範囲は同じである。左から並べていっても右から並べていくとしても表現力は変わらないということ。しかし、「両方可能」ということにすると表現できる範囲は広がる。この場合、表現できる範囲は文脈自由文法と同じとなる。

正規表現

ウィキペディアの正規表現の説明

正規文法の範囲の言語を簡単に表現できる方法として正規表現がある。最近の正規表現は拡張されていて正規文法の範囲を越えた範囲まで表現できるようになっているが、ここでは単純なもののみを扱う。

以下のような記号が使われる。

例えば「(g|yah)o+(gle)?」は以下の文字列にマッチする。gogle, google, yahoo,gooooooo, yahoooooooogle。日本語で言えば「gまたはyahに続いて1個以上のoが来る。その後にgleが来ても来なくても良い」となる。

正規表現の書き換え規則への変換例

上記「(g|yah)o+(gle)?」を書き換え規則で書き直してみる。ここでは右正規文法のほうを使う。

  1. YAHOOGLE -> g OOGLE
  2. YAHOOGLE -> y AHOOGLE
  3. AHOOGLE -> a HOOGLE
  4. HOOGLE -> h OOGLE
  5. OOGLE -> o OOGLE
  6. OOGLE -> o GLE
  7. GLE -> g LE
  8. LE -> l E
  9. E -> e
  10. GLE -> ε

gogleで置き換え規則を試してみよう。

  1. YAHOOGLEから開始する
  2. 規則1からg OOGLEとなる
  3. OOGLEを規則6によってo GLEとする
  4. GLEを規則7でg LEとする
  5. LEを規則8でl Eとする
  6. Eを規則9でeとする
  7. YAHOOGLEを置き換え規則に従ってgogleにすることができた
次はgoで試してみる。
  1. YAHOOGLEから開始する
  2. 規則1からg OOGLEとなる
  3. OOGLEを規則6でo GLEとする
  4. GLEを規則10でε(空文字列)とする
  5. これでYAHOOGLEをgoに置き換えることができた
次はgooooで試してみよう。
  1. YAHOOGLEから開始する
  2. 規則1からg OOGLEとする
  3. OOGLEを規則5でo OOGLEとする
  4. OOGLEを規則5でo OOGLEとする
  5. OOGLEを規則5でo OOGLEとする
  6. OOGLEを規則6でo GLEとする
  7. GLEを規則10でε(空文字列)とする
  8. YHOOGLEをgooooに置き換えられた

オートマトンとの関係

ウィキペディアのチョムスキー階層を参照。

正規文法は有限オートマトンに対応する。有限オートマトンについては後で説明のページを作成する予定。

「構文解析」トップへもどる

正当なCSSです! HTML5 Powered with CSS3 / styling, and Semantics