- ベストアンサー
LALRで解析できてLLで出来ない場合は？
すいません 今Haskellの勉強をしていて Parsecという構文解析ライブラリを触っています コンパイラというのを始めて作ってみて思ったのですが Parsecでも四則演算やif文が動く状態まで作ってみて LL文法でも結構なんでも解析出来ちゃう実感を感じてしまったのですが yacc等で使われているLALR法で解析できるのにLL法で解析できない文法というのは 具体的にはどのような文法なのでしょうか？ 特にどれでも良いので産業界で受け入れられているプログラミング言語の構文など出していただけると幸いです
- m_matsubara
- お礼率60% (216/356)
- その他（プログラミング・開発）
- 回答数2
- ありがとう数2
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
こんにちは HaskellのPersecで検索したところ、↓の参考URLのブログ記事がみつかりました。 左再帰の話題がでていますね。 expr ::= expr '+' term | term の様な構文の場合 exprをパースする関数は、右辺の左端がexprであるので最初に自分自身が再帰的に呼ばれて無限再帰になってしまうということです。（Haskellはよく知らないので表現が的確か不安ですが） ちなみに、同ブログ記事の中にBNFを変形して対応する方法が記載されていますが、これには演算子の結合方向が変化する違いが生じます。 a + b + c という式の場合 本来であれば、(a + b) + c と評価されるべきところが 変形BNFでは、a + (b + c)と評価されてしまうということです。 足し算の場合はどちらも計算結果は同じですが、引き算になると結果が変わってきますよね。 以上、ご参考にしていただければ幸いです。
その他の回答 (1)
- Tacosan
- ベストアンサー率23% (3656/15482)
左再帰
関連するQ&A
- LL(n)構文解析機での高速化手法
プログラム言語の処理系の勉強のために、実際に処理系を作成してみています 四則演算などの基礎的なところが動くようになって喜んでいたのですが 次のような文法で大きく解析速度が落ちてしまうという問題が起きてしまいました (構文解析だけで１分ほどかかってしまいました) ->(n) do if( n.(==)(1), do 1 end, do n.(*)(fact(n.(-)(1))) end ) end 文法の詳細は何となく察していただくとして 解析速度の大きな低下の原因を探ってみたところ 括弧「()」の入れ子階層が深く入り組むほど倍々ゲームで解析速度が落ちている処まで絞り込めてきました おそらく閉じ括弧「)」を先読みしても間違ったものを拾って失敗しているのではないかなと推測しています 一応使っている環境は下に挙げますが おそらくはLL(n)構文解析での一般的な問題だと思いました どうすれば高速化できるか教えていただけないでしょうか？ ・開発言語はC# ・パーサー・コンビネーターでSparacheというライブラリを使用させていただきました https://github.com/sprache/Sprache ・ライブラリは開始括弧「(」をっ見つけると閉じ括弧「)」の先読みを、してくれている…様子です ・トークナイズや中間表現への変更は行わないで直接文字列をプログラムとして評価しています はじめて作ってみた処理系なので失敗してはその原因を調べなおして勉強しているものですが お知恵を貸していただければ幸いです
- 締切済み
- その他（プログラミング・開発）
- Pythonで構文解析する高速なライブラリを探しています
Pythonで、数式（Pythonの式ではない。二項演算・関数呼び出し・タプルなどがある）を解析し、構文木を作ろうとしています。 いままでSimpleParse・PLYを試しましたが処理が遅く、もっと速い方法を探しています。 SimpleParse・PLY・spark以外の構文解析ライブラリをご存知のかたは教えてください。 また、SimpleParseやPLYで高速に解析する方法があれば教えてください。 なお、yaccを使ってCで実装するのは最後の手段と言うことで
- 締切済み
- その他（プログラミング・開発）
- Extended regular expression matching and search library,
Extended regular expression matching and search library, このソースコードを見ています。 構文解析ルーチンのような感じがしますが、 そう理解してよいのでしょうか？ また、 LL（１）文法でかかれたものを コンパイラコンパイラ（構文解析作成ソフト） にかけたら、 これと同じような働きをするものを作れますか？ もし可能なら、 参考になるサイト、文献などを教えてください。 LGPLライセンスで困っています。 これにつかまりたくないのです。 よろしくお願いします。
- ベストアンサー
- C・C++・C#
- SQLの構文解析
プログラミング初心者ですがよろしくお願いします。 SQL文の字句、構文解析を行いたいと思っていて、SQL文が書かれたテキストファイルを入力とし、構文木もしくはそれににた情報を出力できるようなものがほしいです。 どこかにSQL構文のパーサーのソースコードライブラリは無いでしょうか？できればフリーがいいです。 C言語やflex,bisonなどのソースコードがあればいいのですが探しても見つかりません。どなたかご存じありませんか？よろしくお願いします。
- ベストアンサー
- その他（プログラミング・開発）
- プログラミング言語の記法について
現在構文解析や字句解析、コンパイラの勉強をしており、 プログラミング言語ごとの記法を比較しようと思っているのですが、検索してもなかなか出てきません。 定数,変数,選択文,副プログラムの記法など、プログラミング言語の記法を知るにはどうすればいいでしょうか？
- ベストアンサー
- その他([技術者向] コンピューター)
- コンパイラの構文解析（上向き）の習得
コンパイラの仕組みについて興味があり勉強しています。 構文解析について下向きの再帰降下法についてはコンパイラの入門書などにも説明があり、簡単なものであれば自分でコードを書けるレベルになりました。 次にyaccなどに使用されているという上向きの構文解析法（LR/SLR/LALR等）を学びたいと思いましたが、良い資料が見つかりません。 具体的には理論の説明（集合の式等が理解しにくいです）だけではなくて、簡単な式などを評価するソースコードや実際の動作が解説されているものがあれば嬉しいです。 ネット上あるいは市販の3000円台程度の書籍で良いものがありましたらご紹介いただけると嬉しいです。 よろしくお願いします。
- ベストアンサー
- その他（プログラミング・開発）
- プログラミングをはじめたいのですが・・・
私は学生なのですが、以前からプログラミングに興味があります。そこでプログラミングをはじめたいのですが、どうすればよいのでしょうか？ 特にWindowsプログラミングをやりたいと思っています。 学生むきパッケージのVisualStudio.NET 2003を購入しました。しかし、どのプログラミング言語を選ぶのがよいのか分かりませんし、MSDNライブラリの使い方もわかりません。MSDNライブラリでは、プログラミングについてどこまで説明されているんでしょうか？MSDNライブラリがあれば言語の仕様や文法もわかりますか？
- 締切済み
- その他（プログラミング・開発）
- 最近勉強していて、pythonという言語はインデントを元にブロック構造
最近勉強していて、pythonという言語はインデントを元にブロック構造を認識することができるらしいと知りました。 そこで疑問に思ったのですが、コンパイラは「字句解析」や「構文解析」といったステップがありますが、どのステップでブロック構造を認識できるのでしょうか。 予想では「構文解析」かと思ったのですが、正規表現では表せられないと思いました。 正規表現を使っていないだけなのかもしれませんが・・・ もしどのステップで認識するのか、分かる方がいらっしゃいましたら教えていただけると助かります。
- 締切済み
- その他（プログラミング・開発）
- 教育用コンパイラ
VB6やVB.NETで作られた教育用コンパイラを探しています。 できればソースから勉強したいです。 VisualStudio6,2005を持っているので、VB以外の言語で作られたものでも構いません。 スキャナーは理解できましたが、パーサー（構文解析）部と構文実行部が理解できていません。
- 締切済み
- Visual Basic
お礼
なんだか納得いきました 無限再帰は作っている最中、何度も出会っていたのですが構文解析というのはそれが当然と思ってしまっていました 実はこんな当たり前に回避できるものだったのですね