Ich lerne derzeit über Compiler und wie ich in LR (0) verstehe, gibt es Fälle, in denen wir "shift / reduce" oder "reduce / reduce" -Konflikte haben, aber es ist unmöglich, "Shift / Shift" -Konflikte zu haben! Warum können wir keinen "Shift / Shift" -Konflikt haben?
Shift / reduce-Konflikte treten auf, wenn der Parser nicht erkennen kann, ob er verschiebt (das nächste Eingabe-Token auf den Parsing-Stack drückt) oder reduziert (eine Reihe von Terminals und Nonterminals aus dem Parsing-Stack entfernt). Ein Reduce / Reduce-Konflikt liegt vor, wenn der Parser zu reduzieren weiß, aber nicht sagen kann, welche Reduktion durchgeführt werden soll.
Wenn Sie einen Shift / Shift-Konflikt hätten, würde der Parser wissen, dass er das nächste Token auf seinen Parsing-Stack schieben muss, aber nicht wissen würde, wie es geht. Da es nur eine Möglichkeit gibt, das Token auf den Parsing-Stack zu schieben, kann es in der Regel keine Konflikte dieser Form geben.
Das heißt, es ist theoretisch möglich, dass ein Shift / Shift-Konflikt existiert, wenn Sie ein seltsames Setup hatten, bei dem zwei oder mehr Übergänge aus einem bestimmten Parsing-Zustand herausfanden, die mit demselben Terminal-Symbol beschriftet waren. Der Konflikt wäre in diesem Fall, ob man sich verschiebt und zu einem Staat geht oder wechselt und zum nächsten geht. Dies könnte passieren, wenn Sie versucht haben, einen Automaten in weniger Zustände zu komprimieren und dies falsch gemacht haben, oder wenn Sie versucht haben, einen nichtdeterministischen Parsing-Automaten zu erstellen. In der Praxis würde dies niemals passieren.
Hoffe, das hilft!
Tags und Links compilation parsing compiler-construction lr