形式言語

このページでは、文脈自由文法とBNF、構文図の読み方、構文木から3つ組み・4つ組み・逆ポーランド表記を作る方法、正規表現のメタ記号の意味がわかります。

  • 記号の書き方(このメモのルール):

    • 本来は上に線を引いて表す「否定」「補集合」は、論理なら ¬A、集合なら Aᶜ と書く
    • 2乗などのべき乗は 2³、σ² のように書く。log の底は log₂ のように書く
  • 一言で言うと:

    • プログラム言語の「文法」を記号で決め、コンパイラがその文法に沿って文を分解し、正しいかチェックし、中間のコードにする話。

文法を決める(形式文法と言語処理)→ 文法の書き方(BNF・構文図)→ 解析して中間語にする(構文木・逆ポーランド)→ 字句のパターン(正規表現)

覚え方の軸

  • 解析は2段階で、道具がそれぞれ決まっている:
    • 字句解析=字句規則=正規表現=有限オートマトン
    • 構文解析=構文規則=文脈自由文法=BNF
  • 文脈自由文法は G=(N,T,P,S):
    • 非終端記号N、終端記号T、生成規則P、開始記号S。生成規則の左辺は必ず非終端記号1つ
  • BNFは「再帰」で繰り返しを表す:
    • <式>::=<項>|<式><加減演算子><項>。括弧を使えるようにするなら <因子>::=数|'(‘<式>’)’
  • 構文木から中間語へ:
    • 3つ組(演算子,左,右)、4つ組(+結果の置き場所)、逆ポーランド(後行順=左→右→節)
  • 正規表現のメタ記号は5つ:
    • [m−n](範囲の1文字)、*(0回以上)、+(1回以上)、?(0か1回)、|(又は)

形式文法と言語処理:文法を記号で決める

  • 自然言語:
    • ふだん使っている言語
  • 人工言語:
    • 特定の目的のために作られた言語。そのうちコンピュータ処理のための言語がプログラム言語。ほとんどの構文は文脈自由文法で表せる
  • 言語:
    • 1つの規則に基づく文の集合
  • 形式文法:
    • 言語を作る規則を抽象化したもの。基本的なものに句構造文法、文脈依存文法、文脈自由文法、正規文法がある
    • 形式文法で作られる抽象的な言語を形式言語という
  • 文脈自由文法(形式文法):
    • G=(N,T,P,S)で定義する
    • N:
      • 非終端記号の集合(書きかえの対象になる記号)
    • T:
      • 終端記号の集合(これ以上書きかえられない記号)
    • P:
      • 書換え(生成)規則の集合
    • S:
      • 開始記号(書きかえを始める最初の非終端記号)
    • 特徴:
      • 書換え規則の左辺が必ず1つの非終端記号
    • 文脈自由言語:
      • 文脈自由文法で作られる文の集合
  • 例(★試験では正しい生成の過程が問われる):
    • N={S}、T={0,1}、P={S→ε,S→0S1}
    • ①S ⇒ 0S1 ⇒ 01
    • ②S ⇒ 0S1 ⇒ 00S11 ⇒ 0011
    • つまり、この文法は「0をn個並べたあとに1をn個並べた列」(ε、01、0011、000111、…)を作る
    • ε:
      • 空列(長さ0の記号列)
    • 記号「→」は生成の実行(左辺の非終端記号を、規則に従って右辺で置きかえる)。右辺は長さ0以上の、非終端記号と終端記号の並び
  • 言語の構成要素(小さい順):
    • 文字 < 字句(トークン)< 文 < 言語
  • 字句:
    • トークンともいう。文を作る最小の単位
  • 字句規則:
    • 文字から字句を作るための規則
  • 構文規則:
    • 字句の正しい並べ方の規則
  • プログラムを実行する前に、文法に基づいて翻訳(コンパイル)する。字句解析と構文解析を自動化するには、字句規則と構文規則をきちんと定義する必要がある
  • 例(括弧を使わない四則演算の式。price*3−tax など)
    • 字句規則:
      • 数は、0〜9の数文字からなる長さ1以上の列
      • 変数は、a〜zの英小字から始まる長さ1以上の列
      • 演算子は、+、−、*、/のどれか
    • 構文規則:
      • 数は式。変数は式。「式 演算子 式」と並べたものも式
    • この式を作る文脈自由文法:
      • N={式,S}、T={数,変数,演算子}、P={S→式,式→数,式→変数,式→式 演算子 式}
  • 字句解析:
    • 字句規則に基づいて、字句の検査と切り出しを行う
    • 字句規則は正規表現で表せる。正規表現には、それと等価な有限オートマトンがある。字句解析は、この有限オートマトンで行う
    • 例:
      • 「数」は正規表現 [0-9]+ で表せる。Q₀から数字で Q₁(受理)へ、Q₁で数字が続けば Q₁ のまま
  • 構文解析:
    • 切り出した字句を構文規則に従って解析し、文法的に正しいかを検査する
    • 構文規則は文脈自由文法で表せる。それを形式的に書く代表的な記法がBNF

構文規則の記述:BNFと構文図

  • BNF記法:
    • Algol60の構文規則を書くのに使われた記法。今も多くのプログラム言語の構文規則に使われる
    • 文脈自由文法を形式的に書く代表的な方法。構文規則だけでなく、字句規則にも使う
  • BNFの記号
    • ::=:
      • 左辺と右辺の区切り(右辺で左辺を定義する。is defined as)
    • |:
      • 又は(or)
    • < >:
      • 非終端記号をくくる(<数字>、<英字>)
    • a、b、c…、0、1、…9:
      • 終端記号
  • 例:
    • <英数字>::=<英字>|<数字>
    • <数字>::=0|1|2|…|9
    • <英字>::=a|b|c|…|z
  • 算術式(四則演算)の構文(★よく出る)
    • <式>::=<項>|<式><加減演算子><項>
    • <項>::=<因子>|<項><乗除演算子><因子>
    • <因子>::=数
    • <加減演算子>::=+|−
    • <乗除演算子>::=*|/
    • ポイント:
      • */が<項>の中、+−が<式>の中にあるので、掛け算・割り算が先にまとまる
  • 括弧を追加する場合(★試験で書きかえが問われる):
    • <因子>::=数|'(‘<式>’)’
    • 括弧の中身を<因子>として扱えば、括弧の中が先に計算される
  • 再帰的定義:
    • 自分の定義に自分自身を使うこと(<式>の定義に<式>が出てくる)。BNFではこれで「繰り返し」を表す(★よく問われる)
  • 構文図:
    • BNFを、矢印でたどれる図にしたもの。再帰的な定義が読みやすくなる
    • <式>の読み方:
      • 「<項>1つでも<式>」「<式>に<加減演算子>と<項>が続いたら、また<式>」
  • 基本構文図:
    • ①Aが1回以上現れる
    • ②Aが0回以上現れる
    • ③Aが0回か1回現れる
    • ④AかBが現れる
  • 例:
    • <偶数長列>::=<組>|<偶数長列><組>、<組>::=<記号><記号>、<記号>::=a|b
    • <偶数長列>は「2文字の組が1個以上」なので、長さが2の倍数。「abba」は合う、「aba」(3文字)は合わない

構文解析の技法:構文木と中間語

  • 構文木(解析木):
    • 構文解析で、字句が構文規則に合っているかを構文解析表で調べながら、字句を木の形で表したもの
    • 算術式の構文木を、特に算術木という
    • 例:
      • Y=A+B*C−D の構文木は、根が「=」、その下に Y と「−」、「−」の下に「+」と D、「+」の下に A と「*」、「*」の下に B と C
  • 下降型構文解析法:
    • 文法に沿って、構文木を上から下へ作る
  • 上昇型構文解析法:
    • 構文木を下から上へ作る
  • 構文規則に合った文と判断されたら、次は意味解析に進む。構文解析の結果から、3つ組み、4つ組み、逆ポーランド表記法などで中間語(中間コード)を作る
  • 3つ組み:
    • 構文木の下のほうの部分木から順に、「演算子,左の項,右の項」の形でまとめる
    • 例(上の式):
      • L1(*,B,C)、L2(+,A,L1)、L3(−,L2,D)、L4(=,Y,L3)
  • 4つ組み:
    • 3つ組みに、各部分木の演算結果を何に置くかを追加したもの
    • 例(上の式):
      • L1(*,B,C,T1)、L2(+,A,T1,T2)、L3(−,T2,D,T3)、L4(=,T3,∅,Y)
      • L1 は「B*Cの結果をT1に入れる」という意味。∅は空値
  • 逆ポーランド表記法(★):
    • 演算子を、演算の対象(演算数)の右側に書く記法。後置表記法ともいう
    • 構文木からの変換:
      • 構文木を深さ優先で、後行順序木として(帰りがけのなぞり。左→右→節の順)たどる。各ノードを最後に出るときに読む
    • 例:
      • Y=A+B*C−D → Y A B C * + D − =
    • 式から直接変換する方法:
      • 最後に作用する演算から始めて、内側へ順に「[演算数,演算数]演算子」の形にしていき、最後に括弧とカンマを取る
      • [Y,(A+B*C−D)]= → [Y,[(A+B*C),D]−]= → [Y,[[A,(B*C)]+,D]−]= → [Y,[[A,[B,C]*]+,D]−]= → Y A B C * + D − =
    • 例:
      • (A+B)×C → A B + C ×(括弧の中のA+Bを先に計算してからCを掛ける)

正規表現:字句のパターンを決める

  • 正規表現:
    • 字句記号や探索記号の定義などに広く使われるパターン定義法。正規式ともいう
  • 記号列:
    • 0個以上の記号を並べたもの。a₁a₂a₃…aₙ と書く
    • 記号列の長さ:
      • 記号の個数
    • 空列:
      • 長さ0の記号列。記号 ε
  • アルファベット V:
    • 記号列の材料になる有限集合。Vから要素を(重複してよい)取り出して作った記号列を「V上の記号列」という
  • V*:
    • V上の記号列すべての集合。字句は V* の部分集合
    • 例:
      • V={x,y}なら、V*には x、y、xy、yyx、xxyx、… が含まれる
  • 正規表現のメタ記号(メタ文字。★意味は試験問題に示される)
    • [m-n]:
      • m〜n までの連続した文字のうちの1文字
    • *:
      • 直前の正規表現の0回以上の繰返し
    • +:
      • 直前の正規表現の1回以上の繰返し
    • ?:
      • 直前の正規表現が0個か1個
    • r1|r2:
      • r1 又は r2
  • *、+、?の違い
    • GOO*:
      • GO、GOO、GOOO など(2つ目のOなしもよい)
    • GOO+:
      • GOO、GOOO、GOOOO など(2つ目のOが最低1つ)
    • GOAL?:
      • GOA 又は GOAL
  • 例:
    • 「英小文字a〜zが1回以上、続いて数字0〜9が0個か1個」は [a-z]+[0-9]?
    • abc、x7、hello3 などがこの集合の要素。hello35(数字2個)は要素ではない
  • 正規表現の短縮:
    • tanaka と tanuka:
      • tanaka|tanuka → 違いは4文字目だけなので tan(a|u)ka
    • tanaka、tanuka、tanouka:
      • tan(a|o?u)ka

混同しやすいペア

  • 字句解析(字句の切り出し:正規表現、有限オートマトン)/構文解析(並べ方のチェック:文脈自由文法、BNF)
  • 字句規則(文字 → 字句)/構文規則(字句の並べ方)
  • 非終端記号(書きかえられる。BNFでは< >)/終端記号(これ以上書きかえられない)
  • 3つ組み(演算子,左,右)/4つ組み(+結果の置き場所)
  • 逆ポーランド(後置)(演算子が右。後行順=左→右→節)
  • 下降型(上から下へ)/上昇型(下から上へ)
  • 正規表現の *(0回以上)/+(1回以上)/?(0か1回)
  • 構文図の 1回以上/0回以上/0か1回

← 01 基礎理論の目次に戻る

タイトルとURLをコピーしました