翻訳系構成論 2.構文解析と Yacc 構文規則(生成規則)

翻訳系構成論
2. 構文解析と Yacc
広島市立大学大学院
谷川一哉
熊本大学大学院
木山真人
構文規則(生成規則)
Yacc とは
• Y
e
tA
n
o
t
h
e
rC
o
m
p
i
l
e
rCompiler
の
略
• Yacc は BNF に似た構文規則に基づいてパーサー(構文解
析器}を生成
・まずは理論について学ぶ
・理論を理解しないと， Yacc でできること，できないことが
分からない.またデバッグもできない.
・その後で，実際のYacc プログラムに触れてみる
-構文規則
・文法記号の並べ方を規定する規則
.文法記号
・盤描E呈
. その文法で生成される文字列の一部を構成する要素
.非終端記号
・
文法の生成規則肉で使われる終端記号や非終端記号のグルー
プ名
構文規則の表記方法 1
x...
•
·A• X1X2…
• A: 非終端記号
• X1 X2・・・ x"，:文法記号(終端記号 or非終端記号)
・→
構文規則の表記方法
定義を表す畠星呈
・超記号:構文規則を表す記号
その他に r::=J や r=J が使われる
2
A→X 1 X2 ・ "X m I
Z1Z
:
!
"
'
z
.
"
• A→九Xz … xm
·A→z，Zz・..z."
.~盟副:構文規則の右辺は空でもよい
-省略が可能な時によく使われる
・空を表すのには rt:J 室E呈を使う
・→の左側の部分を主畢，右側の部分を圭畢，と呼ぶ
構文規則の例
t 桁以上の数字を表す文法(構文規則の集まり)
.数→数数字 l 数字
・数字→ 0111213141516171819
.A (非終端記号)は，
α( 終端記号) .あるいは，省略
可能
·A •t: la
•
AIまαの 1 回以上の繰り返し
·A•t: 1
Aa
文法と言語
-茎遺構文規則の集まり
開始記号:文法全体で最終的に定義したい非終端記号
般的に開始記号は構文規則の最初に示された規則の左
辺とすることが多い
・文法は.
C
T
.N
.P
.S】の
終
端
記
号
の
集
合
非
終
端
記
号
の
集
合
T.
.
構
文
規
則
の
集
合
P.
.
開
始
記
号
の
N.
S
4つ
で
表
さ
れ
る
文法の例(文法 2.1 )
-式→式+項 l 式・項|項
・項→項'因子 l 項 I 因子 l 因子
.因子→ I
問題
-文法2.1 において，終端記号，非終端記号，開始記号は
何か?
・文法2.1 を伍且旦旦を用いて表せ.
I
(式}
解答
-終端記号
+, ., *, I , (, )
.I
-非終端記号:式，項，因子
・開始記号:式
• T={+,·, *, I , (, )
.I}, N={式，項，因子}. s={式}， P={式→
式+項|式・項|項，項→項*因子|項 I 因子|因子，因
子→ I
I
(式)}
導出(生成)
.!C号夢ljvの中に現れる非終端記号A を構文規員IjA→α を
使って α に置き換え，記骨折Ijwが得られるとき， VはA→α
によってwを豊且する，という.
•
V司W
-文法2.1 の『式』からの導出.下線は導出の対象
・式司式+項司項+項司項+因子時
因子+因子=叫+因子時 i+l
・=が :0 回以上の導出，
~+: 1 回以上の導出，
"#
'
!
"'
&&
$ "%
"
abcde f
a
616263646520660a
61
input
input
expr
expr
expr
expr
term
term
term
factor
factor
factor
i
\n
i
+
i
\n
左再帰と右再帰
-文法記号αがあり， αが連続する記号列 mーを表すには
• (
1
)X→αIXa
，
主 E盟
・ (2)Y
，
宣
亘
畳
→α
l
a
Y
シフト還元動作を観察するため
のプログラムの改良
・
意
味
的
に
は
等
価
た
だ
し
必
要
な
ス
タ
ッ
ク
サ
イ
ズ
は
大
き
く
遭
う
ア
ク
シ
ョ
ン
:
ア
ク
シ
ョ
ン
と
は
.
Yacc
そ
の
ア
ク
シ
ョ
ン
の
直
前
ま
で
認
識
し
た
時
に
行
う
動
作
を
語
で
動
作
を
記
述
で
き
る
機
能
例
expr:
Yacc
の
構
文
規
則
中
の
機
能
プログラム 2.2 (2.1 改，その 1
lこ
，
あ
る
構
文
規
則
が
C言
expr{
a
c
t
i
o
n
1
}'
+
'term{action2};
アクションのE述は rOJ 肉に配述する
アクションはいくつ書いてもよい
action唱は直前の exprまでが認識された時点で実行される
•
action2 は直前の term までが認識された時点で実行される
)
1
. %{
2
. #Include<s
t
d
l
o
.
h
>
3
. %}
4
.% %
5
.
6
. inp
凶
:
7
.
;
expr'
¥
n
'{p
r
i
nt
f
("
c
o
r
r
c
texpression¥
n
"
);
}
8
. expr:expr'
+
'term{prlnt
f
("expr+term>exp 師 H); }
9
.
I
expr ・.' t
erm{prlntf("expr ・ term ・>exp時n"); }
1
0
. I
term
{p
r
l
n
t
f
(
"
t
erm>expr
¥
n
"
)
;}
1
1
. ;
'+
,
&
'-
$%.(#1"/
!)*
0%
演習 2.1
演
習 2.2
下
記
の
よ
う
な
-文法2.1 に闘して
2つ
の
文
法
が
あ
る
と
す
る
.
・文法を満たす最小の入力記号列を見つけよ
.x→ alXa.
左亙盟
・終端記号の全種類が現れ，かつ，最小の入力記号列を見つ
けよ
.y.→αlaY.
室亙盛
・プログラムを作成後
・上記の問題を実際に献してみよ
・入力記号列 n+ lJが文法2.1 がスタックを用いて解析さ
れる様子を示せ.
演習 2.3
-文法2.1 を逆ポーランドEj去に変更せよ
n
i
+
j
.
ni*j
を
満
た
す
か
ど
う
か
確
認
r
l
l
l
+
+j. rill恥」を満たすかどうか確認
r
l
l
l
*
+j. r
l
l
l
+
*j を
満
た
す
か
ど
う
か
確
認
・記号列 ααααの，左再帰での解析木と，右再帰での解析
木をそれぞれ示せ.
・記号列 αααα に対して，左再帰での構文規則を用いた場
合のスタックの様子と，右再帰での構文規則を用いた場
合を示せ.
逆ポーランド記法
-中置記法，中置形
.オペランドとオペランドの聞に演算子を書く
a+b*cのような，式の衰し方
・逆ポーランド記法
-オペランドの終わりに演算子を書く
abc*+ のような式の表し方