この前テレビを見ていたら「瀬戸内海の小島の段々畑で野菜を作っているお婆さん（多分70代）の話」をやっていました。
そのお婆さんは、祖父の「地を這って、土の声を聞け」という言葉を胸に農業を続けてきたそうです。
急斜面の段々畑での農作業を苦に思ったことはなく、毎朝頂上まで登るのが楽しみだそうです。野菜がお婆さんを待っていて、葉の色を見ると野菜が何を欲しがっているか分るそうです。すごいな、と思います。

＝＝＝＝LLとLR構文解析の話＝＝＝＝
LL(k)文法で作られた言語に対しては、LL(k)法という構文解析が可能になります。

LL(k)は、本を読むとゴタゴタ書いてあってよく分りません。ネットに雰囲気を伝えるものがあったので、ある本の記述とつなぎ合わせて、分り易くしました。

＝＝ネットから拾う＝＝
LL(1) 法というのは、構文のはじめの 1 トークン（入力）で構造を決定していく方法。

例えば「if」
っていうトークンを見たら即「ここからif文がはじまる！」と判定する。

また、もし「def」
っていうトークンを見たら「関数定義！」と決めつけちゃう。

LL(2) 法なら、はじめの２トークンまで見て決める。LL(3) なら、はじめの３トークン。以下略。

LL(k)法は、構文の開始よりkトークン先まで読んで構文を予測するので、 「k トークン予測先読み (prediction look-ahead) する」などと言います。

逆に、LL(1) じゃない文法も見てみよう。C言語。

「foo」
って先頭のトークン見ても、これから foo = 100; っていう代入文が始まるのか、 foo myfunc(); っていう関数宣言が始まるのか、はたまた foo[1](“hello”); という配列アクセスした上に関数呼び出しという怪しげな文が 始まるのか、まったく予測できない。こういうのは LL(1) じゃない。

＝＝ある本から拾う＝＝
それでは、生成規則(文法)を見てLL(1)かどうかを見分けるにはどうすればよいか？

Ｓ-> aSc | b

はLL(1)です。何故なら、２つの生成規則（Ｓ->aSc と　Ｓ->b）の右辺は、異なる文字（ a と　b）で始まっている。従って、最左導出の各ステップは１つの入力（トークン）で一意に決めることができる。

逆に、LL(1)でない生成規則は、次のようなものである。

Ｓ-> aAB
Ａ-> aA | a
Ｂ-> bSc

なぜなら、２つの右辺がaで始まっているので、一意に決められない。

LL(1)の構文解析例
次の文法でaabbcの導出を試みる。
S->AB
A->aA|a
B->bB|c

導出
S=>AB
=>aAB
=>aaB
=>aabB
=>aabbB
=>aabbc
終わり

文法がこんな簡単なら、導出の際の適用規則が簡単に分りますが、文法が複雑になると簡単にはいきません。どのタイミングでどの生成規則を適用するのかは、コンパイラで勉強してください。

＝＝＝
LR(1)は、入力文のお尻の方から生成規則を適用していきます。入力を１トークンづつスタックに移し、スタックの上の方のトークンに生成規則を当てはめていきます。この詳しいやり方もコンパイラで勉強してください。

＝＝
今日は２週間ぶりでテニスに行き、ミックスダブルスを１ゲームやって帰ってきました。一見９８％の回復ですが、まだ本調子じゃないですね。