parsing - この文法は文脈自由ですか

Question

次の文法は文脈自由ですか? 私の印象は、パーサーがすでに解析されたものを解釈する必要がない場合、文法は文脈自由であるというものでした。次の文法では、それは必要ありませんが、私の同僚は、それが文脈依存であることを確信しています。

問題は、X が Y または Z 内にあるかどうかを知らずに、X のどの選択肢を一致させる必要があるかを判断できないことです。

X: ( "a" | "a" "b" )
Y: X "b" "c"
Z: X "d"

Answer 1

「コンテキスト依存」という用語は、LL パーサーでは機能するが、Strong LL (SLL) パーサーでは機能しない文法について議論するときに時々発生します。このような場合、LL パーサーを必要とする決定は、正確な決定を行うためにトップダウンの構文解析コンテキストに関する情報を必要とするため、「コンテキスト依存」と呼ばれることがあります。ただし、SLL 文法と LL 文法はどちらも文脈自由文法と見なされます。