Unterschied zwischen: ‚beseitigt linke Rekursion‘ und ‚eine äquivalente eindeutige Grammatik konstruieren‘

Question

Zum Beispiel:

R → R bar R|RR|R star|(R)|a|b 

eine äquivalente eindeutige Grammatik konstruieren:

R → S|RbarS S→T|ST 
T → U|Tstar U→a|b|(R) 

Wie wäre es zu beseitigen linke Rekursion für R → R bar R|RR|R star|(R)|a|b?

Was ist der Unterschied zwischen Eliminate left-recursion und construct an equivalent unambiguous grammar?

Answer 1

Eine eindeutige Grammatik ist eine, bei der es für jede Zeichenfolge in der Sprache genau eine Möglichkeit gibt, sie aus der Grammatik abzuleiten. Im Zusammenhang mit der Compiler-Konstruktion besteht das Problem der mehrdeutigen Grammatik darin, dass aus der Grammatik nicht ersichtlich ist, was der Parse-Baum für eine gegebene Eingabe-Zeichenfolge sein soll. Einige Tools lösen dies mit ihren Regeln zur Auflösung von Mehrdeutigkeiten, während andere einfach die Grammatik als unzweideutig einstufen müssen.

Eine linksrekursive Grammatik ist eine, bei der die Ableitung für ein gegebenes Nicht-Terminal dasselbe Nicht-Terminal wieder erzeugen kann, ohne zuerst ein Terminal zu erzeugen. Dies führt zu unendlichen Schleifen in Parsern mit rekursivem Abstieg, aber es gibt keine Probleme für shift-reduce-Parser.

Beachten Sie, dass eine unzweideutige Grammatik immer noch rekursiv und eine Grammatik ohne linke Rekursion immer noch mehrdeutig sein kann. Beachten Sie außerdem, dass Sie abhängig von Ihren Tools möglicherweise nur Mehrdeutigkeiten entfernen müssen, aber keine Linksrekursion, oder Sie müssen möglicherweise die Linksrekursion entfernen, aber nicht die Mehrdeutigkeit (obwohl eine eindeutige Grammatik im Allgemeinen vorzuziehen ist).

Der Unterschied ist, dass die Beseitigung von Linksrekursion und Mehrdeutigkeit verschiedene Probleme lösen und in verschiedenen Situationen notwendig sind.