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

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

Download Report