LALRで解析できてLLで出来ない場合は？

すいません
今Haskellの勉強をしていて　Parsecという構文解析ライブラリを触っています
コンパイラというのを始めて作ってみて思ったのですが
Parsecでも四則演算やif文が動く状態まで作ってみて
LL文法でも結構なんでも解析出来ちゃう実感を感じてしまったのですが
yacc等で使われているLALR法で解析できるのにLL法で解析できない文法というのは
具体的にはどのような文法なのでしょうか？

特にどれでも良いので産業界で受け入れられているプログラミング言語の構文など出していただけると幸いです

No.2 ベストアンサー 回答者： siffon9 回答日時： 2013/07/25 06:10

こんにちは

HaskellのPersecで検索したところ、↓の参考URLのブログ記事がみつかりました。
左再帰の話題がでていますね。

expr ::= expr '+' term | term　の様な構文の場合
exprをパースする関数は、右辺の左端がexprであるので最初に自分自身が再帰的に呼ばれて無限再帰になってしまうということです。（Haskellはよく知らないので表現が的確か不安ですが）

ちなみに、同ブログ記事の中にBNFを変形して対応する方法が記載されていますが、これには演算子の結合方向が変化する違いが生じます。
a + b + c　という式の場合
本来であれば、(a + b) + c と評価されるべきところが
変形BNFでは、a + (b + c)と評価されてしまうということです。
足し算の場合はどちらも計算結果は同じですが、引き算になると結果が変わってきますよね。

以上、ご参考にしていただければ幸いです。

参考URL：http://d.hatena.ne.jp/kazu-yamamoto/20110127/129 …

この回答へのお礼

なんだか納得いきました
無限再帰は作っている最中、何度も出会っていたのですが構文解析というのはそれが当然と思ってしまっていました
実はこんな当たり前に回避できるものだったのですね

お礼日時：2013/07/26 01:16

No.1 回答者： Tacosan 回答日時： 2013/07/24 00:25

左再帰