これはcompiler designのクラスです。
recursive descent parser は日本語で・・・？
おぉ
再帰下降構文解析！！
なんだそれ！
難しそう！
日本語ムズカシイ！
それはいいとして、卒業したら忘れ去られるであろうことは、せっかくだから書きとめておきたい。
とりあえず簡単なところからいくと
S → ＋SS ｜ a
これですね。
S(){
switch(lookahead){
case('+'):
match('+');
S();
S();
case('a'):
match('a');
default:
error;
}
}
Sは＋かaから始まるから、まず最初のトークンを見て、もし＋だったら＋を食べて、S（）を２回呼ぶと。そのまんまだー。
もしaだったら、aを食べて戻ればいい。。と
まあpseudocodeなのでここらへんは適当に。
問題は、ambiguous な時と、left recursive がある時なので、こんなの（↓）になると面倒。
S → SS+ | SS- | a
left recursion じゃなくするってのが私としてはよくわからーん
まず、例をみると
A → Aa |b
まあ見るからにleft recursiveなんですが、それを取り払うためにこう考える・・・と
要するに・・・
Aが終わる時は必ずターミネーターのbで終わるから、Aの部分が最終的には必ずbになるってことですね。だから「Aは必ずbから始まる」と考えていいってことだよな？
だからAは必ず ba・・・a の形になる・・と？（bの次にaがずらっとくる）
まず最初のbは決まってるから、Aはbで始まるってことにしておいて、残りのaがどのくらい並ぶかは、A'で別処理しようってことになるんですね。
だから、まずはこうなる
A → bA'
で、問題はそのaの並びをどうやって決めるか。
A'では、ひたすらaを思うがままに並べたいだけだから、確実に一番最初はaになる。
で、その後、A'を好きなだけ繰り返して、飽きたらemptyにすればいいと。
だから、こうなる
A'→ aA' | empty
その結果、left recursive はなくなって、万事OK
じゃあ、この場合はどうよって話しだ。
応用できないとねぇ
S → SS+ | SS- | a
さっきのロジックにそってやっていきますと・・
まず、S は必ずaで始まるのは確実。
Sの形は必ずa...+ とか a...- とかの形になる。
...のところには、aとか+とか-とかがずらっと並ぶわけです。
だーかーらー、とりあえずS自体はaで始めてしまって、「...」の部分はまた別処理にする。
まずは
S → aS' に決定。
あとは、S'でaとか+とか-とかの並びを決める
こっからがよくわからーん
単純に S+ とか S- だけだったら、さっきみたいに S'→ +S' | -S' | empty でいいんだろうけど、なんつったってSが二つあるからそうはいかない。
これだと a++++---+-++-++ みたいな感じで、aの後にプラスかマイナスがひたすら並ぶだけになってしまうけど、a もプラスとかマイナスの前にちらほら混ざらないとだめなんです。
プラスとかマイナスの前にaを混ぜるってことは、S を使えばいいってことになるんだけど
ってことで、
S' → S + S' | S - S' | empty
必ずプラスかマイナスで終わらないといけないから、emptyになれるのはS'だけです。
こんな考え方であってるのかどうか・・
最後は正直無理やり。
自分でこれを基に別の応用問題から答えを引き出せるのかが問題だー
あーもう時間が遅いよ。
寝る時間だ。
これのrecursive descent parser は後にしよう。
recursive descent parser は日本語で・・・？
おぉ
再帰下降構文解析！！
なんだそれ！
難しそう！
日本語ムズカシイ！
それはいいとして、卒業したら忘れ去られるであろうことは、せっかくだから書きとめておきたい。
とりあえず簡単なところからいくと
S → ＋SS ｜ a
これですね。
S(){
switch(lookahead){
case('+'):
match('+');
S();
S();
case('a'):
match('a');
default:
error;
}
}
Sは＋かaから始まるから、まず最初のトークンを見て、もし＋だったら＋を食べて、S（）を２回呼ぶと。そのまんまだー。
もしaだったら、aを食べて戻ればいい。。と
まあpseudocodeなのでここらへんは適当に。
問題は、ambiguous な時と、left recursive がある時なので、こんなの（↓）になると面倒。
S → SS+ | SS- | a
left recursion じゃなくするってのが私としてはよくわからーん
まず、例をみると
A → Aa |b
まあ見るからにleft recursiveなんですが、それを取り払うためにこう考える・・・と
要するに・・・
Aが終わる時は必ずターミネーターのbで終わるから、Aの部分が最終的には必ずbになるってことですね。だから「Aは必ずbから始まる」と考えていいってことだよな？
だからAは必ず ba・・・a の形になる・・と？（bの次にaがずらっとくる）
まず最初のbは決まってるから、Aはbで始まるってことにしておいて、残りのaがどのくらい並ぶかは、A'で別処理しようってことになるんですね。
だから、まずはこうなる
A → bA'
で、問題はそのaの並びをどうやって決めるか。
A'では、ひたすらaを思うがままに並べたいだけだから、確実に一番最初はaになる。
で、その後、A'を好きなだけ繰り返して、飽きたらemptyにすればいいと。
だから、こうなる
A'→ aA' | empty
その結果、left recursive はなくなって、万事OK
じゃあ、この場合はどうよって話しだ。
応用できないとねぇ
S → SS+ | SS- | a
さっきのロジックにそってやっていきますと・・
まず、S は必ずaで始まるのは確実。
Sの形は必ずa...+ とか a...- とかの形になる。
...のところには、aとか+とか-とかがずらっと並ぶわけです。
だーかーらー、とりあえずS自体はaで始めてしまって、「...」の部分はまた別処理にする。
まずは
S → aS' に決定。
あとは、S'でaとか+とか-とかの並びを決める
こっからがよくわからーん
単純に S+ とか S- だけだったら、さっきみたいに S'→ +S' | -S' | empty でいいんだろうけど、なんつったってSが二つあるからそうはいかない。
これだと a++++---+-++-++ みたいな感じで、aの後にプラスかマイナスがひたすら並ぶだけになってしまうけど、a もプラスとかマイナスの前にちらほら混ざらないとだめなんです。
プラスとかマイナスの前にaを混ぜるってことは、S を使えばいいってことになるんだけど
ってことで、
S' → S + S' | S - S' | empty
必ずプラスかマイナスで終わらないといけないから、emptyになれるのはS'だけです。
こんな考え方であってるのかどうか・・
最後は正直無理やり。
自分でこれを基に別の応用問題から答えを引き出せるのかが問題だー
あーもう時間が遅いよ。
寝る時間だ。
これのrecursive descent parser は後にしよう。