Parsing mit Klammern und verschiedene Arten von Ausdrücken

Question

Ich verwende derzeit happy zum Parsen einer Sprache, aber ich denke nicht, dass der Parser relevant ist, außer zu sagen, es ist ein LALR-Parser. Hier ist ein kleiner Auszug aus der Grammatik:

ArithExpr -> ArithExpr + ArithExpr 
ArithExpr -> (ArithExpr) 
ArithExpr -> ... 

BoolExpr -> ArithExpr == ArithExpr 
BoolExpr -> (BoolExpr) 
BoolExpr -> ... 

Das Problem ist, dass ich immer Konflikte Verminderungs reduzieren. Ich denke, das Problem entsteht, wenn ich versuche, so etwas wie die folgenden zu analysieren:

((2 + 3) == (4 + 5)) 

Es gibt nur einen Weg, um diesen Ausdruck zu analysieren, aber das Problem ist, ich denke, auch bei der ersten Klammer beginnt der Parser einige Probleme hat. Der Grund dafür ist, dass der Parser nicht weiß, ob er in Zukunft mit ArithExpr oder BoolExpr konfrontiert wird, und da er nur einen Token Lookahead hat, muss er eine willkürliche Entscheidung treffen, die falsch sein kann.

Gibt es überhaupt eine Neuschreibung der Grammatik, um diese Sprache zu akzeptieren? Oder sollte ich wirklich nur beide ArithExpr und BoolExpr nur als eine einheitliche Expr analysieren und mit den tatsächlichen Typen während der Typprüfung befassen?

Answer 1

Sie sollten nur Expr analysieren und die Typprüfung während der semantischen Analyse durchführen. Sonst wird es Ihnen wirklich schwerfallen, entweder mit eingeklammerten Ausdrücken zu arbeiten (Sie können nicht feststellen, um welchen Typ es sich handelt, bis zu spät) oder erstklassige boolesche Werte (eine Variable könnte einen booleschen Wert haben, nein?).

Siehe my answer here für eine Alternative (aber es gibt am Ende den gleichen Rat); Ich stelle den Link der Vollständigkeit halber nur zur Verfügung, weil ich wirklich nicht überzeugt bin von dem Wert der Techniken, die in dieser Antwort beschrieben sind, aber ich denke, es ist im Wesentlichen dieselbe Frage mit einem anderen LALR-Parser-Generator.