文法がLR（1）であるかどうかを理解する

Question

文法が解析テーブル操作なしでLR（1）であるかどうかを理解するための練習が必要です。

文法が続いている：あなたは後ろのトリックが何であるかを

S -> Aa | Bb 
A -> aAb | ab 
B -> aBbb | abb 

知っていますか？

おかげで、:)

Answer 1

あなたはLR（1）パーサだとあなただけのbの先読みとaabを読んだことをことを想像してみてください。 （私は知っている、あなたはおそらく "男、私はいつも私に起こる！"と思っている）あなたはここで正確に何をすべきですか？

文法を見て、あなたが同時にAためとBのためのプロダクションルールを検討する必要があるとしているので、初期生産は、AaまたはBbであったかどうかわかりません。 Aオプションを見ると、A → abを減らすことができます。先読みがbであり、これは拡張時にabと表示されたときに見いだすことができるためですAがあります（ルールはA なので、再帰的に展開されたAの後にはbが続きます）。それは減らすように指示します。一方、Bのオプションを見てください。 とそれに続くbが表示されている場合は、「ああ、その2番目のbはaabbになるでしょう。B → abbこれは私がやりたいことなので、 m LR（1）パーサー。それはシフトするように指示します。その時点で、バム！シフト/リダクションの競合があるので、ほとんど確実にLR（1）文法を持たないでしょう。

これは実際には起こりますか？さて、私たちは本当にaabを読み、先読みとしてbを見なかったかどうかを確認したいLR（1）を、設定セットを構築手放す：

に

Initial State 
S' -> .S [$] 
S -> .Aa [$] 
S -> .Bb [$] 
A -> .aAb [a] 
A -> .ab [a] 
B -> .aBbb [b] 
B -> .abb [b] 

State after reading a 
A -> a.Ab [a] 
A -> a.b [a] 
A -> .aAb [b] 
A -> .ab [b] 
B -> a.Bbb [b] 
B -> a.bb [b] 
B -> .aBbb [b] 
B -> .abb [b] 

State after reading aa 
A -> a.Ab [b] 
A -> a.b [b] 
A -> .aAb [b] 
A -> .ab [b] 
B -> a.Bbb [b] 
B -> a.bb [b] 
B -> .aBbb [b] 
B -> .abb [b] 

State after reading aab 
A -> ab. [b] 
B -> ab.b [b] 

をそしてちょっと！私たちが話していたシフト/減少の競合があります。最初の項目はbで減少しますが、2番目の項目はbで減少します。だからそこに行く！私たちの直感は、これがLR（1）文法ではないと考えるように導いてくれました。テーブルを見ると、証拠はデータによってサポートされています。

これを試してみるとどうでしょうか？まあ、一般的に、これを行うのはかなり難しいです。少なくとも私の主な手がかりは、パーサーがある時点でAかBのいずれかを望んでいるかどうかを推測しなければならないということですが、それは結局のところbの数です。パーサーは、abが好きか、Aが好きか、それともabbが好きか、Bとするかどうかを判断する必要がありましたが、決定する前にbの両方を見ることはできません。それで私は、いくつかの再帰が起こっていることを知るのに十分なことが分かったところで（何故ならば、末尾のbが問題を引き起こすように）、再帰が異なる場所を見つけるために何らかの矛盾を見つけたいと思った2つの制作ルール