Linke Rekursion und rechte Rekursion erzeugen denselben Syntaxbaum oder nicht?

Question

Dies ist die richtige Rekursion Grammatik:

<assign> -> <id> = <exp> 
<id> -> A | B | C 
<exp> -> <term> + <exp> | <temp> 
<term> -> <factor> * <term> | <factor> 
<factor> -> (<exp>) | <id> 

Dies ist Linksrekursion Grammatik:

<assign> -> <id> = <exp> 
<id> -> A | B | C 
<exp> -> <exp> + <term> | <term> 
<term> -> <term> * <factor> | <factor> 
<factor> -> (<exp>) | <id> 

Wird jene Grammatik den gleichen Parse-Baum für String B + C + A produziert? Das folgende Bild ist für die linke Rekursion.

jedoch zeichne ich der Parse-Baum für die rechte Rekursion, es zwischen der Position der Knoten sind ein bisschen anders. Ich weiß nicht, ob das, was ich tue, richtig ist. Ich frage mich also, ob Left Recursion und Right Recursion zwei verschiedene Parse-Bäume erzeugen oder der gleiche Parse-Baum sein sollten. Bitte helfen Sie dieses Problem zu klären. Vielen Dank.

Answer 1

Die linke und rechte Rekursion erzeugt keine identischen Bäume.
Sie können leicht aus den Grammatiken, dass A+B+C wird auf der „oberen Ebene‘ haben <term> <op> <exp> oder <exp> <op> <term> (‚exp‘ Wesen ‚B + C‘ in einem Fall und ‚A + B‘ in dem anderen.

Die Bäume werden nur in trivialen Fällen identisch sein, wo alle Produktionen eine direkte Übereinstimmung ergeben.
(zB A (Überspringen assign) <exp> --> <term> --> <factor> --> <id>

Answer 2

wäre Da beide Grammatiken unterscheiden würde ich verschiedene Syntaxbäume erwarten. Die richtige Rekursion tauschen würde der Zusatz und die einzige Erweiterung auf dem Knoten an der Spitze, die mit <expr> = <expr> + <term> beschriftet ist Die Grammatik der richtigen Rekursion würde auf <expr> = <term> + <expr> expandieren, so dass beide Kinder ausgetauscht würden.

Wenn Sie versuchen, einen Compiler für mathematische Ausdrücke zu schreiben, ist eine Sache, die mehr zählt, die Vorrangstellung des Operators, aber nicht sicher, was Sie vorhaben.