言語処理系（５） 金子敬一

４　プログラミング言語の構文の定義 ４．１　文脈自由文法 ４．２　導出と解析木 ４．３　文脈自由文法の能力

４．１　文脈自由文法 文脈自由文法 BNF記法 プログラミング言語の 構文を指定

４．１ 文脈自由文法 書換え規則（生成規則） 文 → if 式 then 文 else 文 式 → 式 + 式 ４．１　文脈自由文法 書換え規則（生成規則） 文 → if 式 then 文 else 文 式 → 式 + 式 文 → begin 文の並び end 文の並び → 文 | 文; 文の並び

４．１ 文脈自由文法 書換え規則（生成規則） 終端記号：言語の文字列の基本記号．字句と同義 非終端記号：文，式，文の並び，などの構文上の分類 ４．１　文脈自由文法 書換え規則（生成規則） 終端記号：言語の文字列の基本記号．字句と同義 非終端記号：文，式，文の並び，などの構文上の分類 出発記号：非終端記号の1つ．対象としている言語を表す． 生成規則：構文上の分類を他の分類や終端記号から生成する規則

４．１ 文脈自由文法 書換え規則（生成規則） 文 → begin 文の並び end 文の並び → 文 | 文; 文の並び 文の並び → 文 ４．１　文脈自由文法 書換え規則（生成規則） 文 → begin 文の並び end 文の並び → 文 | 文; 文の並び 文の並び → 文 文の並び → 文; 文の並び

４．１ 文脈自由文法 生成規則例 非終端記号 式 → 式 演算子 式 式 → ( 式 ) 式 → - 式 式 → id 演算子 → + ４．１　文脈自由文法 生成規則例 非終端記号 式 → 式 演算子 式 式 → ( 式 ) 式 → - 式 式 → id 演算子 → + 演算子 → - 演算子 → * 演算子 → / 演算子 → ^

４．１ 文脈自由文法 表記上の約束 次の記号は非終端記号 式，文，演算子のようなゴシック体の日本語による名前 ４．１　文脈自由文法 表記上の約束 次の記号は非終端記号 式，文，演算子のようなゴシック体の日本語による名前 アルファベットの最初の方のイタリック体の大文字 文字S．これは出発記号

４．１ 文脈自由文法 表記上の約束 次の記号は終端記号 １字の小文字a, b, c +, - のような演算子記号 ４．１　文脈自由文法 表記上の約束 次の記号は終端記号 １字の小文字a, b, c +, - のような演算子記号 括弧やコンマのような区切り記号 数字0, 1, ..., 9

４．１ 文脈自由文法 表記上の約束 アルファベットの終わりの方の大文字は文法記号（非終端記号または終端記号）．主にX, Y, Z ４．１　文脈自由文法 表記上の約束 アルファベットの終わりの方の大文字は文法記号（非終端記号または終端記号）．主にX, Y, Z アルファベットの終わりの方の小文字は終端記号列．主にu, v, ..., z

４．１　文脈自由文法 表記上の約束 Aを左辺に持つ生成規則全体をA生成規則．A → a1, A → a2, ..., A → akがA生成規則ならば，A→a1 | a2 | ... | akと書いても良い．a1, a2, ..., akを代替と呼ぶ．

４．１　文脈自由文法 表記上の約束 小文字のギリシャ文字，例えばa, b, g, は文法記号列を表す 最初の生成規則の左辺を出発記号

４．１ 文脈自由文法 生成規則例 E → E A E | ( E ) | - E | id A → + | - | * | / | ^ ４．１　文脈自由文法 生成規則例 式 → 式 演算子 式 式 → ( 式 ) 式 → - 式 式 → id 演算子 → + 演算子 → - 演算子 → * 演算子 → / 演算子 → ^ E → E A E | 　( E ) | 　- E | id A → + | - | * | 　/ | ^

４．２　導出と解析木 導出 A → g : 生成規則 a, b : 文法記号 a A b ⇒ a g b : 導出

４．２　導出と解析木 導出 a1 ⇒ a2 ⇒ ... ⇒ an a1はanを導出する． a1からanへの導出

４．２　導出と解析木 導出 ⇒*： 0回以上の導出 ⇒+： 1回以上の導出

４．２ 導出と解析木 文と文形式 文脈自由文法G 出発記号S L(G) : Gが w : 終端記号のみからなる文字列 生成する言語 ４．２　導出と解析木 文と文形式 文脈自由文法G 出発記号S w : 終端記号のみからなる文字列 S ⇒+ w ⇔　w ∈ L(G) L(G) : Gが 生成する言語 Gの文

４．２ 導出と解析木 文と文形式 w : 終端記号のみからなる文字列 Gの文 S ⇒+ w ⇔ w ∈ L(G) ４．２　導出と解析木 文と文形式 w : 終端記号のみからなる文字列 S ⇒+ w ⇔　w ∈ L(G) S ⇒+ a, a : 非終端記号を含みうる Gの文 Gの文形式

４．２ 導出と解析木 文と文形式 E → E + E | E * E | ( E ) | - E | id ４．２　導出と解析木 文と文形式 E → E + E | E * E | ( E ) | - E | id E ⇒ - E ⇒ - ( E ) 　 ⇒ - ( E + E ) 　 ⇒ - ( id + E ) 　　⇒ - ( id + id ) 文形式 文

４．２ 導出と解析木 文と文形式 E ⇒ - E ⇒ - ( E ) ⇒ - ( E + E ) ⇒ - ( id + E ) ４．２　導出と解析木 文と文形式 E ⇒ - E ⇒ - ( E ) 　 ⇒ - ( E + E ) 　 ⇒ - ( id + E ) 　　⇒ - ( id + id ) 最左導出：導出の過程で最も左の非終端記号を置換 ｃｆ．最右導出

４．２ 導出と解析木 解析木 置換え順序によらない図表現 E ⇒ - E ⇒ - ( E ) ⇒ - ( E + E ) ４．２　導出と解析木 解析木 置換え順序によらない図表現 E E ⇒ - E ⇒ - ( E ) 　 ⇒ - ( E + E ) 　 ⇒ - ( id + E ) 　　⇒ - ( id + id ) E - ( E ) E + E id id

４．２ 導出と解析木 a1 ⇒ a2 ⇒ ... ⇒ anから解析木を生成 a1の節点のみからなる木 ４．２　導出と解析木 解析木 a1 ⇒ a2 ⇒ ... ⇒ anから解析木を生成 a1の節点のみからなる木 ai=X1X2...Xkなる解析木に対して，aiをai-1のXjをb=Y1Y2...Yrで置換して得るとき，ai-1を表す解析木のXjに対応する葉に，左からY1, Y2, ..., Yrと名前を付けた子を与える

４．２　導出と解析木 解析木 Eの節点のみからなる木 E

４．２　導出と解析木 解析木 E ⇒ - E ⇒ - ( E ) E E - E E - ( E )

４．２　導出と解析木 解析木 - ( E ) ⇒ - ( E + E ) E - E E - ( E ) ( E ) E +

４．２　導出と解析木 解析木 - ( E + E ) ⇒ - ( id + E ) E - E ( E ) E + E + id

４．２ 導出と解析木 解析木 - ( id + E ) ⇒ - ( id + id ) E - E ( E ) E + id id id ４．２　導出と解析木 解析木 - ( id + E ) ⇒ - ( id + id ) E - E ( E ) E + id id id id

４．２ 導出と解析木 解析木 E ⇒ E + E ⇒ id + E ⇒ id + E * E ⇒ id + id * E ４．２　導出と解析木 解析木 E ⇒ E + E ⇒ id + E ⇒ id + E * E ⇒ id + id * E ⇒ id + id * id E ⇒ E * E ⇒ E + E * E

４．２ 導出と解析木 解析木 E ⇒ E + E ⇒ id + E ⇒ id + E * E ⇒ id + id * E ４．２　導出と解析木 解析木 E ⇒ E + E ⇒ id + E ⇒ id + E * E ⇒ id + id * E ⇒ id + id * id E E + E id E * E id id

４．２ 導出と解析木 解析木 E ⇒ E * E ⇒ E + E * E ⇒ id + E * E ⇒ id + id * E ４．２　導出と解析木 解析木 E ⇒ E * E ⇒ E + E * E ⇒ id + E * E ⇒ id + id * E ⇒ id + id * id E E * E E + E id id id

４．２　導出と解析木 曖昧性 複数の解析木を生成する文法は曖昧 曖昧除去規則（結合性，優先順序）

優先順位：- > ^ > {* /} > {+ -} ４．２　導出と解析木 左結合 曖昧性 E → E + E | E - E | E * E | E / E | E ^ E | ( E ) | - E | id に対して曖昧性を除去するには， 右結合 優先順位：- > ^ > {* /} > {+ -}

４．２ 導出と解析木 曖昧性 - １次子 ^ 因子 * / 項 + - 式 式 → 式+項 | 式–項 | 項 ４．２　導出と解析木 曖昧性 - １次子 ^　　　因子 * /　項 + -　式 式 → 式+項 | 式–項 |　項 項 → 項*因子 | 項/因子 | 　　　　 因子 因子 → １次子^因子 | １次子 １次子 → -１次子 | 要素 要素 → ( 式 ) | id

４．２ 導出と解析木 導出例： x + y * z 式 ⇒ 式+項 ⇒項+項 式 → 式+項 | 式–項 | 項 ⇒因子+項 ４．２　導出と解析木 導出例： x + y * z 式 ⇒　式+項 ⇒項+項 ⇒因子+項 ⇒１次子+項 ⇒要素+項 ⇒id+項 ⇒id+項*因子 ⇒id+因子*因子 ⇒…⇒id+id*因子⇒…⇒id+id*id 式 → 式+項 | 式–項 |　項 項 → 項*因子 | 項/因子 | 　　　　 因子 因子 → １次子^因子 | １次子 １次子 → -１次子 | 要素 要素 → ( 式 ) | id

４．２ 導出と解析木 導出例： x + y * z 式 ⇒ 式+項 ⇒項+項 ⇒因子+項 ⇒１次子+項 ⇒要素+項 ⇒id+項 ４．２　導出と解析木 導出例： x + y * z 式 式 ⇒　式+項 ⇒項+項 ⇒因子+項 ⇒１次子+項 ⇒要素+項 ⇒id+項 ⇒id+項*因子 ⇒id+因子*因子 ⇒…⇒id+id*因子⇒…⇒id+id*id 式 + 項 項 項 * 因 因 因 １ １ １ 要 要 要 id id id

ちょっと休憩 （雑談）

言葉の語源 おくび ゲップのこと 江戸患い 脚気のこと 土左衛門 力士の名前から へちま （い）とうり→へちまうり おくび　　　　　 ゲップのこと 江戸患い　　　 脚気のこと 土左衛門　　　 力士の名前から へちま　　　　　（い）とうり→へちまうり ろくでもない　　ろく＝陸＝平坦

休憩おわり

４．３ 文脈自由文法の能力 正規表現と文脈自由文法 正規表現で表現可能 ⇒ 文脈自由文法で表現可能 ４．３　文脈自由文法の能力 正規表現と文脈自由文法 正規表現で表現可能 ⇒　文脈自由文法で表現可能 正規表現の方が，理解しやすく，効率のよい処理系を生成しやすい

４．３ 文脈自由文法の能力 文脈自由文法の例 S → ( S ) S | ε Sから導出される全ての文は，括弧の釣合がとれている ４．３　文脈自由文法の能力 文脈自由文法の例 S → ( S ) S | ε Sから導出される全ての文は，括弧の釣合がとれている 釣合のとれた括弧のみからなる文字列はすべて，Sから生成可能

４．３ 文脈自由文法の能力 文脈自由文法の例 S → ( S ) S | ε Sから導出される全ての文は，括弧の釣合がとれている S ⇒ ε ４．３　文脈自由文法の能力 文脈自由文法の例 S → ( S ) S | ε Sから導出される全ての文は，括弧の釣合がとれている S ⇒ ε S ⇒ ( S ) S ⇒* ( x ) S ⇒* ( x ) y

４．３ 文脈自由文法の能力 文脈自由文法の例 S → ( S ) S | ε 釣合のとれた括弧のみからなる文字列はすべて，Sから生成可能 ４．３　文脈自由文法の能力 文脈自由文法の例 S → ( S ) S | ε 釣合のとれた括弧のみからなる文字列はすべて，Sから生成可能 長さ0の空列εはSから導出可能 長さ2nの釣合う括弧の列w=( x ) y S ⇒ ( S ) S ⇒* ( x ) S ⇒* ( x ) y

４．３ 文脈自由文法の能力 文脈自由でない言語 L1 = {wcw | wは(a|b)*に属する} ただし，a, b, c: 終端記号 ４．３　文脈自由文法の能力 文脈自由でない言語 L1 = {wcw | wは(a|b)*に属する} ただし，a, b, c: 終端記号 　　　　　w: 終端記号列 L1’ = {wcwR | wは(a|b)*に属する} S → a S a | b S b | c

４．３ 文脈自由文法の能力 文脈自由でない言語 L2 = {anbmcndm | n>0かつm>0} ４．３　文脈自由文法の能力 文脈自由でない言語 L2 = {anbmcndm | n>0かつm>0} ただし，a, b, c, d: 終端記号 L2’ = {anbmcmdn | n>0かつm>0} S → a S d | b A c A → b A c| bc

４．３ 文脈自由文法の能力 文脈自由でない言語 L2 = {anbmcndm | n>0かつm>0} ４．３　文脈自由文法の能力 文脈自由でない言語 L2 = {anbmcndm | n>0かつm>0} ただし，a, b, c, d: 終端記号 L2” = {anbncmdm | n>0かつm>0} S → A B A → a A b| a b B → c B d | c d

４．３ 文脈自由文法の能力 文脈自由でない言語 L3 = {anbncn | n>0} ただし，a, b, c: 終端記号 ４．３　文脈自由文法の能力 文脈自由でない言語 L3 = {anbncn | n>0} ただし，a, b, c: 終端記号 L3’ = {anbn | n>0} S → a S b | a b