Ich lerne gerade über Compiler und wie ich in LR (0) verstehe, gibt es Fälle, in denen wir "shift/reduce" oder "reduce/reduce" -Konflikte haben, aber "Shift/Shift" -Konflikte sind unmöglich! Warum können wir keinen "Shift/Shift" -Konflikt haben?Warum kann ein Compiler keinen "Shift/Shift" -Konflikt haben?
Verschiebungs-/Reduzierungskonflikte treten auf, wenn der Parser nicht unterscheiden kann, ob verschoben werden soll (das nächste Eingabetoken auf dem Parsingstapel drücken) oder reduzieren (eine Folge von Terminals und Nichtterminals aus dem Parsingstack entfernen). Ein Reduzierungs-/Reduzierungskonflikt liegt vor, wenn der Parser zu reduzieren weiß, aber nicht sagen kann, welche Reduktion ausgefü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 musste, 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, in dem zwei oder mehr Übergänge aus einem Parsing-Zustand mit demselben Terminal-Symbol hervorgingen. 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!
Der dritte Absatz ist sehr nützlich, danke! – alcuadrado
Es gibt reduce-reduce-Konflikte, weil es 2 Produktionen gibt, die ausgewählt werden können, um das Handle zu reduzieren. Es gibt Shift-Reduce-Konflikte, weil Sie mit etwas Produktion sowohl verschieben als auch reduzieren können und das Parsing offensichtlich immer noch vorwärts bringen. Shift bedeutet nur 1 Sache, du bringst den Input-Stream voran, es kann also keinen Shift-Shift-Konflikt geben. – axiom