このページでは、文脈自由文法と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個)は要素ではない
- 「英小文字a〜zが1回以上、続いて数字0〜9が0個か1個」は
- 正規表現の短縮:
- tanaka と tanuka:
tanaka|tanuka→ 違いは4文字目だけなのでtan(a|u)ka
- tanaka、tanuka、tanouka:
tan(a|o?u)ka
- tanaka と tanuka:
混同しやすいペア
- 字句解析(字句の切り出し:正規表現、有限オートマトン)/構文解析(並べ方のチェック:文脈自由文法、BNF)
- 字句規則(文字 → 字句)/構文規則(字句の並べ方)
- 非終端記号(書きかえられる。BNFでは< >)/終端記号(これ以上書きかえられない)
- 3つ組み(演算子,左,右)/4つ組み(+結果の置き場所)
- 逆ポーランド(後置)(演算子が右。後行順=左→右→節)
- 下降型(上から下へ)/上昇型(下から上へ)
- 正規表現の *(0回以上)/+(1回以上)/?(0か1回)
- 構文図の 1回以上/0回以上/0か1回