4

プログラミング言語を解析したい。形式言語、チョムスキー階層、ANTLR についてよく読んでいます。しかし、言語 ANTLR v3 を LL(*) 再帰降下パーサーが受け入れるようにチョムスキー階層に関連付ける方法に関する情報を見つけることができませんでした。

チョムスキー型はどのように LL(*) と混ざりますか? あらゆる情報 (オンライン、本、論文) は大歓迎です。

編集:構文/意味述語とANTLRのバックトラッキングはこれにどのようにマップされますか?

4

2 に答える 2

12

チョムスキー階層は基本的に次のとおりです。

  1. 正規言語
  2. 文脈自由文法
  3. 文脈依存文法
  4. 再帰的に列挙可能な (チューリング完全) 文法

LL 文法 (およびパーサー) は、文脈自由文法のサブセットです。通常の言語はプログラミング目的には弱すぎるため、また一般的なコンテキストフリーパーサーは O(n^3) であり、プログラムの解析には遅すぎるため、これらが使用されます。確かに、パーサーをヘルパー関数で拡張すると、パーサーはより強力になります。 LL パーサーに関するウィキペディアのエントリでは、このいくつかについて説明しています。Dragon Bookは、コンパイラに関する主要な教科書と見なされており、さらに詳しく説明されている可能性があります。

于 2009-01-14T09:24:06.547 に答える
4

LL(*) は文脈自由言語のサブセットです。ただし、別の問題は、antlr の能力を拡張する述語とバックトラッキングが与えられた場合に、antlr が何を解析できるかということです。

LL(*) について話す場合、それは 2 ではなく ANTLR v3 を意味することに注意してください。

于 2009-01-14T09:20:13.323 に答える