言語プロセッサ2005 -No.6-

言語プロセッサ2012
-No.5東京工科大学
コンピュータサイエンス学部
亀田弘之
これからの内容
1.
字句解析プログラムの作成方法
•
•
(手書きの方法)
Flexを利用する方法 <= こちらをマスターしよう！
•
•
•
•
解析手法の種類
左再帰とその除去
括りだし
FirstとFollow <= これが構文解析では一番重要
2. 構文解析
言語プロセッサ(東京工科大学)
2
正規表現の練習（確認）
• PCを立ち上げてください。
• HTMLのソースコードから情報を抽出して
みよう！
例） URLのタグは <[^>]+> で
マッチする。やってみよう！
言語プロセッサ(東京工科大学)
3
正規表現が活躍する例
• HTMLのリンク先情報を抽出したい
例： <a href=“www.teu.ac.jp”>
• メールアドレスを抽出したい
例： [email protected]
Q: どのような正規表現を
使えばいいのだろうか？
言語プロセッサ(東京工科大学)
4
正規表現は
字句解析でも活躍する
言語プロセッサ(東京工科大学)
5
例題１
字句解析の実際
• 「符号なし数」の字句解析
num → digit+ ( . digit+)? (E(+|-)?digit+)?
=> n → d+( . d+)? (E(+|-)?d+)?
=> num → d+(.d+|ε)( (E((+|-)|ε)) d+|ε) |ε)
例： 3.14159
6.02E23
1.38E-23
256
6.624E-34
言語プロセッサ(東京工科大学)
6
Flexのソースコード例
参考
D [0-9]
%%
[\t ] { printf("Tab or Space\n"); }
{D}+(\.{D}+)?(E(\+|\-)?{D}+)? {printf("%s\n", yytext); }
. { printf("NG %s\t", yytext); }
%%
言語プロセッサ(東京工科大学)
7
例題２
識別子のシンタックス
• letter → a|b|c|…|z|A|B|C|…|Z
• digit → 0|1|2|…|9
• id → letter (letter|digit)*
言語プロセッサ(東京工科大学)
8
Flexのコード例
LETTER
DIGIT
[a-zA-Z]
[0-9]
%%
[\t ] { printf("Tab or Space\n"); }
{LETTER}({LETTER}|{DIGIT})* {printf("id=%s\n",
yytext); }
. { printf("NG %s\t", yytext); }
%%
言語プロセッサ(東京工科大学)
9
符号なし数のシンタックス
•
•
•
•
•
digit → 0|1|2|3|4|5|6|7|8|9
digits → digit digit*
optional_fraction → . digits |ε
optional_exponent → (E(+|-|ε)digits)|ε
num → digits optional_fraction
optional_exponent
言語プロセッサ(東京工科大学)
10
トークン認識プログラム作成
• （教科書を参考に作成してみよう！）
言語プロセッサ(東京工科大学)
11
プログラムの文法（例)
言語プロセッサ(東京工科大学)
12
• stmt → if expr then stmt
| if expr then stmt else stmt
|ε
• expr → term relop term
| term
• term → id
| num
言語プロセッサ(東京工科大学)
13
•
•
•
•
•
•
if → if
then → then
else → else
relop → <|<=|=|<>|>|>=
id → letter(letter|digit)*
num → digit+(.digit+)?(E(+|-)?
言語プロセッサ(東京工科大学)
14
• delim → blank|tab|newline
• ws → delim+
言語プロセッサ(東京工科大学)
15
トークン-正規表現パタン
正規表現トークン属性値
（なし）
（なし）
ws
if
（なし）
if
then
（なし）
then
else
（なし）
else
id
記号表のエントリへの
id
num
ポインタ
num
relop
LT
<
relop
LE
<=
relop
EQ
=
relop
NE
<>
relop
GT
>
relop
GE
>=
言語プロセッサ(東京工科大学)
16
（参考）オートマトンの作成
• ここはあくまでも参考情報です。
あっさりと通り過ぎてしまいましょう。
言語プロセッサ(東京工科大学)
17
＝
０
＞
６
７
other
８
言語プロセッサ(東京工科大学)
18
1
０
＜
＝
2
Return(relop,LE)
＞
3
Return(relop,NE)
4
Return(relop,LT)
other
＞
＝
5
Return(relop,EQ)
６
＝
７ Return(relop,GE)
other
図. 関係演算子の遷移図
言語プロセッサ(東京工科大学)
８
Return(relop,GT)
19
letter
9
letter
10
digit
other
11
Return(get_token( ),
install_id( ))
図. 識別子とキーワードに対する遷移図
言語プロセッサ(東京工科大学)
20
17
digit
12
13
digit
digit
－
E
19
＋
.
16
other
digit
18
E
14
digit
15
digit
digit
図. 数の遷移図(1)
言語プロセッサ(東京工科大学)
21
digit
digit
20
digit
.
21
22
digit
23
24
digit
25
digit
26
other
27
図. 数の遷移図(2)
言語プロセッサ(東京工科大学)
22
例）単純な遷移図
b
a
a
1
2
0
b
言語プロセッサ(東京工科大学)
23
state = 0;
while(TRUE) {
switch(state) {
case 0: c = nextChar( ); /* 先読み */
switch(c){
case ‘a’: state = 1; break;
case ‘b’: state = 2; break; }
case 1: c = nextChar( );
switch(c){
case ‘a’: state = 2; break;
case ‘b’: state = 1; break; }
}
}
言語プロセッサ(東京工科大学)
24
state = 0;
while(TRUE) {
switch(state) {
case 0: c = nextChar( ); /* 先読み */
switch(c){
case ‘a’: state = 1; break;
case ‘b’: state = 2; break; }
case 1: c = nextChar( );
switch(c){
case ‘a’: state = 2; break;
case ‘b’: state = 1; break; }
}
}
言語プロセッサ(東京工科大学)
25
簡単な遷移図
b
a
a
26
a
25
b
28
27
b
言語プロセッサ(東京工科大学)
26
自主問題
1. 直前のページのオートマトンをシミュレー
トするプログラムを作成せよ。
2. 符号なし数を処理する字句解析プログラ
ムを作成せよ。
3. 次ページに示した（C言語の）浮動小数
点定数を処理する字句解析プログラム
を作成せよ。
言語プロセッサ(東京工科大学)
27
参考：（C言語の）浮動小数点定数
．
Numbers
Numbers
Numbers
f
．
e
+
Numbers
l
Numbers
E
－
言語プロセッサ(東京工科大学)
F
L
28
今度はflexを使ってみよう！
言語プロセッサ(東京工科大学)
29
手順
ライブラリ（ｆｌ）
Flex
Program
Flex
Lex.yy.c
文字列入力
gcc
a.exe
言語プロセッサ(東京工科大学)
出力
30
Flexプログラムの記述(1)
delim
ws
letter
digit
id
number
%%
[ \t\n]
{delim}+
[a-zA-Z]
[0-9]
{letter}({letter}|{digit})*
{digit}+(\.{digit}+)?(E[+\-]?{digit}+)?
言語プロセッサ(東京工科大学)
31
Flexプログラムの記述(2)
{ws}
{ /* do nothing */ }
If
{return(IF);}
Then
{return(THEN);}
else
{return(ELSE);}
{id}
{yylval = install_id( ); return(ID);}
{number} {yylval = install_num();
return(NUMBER);}
言語プロセッサ(東京工科大学)
32
Flexプログラムの記述(3)
“<”
“<=“
“=“
“<>”
“>“
“>=“
%%
{yylval = LT; return(RELOP);}
{yylval = LE; return(RELOP);}
{yylval = EQ; return(RELOP);}
{yylval = NE; return(RELOP);}
{yylval = GT; return(RELOP);}
{yylval = GE; return(RELOP);}
言語プロセッサ(東京工科大学)
33
Flexプログラムの記述(4)
install_id( ){
static int id_ptr=0;
return(id_ptr); }
install_num( ){
static int num_ptr=0;
return(num_ptr); }
言語プロセッサ(東京工科大学)
34
Flexのデモ
• （自分で実際に作ってみよう）
言語プロセッサ(東京工科大学)
35
手順
1. Flexのプログラムを書く。
2. Flexのプログラムをflexにかける。
3. 出力ファイルlex.yy.cをgccでコンパイル
する。
4. 出力a.exeを実行する。
5. さまざまな文字列を入力する。
言語プロセッサ(東京工科大学)
36
手順
ライブラリ（ｆｌ）
Flex
Program
Flex
Lex.yy.c
文字列入力
gcc
a.exe
言語プロセッサ(東京工科大学)
出力
37
実際の手順
C:\> flex sample01.l
C:\> gcc lex.yy.c –lfl
C:\> a.exe
それでは、実際にやってみよう。
言語プロセッサ(東京工科大学)
38
字句解析から構文解析へ
以上で、字句解析は終わり。
字句解析の次の処理は、構文解析でしたね。
言語プロセッサ(東京工科大学)
39
構文解析編（再）
言語プロセッサ(東京工科大学)
40
キーワード（構文解析）
• 上向き解析/下向き解析
（bottom up & top down）
• Backtracking
• 括りだし(factoring)
• 左再帰性
• First集合/Follow集合など
言語プロセッサ(東京工科大学)
41
いろいろな構文解析法
• 構文解析手法はとてもよく研究されており、
様々な手法が知られている。
• 例えば、
– Early法
– Chart法
などなど（余裕のある人はいずれ
勉強してください）
プチお知らせ
自然言語処理（CS学部３年後期開講科目，担当教員：亀田）
言語プロセッサ(東京工科大学)
42
• 処理対象の文法の性質を利用して、
より効率的な手法がいろいろと提案
されている。
言語プロセッサ(東京工科大学)
43
• 文脈自由文法
– Early法・Chart法など
• 通常のプログラミング言語は、文脈自由文
法ではないが、その構成要素の多くは文
脈自由文法で記述可能！
• 文法の制限の仕方にもいろいろある。
言語プロセッサ(東京工科大学)
44
LR文法とLL文法(1)
• LR文法に対する構文解析法（LR構文解析法）
→ bottom up 型
• LL文法に対する構文解析法（LL構文解析法）
→ top down 型
（教科書76-77ページ参照）
言語プロセッサ(東京工科大学)
45
LR文法とLL文法(2)
• LR文法に対する構文解析法（LR構文解析法）
→ bottom up 型＜＝自動生成向き(Bison)
• LL文法に対する構文解析法（LL構文解析法）
→ top down 型＜＝手作業可能
（教科書76-77ページ参照）
言語プロセッサ(東京工科大学)
46
LL(k)文法
• 構文解析は、文法規則（書き換え規則）を
適用しつつ進行。
• 適用すべき規則は、一般には複数個存在。
→ backtrack発生
→ 効率低下（回避すべき！）
• k文字先読で適用すべき規則が決定され
る文法がある！（LL(k)文法と呼ぶ）
Backtrackなし！
言語プロセッサ(東京工科大学)
これは
すご
い！
47
以下、LL(1)を取り扱います
言語プロセッサ(東京工科大学)
48
実例で考えよう！
1. 括りだし
2. 左再帰の回避
言語プロセッサ(東京工科大学)
49
１．括りだし（今日の話はここから）
• 文法
S → aBd
B → b | bc
• 入力： abcd
言語プロセッサ(東京工科大学)
50
a
b
c
言語プロセッサ(東京工科大学)
d
51
S
B
a
b
c
言語プロセッサ(東京工科大学)
d
52
S
B
a
b
c
?
言語プロセッサ(東京工科大学)
d
53
Backtrac発生！
S
B
a
b
c
言語プロセッサ(東京工科大学)
d
54
S
解析成功！
B
a
b
c
言語プロセッサ(東京工科大学)
d
55
• backtrack回避の方法
→ 括りだし
言語プロセッサ(東京工科大学)
56
１．括りだし
• 文法
S → aBd
B → b | bc
S → aBd
B → b (c |ε)
言語プロセッサ(東京工科大学)
57
左再帰の回避
A→Aβ
A
A
Fermat
β
A
無限降下だ！
β
58
言語プロセッサ
(東京工科大学)
左再帰の回避方法
• A→Aα|β
 A → βA’
A’ → αA’ | ε
（教科書81ページ参照）
言語プロセッサ(東京工科大学)
59
左再帰の例
E→E+T|T
T→T*F|F
F → ( E ) | id
言語プロセッサ(東京工科大学)
60
左再帰の回避
E→E+T|T
T→T*F|F
F → ( E ) | id
E → T E’
E’ → + T E’ | ε
言語プロセッサ(東京工科大学)
61
左再帰の回避
E→E+T|T
T→T*F|F
F → ( E ) | id
E → T E’
E’ → + T E’ | ε
T → F T’
T’ → * F T’ | ε
F → ( E ) | id
言語プロセッサ(東京工科大学)
62
LL(1)文法
• LL(1)文法は、１文字先読みすることで、適
用すべき規則が一意に決まる、という性質
を備え持っている。
• つまり、「A→α｜β」に対して、１文字先読
みすれば、「A→α」と「A→β」のどちらを
適用すればいいのかが決まる。
（効率のよい処理が望める）
言語プロセッサ(東京工科大学)
63
でも、与えられた文法がLL(1)文法であること
をどうやって知ることができるのだろうか？
言語プロセッサ(東京工科大学)
64
LL(1)文法の判定法
• First
• Follow
これは後日やりましょ
う。少し煩雑ですが、
難しくはありません。
でも重要ですよ！
言語プロセッサ(東京工科大学)
65

Download Report