この前テレビを見ていたら「瀬戸内海の小島の段々畑で野菜を作っているお婆さん(多分70代)の話」をやっていました。
そのお婆さんは、祖父の「地を這って、土の声を聞け」という言葉を胸に農業を続けてきたそうです。
急斜面の段々畑での農作業を苦に思ったことはなく、毎朝頂上まで登るのが楽しみだそうです。野菜がお婆さんを待っていて、葉の色を見ると野菜が何を欲しがっているか分るそうです。すごいな、と思います。
====LLとLR構文解析の話====
LL(k)文法で作られた言語に対しては、LL(k)法という構文解析が可能になります。
LL(k)は、本を読むとゴタゴタ書いてあってよく分りません。ネットに雰囲気を伝えるものがあったので、ある本の記述とつなぎ合わせて、分り易くしました。
==ネットから拾う==
LL(1) 法というのは、構文のはじめの 1 トークン(入力)で構造を決定していく方法。
例えば「if」
っていうトークンを見たら即「ここからif文がはじまる!」と判定する。
また、もし「def」
っていうトークンを見たら「関数定義!」と決めつけちゃう。
LL(2) 法なら、はじめの2トークンまで見て決める。LL(3) なら、はじめの3トークン。以下略。
LL(k)法は、構文の開始よりkトークン先まで読んで構文を予測するので、 「k トークン予測先読み (prediction look-ahead) する」などと言います。
逆に、LL(1) じゃない文法も見てみよう。C言語。
「foo」
って先頭のトークン見ても、これから foo = 100; っていう代入文が始まるのか、 foo myfunc(); っていう関数宣言が始まるのか、はたまた foo[1](“hello”); という配列アクセスした上に関数呼び出しという怪しげな文が 始まるのか、まったく予測できない。こういうのは LL(1) じゃない。
==ある本から拾う==
それでは、生成規則(文法)を見てLL(1)かどうかを見分けるにはどうすればよいか?
S-> aSc | b
はLL(1)です。何故なら、2つの生成規則(S->aSc と S->b)の右辺は、異なる文字( a と b)で始まっている。従って、最左導出の各ステップは1つの入力(トークン)で一意に決めることができる。
逆に、LL(1)でない生成規則は、次のようなものである。
S-> aAB
A-> aA | a
B-> bSc
なぜなら、2つの右辺がaで始まっているので、一意に決められない。
LL(1)の構文解析例
次の文法でaabbcの導出を試みる。
S->AB
A->aA|a
B->bB|c
導出
S=>AB
=>aAB
=>aaB
=>aabB
=>aabbB
=>aabbc
終わり
文法がこんな簡単なら、導出の際の適用規則が簡単に分りますが、文法が複雑になると簡単にはいきません。どのタイミングでどの生成規則を適用するのかは、コンパイラで勉強してください。
===
LR(1)は、入力文のお尻の方から生成規則を適用していきます。入力を1トークンづつスタックに移し、スタックの上の方のトークンに生成規則を当てはめていきます。この詳しいやり方もコンパイラで勉強してください。
==
今日は2週間ぶりでテニスに行き、ミックスダブルスを1ゲームやって帰ってきました。一見98%の回復ですが、まだ本調子じゃないですね。