Predictive Parser LL (1) Zustand

Question

Lasst uns sagen, dass wir den vorhersagenden Parser ll verwenden (1).Warum ist es notwendig, dass

$ erster (\ alpha) \ cap zuerst (\ beta)=emeleyet $ ,

für alle $ \ alpha, \ beta $ rechte Seite der alternativen Produktionen d. H. Produktionen, die mit demselben Nicht-Terminal verbunden sind.Warum ist dieser Zustand notwendig?

Answer 1

Hier ist eine intuitive Erklärung:

Es folgt im Wesentlichen aus der Art von LL (1) Parsers: LL (1) Parsers erstellen einen ll (1) Parsing-Tisch. Die Reihen des Tisches sind Nichtterminals, und die Säulen sind Klemmen. Wir können über ll (1) nachdenken, wie (1) TABLE-Lookups beim Anstoß jedes Symbols in der Eingabe angenommen werden: Wir betrachten den von dem aktuellen nichtterminalen und dem Eingangsanschluss bestimmten Eintrag und wenden Sie eine entsprechende Produktionsregel an. Somit kann die Tabelle LL (1) nicht bei jedem Eintrag mehrere Produktionsregeln enthalten, ansonsten kann der Parser nicht entscheiden, welche Regel auftragen kann.

Wenn die rechte Seite einer Produktion $ \ alpha $ , $ \ beta $ überkreuzt Erste Sets, dann hatten wir mehrere Regeln auf einem einzigen Eintrag in der ll (1) Tabelle (dh duplizierenden / widersprüchlichen Einträgen) --- Die nichtriviale Kreuzung der ersten Sets hindert uns im Wesentlichen daran, den lL (1) Parsing-Tisch zu erstellen.

Wenn Sie immer noch unklar sind, warum diese Bedingung erforderlich ist (1) Parsing-Tabelle oder Verwenden Sie einen der Online-Visualisierungstools ; Sie finden sofort einen Konflikt.