parsing - SLR(1) または LR(1) 解析

Question

次の型のプロダクションが見つかった場合、 follow(A) を見つけます

あ→α

ここで α は ε でありえますか?

以下の例のように:

P → aPa | bPb | ε

α が ε である場合、それは LR(1) ではありません

Answer 1

はい、α は ε です。α は任意の文字列を表し、ε は文字列なので可能な α

このため、文法は LR(1) ではないため、SLR(1) でもありません (すべての SLR(1) 文法も LR(1) であるため)。

これを確認するために、LR(1) 構成セットを構築できます。

(1)  P' -> .P     ($)
     P  -> .aPa   ($)
     P  -> .bPb   ($)
     P  -> .      ($)

(2)  P  -> a.Pa   ($)
     P  -> .aPa   (a)
     P  -> .bPb   (a)
     P  -> .      (a)

この時点で、shift/reduce の競合があるため、停止できます。a端子 が与えられた P → ε をシフトするか、減らすかを判断できませんa。

より高度な数学を使用して、この言語 (すべての偶数回文の言語) には LR(1) 文法がないことを証明できます。これは、LR(1) 文法を持つ言語が正確に決定論的文脈自由言語であり、すべての偶数回文のセットが決定論的文脈自由言語ではないためです。

お役に立てれば！