パーサーを構築する方法はいくつありますか？

Question

私は、いわゆる適応LL（*）アルゴリズムに基づいたパーサージェネレータであるANTLR v4について学んでいます。 LL（*）アルゴリズムと比較して大きな改善点であると主張している。しかし、私はLRのようないくつかのアルゴリズムについても聞いた。パーサを構築するためにどのように多くの現代のアルゴリズム

• あります

  ので、好奇心から全体像を取得しますか？

• ANTLRのアダプティブLL（*）アルゴリズムの利点/限界は何ですか？

Answer 1

パーサーを構築するためにいくつの現代的なアルゴリズムがありますか？

まず、一般的なパーサージェネレータのリストを見ることができます。
参照：Comparison of parser generatorsおよび見出しParsing algorithmを参照してください。

ALL(*) 
Backtracking Bottom-up 
Backtracking LALR(1) 
Backtracking LALR(k) 
GLR 
LALR(1) 
LR(1) 
IELR(1) 
LALR(K) 
LR(K) 
LL 
LL(1) 
LL(*) 
LL(1), Backtracking, Shunting yard 
LL(k) + syntactic and semantic predicates 
LL, Backtracking 
LR(0) 
SLR 
Recursive descent 
Recursive descent, Backtracking 
PEG parser interpreter, Packrat 
Packrat (modified) 
Packrat 
Packrat + Cut + Left Recursion 
Packrat (modified), mutating interpreter 
2-phase scannerless top-down backtracking + runtime support 
Packrat (modified to support left-recursion and resolve grammar ambiguity) 
Parsing Machine 
Earley 
Recursive descent + Pratt 
Packrat (modified, partial memoization) 
Hybrid recursive descent/operator precedence 
Scannerless GLR 
runtime-extensible GLR 
Scannerless, two phase 
Combinators 
Earley/combinators 
Earley/combinators, infinitary CFGs 
Scannerless GLR 
delta chain 

パーサジェネレータに加えて、解析する他のアルゴリズム/手段もあります。特にPrologはDCGであり、正式なトレーニングなしに最初のパーサを最初から書いた人の多くは、通常recursive descentで始まります。また、Chart parserおよびLeft corner parser。

パーザを書く際に、私が常に尋ねる最初の質問は、Chomsky hierarchyの中で最も高いタイプの言語の文法をどうやって作ることができるかということです。ここで、最低はタイプ0であり、最高はタイプ-3である。

タイプ2の文法（context-free grammars）のほぼ90％は、より簡単なタスクではタイプ3の文法（regular grammars）です。私はタイプ1の文法（context-sensitive grammars）とタイプ0の文法（unrestricted grammars）で実験しました。

ANTLRのアダプティブLL（*）アルゴリズムの利点/制限は何ですか？実用的な観点からAdaptive LL(*)で Adaptive LL(*) Parsing: The Power of Dynamic Analysis

は、あなたがより速くあなたがいるのでできるだけ多くの解析理論を理解する必要がないため、作業パーサに文法から取得することができます：

Terrence ParrAdaptive LL(*)の作成者によって書かれた紙を参照してください。 Adaptive LL(*)は、あなたが知らないうちに文法に載せている鉱山を踏み外すのに十分な機敏さです。これは、あなたが知らないうちに文法に入れた鉱山の中には、パーサーの実行時に非効率につながるものがあるということです。

最も実用的なプログラミング言語の目的では、Adaptive LL(*)で十分です。 IIRC Adaptive LL(*)を行うことができないタイプ0文法（unrestricted grammars）私が言ったようにPrologのDCGは、しかし、ほとんどの人と最も一般的なプログラミングタスクのみ3.

はまた、ほとんどのパーサジェネレータは、タイプ2のためのもののいずれかのタイプ2またはタイプを必要とすることができましたしかし、それは彼らがタイプ1をやっていないか、あるいはタイプ0をすることができないということを意味するものではありません。

解析ツールまたはライブラリを使用するたびに、それを使用する方法とできないことを学習する学習曲線があります。あなたが/解析を字句する新機能で、本当にそれはもっとしてコースを受講および/またはこのテーマに書かれていCompilers: Principles, Techniques, and Tools (2nd Edition)