parsing - 無制限の先読みを必要とする文法?

Question

私はさまざまな種類のパーサーについて読んでおり、いくつかの論文で人々は無制限の先読みを必要とする文法について言及していますが、例は決して与えられていません。私が知っておくべき標準的な例はありますか?

Answer 1

無制限の先読みを必要とする曖昧さのない文法を思い付くのは簡単です。次の簡単なものを考えてみましょう。

• S→SX
• S→SY
• SX→XBx
• SY→YBy
• X→a
• Y→a
• B→b
• B→BB

ここでは、イニシャルを減らすか、入力の最後まで読むまで減らすかを決定できaませXんY。しかし、言語自体は明らかにLR（1）文法で解析可能であるため、これはそれほど興味深いことではありません。

LR（k）文法が存在しない言語もあります。正規の例は、明確な文法を持つすべての偶数長の回文配列（少なくとも2つのサイズのアルファベット）の言語だと思います。

• P2→P2a
• P2→bP2b
• P2→ε

少なくとも、これに無制限の先読みが必要な理由は直感的に理解できるはずです。入力のちょうど半分になるまで、いつ削減を行うかはわかりませんが、すべての入力を確認するまで、入力の長さを知ることはできません。 。