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

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

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

４．１　文脈自由文法文脈自由文法 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 に対して曖昧性を除去するには，右結合優先順位：- > ^ > {* /} > {+ -}

４．２導出と解析木導出例： 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

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

Similar presentations

Presentation on theme: "言語処理系（５）金子敬一."— Presentation transcript:

Similar presentations

About project

フィードバック

ログインする

Auth with social network:

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

Similar presentations

Presentation on theme: "言語処理系（５） 金子敬一."— Presentation transcript:

Similar presentations

About project

フィードバック

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

Presentation on theme: "言語処理系（５）金子敬一."— Presentation transcript: