Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.2k views
in Technique[技术] by (71.8m points)

compiler construction - Show that an LR(1) grammar that is not LALR(1) must have only reduce/reduce conflicts

Can someone please explain to me why an LR(1) grammar that is not LALR(1) must have only reduce/reduce conflicts

question from:https://stackoverflow.com/questions/65906675/show-that-an-lr1-grammar-that-is-not-lalr1-must-have-only-reduce-reduce-conf

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)

Because if there were a shift-reduce conflict, it would also exist in the LR(1) parser.

The proof is in pretty well every textbook which introduces LALR parsing. The LALR algorithm merges states with the same statesets, so the possible shift actions are the same in the merged state as in every one of the original states. Furthermore, every reduction action in the merged state is in at least one of the original states. So if a reduction action in the merged state conflicts with a shift action, it must also conflict with that shift action in the original state(s) in which the reduction action appears.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...