言語処理系（５）
金子敬一
４ プログラミング言語の構文の定義
４．１ 文脈自由文法
４．２ 導出と解析木
４．３ 文脈自由文法の能力
４．１ 文脈自由文法
• 文脈自由文法
−文脈自由文法
− BNF記法
プログラミング言語の
構文を指定
４．１ 文脈自由文法
•
書換え規則（生成規則）
文 → if 式 then 文 else 文
式 → 式 + 式
文 → begin 文の並び end
文の並び → 文 | 文; 文の並び
４．１ 文脈自由文法
• 書換え規則（生成規則）
 終端記号：言語の文字列の基本記号．
字句と同義
 非終端記号：文，式，文の並び，など
の構文上の分類
 出発記号：非終端記号の1つ．対象と
している言語を表す．
 生成規則：構文上の分類を他の分類
や終端記号から生成する規則
４．１ 文脈自由文法
• 書換え規則（生成規則）
文 → begin 文の並び end
文の並び → 文 | 文; 文の並び
文 → begin 文の並び end
文の並び → 文
文の並び → 文; 文の並び
４．１ 文脈自由文法
•
生成規則例
非終端記号
式 → 式 演算子 式
演算子 → +
式 → ( 式 )
演算子 → -
式 → - 式
演算子 → *
式 → id
演算子 → /
演算子 → ^
４．１ 文脈自由文法
•
表記上の約束
1. 次の記号は非終端記号
a. 式，文，演算子のようなゴシック
体の日本語による名前
b. アルファベットの最初の方のイタ
リック体の大文字
c. 文字S．これは出発記号
４．１ 文脈自由文法
•
表記上の約束
2. 次の記号は終端記号
a. １字の小文字a, b, c
b. +, - のような演算子記号
c. 括弧やコンマのような区切り記号
d. 数字0, 1, ..., 9
４．１ 文脈自由文法
•
表記上の約束
3. アルファベットの終わりの方の大文
字は文法記号（非終端記号または
終端記号）．主にX, Y, Z
4. アルファベットの終わりの方の小文
字は終端記号列．主にu, v, ..., z
４．１ 文脈自由文法
•
表記上の約束
5. Aを左辺に持つ生成規則全体をA
生成規則．A → a1, A → a2, ..., A →
akがA生成規則ならば，A→a1 | a2
| ... | akと書いても良い．a1, a2, ...,
akを代替と呼ぶ．
４．１ 文脈自由文法
•
表記上の約束
6. 小文字のギリシャ文字，例えばa, b,
g, は文法記号列を表す
7. 最初の生成規則の左辺を出発記号
４．１ 文脈自由文法
•
生成規則例
式 → 式 演算子 式
式 → ( 式 )
式 → - 式
式 → id
演算子 → +
演算子 → 演算子 → *
演算子 → /
演算子 → ^
E → E A E |
( E ) |
- E | id
A → + | - | * |
/ | ^
４．２ 導出と解析木
•
導出
g生成規則
a,b文法記号
abagb導出
４．２ 導出と解析木
•
導出
a1a2an
a1はanを導出する．
a1からanへの導出
４．２ 導出と解析木
•
導出
*： 0回以上の導出
+： 1回以上の導出
４．２ 導出と解析木
• 文と文形式
文脈自由文法G
出発記号S
L(G) : Gが
生成する言語
Gの文
w : 終端記号のみからなる文字列
S ⇒+ w ⇔ w ∈ L(G)
４．２ 導出と解析木
• 文と文形式
Gの文
w : 終端記号のみからなる文字列
S ⇒+ w ⇔ w ∈ L(G)
S ⇒+ a, a : 非終端記号を含みうる
Gの文形式
４．２ 導出と解析木
• 文と文形式
E → E + E | E * E | ( E ) |
- E | id
文
E ⇒
⇒
⇒
⇒
-
E
(
(
(
⇒ - ( E )
E + E )
id + E )
id + id )
文形式
４．２ 導出と解析木
• 文と文形式
E ⇒ - E ⇒ - ( E )
⇒ - ( E + E )
⇒ - ( id + E )
⇒ - ( id + id )
最左導出：導出
の過程で最も左
の非終端記号を
置換
ｃｆ．最右導出
４．２ 導出と解析木
• 解析木
− 置換え順序によらない図表現
E
E ⇒ - E ⇒ - ( E )
⇒ - ( E + E )
⇒ - ( id + E )
⇒ - ( id + id )
-
E
(
E
)
E
+
E
id
id
４．２ 導出と解析木
• 解析木
a1a2anから解析木を生成
1. a1の節点のみからなる木
2 ai=X1X2...Xkなる解析木に対して，
aiをai-1のXjをb=Y1Y2...Yrで置換し
て得るとき，ai-1を表す解析木のXj
に対応する葉に，左からY1, Y2, ...,
Y と名前を付けた子を与える
４．２ 導出と解析木
• 解析木
1 Eの節点のみからなる木
E
４．２ 導出と解析木
• 解析木
2. E ⇒ - E ⇒ - ( E )
E
E
(
E
)
４．２ 導出と解析木
• 解析木
2. - ( E ) ⇒ - ( E + E )
E
E
(
E
)
E
+
E
４．２ 導出と解析木
• 解析木
2. - ( E + E ) ⇒ - ( id +
E
E )
E
(
E
)
E
+
E
id
４．２ 導出と解析木
• 解析木
2. - ( id + E ) ⇒ - ( id +
E
id )
E
(
E
)
E
+
E
id
id
４．２ 導出と解析木
• 解析木
E ⇒ E + E ⇒ id + E
⇒ id + E * E ⇒ id + id * E
⇒ id + id * id
E ⇒ E * E ⇒ E + E * E
⇒ id + E * E ⇒ id + id * E
⇒ id + id * id
４．２ 導出と解析木
• 解析木
E ⇒ E + E ⇒ id + E
⇒ id + E * E ⇒ id + id * E
⇒ id + id * id
E
E
+
E
id
E
*
id
E
id
４．２ 導出と解析木
• 解析木
E ⇒ E * E ⇒ E + E * E
⇒ id + E * E ⇒ id + id * E
⇒ id + id * id
E
E
id
E
*
E
+
E
id
id
４．２ 導出と解析木
• 曖昧性
複数の解析木を生成する文法は曖昧
曖昧除去規則（結合性，優先順序）
４．２ 導出と解析木
左結合
• 曖昧性
E → E + E | E - E |
E * E | E / E |
E ^ E | ( E ) |
右結合 - E | id
に対して曖昧性を除去するには，
優先順位：- > ^ > {* /} > {+ -}
４．２ 導出と解析木
• 曖昧性
-
１次子
^
因子
* / 項
+ - 式
式 → 式+項 | 式–項 | 項
項 → 項*因子 | 項/因子 |
因子
因子 → １次子^因子 | １次子
１次子 → -１次子 | 要素
要素 → ( 式 ) | id
４．２ 導出と解析木
• 導出例： x + y * z
式 ⇒ 式+項
式 → 式+項 | 式–項 | 項
⇒項+項
項 → 項*因子 | 項/因子 |
⇒因子+項
因子
⇒１次子+項
因子 → １次子^因子 | １次子
⇒要素+項
１次子 → -１次子 | 要素
⇒id+項
⇒id+項*因子 要素 → ( 式 ) | id
⇒id+因子*因子
⇒…⇒id+id*因子⇒…⇒id+id*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 ⇒* ( x ) S
⇒* ( x ) y
４．３ 文脈自由文法の能力
• 文脈自由文法の例
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: 終端記号
w: 終端記号列
L1’ = {wcwR | wは(a|b)*に属する}
S→aSa|bSb|c
４．３ 文脈自由文法の能力
• 文脈自由でない言語
L2 = {anbmcndm | n>0かつm>0}
ただし，a, b, c, d: 終端記号
L2’ = {anbmcmdn | n>0かつm>0}
S→aSd|bAc
A → b A c| bc
４．３ 文脈自由文法の能力
• 文脈自由でない言語
L2 = {anbmcndm | n>0かつm>0}
ただし，a, b, c, d: 終端記号
L2” = {anbncmdm | n>0かつm>0}
S→AB
A → a A b| a b
B→cBd|cd
４．３ 文脈自由文法の能力
• 文脈自由でない言語
L3 = {anbncn | n>0}
ただし，a, b, c: 終端記号
L3’ = {anbn | n>0}
S→aSb|ab

83 KB

計算の理論 I －講義についてー

文法と言語

Document

計算の理論 I －講義についてー

第3章 ブール代数

独習JAVA

文法と言語