Kapitel 2: Syntaxanalyse

Was lernen wir in diesem Kapitel?

Die Rolle des Parsers
Kontextfreie Grammatiken
Eine Grammatik schreiben
Parsing-Techniken
. Top-Down-Parsing
. Bottom-up Parsing - 6 Stunden

2.1 Einführung
Jede Programmiersprache wie C oder PASCAL hat Regeln, die die syntaktische Struktur vorschreiben.
Struktur von wohlgeformten Programmen. Die Syntax von Programmiersprachenkonstrukten kann
Durch CFG oder BNF (Backus Naur Form) Notation beschrieben werden. Der Parser bestimmt das
Syntax oder Struktur eines Programms. Das heißt, es überprüft, ob die Eingabe syntaktisch korrekt ist.
Korrekt oder nicht. Bevor wir weiter fortfahren, lassen Sie uns sehen, was eine kontextfreie Grammatik ist, was
ist Ableitung und einige andere wichtige Begriffe, die in den kommenden Kapiteln verwendet werden.

2.2 Kontextsensitive Grammatiken

Was ist eine kontextfreie Grammatik?

Definition: Die kontextfreie Grammatik, kurz CFG, ist ein 4-Tupel G = (V, T, P, S), wobei
V ist die Menge der Variablen. Die Variablen werden auch Nicht-Terminals genannt.
T ist die Menge der Terminals.
P ist die Menge der Produktionen. Alle Produktionen in P sind der Form A→ α, wobei A ein Anonym ist.
terminaland α ist eine Zeichenkette von Grammatiksymbolen.
S ist das Startsymbol.

Ex 1: Grammatik zur Erzeugung von einem oder mehreren a's ist unten dargestellt:
A → a | aA
Beispiel 2: Die Grammatik zur Erkennung einer Wenn-Anweisung ist unten dargestellt:
S→iCtS|iCtSeS|a
C→b
2.2 Syntaxanalysator
woi – steht für wenn Schlüsselwort
t steht für das Schlüsselwort
e–steht für elsekeyword
a steht für eine Aussage
b steht für eine Aussage
Lassen Sie uns nun sehen: "Was sind die verschiedenen Notationen, die verwendet werden, wenn wir die Grammatiken schreiben?"
Verschiedene Notationen, die in einer kontextfreien Grammatik verwendet werden, sind unten dargestellt:

[Link] folgenden Symbole sind Terminale

a) Die Schlüsselwörter wie if, for, while, do-while usw.
Ziffern von 0 bis 9
c) Symbole wie +, -, *, / usw.
d) Die Kleinbuchstaben zu Beginn des Alphabets, wie zum Beispiela, b, c, usw.
e) Die fettgedruckten Buchstaben wie id

2. Die folgenden Symbole sind Nicht-Terminals

a) Die Kleinbuchstabennamen wieexpression,operator,operand,statementetc
b) Die Großbuchstaben am Anfang des Alphabets wie A, B, C, D usw.
c) Der Buchstabe S ist das Startsymbol
3. Die Kleinbuchstaben am Ende des Alphabets wie u, v, w, x, y, z vertreten
Reihe von Terminals.
4. Die Großbuchstaben am Ende des Alphabets wie U, V, W, X, Y, Z usw.
represent grammar symbols. A grammar symbol can be a terminal or a non-terminal.
Die griechischen Buchstaben wie α, β, γ, δ usw. repräsentieren eine Folge von Regelzeichen.

2.3 Ableitung
Was ist Ableitung?
Definition:The process of obtaining string of terminals and/or non-terminals from the
Das Startsymbol wird durch die Anwendung einer bestimmten Menge von Produktionen (es können alle Produktionen einbezogen werden) erzeugt.

genanntes Derivat.
Zum Beispiel, wenn A→ B und B→ sind die Produktionen, die Zeichenfolge kann sein
aus der A-Produktion erhalten, wie unten gezeigt:
A B [ Wenden Sie die Produktion A→ an B ]
[ Ersetzen Sie B durch Verwendung der Produktion B → ]
Die obige Ableitung kann auch wie unten gezeigt geschrieben werden:

Ein
 Systematischer Ansatz zur Compiler-Entwicklung - 2.3

Beachten Sie die folgenden Punkte:

Wenn eine Zeichenkette durch die Anwendung nur einer Produktion erhalten wird, wird sie als ein Schritt bezeichnet
Ableitung und wird durch das Symbol „ bezeichnet „.
Wenn eine oder mehrere Produktionen angewendet werden, um den String zu erhalten von A, dann schreiben wir

Ein
If zero or more productions are applied to get the string von A, dann schreiben wir
Ein

Beispiel 2.1: Betrachten Sie die Grammatik unten, aus der jede arithmetische
Ausdruck kann erhalten werden.
E→E + E
E→E - E
E→E * E
E→E / E
E→ id
Erhalten Sie die stringid + id * id und zeigen Sie die Ableitung dafür.

Lösung: Die Ableitung, um die stringid + id * id zu erhalten, ist unten aufgeführt.

E E+E
id+ E
id+ E * E
id+id* E
id+id*id
Somit kann die obige Abfolge von Schritten auch geschrieben werden als:

E id + id * id
was darauf hinweist, dass die stringid + id * idis in einem oder mehreren Schritten durch Anwendung erhalten wurde
verschiedene Produktionen.

Jetzt sehen wir uns an: 'Was sind die zwei Arten von Ableitungen?' Die zwei Arten von Ableitungen.
sind:
Linksabgeleitete Ableitung
Rechtsableitung

2.3.1 Linke Ableitung

Was ist eine linksableitende Ableitung?

2.4 Syntax-Analyzer
Definition: Der Prozess, eine Zeichenkette von Terminalen aus einer Sequenz zu erhalten.
Ersatz, sodass bei jedem Schritt nur das linke nicht-terminal ersetzt wird, ist
linksableitende Ableitung.

Betrachten Sie zum Beispiel die folgende Grammatik:

E→E + E
E→E * E
E→(E)
E→ id

Die linksseitige Ableitung für den String id + id * id kann wie unten gezeigt erhalten werden:

E E+E
lm

id+ E
id+ E * E
id+id* E
id+id*id

2.3.2 Rechtsableitung
Lassen Sie uns nun sehen: "Was ist die rechtsverknüpfte Ableitung?"

Definition: Der Prozess, eine Zeichenkette aus einer Folge von Terminalen zu erhalten.
Ersetzungen, sodass jeweils nur das rechte nicht-terminale Symbol in jedem Schritt ersetzt wird, sind
genannt rechtsbündige Ableitung.

Zum Beispiel, betrachten Sie die folgende Grammatik:

E→E + E
E→E * E
E→(E)
E→ id

Die rechtsgültige Ableitung für den String id + id * id kann wie unten gezeigt erhalten werden:

E E+E
rm
E+E*E
E + E *id
E +id*id
id+id*id
 Systematischer Ansatz zur Compiler-Entwicklung - 2.5

2.4 Satz

Jetzt lass uns sehen: 'Was ist ein Satz?'

Definition: Sei G = (V, T, P, S) eine kontextfreie Grammatik. Jeder String w (V T)* das ableitbar ist
vom Startsymbol S, so dass S w wird als Satz oder als satzförmige Darstellung von G bezeichnet. Für
Beispiel, betrachten Sie die Ableitung:

E E+E
id+ E
id+ E * E
id+id* E
id+id*id
Der finale String aus Terminals, d.h. id + id * id, wird als Satz der Grammatik bezeichnet.

Jetzt sehen wir uns an: „Was sind die verschiedenen Satzformen?“ Die beiden Satzformen sind:
Linke Satzform
Richtige Satzform

2.4.1 Linke Satzform

Lass uns nun sehen: "Was ist die verbleibende Satzform?"

Definition: Wenn es eine Ableitung der Form S gibt α, wo bei jedem Schritt in der Ableitung
Prozessiert nur eine linksseitige Variable wird ersetzt, dann wird α als links-sententielle Form von G bezeichnet.

Betrachten Sie beispielsweise die folgende Grammatik und ihre linksseitige Ableitung:

Grammatik linksableitende Ableitung

E E+E
E→E + E lm
E→E * E id+ E
E→(E) id+ E * E
E→ ID id+id* E
id+id*id
In der oben links stehenden Ableitung wird die Folge von Grammatiksymbolen, die in jedem Schritt erhalten wird,
wie:
{ E + E, id + E, id + E * E, id + id * E, id + id * id }

sind verschiedene links-satzliche Formen der gegebenen Grammatik.

2.6 Syntaxanalysator
2.4.2 Rechte sentenzielle Form

Lass uns nun sehen: "Was ist eine richtige Satzform?"

Definition: Wenn es eine Ableitung der Form S gibt α, wo bei jedem Schritt in der Ableitung
Es wird nur das am weitesten rechts stehende Nichtterminal ersetzt, dann wird α als rechtssatzform bezeichnet.
von G.

Betrachten Sie zum Beispiel die folgende Grammatik und ihre rechtsäußerste Ableitung:

Grammatik rechteste Ableitung

E E+E
E→E + E rm
E→E * E E+E*E
E→(E) E + E *id
E→ id E +id*id
id+id*id
In der obigen rechtsmost Ableitung wird in jedem Schritt die Zeichenfolge von Grammatiksymbolen erzielt
wie zum Beispiel:

{ E + E, E + E * E, E + E *id, E +id*id,id+id*id }
sind verschiedene rechtssatzliche Formen der gegebenen Grammatik.

Beispiel 2.2: Erhalten Sie die linke Ableitung für die Zeichenkette aaabbabbba unter Verwendung der
folgende Grammatik.
S →aB| bA
A →aS | bAA | a
B →bS | aBB | b

Die linksgenannte Ableitung für den String aaabbabbb ist unten dargestellt:
S lm aB (Anwendung S aB)
aaBB (Anwendung B aBB)
aaaBBB (Anwendung B aBB)
aaabBB (Anwendung B b)
aaabbB (Anwenden B b)
aaabbaBB (Anwendung B aBB)
aaabbabB (B beantragen b)
aaabbabbS (Anwendung B bS)
aaabbabbbA (Anwendung S bA)
aaabbabbba (Anwendung A a)
 Systematischer Ansatz zur Compiler-Entwicklung - 2.7

2.4.3 Language

Jetzt wollen wir sehen: "Was ist die von der Grammatik erzeugte Sprache?" Die formale Definition von
Die Sprache, die von einer Grammatik akzeptiert wird, ist wie folgt definiert.

Definition: Sei G = (V, T, P, S) eine Grammatik. Die Sprache L(G), die von der
Die Grammatik G ist
L(G) = {w | S w und w T*}
d.h., w ist eine Zeichenkette von Terminalsymbolen, die aus dem Startsymbol S durch Anwendung verschiedener
Produktionen.

For example, for the grammar A→ a | aA the various strings that are generated area,aa,
aaa, ……und so weiter.

So, L = { a, aa, aaa, aaaa, …….}

2.4.4 Ableitungsbaum (Parsebaum)

Die Ableitung kann in Form eines Baumes dargestellt werden. Solche Bäume werden Ableitungs- oder
Ableitungsbäume. Sowohl die linksseitige Ableitung als auch die rechtsseitige Ableitung können
darstellt, die mit Ableitungsbäumen. Lassen Sie uns nun sehen: "Was ist ein Ableitungsbaum oder Parse-Baum?"
The derivation tree can be defined as shown below.
Definition: Sei G = (V, T, P, S) eine kontextfreie Grammatik (CFG). Der Baum ist ein Ableitungsbaum (Parse-Baum) mit
die folgenden Eigenschaften.
Die Wurzel hat das Etikett S.
2. Jeder Knoten hat ein Etikett, das in (V U T U) ist. ).
3. Jeder Blattknoten hat ein Etikett aus T und ein innerer Scheitel hat ein Etikett aus V.
4. Wenn ein Scheitelpunkt mit A beschriftet ist und wenn X1, X2, X3, …. Xnsind alle Kinder von A links,
dann A X1X2X3….Xnmuss eine Produktion in P sein.
Betrachten Sie beispielsweise die folgende Grammatik und ihre rechtsseitige Ableitung zusammen mit
Parsebaum:

Grammatik rechtsableitende Ableitung Parsebaum

E E+E E
E→E + E rm

E→E * E E+E*E E E
+
E→(E) E + E *id
E→ id E +id*id E *
id E
id+id*id
id ID
2.8 Syntax-Analysator
Lass uns nun sehen: "Was ist der Ertrag des Baums?" Der Ertrag eines Baums kann formal
definiert wie folgt:

Definition: DerDer Ertrag eines Baumes ist die Zeichenkette, die durch das Lesen von nur
Blätter des Baumes von links nach rechts ohne Berücksichtigung der -Symbole. Der Ertrag von der
Der Baum leitet sich immer von der Wurzel ab und die Ernte des Baumes ist immer eine terminale Zeichenkette.

Zum Beispiel, betrachten Sie den Ableitungsbaum (oder Parsingbaum), der unten gezeigt ist:

E + E

E *
id E
id id
Wenn wir nur die Terminalsymbole im obigen Parsebaum von links nach rechts lesen, erhalten wir id +
id * idandid + id * id ist der Ertrag des gegebenen Parsebaums.

2.5 Mehrdeutige Grammatik

In diesem Abschnitt wollen wir sehen: "Was ist mehrdeutige Grammatik?"

Definition: Lassen Sie G = (V, T, P, S) eine kontextfreie Grammatik sein. Eine Grammatik G ist mehrdeutig.
wenn und nur wenn es mindestens einen String gibt T* für die zwei oder mehr links
Es existieren Ableitungen oder es existieren zwei oder mehr rechte Ableitungen. Das heißt, die mehrdeutige Grammatik
hat zwei oder mehr Bedeutungen oder Interpretationen.
Da für jede Ableitung ein Parse-Baum existiert, kann die mehrdeutige Grammatik auch sein
definiert als derjenige, der zwei oder mehr verschiedene Parsing-Bäume für den abgeleiteten String hat
vom Startsymbol S.

Beispiel 2.3: Betrachten Sie die folgende Grammatik, aus der ein arithmetischer Ausdruck abgeleitet werden kann.
erhalten werden:

E→E + E
E→E - E
E→E * E
E→E / E
E→(E)|I
Ich→ id
Zeigen Sie, dass die Grammatik mehrdeutig ist.
 Systematischer Ansatz zum Entwurf von Compilern - 2.9

Lösung: Die Satz-ID + ID * ID kann durch die linksableitende Ableitung in zwei erhalten werden.
Wege wie unten angezeigt.

E E+E E E*E
id+ E E+E*E
id+ E * E id + E * E
id+id* E id+id* E
id+id*id id+id*id

Die entsprechenden Ableitungsbäume für die beiden linksnächsten Ableitungen sind unten dargestellt:

E E

E + E E * E

E * E + id
id E E
id id id id
Da die beiden Parse-Bäume für denselben Satz id+id*id unterschiedlich sind, indem sie anwenden
Die linksseitige Ableitung, die Grammatik ist mehrdeutig.

Beispiel 2.4: Ist die folgende Grammatik mehrdeutig? (if-Anweisung oder if-then-else)
S→iCtS | iCtSeS | a
C→b
Die Zeichenkette ibtibtaeacan kann durch Anwenden der linksseitigen Ableitung wie gezeigt erhalten werden.
unten zusammen mit parsen.
Linke Ableitung Parsenbaum
S
S iCtS
ibtS
ibtiCtSeS i C t S
ibtibtSeS
ibtibtaeS b i C t S e S
ibtibtaea
b a a
Der Stringibtibtaeacan kann erneut durch Anwendung der linksseitigen Ableitung unter Verwendung von erhalten werden
verschiedene Produktionsmengen wie unten gezeigt zusammen mit Parsebaum.
Note:i–if, t–then, e–else , b–other statement, a–other statement
2.10 Syntax-Analyzer
Linksableitung Parsebaum
S
S iCtSeS
ibtSeS ich C t S e S
ibtiCtSeS
ibtibtSeS
b ich C t S ein
ibtibtaeS
ibtibtaea
b a

Da es zwei verschiedene Parsbäume für den String „ibtibtaea“ durch Anwendung der linkssemitischen Ableitung gibt.
Die gegebene Grammatik ist mehrdeutig. Die Grammatik hat zwei Interpretationen oder zwei
Bedeutungen.

2.6 Ambiguität beseitigen

Einige Grammatikformen, die mehrdeutig sind, können in eindeutige Grammatikformen umgewandelt werden. Dies
kann mit zwei Methoden durchgeführt werden:
Entschlüsselungsregel
Verwendung der Vorrang- und Assoziativität von Operatoren

2.6.1 Regel zur Aufhebung von Mehrdeutigkeiten

Wir haben bereits im vorherigen Problem gesehen, dass die Grammatik, die zu if- gehört
Die Aussage ist mehrdeutig. Dies liegt an der schwebenden Else. Das Problem der schwebenden Else kann behoben werden.
Eliminiert und somit kann auch die Mehrdeutigkeit der Grammatik eliminiert werden.
Nun, lassen Sie uns sehen: "Was ist das Problem mit dem schwebenden Else?" Betrachten Sie die folgende Grammatik:

S→iCtS | iCtSeS | a
C→b
wo
i steht für Keywordif
C steht für Bedingung, die erfüllt sein muss. Hier ist C ein Nicht-Terminal.
t steht für Schlüsselwort dann
S steht für Nichtterminal
e steht für keywordelse
a steht für eine andere Aussage
b steht für andere Aussage
Da die obige Grammatik mehrdeutig ist, erhalten wir zwei verschiedene Parse-Bäume für den String
ibtibtaea(Siehe Lösung für das vorherige Problem für Details) wie unten gezeigt:
 Systematischer Ansatz zur Compiler-Entwicklung - 2.11

S S

i C t S ich C t S e S

b i C t S e S b i a
C t S

b a a
b a
Parsebaum 1 Parse-Baum 2

Since there are two parse trees for the same stringibtibtaeathe given grammar is
mehrdeutig. Beachten Sie die folgenden Punkte:
Der erste Parsebaum assoziiert else mit 2ndFall-Anweisung
Der zweite Parsebaum verknüpft else mit der ersten if-Anweisung.
Diese Mehrdeutigkeit, ob else mit der ersten if-Anweisung oder der zweiten if-Anweisung zu verbinden ist,
genannt „hängendes Sonst-Problem“.

Nun, lassen Sie uns sehen, wie das "Dangling Else-Problem gelöst werden kann?" Das Dangling Else-Problem
kann gelöst werden, indem eine eindeutige Grammatik wie unten dargestellt konstruiert wird:

Example 2.5:Eliminate ambiguity from the following ambiguous grammar:

S→iCtS | iCtSeS | a
C→b
Lösung: In allen Programmiersprachen, wenn if-Anweisungen verschachtelt sind, ist der erste Parsebaum
is preferred. So, the general rule is “Match eachelsewith closest unmatchedthen”. This
Regeln können direkt in die Grammatik integriert werden und Mehrdeutigkeit kann wie gezeigt beseitigt werden.
unten:
Schritt 1: Die übereinstimmende Aussage M ist eine if-else-Anweisung, bei der die Aussage S davor steht.
sonst und nach dem Schlüsselwort sonst wird übereinstimmen. Dies kann ausgedrückt werden als:

M→iCtMeM

Schritt 2: Eine unübereinstimmende Aussage U besteht aus:

a) einfaches if-Statement, bei dem die Aussage S übereinstimmend oder nicht übereinstimmend ist
Die äquivalente Produktion beträgt:
U→iCtS
b) if-else-Anweisung, bei der die Anweisung vor else übereinstimmt und die Anweisung danach
sonst ist nicht übereinstimmend. Die äquivalente Produktion ist:
U→iCtMeU
2.12 Syntax-Analysator
Schritt 3: Die übereinstimmende Aussage und die nicht übereinstimmende Aussage können mithilfe der
Aussage S wie unten dargestellt:
S→M|U

Die endgültige Grammatik, die eindeutig ist, ist unten dargestellt:

S→M|U
M→iCtMeM
U→iCtS
U→iCtMeU

Beobachten Sie, dass die obige Grammatik else mit dem nächstgelegenen then verknüpft und eliminiert.
Mehrdeutigkeit aus der Grammatik.

2.6.2. Mehrdeutigkeiten durch Rangfolge und Assoziativität beseitigen

Diese Methode wird mit folgendem Beispiel erklärt:

Beispiel 2.6: Wandeln Sie die folgende mehrdeutige Grammatik in eine eindeutige Grammatik um
E→E * E | E - E
E→E ^ E | E / E
E→E + E
E→(E)| id
Die Grammatik kann unter Verwendung der Priorität in eine eindeutige Grammatik umgewandelt werden.
Operatoren sowie Assoziativitätsoperatoren wie unten gezeigt:
Schritt 1: Ordnen Sie die Operatoren in aufsteigender Reihenfolge der Priorität an, zusammen mit
Assoziativität wie unten gezeigt:
Operatoren Assoziativität Nichtterminal verwendet
+ ,– LINKS E
*, / LINKS T
^ RECHT P
Da es drei Ebenen der Priorität gibt, assoziieren wir drei Nichtterminals: E, T und P.
Auch ein zusätzliches Nichtterminal F, das Grundeinheiten in einem arithmetischen Ausdruck generiert.

Schritt 2: Die grundlegenden Einheiten im Ausdruck sind id (Identifikator) und in Klammern gesetzte Ausdrücke.
Die Produktion, die damit zusammenhängt, kann wie folgt geschrieben werden:

F→(E)| id
 Systematischer Ansatz zur Compiler-Entwicklung - 2.13

Schritt 3: Der nächsthöhere Prioritätsoperator ist ^ und er ist rechtsassoziativ. Also, der
Die Produktion muss von dem Nichtterminal P ausgehen und sie sollte eine Rechtsrekursion haben, wie gezeigt.
unten:
P→F^P|F

Schritt 4: Die nächsthöheren Prioritätsoperatoren sind * und / und sie sind linksassoziativ. Also,
Die Produktion muss vom Nichtterminal T ausgehen und sie sollte linksrekursiv sein.
unten dargestellt:

T→T*P|T/P|P

Schritt 5: Die nächsthöheren Prioritätsoperatoren sind + und – und sie sind linksassoziativ. Also,
Die Produktion muss von dem Nicht-Terminal E beginnen und sie sollte Linksrekursion haben.
unten gezeigt:

E→E+T|E–T|T

Schritt 6: Die endgültige Grammatik, die eindeutig ist, kann wie folgt geschrieben werden:

E→E+T|E–T|T
T→T*P|T/P|P
P→F^P|F
F →(E)| id

Beispiel 2.7: Wandeln Sie die folgende mehrdeutige Grammatik in eine eindeutige Grammatik um

E→E+E
E → E –E
E→E^E
E→E*E
E→E/E
E →(E)| id

indem man * und –Operatoren die niedrigste Priorität zuweist und sie linksassoziativ sind, / und +
Operatoren haben die höchste Priorität und sind rechtsassoziativ, und der ^ Operator hat Vorrang.
dazwischen und es ist linksassoziativ.

Die Grammatik kann in eine eindeutige Grammatik umgewandelt werden, indem die Vorrangfolge verwendet wird.
Operatoren sowie Assoziativität von Operatoren wie unten gezeigt:
2.14 Syntax-Analyzer
Schritt 1: Ordnen Sie die Operatoren in aufsteigender Reihenfolge der Priorität an sowie
Assoziativität, wie unten gezeigt:

Prioritätsoperatoren Assoziativität Nichtterminal verwendet

(niedrigste) * ,– Links E
^ LINKS P
(höchste) /, + RECHT T

Da es drei Ebenen der Priorität gibt, verbinden wir drei Nichtterminale: E, P und T.
Verwenden Sie auch ein zusätzliches Nicht-Terminal F, das grundlegende Einheiten in einem arithmetischen Ausdruck erzeugt.

Schritt 2: Die grundlegenden Einheiten im Ausdruck sind id (Bezeichner) und in Klammern gesetzte Ausdrücke.
Die Produktion, die damit verbunden ist, kann wie folgt geschrieben werden:

F→(E)| id

Schritt 3: Die nächsthöheren Prioritätsoperatoren sind + und / und sie sind rechtsassoziativ. Also,
Die Produktion muss vom Nichtterminal T ausgehen und sie sollte rechtsrekursiv im RHS sein.
der Produktion wie unten gezeigt:

T→F+T|F/T|F

Schritt 4: Der nächsthöhere Prioritätsoperator ist ^ und er ist linksassoziativ. Also, die Produktion
muss von dem Nicht-Terminal P ausgehen und es sollte linksrekursiv auf der rechten Seite sein.
production as shown below:

P→P^T|T

Schritt 5: Die nächsthöheren Prioritätsoperatoren sind * und – und sie sind linksassoziativ. Also,
Die Produktion muss von dem Nichtterminal E ausgehen und sie sollte im rechten Teil rekursiv nach links sein.
der Produktion wie unten gezeigt:

E→E+P|E–P|P

Schritt 6: Die endgültige Grammatik, die eindeutig ist, kann wie unten gezeigt geschrieben werden:

E→E+P|E–P|P
P→P^T|T
T→F+T|F/T|F
F →(E)| id
 Systematic approach to Compiler Design - 2.15

2.7 Die Rolle des Parsers

Zuerst fragen wir: "Was ist Parsen?"
Definition: Parsing ist der Prozess, bei dem Tokens vom lexikalischen Analysator erhalten werden und
eine Ableitung für die Sequenz von Tokens und erstellt einen Parsebaum. Wenn das Programm also ist
Syntaxisch korrekt wird der Parse-Baum generiert. Wenn eine Ableitung für die Folge von Tokens
existiert nicht d.h., wenn das Programm syntaktisch falsch ist, führt dies zu einem Syntaxfehler und dem
Der Parser zeigt die entsprechenden Fehlermeldungen an. Die Parse-Bäume sind sehr wichtig in
Die Bedeutung eines Programms oder eines Teils des Programms herauszufinden. Der Parse-Baum wird auch genannt
Syntaxbaum-Parser, auch als Syntaxanalysator bezeichnet, ist derjenige, der das Parsen durchführt.

Das Blockdiagramm, das die Interaktion des Parsers mit anderen Modulen und Phasen zeigt, ist
unten gezeigt:

Symbol
Tisch

Token
Quelle lexikalisch Syntax parsen Rest von
Programm Analyzer Analysator Baum Phasen
holen
nächstes Token

Fehler
Handler

Die Rolle des Parsers oder die verschiedenen Aktivitäten, die vom Parser durchgeführt werden, sind gezeigt.
darunter:
Der Parser liest eine Sequenz von Token vom lexikalischen Analysator.
Der Parser überprüft, ob die vom lexikalischen Analysator erhaltenen Tokens verarbeitet werden können.
Erfolgreich generiert. Dies geschieht, indem man eine Ableitung für die Folge von
Tokens und erstellt den Parse-Baum.
Wenn eine Ableitung mit der Sequenz von Token erhalten wird, zeigt dies an, dass das Programm
syntaktisch korrekt und der Parsebaum wird generiert.
Wenn eine Ableitung nicht mit der Sequenz von Tokens erreicht wird, bedeutet das, dass das Programm
syntaktisch falsch und der Parse-Baum wird nicht erzeugt. Nun berichtet der Parser
Angemessene Fehlermeldungen klar und genau zusammen mit Zeilennummern
Der Parser erholt sich auch schnell von jedem Fehler, sodass nachfolgende Fehler erkannt werden können.
and displayed so that the user can correct the programs.
2.16 Syntax-Analyse

2.7.1 Fehlerbehebungsstrategien

Die folgenden Aktivitäten werden durchgeführt, sobald Fehler vom Parser erkannt werden:
Detect the syntax errors accurately and produce appropriate error messages so that the
Der Programmierer kann das Programm korrigieren.
Es muss sich schnell von den Fehlern erholen und nachfolgende Fehler im Programm erkennen.
Der Fehlerbehandler sollte alle Maßnahmen sehr schnell ergreifen und darf nicht verlangsamen.
Kompilierungsprozess.

Nun, lassen Sie uns sehen: "Was sind die Fehlerbehebungsstrategien des Parsers (oder Syntaxanalysators)?"
The various error recovery techniques are:
Panikmodus-Wiederherstellung
Fehlerproduktionen
Phrasenebene Wiederherstellung
Globale Korrektur

Panikmodus-Wiederherstellung: Es ist die einfachste und beliebteste Fehlerrückgewinnungsmethode. Wenn

Ein Fehler wird erkannt, der Parser verwirft die Symbole nacheinander, bis das nächste gültige Token erreicht ist.
(genannt Synchronisationstoken) wird gefunden. Die typischen Synchronisationstoken sind:
Anweisungstermine wie Semikolon
Ausdrucksbeendiger wie \n

Es überspringt oft eine erhebliche Menge an Eingaben, ohne sie auf zusätzliche Fehler zu überprüfen.
Sobald das Synchronisierungstoken gefunden ist, wird der Parser ab diesem Punkt fortfahren, um
Identifizieren Sie die nachfolgenden Fehler. In Situationen, in denen mehrere Fehler dieselbe sind.
Diese Methode ist nicht nützlich.

Zum Beispiel betrachten Sie den fehlerhaften Ausdruck:

(5 ** 2) + 8

Der Parser scannt die Eingabe von links nach rechts und findet nach dem Lesen (, 5 keinen Fehler.
und *.
Nach dem Lesen des zweiten *, weiß es, dass kein Ausdruck aufeinanderfolgende *-Operatoren hat.
und es zeigt einen Fehler "Zusätzliches * in der Eingabe" an
Jetzt muss es sich von dem Fehler erholen. Im Wiederherstellungsmodus bei Panik überspringt es alle Eingaben.
Symbole bis die nächste Ganzzahl 2 erreicht wird. Hier ist 2 das synchronisierende Token.
So wird der Fehler erkannt und aus dem Fehler im Panikmodus wiederhergestellt.
 Systematischer Ansatz zur Compiler-Entwicklung - 2.17

Fehlerproduktionen: In dieser Art von Fehlerbehebungsstrategie führen wir einen Fehler ein
productions. The error productions specify commonly known mistakes in the grammar.
Wenn wir den Parser implementieren, zeigt er, wenn eine Fehlerproduktion verwendet wird,
angemessene Fehlermeldung. Betrachten Sie beispielsweise den Ausdruck 10x. Mathematisch ist es
bedeutet, 10 mit x zu multiplizieren. Aber in einer Programmiersprache sollten wir 10*x schreiben. So
Fehler können sehr einfach identifiziert werden, indem Fehlerproduktionen und innerhalb der
Körper der Funktion, angemessene Fehlermeldungen anzeigen.

Nachteile
Kann viele Fehler beheben, aber nicht alle potenziellen Fehler.
Die Einführung von Fehlerproduktionen wird die Grammatik komplizieren.

Phrasenebene Wiederherstellung: Es handelt sich um eine Fehlerkorrekturmethode. Bei der Entdeckung eines Fehlers, ...
Der Parser kann lokale Korrekturen an den verbleibenden Eingaben vornehmen. Dies geschieht normalerweise durch
Einfügen, Löschen und/oder Ersetzen der Eingabe und dem Parser ermöglichen, mit der Analyse fortzufahren.

Beispiel: Ersetzen eines Kommas durch ein Semikolon, Löschen eines überflüssigen Semikolons oder Einfügen eines
fehlendes Semikolon.

Nachteile
Sehr schwierig umzusetzen
Verlangsamt das Parsen von korrekten Programmen
Bei der Auswahl von Ersatzteilen muss sorgfältig vorgegangen werden, da sie zu unendlichen führen können.
Schleifen.

Globale Korrektur: Dies ist auch eine der Fehlerkorrekturstrategien. Die verschiedenen Punkte
sich an diese Fehlerkorrekturmethoden zu erinnern, sind:
These methods replace incorrect input with correct input using least-cost-correction
Algorithmen.
Diese Algorithmen nehmen eine falsche Eingabezeichenfolge x und eine Grammatik G und finden einen Parse.
Baum für einen verwandten String y, so dass die Anzahl der Einfügungen, Löschungen und Änderungen von
Die benötigten Token, um x in y zu verwandeln, sind so gering wie möglich.
Diese Methoden sind in Bezug auf Zeit und Raum kostenintensiv in der Umsetzung und daher nur ...
von theoretischem Interesse.

2.7.2 Parsing-Techniken
In diesem Abschnitt wollen wir sehen: "Was sind die verschiedenen Arten von Parsern?"
2,18 Syntax-Analyzer

Die Parser sind wie unten angegeben klassifiziert:

Rekursiver Abwärtsparser mit Rückverfolgung

Top-Down-Parser
Rekursiver Abwärts-Parser ohne Rückverfolgung
(Prädiktiver Parser)

SLR (Einfaches LR)

Bottom-up-Parser LALR (Look Ahead LR)
Kanonic LR
2.8 Top-down Parsing

Was ist ein Top-Down-Parser?

Definition: Der Prozess der Konstruktion eines Parsing-Baums für die Zeichenkette von Token (erhalten
vom lexikalischen Analysator) von oben d.h. beginnend mit dem Wurzelknoten und das Erstellen der Knoten
of the parse tree in preorder in depth-first-search manner is calledtop down parsing
Technik. Daher kann das Top-Down-Parsing als ein Versuch betrachtet werden, den linksäußersten
Ableitung für eine Eingabestring und Konstruktion des Parsebaums für diese Ableitung. Der
Ein Parser, der diesen Ansatz verwendet, wird als Top-Down-Parser bezeichnet. Da das Parsen von oben beginnt.
(d.h. Wurzel) bis zu den Blättern, wird es als Top-Down-Parser bezeichnet.

Beispiel 2.8: Zeigen Sie den Top-Down-Parsing-Prozess für die Zeichenfolge id + id * id für das
Grammatik
E→E+E
E→E * E
E→ (E)
E→id

Lösung: Der String id + id * id kann durch die Grammatik erhalten werden, indem man von links nach rechts anwendet.
Ableitung wie unten gezeigt:

E E+E (Abb. a) Schritt 1

lm

id+ E (Abb. b) Schritt 2

id+ E * E (Abb. c) Schritt 3
id+id* E (Abb. d) Schritt 4
id+id*id (Abb. e) Schritt 5
 Systematischer Ansatz zur Compiler-Entwicklung - 2.19

Die obige Ableitung kann in Form eines Parse-Baums vom Startsymbol geschrieben werden.
Verwendung des Top-Down-Ansatzes, wie unten gezeigt:

Eroot Eroot Eroot

E + E E + E

id

(Abb. a) (Abb. b) (Abb. c)

Eroot Eroot Eroot

E + E E + E E + E

id E * E id E * E id E * E

id id id
(Abb. d) (Abb. e) (Abb. f)

Beginne vom Wurzelknoten E

Schritt 1: Ersetzen Sie E durch E + E mit E → E + E. Es ist in Abbildung (b) dargestellt.

Schritt 2: Ersetzen Sie E durch id unter Verwendung von E → id. Es ist in Abbildung (c) dargestellt.

Schritt 3: Ersetzen Sie E durch E * E mit E → E * E. Es wird in Abbildung (d) gezeigt.

Schritt 4: Ersetze E durch id, indem du E → id verwendest. Es ist in Abbildung (e) dargestellt.

Schritt 5: Ersetzen Sie E durch id mit E → id. Es ist in Abbildung (f) dargestellt.

2.8.1 Rekursiver Abwärtsparser

Was ist ein rekursiver Abstiegparser?

2,20 Syntax-Analyse
Definition: Ein rekursiver Abwärts-Parser ist ein Top-Down-Parser, in dem der Parse-Baum erstellt wird.
vom oberen Teil ausgehend, beginnend mit dem Wurzelknoten und die Produktionen von links auswählend
nach rechts (wenn zwei oder mehr alternative Produktionen existieren). Für jedes Nichtterminal gibt es
existiert ein rekursives Verfahren und die rechte Seite der Produktion dieses Nicht-Terminals ist
als Körper des Verfahrens implementiert. Die Sequenz von Terminals und Nicht-Terminals
auf der rechten Seite der Produktion entsprechen dem Abgleich mit Eingabesymbolen und
Aufrufe an andere Verfahren während der Auswahl der alternativen Produktion werden implementiert mit
Switch- oder If-Anweisungen. Damit steht die Syntax oder Struktur des resultierenden Programms in engem Zusammenhang.
spiegelt die Grammatik wider, die es erkennt.

Zum Beispiel kann das Verfahren zur Produktion A → α wie unten gezeigt geschrieben werden:

Verfahren A () // Funktionskopf
{
……
…… Körper der Funktion
……
}

Beachten Sie die folgenden Punkte:

Für die Variable A auf der linken Seite der Produktion schreiben wir die Funktion
header
Für die Zeichenkette von Grammatiksymbolen, die durch α auf der rechten Seite bezeichnet wird.
Die Produktion entspricht dem Funktionskörper.
Somit schreiben wir für jedes Nichtterminal in der Grammatik die Prozedur oder Funktion wie folgt
die vorherigen zwei Schritte.

Arbeiten: Der rekursive Abstiegparser funktioniert wie unten gezeigt:

Die Ausführung beginnt mit der Funktion, die dem Startsymbol entspricht.
Grammatik
Wenn der Körper der Funktion den gesamten Eingabestring scannt, dann ist das Parsen erfolgreich.
Andernfalls ist der Eingabestring nicht korrekt und das Parsen wird gestoppt.
Jeder Nicht-Terminal ist mit einem Parsing-Verfahren oder einer Funktion verbunden, die
erkennen Sie jede Folge von Tokens, die von diesem Nicht-Terminal generiert werden

Innerhalb der Funktion werden sowohl Nicht-Terminals als auch Terminals abgeglichen.
Um das Nichtterminal A zuzuordnen, rufen wir die Funktion/Prozedur A auf, die entspricht
Nicht-terminal A. Diese Aufrufe können rekursiv sein und damit der Name rekursiver Abstieg.
Parser.
 Systematic approach to Compiler Design - 2.21
Um die Terminale abzugleichen, vergleichen wir das aktuelle Eingabesymbol mit a. Wenn es eine Übereinstimmung gibt, dann
ist syntaktisch korrekt und wir erhöhen den Eingabepointer und erhalten das nächste Token
Wenn das aktuelle Eingabesymbol nota ist, ist es syntaktisch falsch und es ist ein entsprechender Fehler.
Nachricht wird angezeigt
Einige Fehlerkorrekturen können durchgeführt werden, um sich schnell von jedem Fehler zu erholen, sodass
Nachfolgende Fehler können erkannt und angezeigt werden, sodass der Benutzer sie korrigieren kann.
Programme.

The general procedure for a recursive-descent parsing that uses top-down parser is shown
darunter:

Beispiel 2.9: Algorithmus für rekursiven Abstieg Parser (Backtracking wird nicht unterstützt)

Verfahren A() // A → X1X2X3…….Xk

{
für i = 1 bis k mache
wenn (Xichist ein Nicht-Terminal)
Rufe Prozedur X aufich();
sonst wenn (XIchist dasselbe wie das aktuelle Eingabesymbol a)
Bewege den Eingabewert zum nächsten Symbol
sonst
error();
Ende für
}

Lassen Sie uns nun die rekursiven Parser für einige der Grammatiken schreiben.

Beispiel 2.10: Schreiben Sie den rekursiven Abwärtsparser für die folgende Grammatik
E→T
T→F
F → (E) |id

// Funktion entsprechend der Produktion E → T

Verfahren E()
{
T();
}
2.22 Syntax-Analyse

// Funktion entsprechend der Produktion T→F

Prozedur T()
{
F();
}

// Funktion entsprechend der Produktion F→(E) | id

// F→( E ) | id
Verfahren F()
{
wenn (eingabe_symbol == „(„)

Eingabepointer voranstellen
E();
wenn(eingabesymbol == „)‟)
Eingabepointer voranstellen
sonst
Fehler()
Ende wenn

sonst wenn (eingabe_symbol == id)

advance input pointer
sonst
error();
Ende wenn
}

Nun, lassen Sie uns sehen: „Was sind die verschiedenen Arten von rekursiven Abwärts-Parsern?“ Der rekursive
Descent-Parser können in zwei Typen klassifiziert werden:
Rekursiver Abwärtsparser mit Backtracking
Rekursiver Abstiegparser ohne Backtracking (prädiktiver Parser)

2.8.2 Rekursiver Abwärtsparser mit Backtracking

Lass uns nun sehen: „Was ist die Notwendigkeit für Backtracking in einem rekursiven Abwärtsparser?“
Backtracking ist aus folgenden Gründen notwendig:
During parsing, the productions are applied one by one. But, if two or more
Alternative Produktionen gibt es, sie werden der Reihe nach von links nach rechts angewendet.
Zeit.
 Systematischer Ansatz zum Compiler-Design - 2.23

Wenn eine bestimmte Produktion nicht ordnungsgemäß das Nichtterminal erweitert, dann
müssen die alternative Produktion angewendet werden. Bevor Sie die alternative Produktion versuchen, ist es
necessary undo the activities done using the current production. This is possibly only
mit Backtracking.

Aber die rekursiven Abstiegsparser mit Backtracking werden nicht häufig verwendet. Also, wir einfach
konzentriere dich darauf, wie sie mit einem Beispiel arbeiten.

Beispiel 2.11: Zeigen Sie die Schritte, die an einem rekursiven Abwärtsparser mit Backtracking beteiligt sind für
der Eingabestringcadfür die folgende Grammatik
S→cAd
A→ab | a

Lösung: Die drei Teile, die beim Parsen des Strings verwendet werden, sind:

Gegebene Grammatik Zu parsender String Parsebaum

S→cAd cad S(Wurzel)
A→ab | a ↑
Eingabepointer
Beachten Sie, dass der Eingabezeiger auf das nächste Zeichen zeigt, das gelesen werden soll.

Schritt 1: Der einzige unerforschte Knoten ist S und wir wenden die Produktion S→cAd an, um zu erweitern
das Nichtterminal S wie unten gezeigt:
Sroot

c A d
vergleichen(c) und Eingabepointer erhöhen
c ad
↑
Eingabepointer

Step 2:Now, the next node to be expanded is A and input pointer points toWie gezeigt
unten:
Sroot

c Ein d

cad
↑
Eingabepointer
2,24 Syntax-Analysator
Schritt 3: Da es zwei Produktionen von A gibt, wird die erste Produktion A→ab ausgewählt.
und das Nichtterminal A wird wie unten gezeigt erweitert:

Sroot Sroot

c A d c Ein d b tut nicht

Treffen mit
a b a b
c a d match(a) und c a d
↑ i/p erhöhen ↑
Eingabepointer Zeiger Eingabezeiger

Schritt 4: Beachten Sie, dass durch die Auswahl von A→ab der Eingabestring nicht übereinstimmt. Daher müssen wir
Setzen Sie den Zeiger auf das Eingabesymbol zurück (um den Parsebaum, der in Schritt 2 gezeigt wird, zu erhalten). Dies ist
Fertig mit Backtracking und in (Abb. a) dargestellt. Nach dem Backtracking versuchen Sie, A zu erweitern.
Verwenden Sie die zweite Produktion A→a und fahren Sie dann fort, wie in (Abb. b) gezeigt.

Sroot Sroot

c Ein d c A d match(a) und

a Inkrement i/p
cad
pointer
↑ cad
Eingabezeiger ↑
Eingabepunkt
(Abb. a.)

Schritt 5: Jetzt, das nächste SymbolDie Grammatik wird mit der Eingabe verglichen und sie
Treffer. Schließlich halten wir an und kündigen den erfolgreichen Abschluss des Parsens an.

Nun, lassen Sie uns sehen, für welke Art von Grammatiken ein rekursiver Abwärts-Parser nicht verwendet werden kann.

konstruiert? Was ist die Lösung?

Der rekursive Abwärtsparser kann nicht für Grammatiken konstruiert werden, die:
Mehrdeutigkeit. Die Lösung besteht darin, Mehrdeutigkeit aus der Grammatik zu beseitigen.
Linke Rekursion. Die Lösung besteht darin, die linke Rekursion aus der Grammatik zu eliminieren.
Zwei oder mehr Alternativen mit einem gemeinsamen Präfix. Die Lösung besteht darin, nach links zu faktorisieren.
Grammatik.
 Systematischer Ansatz zum Compiler-Design - 2.25

2.8.3 Linke Rekursion

Lassen Sie uns jetzt sehen: "Was ist linke Rekursion? Welche Probleme treten auf, wenn eine rekursive
Ein Abstieg-Parser wird für eine Grammatik mit linksrekursiven Regeln konstruiert?

Definition:A grammar G is said to be left recursive if it has non-terminal A such that

Es gibt eine Ableitung der Form:

Ein Ein (Erhalten durch Anwendung von einer oder mehreren Produktionen)

wo ist eine Folge von Terminal- und Nicht-Terminalsymbolen. Das heißt, jedes Mal, wenn das erste Symbol in einem
Die partielle Ableitung ist dasselbe wie das Zeichen, von dem diese partielle Ableitung abgeleitet ist.
Dann wird gesagt, dass die Grammatik linkrekursiv ist. Eine Grammatik kann Folgendes haben:
sofortige linke Rekursion
indirekte linke Rekursion
Unmittelbare linke Rekursion: Eine Grammatik G hat unmittelbare linke Rekursion, wenn sie eine hat
Produktion der Form:
A→ A
Betrachten Sie zum Beispiel die folgende Grammatik:

E→E+T|T
T→T*F|F
F→ (E) |id
Betrachten Sie in der obigen Grammatik die ersten beiden Produktionen:

E→E+T
T→T*F
Beachte, dass in den oben genannten zwei Produktionen das erste Symbol auf der rechten Seite des
Die Produktion ist dasselbe wie das Symbol auf der linken Seite der Produktion. Also ist das Gegebene
Die Grammatik hat unmittelbare linke Rekursion in zwei Produktionen.

Indirekte linke Rekursion: Eine linke Rekursion, die Ableitungen in zwei oder mehr Schritten umfasst, sodass
Das erste Symbol auf der rechten Seite der partiellen Ableitung ist dasselbe wie das Symbol
Von dem aus die Ableitung begann, wird als indirekte linke Rekursion bezeichnet. Zum Beispiel, berücksichtige
die folgende Grammatik:
E→ T
T→F
F → E + T | id
Betrachten Sie die folgende Ableitung:
E T F E+T
2.26 Syntax-Analyzer
In der obigen Ableitung beachten Sie, dass in der partielle Ableitung, um den Ausdruck E + T zu erhalten, die erste
Das Symbol ist E, das dasselbe ist wie das Symbol, von dem die Ableitung begann. Aber, das
Der Ausdruck E+T wird aus E erzeugt, indem zwei oder mehr Produktionen angewendet werden. Somit ist das Gegebene
Die Grammatik hat zwar keine unmittelbare linke Rekursion, aber sie hat indirekte linke Rekursion.
Rekursion und damit ist die Grammatik linksrekursiv.

Lassen Sie uns nun den rekursiven Abstieg-Parser für die Grammatik mit linksrekursiven Regeln schreiben.

Beispiel 2.12: Betrachten Sie die Produktion E→E + T. Schreiben Sie den rekursiven Abwärtsparser.

Lösung: Der rekursive Abstiegparser für die Produktion E→E + T kann geschrieben werden als
unten angezeigt:

// Funktion entsprechend der Produktion E → E + T

Verfahren E()
{
E();

if (input_symbol = „+‟)
Zeiger vorwärts verschieben
sonst
Fehler
Ende wenn

T();
}

Lassen Sie uns nun sehen: "Was ist das Problem beim Konstruieren eines rekursiven Abwärts-Parsers für die
Grammatik mit linksrekursiven? Beachten Sie die folgenden Punkte (in Bezug auf das Obige
Verfahren, das linke Rekursion hat
Wenn ein Verfahren aufgerufen wird, werden die Parameterwerte zusammen mit der Rücksprungadresse übergeben.
pushed on to the stack and hence stack size decreases
Das Verfahren E() wird rekursiv unendlich aufgerufen, ohne Eingaben zu verbrauchen und
Daher wächst die Größe des Stacks sehr schnell und der Stack wird bald voll sein.
Da kein Platz mehr auf dem Stack ist, um Parameterwerte und die Rücksprungadresse zu speichern,
Das System stürzt ab.
So. the recursive descent parser that is built using left-recursive grammar can cause a
Parser, der schließlich in eine Endlos-Schleife gerät, wodurch das System abstürzt und somit der Rest.
Rekursive Grammatik ist nicht geeignet für rekursive Abwärtsparser. Daher müssen wir
Eliminiere die linke Rekursion aus der Grammatik und analysiere dann die Zeichenkette.
 Systematische Vorgehensweise bei der Compiler-Entwicklung - 2.27

2.8.4 Verfahren zur Beseitigung der linken Rekursion

Betrachten Sie die Produktion der Form:

A→ A | β
woβ nicht mit A beginnt. Beachten Sie, dass die obige Grammatik eine linke Rekursion hat. Lassen Sie uns nun
sehen Sie, wie man linke Rekursion eliminiert. Die verschiedenen Zeichenfolgen, die durch die obigen erzeugt werden können.
Die Grammatik wird unten angezeigt:

Ableitung: 1st 2nd 3rd 4thund so weiter.

A β A A A Ein A A
β Ein Ein
β A
β

{ β, β , β , β ……..}
Beobachten Sie aus den obigen Ableitungen, dass die Sprache L aus β gefolgt von null oder mehr besteht.
α‟s. Die gleiche Sprache kann mit unterschiedlicher Grammatik dargestellt und generiert werden als
unten gezeigt:
L = { β Ich| ich 0}
↓ ↓
A → β A' wo A‟soll null oder mehr α‟s erzeugen
Von A' können wir null oder mehr α's mit den folgenden Produktionen erhalten:
A'→ ϵ | αA'

Die endgültige Grammatik, die β gefolgt von null oder mehr α's, die nicht haben.
Linke Rekursion ist unten dargestellt:
A → β A'
A'→ ϵ | αA'

Daher kann die Grammatik, die linke Rekursion enthält, in der Form einer anderen geschrieben werden.
Grammatik, die keine linke Rekursion hat, wie unten gezeigt:
Links rekursive Grammatik Rechtsrekursive Grammatik
A→ A | β A → β A'
A'→ ϵ | αA'
Im Allgemeinen,

A→ A 1|A 2|A 3|……|A n|β1| β2| β3| ……..| βm A→ β1A'| β2A'|β3A'| ……..|βmA'
A'→ 1A'| 2A'| 3A'|……| nA'| ϵ
2,28 Syntax-Analyzer

Example 2.13:Eliminate left recursion from the following grammar

E→E +T | T
T→T * F | F
F→(E) | id

Solution:The given grammar is shown below:

E→E +T | T
T→T * F | F
F→(E) | id
Da das erste Symbol auf der rechten Seite der E-Produktion und der T-Produktion dasselbe ist wie
Das Symbol auf der linken Seite der Produktion, die Grammatik hat sofort links.
Die unmittelbare linke Rekursion kann nun aus der Grammatik entfernt werden, da
unten gezeigt:

Links rekursive Produktionen Rechtsrekursive Produktionen

A→ A 1|A 2|A 3|……|A n|β1| β2| β3| ……..| βm A→ β1A'| β2A'|β3A'| ……..| βmEin'
A'→ 1A'| 2A'| 3A'|……| nA'| ϵ

1) E → E + T | T E→ TE'
↓ ↓ ↓ ↓ E'→ +TE'| ϵ
A→A 1| β1

2) T →T * F | F T → FT'
↓ ↓ ↓ ↓ T'→ *FT'| ϵ
A→A 1| β1

3) F →(E) | id F→(E) | id

Die endgültige Grammatik, die nach der Eliminierung der linken Rekursion erhalten wurde, kann wie folgt geschrieben werden

unten:
E → TE'
E→
1 +TE'| ϵ
T → FT'
T→
1 *FT'| ϵ
F→(E) | id
 Systematischer Ansatz zum Compiler-Design - 2.29
Jetzt können wir den rekursiven Abwärtsparser für die oben genannte Grammatik schreiben, die erhalten wurde.
nach der Beseitigung der linken Rekursion.

Beispiel 2.14: Schreiben Sie den rekursiven Abwärtsparser für die folgende Grammatik:
E → TE'
E'→ +TE'| ϵ
T → FT'
T'→ *FT'| ϵ
F→(E) | id

Der rekursive Abwärtsparser für die obige Grammatik ist unten dargestellt. Beachten Sie, dass für jede
Nichtterminal gibt es ein Verfahren und die rechte Seite der Produktion ist
wurde als der Körper des Verfahrens wie unten gezeigt implementiert:

// Funktion entsprechend der Produktion: E → T E'

Verfahren E()
{
T();
EDASH();
}

// function corresponding to the production: E'→+T E'|

Verfahren EDASH()
{
if ( inputsymbol == „+‟)
{
Eingabepointer vorwärts bewegen
T();
EDASH();
}
}

// Funktion, die der Produktion entspricht: T→F T'

Verfahren T()
{
F();
TDASH();
}
2,30 Syntax-Analyzer

// Funktion entsprechend der Produktion: T'→* F T'| ϵ

Verfahren TDASH()
{
wenn (inputsymbol == „*‟)
{
Zeiger vorwärts bewegen
F();
TDASH();
}
}
// Funktion entsprechend der Produktion: F→( E ) | id
Verfahren F()
{
if ( inputsymbol == „(„)
{
Eingabepointer vorwärts bewegen
E();
wenn ( inputsymbol == „)‟)
Eingabezeiger vorwärts bewegen
sonst Fehler();
}
sonst
{
wenn (inputsymbol == id )
Eingabezeiger voranstellen
ansonsten Fehler();
}
}

Beispiel 2.15: Erhalten Sie eine Top-Down-Analyse für den String id+id*id für die folgende Grammatik
E → TE'
E'→+TE'|
T → FT'
T'→*FT'|
F → (E) | id
Der Top-Down-Parse für den String id+id*id für die obige Grammatik kann geschrieben werden als
unten angezeigt:
 Systematischer Ansatz zur Compiler-Entwicklung - 2.31

E lm E lm E

T E1 T E1
lm E lm E lm F ET1

T E1 T E1 T E1
F T1 F T1 F T1 + T E1
id id ϵ id ϵ

lm E lm E lm E

T E1 T E1 T E1
F T1 + T E1 F T1 + T E1 F T1 + T E1
id ϵ F T1 id ϵ F T1 id ϵ F T1
id id * F T1

lm E lm E lm E

T E1 T E1 T E1
F T1 + T E1 F T1 + T E1 F T1 + T E1
id ϵ F T1 id ϵ F T1 id ϵ F T1 ϵ
id * F T1 id * F T1 id * F T1

id idϵ idϵ

Example 2.16:Eliminate left recursion from the following grammar:

S → Aa | b
A → Ac | Sd | ϵ

Lösung: Linke Rekursion kann wie unten gezeigt beseitigt werden:

Schritt 1: Die S-Produktion hat keine unmittelbare linke Rekursion. Lassen Sie uns also nicht berücksichtigen.
die Produktion S → Aa | b
2,32 Syntax-Analysator
Schritt 2: Betrachten Sie die Produktion: A → Ac | Sd | ϵ. Ersetzen Sie das Nichtterminal S durch das
productionS → Aa | b erhalten wir folgende A-Produktion:

A → Ac | Aad | bd | ϵ

Schritt 3: Jetzt wird die Grammatik, die nach der Eliminierung rekursiver indirekter Links erzeugt wurde, angezeigt.
unten:
S → Aa | b
A → Ac | Aad | bd | ϵ
Jetzt kann die unmittelbare linke Rekursion wie unten gezeigt eliminiert werden:

Linksrekursive Produktionen Rechtsrekursive Produktionen

A→ A 1|A 2|A 3|……|A n|β1| β2| β3| ……..| βm A→ β1A'| β2A'|β3A'| ……..|βmA'
A'→ 1A'| 2A'| 3A'|……| nA'| ϵ

1)S → Aa | b S → Aa | b

2) A → A c | A ad | bd | ϵ A → bd A'| ϵA'
↓ ↓ ↓ ↓ ↓ A'→ cA'| adA'|ϵ
A→A 1A 2|β 1|β2

Die endgültige Grammatik, die nach der Eliminierung der linken Rekursion erhalten wurde, ist unten dargestellt:

S → Aa | b S → Aa | b
A → bd A'| ϵA' kann geschrieben werden alsA → bd A'| A'

A'→ cA'| adA'|ϵ A'→ cA'| adA'|ϵ

Jetzt lassen Sie uns "Den Algorithmus zur Eliminierung von linker Rekursion schreiben" Der Algorithmus zur Eliminierung
Die linke Rekursion ist unten dargestellt:

Beispiel 2.17: Algorithmus zur Eliminierung von linker Rekursion (einschließlich indirekter linker Rekursion)

Grammatik G ohne ϵ-Produktionen und ohne Zyklen

Grammatik ohne linke Rekursion. Sie kann ϵ-Produktionen haben.
Ordne die Nicht-Terminale in der Reihenfolge A1, A2, A3,……..An
 Systematischer Ansatz zum Compiler-Design - 2.33
fori = 1ronde
für j = 1 bis i-1 tue
Lass Aj→ β1| β2|β3|….. βk
A ersetzenich→ Ajα vonAich→ β1α | β2α | β3α |….. βkα
Ende für
Beseitige die unmittelbare linke Rekursion bei AichProduktionen
Ende für

2.8.5 Linksfaktorisierung

Was ist Linkfaktorisierung? Was ist der Bedarf an Linkfaktorisierung?

Definition: Eine Grammatik, in der zwei oder mehr Produktionen von einem Nicht-Terminal A nicht
Ein gemeinsames Präfix von Symbolen auf der rechten Seite der A-Produktionen wird genannt
links faktorisierte Grammatik. Die links faktorisierte Grammatik ist geeignet für Top-Down-Parser wie
rekursiver Abstiegparser mit oder ohne Rückverfolgung.

Die Grammatik zur Erzeugung von Zeichenfolgen, die aus mindestens einem „a“ gefolgt von mindestens bestehen.
Ein „b“ kann wie unten gezeigt geschrieben werden:
S → aAbB
A→ aA | ϵ Links faktorisierte Grammatik
B → bB | ϵ

Beachten Sie die folgenden Punkte:

Die S-Produktion hat nur eine Produktion und sie kann kein gemeinsames Präfix haben auf dem
rechte Seite der Produktion.
Die beiden A-Produktionen haben kein gemeinsames Präfix auf der rechten Seite.
Schließlich haben zwei B-Produktionen kein gemeinsames Präfix auf der rechten Seite davon.
Produktion

Ex 2: Die Grammatik, die eine Zeichenkette erzeugt, die aus mindestens einem „a“ besteht, gefolgt von mindestens
ein „b‟ kann auch wie unten gezeigt geschrieben werden:

S → AB
A → aA | a Nicht links faktorisierte Grammatik
B → bB | b

Beobachten Sie die folgenden Punkte:

Die S-Produktion hat nur eine Produktion und hat keinen gemeinsamen Präfix.
rechte Seite der Produktion.
Die beiden A-Produktionen haben ein gemeinsames Präfix "a" auf der rechten Seite der Produktion.
2.34 Syntax-Analyzer
Die beiden B-Produktionen haben ein gemeinsames Präfix "b" auf der rechten Seite der Produktion.
Da das gemeinsame Präfix sowohl in A-Produktionen als auch in B-Produktionen vorhanden ist, ist es nicht
links-faktorisierte Grammatik.

Hinweis: Wenn zwei oder mehr Produktionen, die von demselben Nichtterminal ausgehen, ein gemeinsames Präfix haben,
Die Grammatik ist nicht linksfaktoriert.

Lass uns jetzt sehen: "Was ist der Nutzen von linker Faktorisierung?" Linke Faktorisierung ist notwendig für einen Top-Down-Ansatz.

Parser wie rekursiver Abstiegparser mit Backtracking oder prädiktiver Parser, der ist
auch rekursiver Abstiegparser ohne Backtracking. Dies liegt daran, dass die A-Produktion hat
zwei oder mehr alternative Produktionen, und sie haben ein gemeinsames Präfix, dann hat der Parser
Einige Verwirrung bei der Auswahl der angemessenen Produktion zur Erweiterung des Nicht-Terminals A

Ex 1: Betrachten Sie die folgende Grammatik, die die if-Anweisung erkennt:

S → wenn E dann S sonst S | wenn E dann S

Beachten Sie die folgenden Punkte:

. Beide Produktionen beginnen mit keywordif.
. Wenn wir also das Eingangszeichen „if“ vom lexikalischen Analysator erhalten, können wir nicht sagen, ob wir es verwenden sollen.
die erste Produktion oder die zweite Produktion verwenden, um das Nichtterminal S zu erweitern.
. Wir müssen die Grammatik so umwandeln, dass sie keinen gemeinsamen Präfix haben.
That is, left factoring is must for parsing using top-down parser.

Jetzt stellt sich die Frage: "Wie macht man Linksfaktorisierung?" Die Links-faktorisierung kann wie folgt durchgeführt werden:

unten gezeigt:

1) Betrachten Sie zwei A-Produktionen mit gemeinsamem Präfix α:

A → αβ1| αβ2
2) Lassen Sie den Eingabewert mit einem aus α abgeleiteten Zeichenfolgen beginnen. Da α das gemeinsame Präfix ist,
behalte α und wir ersetzen entweder β1oder β2durch das Nichtterminal A'. Also können wir schreiben die
obige Produktion als:
A → α A'

wo A' entweder β erzeugen kann1orβ2unter Verwendung der Produktion:

A'→ β1| β2
 Systematischer Ansatz zur Compiler-Entwicklung - 2.35

Jetzt, nachdem wir die Eingabe, die von α abgeleitet wurde, gesehen haben, können wir A entweder auf β erweitern.1oder zu β2. Also,
Die gegebene Grammatik wurde wie unten gezeigt in eine linksgelagerte Grammatik umgewandelt:

A → αβ1| αβ2 A → α A'

A'→ β1| β2

Nicht links faktorisierte Grammatik Links-faktorisierte Grammatik

Jetzt lass uns „Den Algorithmus zum Durchführen von Links-Faktorisierung schreiben“ Der Algorithmus zum Durchführen von Links-
Die Faktorisierung ist unten dargestellt:

Beispiel 2.18: Der Algorithmus zum Links-Faktorisieren

AlgorithmusLINKS_FAKTOR(G)

Grammatik G

Eine äquivalente linksfaktorierte Grammatik

Methode: Das folgende Verfahren wird verwendet:

1) Für jedes Nicht-Terminal A, finde das längste Präfix α, das zwei oder mehr gemeinsam haben.
seiner Alternativen.

2) Wenn es eine Produktion in der Form gibt:

A → αβ1| αβ2|αβ3|….. αβn| γ
wo γ nicht mit α beginnt, dann kann die obige A-Produktion wie folgt geschrieben werden
unten
A → α A' | γ
A'→ β1| β2|β3|….. βn

Hier ist A' ein neues Nichtterminal.

3) Wenden Sie die Transformation in Schritt 2 wiederholt an, solange es zwei Alternativen für einen Nicht-
Terminal haben ein gemeinsames Präfix

Geben Sie die endgültige Grammatik an, die links faktorisierte ist.
2,36 Syntax-Analyser

Beispiel 2.19: Führen Sie das Left-Factoring für die folgende Grammatik durch:

S→iCtS | iCtSeS | a
C → b

Lösung: Die gegebene Grammatik ist unten dargestellt:

S →iCtS | iCtSeS | a
C → b
Da die S-Produktionen das gemeinsame Präfix iCtS in mehr als einer Produktion haben, ist das linke Faktorisieren erforderlich.
Notwendig. Das Links-Faktorisieren der obigen Grammatik kann unter Verwendung des gezeigten Algorithmus durchgeführt werden.

unten

Gegebene Produktionen Linksfaktorisierte Produktionen

A→ α A'| γ
A → αβ1| αβ2|αβ3|….. αβn| γ A'→ β1| β2|β3|….. βn

1)S → iCtS ϵ | iCtS eS | a S → iCtSS'| a

A→ α β1|α β 2| γ S' → ϵ | eS

2)C → b C→b

Die endgültige Grammatik, die nach der Links-Faktorisierung erhalten wird, ist unten dargestellt:

S → iCtSS'| a
S'→ ϵ | eS
C→b

2.8.6 Probleme mit dem Top-Down-Parser

Erläutern Sie kurz die Probleme, die mit einem Top-Down-Parser verbunden sind?
Die verschiedenen Probleme, die mit dem Top-Down-Parser verbunden sind, sind:

Mehrdeutigkeit in der Grammatik

Linke Rekursion
Nicht links faktorisierte Grammatik

Backtracking
 Systematischer Ansatz zum Compiler-Design - 2.37

Mehrdeutigkeit in der Grammatik: Eine Grammatik, die zwei oder mehr linksseitige Ableitungen hat oder
Zwei oder mehr rechtsseitige Ableitungen werden als mehrdeutige Grammatik bezeichnet. Zum Beispiel die
Die folgende Grammatik ist mehrdeutig:

E → E + E | E – E | E * E | E / E | ( E ) | id

Die mehrdeutige Grammatik ist nicht für einen top-down Parser geeignet. Daher muss die Mehrdeutigkeit behoben werden.
aus der Grammatik entfernt. (Für Einzelheiten siehe Abschnitt 2.6)

Linksrekursion: Eine Grammatik G wird als linksrekursiv bezeichnet, wenn sie ein Nicht-Terminal A hat.
so dass es eine Ableitung der Form gibt:

A Ein (Erhalten durch die Anwendung von einer oder mehreren Produktionen)

wo ist eine Zeichenkette von Terminalen und Nichtterminalen. Das heißt, wann immer das erste Symbol
In einer partiellen Ableitung ist das gleiche wie das Symbol, von dem diese partielle Ableitung stammt.
erhalten, dann wird die Grammatik als linksrekursive Grammatik bezeichnet. Zum Beispiel,
consider the following grammar:

E→ E + T | T
T→T*F|F
F → ( E ) | ist

Die obige Grammatik ist eindeutig, hat jedoch eine linke Rekursion und ist daher nicht
Geeignet für einen Top-Down-Parser. Daher muss die linke Rekursion eliminiert werden (Für Details siehe
Abschnitt 2.8.3 und 2.8.4

Nicht links faktorierte Grammatik: Wenn die A-Produktion zwei oder mehr alternative Produktionen hat
und sie haben ein gemeinsames Präfix, dann hat der Parser einige Verwirrung bei der Auswahl des
angemessene Produktion zur Erweiterung des Nichtterminal A. Zum Beispiel, betrachten Sie die
folgende Grammatik, die die if-Anweisung erkennt:

S →wenn E dann S sonst S | wenn E dann S

Beobachten Sie die folgenden Punkte:

. Beide Produktionen beginnen mit keywordif.
. Wenn wir also den Input „if“ vom lexikalischen Analysator erhalten, können wir nicht sagen, ob wir
verwenden Sie die erste Produktion oder verwenden Sie die zweite Produktion, um das Nicht-
Terminal S.
. Also müssen wir die Grammatik so umformen, dass sie keine gemeinsamen haben.
Präfix. Das bedeutet, dass Left Factoring für das Parsen mit einem Top-Down-Parser erforderlich ist.
2,38 Syntax-Analysator
Eine Grammatik, in der zwei oder mehr Produktionen von jedem Nichtterminal A nicht haben
Ein gemeinsames Präfix von Symbolen auf der rechten Seite der A-Produktionen wird als links bezeichnet.
faktorisierte Grammatik. (Siehe vorherigen Abschnitt für das Durchführen von Left-Factoring)

Backtracking: Das Backtracking ist notwendig für den Top-Down-Parser für Folgendes
reasons:
1) Während des Parse-Vorgangs werden die Produktionen nacheinander angewendet. Aber wenn zwei oder mehr
Alternative Produktionen sind vorhanden, sie werden der Reihenfolge nach von links nach rechts angewendet.
eine Zeit.
2) Wenn eine bestimmte Produktionsanwendung nicht in der Lage ist, das Nichtterminal ordnungsgemäß zu erweitern,
Wir müssen die alternative Produktion anwenden. Bevor wir die alternative Produktion ausprobieren, ist es
notwendig, die mit der aktuellen Produktion durchgeführten Aktivitäten rückgängig zu machen. Dies ist möglicherweise
nur mit Backtracking.

Auch wenn Backtracking-Parser mächtiger sind als prädiktive Parser, sind sie
auch viel langsamer, was im Allgemeinen exponentielle Zeit benötigt und daher Backtracking erfordert
Parser sind nicht für praktische Compiler geeignet.

2.8.7 Rekursiver Abwärts-Parser ohne Backtracking (Prädiktiver Parser)

Was ist ein prädiktiver Parser? Erklären Sie die Funktionsweise eines prädiktiven Parsers.

Definition: Ein prädiktiver Parser ist ein Top-Down-Parser. Es ist eine effiziente Möglichkeit, dies umzusetzen.
ein rekursiver Abwärtsparser, der einen Stapel explizit statt implizit überführt
rekursive Aufrufe. Der prädiktive Parser kann korrekt erraten oder vorhersagen, welche Produktion zu
use if two or more alternative productions are there. This is done using two ways:
Durch das Betrachten der nächsten paar Token (oft als Lookahead bezeichnet) wählt es das richtige aus.
Produktion aus zwei oder mehr Alternativen und Erweitern des Nicht-Terminals
Ohne Rückschritte. Es gibt also keine Frage des Rückgängig-machens schlechter Entscheidungen mit
Backtracking. Tatsächlich werden schlechte Entscheidungen niemals vorkommen.

Da es vorhersagen kann, welche Produktion beim Parsen verwendet werden soll, wird es als prädiktiver Parser bezeichnet.
Die prädiktiven Parser akzeptieren eine eingeschränkte Grammatik, die als LL(k)-Grammatiken bezeichnet wird (definiert in
Abschnitt 2.10)

Lass uns nun sehen: "Was sind die verschiedenen Komponenten eines prädiktiven Parsers? Wie funktioniert er?"
Die Funktionsweise eines prädiktiven Parsers kann leicht erklärt werden, indem man die verschiedenen kennt.
Komponenten des prädiktiven Parsers. Das Blockdiagramm zeigt die verschiedenen Teile von
Prädiktive Parser sind unten dargestellt:
 Systematischer Ansatz zur Compiler-Entwicklung - 2.39

Eingabepuffer
a1a2a3......an$ Der prädiktive Parser hat
vier Komponenten, nämlich:
Eingang
Stapel
X Ausgabe Parsing-Tabelle
Parser program
Y
Z Parsing-Programm
$ Ausgabe
Stack

Parsing-Tabelle
Der Eingabepuffer enthält den zu analysierenden String und der Eingabestring endet
mit „$‟. Hier zeigt $ das Ende der Eingabe an.

Stapel: Es enthält eine Abfolge von Grammatiksymbolen und „$“ wird anfangs oben darauf platziert.
der Stapel. Wenn $ oben auf dem Stapel liegt, bedeutet das, dass der Stapel leer ist.

Parsing-Tabelle: Es handelt sich um ein zweidimensionales Array M[A, a], wobei A ein Nichtterminal ist und
Das Nichtterminal A repräsentiert den Zeilenindex und das Terminal a.
Repräsentieren Sie den Spaltenindex. Der Eintrag in M[A, a] enthält entweder eine Produktion oder
leerer Eintrag.

Parser: Es ist ein Programm, das je nach X, dem Symbol, unterschiedliche Aktionen ausführt.
oben auf dem Stapel und das aktuelle Eingabesymbol a.

Output:As output, the productions that are used are displayed using which the parse
Der Baum kann gebaut werden.

Funktionsweise des Parsers: Die verschiedenen vom Parser durchgeführten Aktionen sind unten aufgeführt:

1)Wenn X = a = $, das heißt, wenn das Symbol oben im Stapel und das aktuelle Eingabesymbol ist
$, dann ist das Parsen erfolgreich.

2) Wenn X = a≠$, das heißt, wenn das Symbol oben auf dem Stapel dasselbe ist wie der aktuelle Eingabewert.
Symbol aber nicht gleich $, dann poppe X vom Stapel und rücke den Eingabepointer vor.
Zeigen Sie auf das nächste Symbol.
2,40 Syntax Analyzer
3) Wenn X ein Terminal ist und ≠ a, das heißt, das Symbol oben auf dem Stapel ist nicht gleich der
aktuelles Eingabesymbol, dann Fehler()

4) Wenn X ein Nicht-Terminal ist und a das Eingabesymbol ist, konsultiert der Parser die Parse-Tabelle.
M[X, a], das entweder eine X-Produktion oder einen Fehler-Eintrag enthält. Wenn X→UVW die
Der Parser entfernt X vom Stack und fügt U, V und W hinzu.
in umgekehrter Reihenfolge auf den Stapel.

Bevor wir sehen, wie der Parser den String analysiert, lassen Sie uns die Parsing-Tabelle erklären.
Wie benutzt man die Parsing-Tabelle? Oder "Welche Informationen werden im prädiktiven Parsing gegeben?"
Tabelle? Die Einzelheiten der Parsing-Tabelle und wie sie verwendet werden kann, können mit Hilfe von der erklärt werden.
beispiel.

Beispiel 2.20: Betrachten Sie die folgende Grammatik und das entsprechende prädiktive Parsen
table:
E→TE'
GRAMMATIK
E'→+TE'|
T → FT'
T'→*FT'|
F → (E) | id
Vorausblick Token
M 2D Parsing-Tabelle
id + * ( ) $
E E → TE' E→ TE'
E' E'→ +TE' E'→ E'→
T T → FT' T → FT'
T' T'→ T'→ *FT1 T'→ T'→
F F → id F → (E)

linksseitige Variable

Die verschiedenen Informationen, die wir aus der obenstehenden Parsing-Tabelle erhalten, sind unten aufgeführt:
Die in der ersten Spalte der Tabelle M vorhandenen Symbole, d.h. E, E', T, T' und F, stehen für
links am weitesten außen stehende Nichtterminale in der Ableitung. Lassen Sie uns das Nichtterminal allgemein bezeichnen
vonA
 Systematischer Ansatz zur Compiler-Design - 2.41

Die in der ersten Zeile präsenten Symbole wie id, +, *, (, ) und $ repräsentieren die nächste Eingabe
tokens obtained from the lexical analyzer. Let us denote the terminal in general by
„a’.

Der Eintrag in einer bestimmten Zeile A und Spalte "a", bezeichnet durch M[A, a], kann entweder sein.
leer oder eine Produktion. Dies ist die für eine Variable A vorhergesagte Produktion, wenn die
Das Eingabesymbol ist „a“. Jetzt wird das Parsen wie unten gezeigt durchgeführt:

1) Wenn E oben auf dem Stapel ist und andis das Eingabesymbol ist, konsultiert der Parser die
Parsing-Tabelle M[E,id], erhält die Produktion E → TE'. Jetzt entfernt der Parser E
Vom Stack und schiebe TE' in umgekehrter Reihenfolge. Also, der Eintrag M[E,id] = E → TE'
weist darauf hin, dass E in der aktuellen linksäußersten Ableitung das linksäußerste Nicht-Terminal ist.
Wenn die Tokenisierer vom Eingang lesen, erweitern wir das Nicht-Terminal E unter Verwendung der
Produktion E → TE'.

2) Wenn E' oben auf dem Stapel ist und die Eingabe „ )“ ist, konsultiert der Parser die Parsing-Tabelle.
M[E', )] und erhält die Produktion E'→ ϵ. Jetzt entfernt der Parser E' aus dem
Stapel. Aber es ist nichts auf der rechten Seite der Produktion, um es zu schieben. Das heißt, die
Der Eintrag M[E', )] = E'→ ϵ zeigt an, dass in der aktuellen linksständigen Ableitung E' der
Das linke Nonterminal wird durch ϵ ersetzt. Somit ist nur die linke Variable übrig.
bei jedem Schritt ersetzt, wenn das Eingabesymbol (Lookahead-Token) vom
Eingabepuffer, der zu einer linksseitigen Ableitung führt. Daher sagen wir, dass prädiktiv
Das Parsen wird die linkseste Ableitung nachahmen.

3) Der Eintrag in Zeile E und Spalte „ +“ ist leer. Dies weist auf einen Fehlerhinweis hin und die
Der Parser sollte geeignete Fehlermeldungen anzeigen.

Now, the various actions performed by the parser are can be implemented using algorithm. The
complete algorithm to parse the string using predictive parser is shown below:

Beispiel 2.21: Der prädikative Parsing-Algorithmus

Die Zeichenfolgewending with $ (end of the input) and the parsing table

Wennw L(G), das heißt, wenn der Eingabestring erfolgreich vom Parser erzeugt wird, dann die
Der Parsebaum wird unter Verwendung der linksseitigen Ableitung konstruiert. Andernfalls zeigt der Parser einen Fehler an.
message.
2,42 Syntax-Analyser
Methode: Zunächst werden das $ und S auf den Stapel gelegt und der Eingabepuffer enthält Eingaben.
Stringwending mit $. Der unten stehende Algorithmus verwendet die Parsing-Tabelle und erzeugt
der Parsebaum. Statt den Parsebaum anzuzeigen, erzeugen wir die Produktionen, die
werden verwendet, um den Ableitungsbaum zu erzeugen.

Lassen Sie den Eingabezeiger auf das erste Symbol von w zeigen

Lass X = S sein das Symbol oben auf dem Stapel.

während (X ≠ $) // Der Stapel ist nicht leer

Wenn ( X == a) // Stapelsymbol = Eingabesymbol
Pop X vom Stapel
Bewege den Eingabezeiger voran.
ansonsten, wenn X ein Terminal ist

Error()
ansonsten, wenn M[X, a] leer ist

Fehler()
ansonsten, wenn M[X, a] = X → Y1Y2Y3…….Yk

Gebe die Produktion X → Y aus1Y2Y3…….Yk

Entfernen Sie X vom Stapel
Drücke Y1,Y2,Y3,…….Ykin umgekehrter Reihenfolge

endif
Sei X = oberstes Stapelsymbol
Ende der Schleife

Die anfängliche Konfiguration des Parsers

Stapel Eingabe
$S w$
Endkonfiguration des Parsers, falls das Parsen erfolgreich ist

Stapel Eingang
$ $
 Systematischer Ansatz zur Compiler-Entwicklung - 2.43

Beispiel 2.22: Betrachten Sie die folgende Grammatik und die entsprechende prädiktive
Parsing-Tabelle:
E → TE'
GRAMMATIK
E'→+ TE'|
T → FT'
T'→*FT'|
F → (E) | id

M Parsing-Tabelle
id + * ( ) $
E E → TE' E→ TE'
E' E1+TE' E'→ E'→
T T → FT' T → FT'
T' T'→ T1→ *FT' T'→ T'→
F F → id F → (E)

Zeigen Sie die Abfolge der Züge, die der prädiktive Parser für die Zeichenkette id+id*id während des Parsens gemacht hat.

Lösung: Die Abfolge der Züge, die der Parser für den String id+id*id gemacht hat, wird angezeigt.
unten:

id + * ( ) $
E E → TE' E→ TE'
E' E'→ +TE' E'→ E'→
T T → FT' T → FT'
T' T'→ T'→ *FT' T'→ T'→
F F →id F → (E)

M[E, id] = E → TE'

Stapel Eingabe Output Aktion

$E id+id*id$ E → TE' [Entferne E und drücke TE' rückwärts]

$ E'T id+id*id$ T → FT' [Entfernen Sie T und drücken Sie FT in umgekehrter Reihenfolge]
2.44 Syntax-Analyzer
$ E'T'F id+id*id$ F →id [Entferne F und pushid]

$ E'T'id id+id*id$ match(id) [Entferneidincrement i/p ptr]

$ E'T' +id*id$ T'→ [ Entferne T' vom Stapel ]

$ E' +id*id$ E'→ +TE' [Entferne E' und drücke +TE' rückwärts]

$ E'T+ +id*id$ spielen(+) [Entferne+erhöhe i/p Zeiger]

$ E'T id*id$ T → FT' [T entfernen und FT umgekehrt schieben]

$ E'T'F id*id$ F → id [Entferne F und pushid]

$ E'T'id id*id$ Übereinstimmen(id)

[ID entfernen und Zeiger auf Eingabedaten erhöhen]

$ E'T' *id$ T→
1 *FT' [Entferne T' und drücke *FT' rückwärts]

$ E'T'F * *id$ Übereinstimmung (*)[Entferne*Inkrement i/p Zeiger]

$ E'T'F id$ F → id [Entferne F und pushid]

$ E'T'id id$ Übereinstimmung(id)

[ID entfernen und Eingabezeiger erhöhen]

$ E'T' $ T'→ [Entferne T' vom Stapel]

$ E' $ E'→ [E' vom Stapel entfernen]

$ $ AKZEPTIEREN

Da der Stapel $ enthält und der Eingabezeiger auf $ zeigt, wird der Stringid+id*idis analysiert.
erfolgreich.

2.9 FIRST und FOLLOW

Der prädiktive Parser kann leicht konstruiert werden, sobald wir die FIRST- und FOLLOW-Mengen kennen.
Diese Symbolgruppen helfen uns, die prädiktive Parsing-Tabelle sehr einfach zu erstellen.

2.9.1 Berechnung der FIRST-Symbole

Lassen Sie uns „FIRST(α) definieren“

 Systematischer Ansatz zur Compiler-Entwicklung - 2.45

Definition: FIRST(α) ist definiert als die Menge von Terminalsymbolen, die am Anfang erscheinen.
Ableitung von α. Formal wird FIRST(α) wie unten gezeigt definiert:

ϵ wenn α = ϵ Definition 1
ERSCHIENEN(α) = ϵ wenn α ϵ Definition 2
ein wenn α aβ Definition 3

Beispiel 2.23: Berechnen Sie die FIRST-Mengen für jedes Nichtterminal in der folgenden Grammatik
E → TE'
E'→+TE'|
T → FT'
T'→*FT'|
F → (E) | id

Solution:The FIRST sets for the given grammar can be computed by obtaining various
Ableitungen wie unten gezeigt:

E T E' F T'E' ( E ) T'E'

E T E' F T'E' id T'E'

FIRST(E) =
FIRST(T) =
FIRST(F) = { (, id }
Berücksichtigen Sie die Ableitungen, die in der vorherigen Ableitung nicht verwendet wurden:

E' + T E' T' * F T'

E' ϵ T' ϵ

So, FIRST(E')={ ϵ, + } Also, FIRST(T')= {ϵ,* }

Jetzt sind die endgültigen FIRST-Mengen wie unten angegeben geschrieben:

E E' T T' F
ERSTE (, id ϵ, + (, id ϵ, * (, id
2,46 Syntax-Analyzer
Jetzt stellt sich die Frage: "Was ist der Zweck von FIRST-Mengen?" Die FIRST-Mengen können verwendet werden
Während der prädiktiven Analyse beim Erstellen der prädiktiven Analyse-Tabelle wie unten gezeigt:
Betrachten Sie die A-Produktion A→ α | β und nehmen Sie an, dass FIRST(α) und FIRST(β) disjunkt sind.
d.h., FIRST(α) ∩ FIRST(β) = {} was eine leere Menge ist.
Wenn das von dem lexikalischen Analysator erhaltene Eingabesymbol ist a und wenn a in FIRST(α) ist, dann
Verwenden Sie die Produktion A→ α während des Parsens.

Wenn das Eingabesymbol, das vom lexikalischen Analysator erhalten wurde, band ist und ifbis in FIRST(β) ist, dann
Verwenden Sie die Produktion A → β während der Analyse.

So können wir mithilfe von FIRST-Mengen auswählen, welche Produktion zwischen den beiden verwendet werden soll.

Produktionen A→ α | β, wenn das Eingabesymbol a oder b ist.

Lass uns nun sehen: "Was sind die Regeln, die befolgt werden müssen, um FIRST(X) zu berechnen?" oder "Was ist
der Algorithmus zur Berechnung von FIRST(X)? Der Algorithmus oder die Regeln zur Berechnung von FIRST(X)
werden unten gezeigt:

ALGORITHMUS ERSTE(X)
Regel 1: Wenn X→a wo ist ein Terminal, dann FIRST(X)←a
Regel 2: Wenn X → ϵ, dann FIRST(X) ← ϵ

Regel 3: Wenn X → Y1Y2Y3………Ynund wenn Y1Y2Y3………Yich– 1ϵ,dann

FIRST(X) ← nicht-ϵ Symbole in FIRST(Yich).

Regel 4: Wenn X→Y1Y2Y3………Ynund Y1Y2Y3………Yn ϵ, dann FIRST(X) ← ϵ

Regel 5: Wenn X ein Terminal oder ,ϵ ist, dann FIRST(X) ← X

Lass uns jetzt sehen, wie die FIRST-Mengen berechnet werden, indem wir einige spezifische Beispiele betrachten:

Regel 1 wird angewendet, wenn das erste Symbol auf der rechten Seite der Produktion ein ist.
Terminal. Wenn ja, fügen Sie nur das erste Zeichen hinzu.
Ex 1: wenn A → aBC, dann FIRST(A) = {a}
Ex 2: wenn E → +TE1dann FIRST(E) = {+}
Ex 3: Wenn A → abc, dann FIRST(A) = {a}
Regel 2 wird nur für ϵ -Produktionen angewendet
Ex 1: wenn A → ϵ, dann FIRST(A) = { ϵ }
1
Ex 2: wenn E → ϵ, dann FIRST(E1) = {ϵ }
Regel 3 wird auf alle Produktionen angewendet, die in den ersten beiden Schritten nicht berücksichtigt wurden.
 Systematischer Ansatz zur Compiler-Entwicklung - 2.47
Beispiel: Betrachten Sie die Produktionen:
S → ABCd
A→ ϵ |+B
B→ ϵ |*B
C→ ϵ |%B
FIRST(A), FIRST(B), FIRST(C) werden mit den Regeln 1 und 2 wie unten gezeigt berechnet:
S A B C
ERSTE ϵ,+ ϵ,* ϵ,%

To compute FIRST(S) consider the production S → ABCd and apply rule 3 as shown
unten:
a)S → ABCd Fügen Sie die Nicht-ϵ-Symbole von FIRST(A) zu FIRST(S) hinzu

b)S → ABCd Seit A ϵ, füge Nicht-ϵ-Symbole von FIRST(B) zu FIRST(S) hinzu

c)S → ABCd Seit AB ϵ, füge Nicht-ϵ-Symbole von FIRST(C) hinzu

ERSTE(N)

d)S → ABCd Seit ABC ϵ, füge non-ϵ-Symbole von FIRST(d) hinzu

ERSTE(N)
Die oben genannten Aktionen sind bildlich wie folgt dargestellt:
S Ein B C
ERSTE %, *, +, d ϵ,+ ϵ,* ϵ,%
Schritt (d)
Schritt (a)
Schritt (b)
Schritt (c)

4) Regel 4 wird für alle Produktionen angewendet, deren rechter Teil ϵ ergibt.

Betrachten Sie die Produktionen:

S → ABC
A→ ϵ | +B
B→ ϵ | *B
C→ ϵ | %B
FIRST(A), FIRST(B), FIRST(C) werden unter Verwendung der Regeln 1 und 2 wie unten gezeigt berechnet:
2,48 Syntax-Analysator

S Ein B C
ERSTE ϵ,+ ϵ,* ϵ,%

Um FIRST(S) zu berechnen, betrachten Sie die Produktion S → ABC und wenden Sie Regel 3 an, wie gezeigt.
darunter:
a)S → ABC Fügen Sie Nicht-ϵ-Symbole von FIRST(A) zu FIRST(S) hinzu

b)S → ABC Seit A ϵ, füge Nicht-ϵ-Symbole von FIRST(B) zu FIRST(S) hinzu

c) S → ABC Seit AB ϵ, füge Nicht-ϵ-Symbole von FIRST(C) hinzu

ERSTE(N)

d)S → ABC Seit ABC ϵ, füge ϵ zu FIRST(S) hinzu

Alle oben genannten Aktionen sind bildlich dargestellt, wie unten gezeigt:

S Ein B C
ERSTE %, *, +,ϵ ϵ,+ ϵ,* ϵ,%
Schritt (d)
Schritt (a)
Schritt (b)
Schritt (c)

Regel 5 gilt nur für Terminals.

Ex 1:+ ist terminal. Also, FIRST(+) = { + }
Ex 2: a ist ein Terminal. Daher ist FIRST(a) = {a}
Ex 3: id ist ein Terminal. Also, FIRST(id) = {id}

Hinweis: ERSTE(X1X2X3………Xn) kann wie folgt berechnet werden :

1) ERSTE(X1X2X3………Xn) ← Nicht-ϵ-Symbole von FIRST(X1)
2) wenn FIRST(X1) = ϵ, dann FIRST(X1X2X3………Xn) ← ERSTE(X2) -ϵ
3) wenn FIRST(X1) und FIRST(X2) = ϵ dann FIRST(X1X2X3………Xn) ← ERSTE(X3) -ϵ
……..
……..
4) Wenn FIRST(X1), ERSTE(X2),….. und ERSTE(Xn) = ϵ, dann FIRST(X1X2…Xn) ← ϵ
 Systematischer Ansatz zur Compiler-Entwicklung - 2.49

Beispiel 2.24: Lass FIRST(A) = {+,ϵ}, FIRST(B) = { *,ϵ} und FIRST(C) = { %, - }

Berechne FIRST(ABC)

Lösung: Durch die Verwendung von FIRST(A), FIRST(B) und FIRST(C) kann FIRST(ABC) ermittelt werden.
wie unten gezeigt:

Ein B C
ERSTE(ABC) ERSTE+, ϵ *, ϵ %, -
nicht-ϵSymbole 1 2 3
+
Nicht-ϵ-Symbole
*
nicht-ϵSymbole
%, -

1Fügen Sie Non- ϵ-Symbole von FIRST(A) hinzu

2 Da FIRST(A) ϵ enthält, fügen wir Nicht-ϵ-Symbole von FIRST(B) hinzu.

3 Da FIRST(A) und FIRST(B) ϵ enthalten, fügen wir die Nicht-ϵ-Symbole von FIRST(C) hinzu.

Also, FIRST(ABC) = {+, *, %, - }

Beispiel 2.25: Seien FIRST(A) = {+,ϵ}, FIRST(B) = { *,ϵ} und FIRST(C) = { %, -,ϵ}
Berechnen Sie FIRST(ABC)

Lösung: Mit FIRST(A), FIRST(B) und FIRST(C) kann FIRST(ABC) erhalten werden.
wie unten gezeigt:

A B C
ERSTE(ABC) ERSTE+, ϵ *, ϵ %, -, ϵ
Nicht-ϵ-Symbole 1 2 3
+
nicht-ϵ-Symbole
*
nicht-ϵSymbole
%, -

ϵ ϵ 4
2,50 Syntax-Analyzer
1Fügen Sie Nicht- ϵ-Symbole von FIRST(A) hinzu

2 Da FIRST(A) ϵ enthält, fügen wir die Nicht-ϵ-Symbole von FIRST(B) hinzu.

3 Da FIRST(A) und FIRST(B) ϵ enthalten, fügen wir die Nicht-ϵ-Symbole von FIRST(C) hinzu.

4 Da FIRST(A), FIRST(B) und FIRST(C) ϵ enthalten, fügen wir das ϵ-Symbol hinzu.

Also, FIRST(ABC) = {+, *, %, -, ϵ }

2.9.2 Berechnung von FOLLOW-Symbolen

Sobald wir wissen, wie man FIRST-Mengen berechnet, wollen wir uns darauf konzentrieren, wie man ...
FOLLOW-Mengen. Bevor wir weiter fortfahren, lassen Sie uns "FOLLOW(A) definieren?"

Definition: Das FOLLOW(A) für ein Nichtterminal A ist definiert als die Menge der Terminals.
das wird unmittelbar rechts von A in einer Satzform erscheinen. Das heißt, die Menge von
Terminalsasuch, dass es eine Ableitung der Form gibt:
SαAaβ
Für einige α und β. Wenn A als das letzte Symbol in einer bestimmten Form erscheint, dann platziere
in FOLLOW(A), wobei das Symbol $ als "Endmarker" behandelt wird.
Lassen Sie uns nun sehen: "Was ist der Algorithmus zur Berechnung von FOLLOW(A)?" Der Algorithmus zur
Die Berechnung von FOLLOW(A) ist unten dargestellt:

ALGORITHMFOLGEN(A)
Regel 1: FOLLOW(S) ← $ wobei S das Startsymbol ist.
Regel 2: Wenn A → B ist eine Produktion und ≠ dann FOLLOW(B) ← nicht- Symbole in
ERSTE )
Regel 3: Wenn A → B ist eine Produktion und , dann FOLLOW(B) ←FOLLOW(A)

Beispiel 2.26: Berechnen Sie die FIRST- und FOLLOW-Mengen für die folgende Grammatik:
E → TE'
E'→+ TE'|
T → FT'
T'→*FT'|
F → (E) | id
 Systematischer Ansatz zur Compiler-Entwicklung - 2.51
a) Berechnung der FIRST-Mengen: Die FIRST-Mengen können wie unten gezeigt berechnet werden:

Regel 1: E'→+ TE' T'→ * FT' F→ ( E )

F→id

Rule 2: E'→ ϵ T'→ ϵ

+,ϵ *, ϵ (, id
E E' T T' F
Regel 3 - (a) Regel 3 - (b)

Regel 3: Berücksichtigen Sie die zuvor nicht berücksichtigten Produktionen und erhalten Sie die FIRST-Mengen wie gezeigt.
unten:
a) E → T E' Fügen Sie „FIRST(T) -ϵ“ zu FIRST(E) hinzu, d.h. zeichnen Sie ein
Kante von T nach E in der obigen Abbildung.

b) T →F T' Fügen Sie "FIRST(F)-ϵ" zu FIRST(T) hinzu, d.h. ziehen Sie ein
Kante von F nach T in der obigen Abbildung.

Über der Abbildung, übertrage FIRST(T) zu FIRST(E) und von FIRST(F) zu FIRST(T). So,
Die endgültigen FIRST-Mengen sind unten dargestellt:

ERSTE (, id +,ϵ (, id *, ϵ (, id
E E' T T' F

b) Berechnung der FOLLOW-Mengen:

E $, ) E' $, ) T +, $, ) T' +, $, ) F +, *, $, )

Regel 1: $ wird in FOLLOW(E) platziert, da E das Startsymbol ist.

Regel 2 & 3: Wenden Sie Regel 2 und 3 auf jede Produktion der Form A → αBβ an, wobei B
ist ein Nichtterminal. In der ersten Spalte, die unten gezeigt wird, kopiere von FIRST(β) bis
FOLLOW(B) and in the second column copy from FOLLOW(A) to FOLLOW(B).
2,52 Syntax-Analyse

Rule 2(β ≠ ϵ)FOLLOW(B)←FIRST(β) -ϵRule 3(β ϵ) FOLLOW(A)→FOLLOW(B)

Von rechts nach links kopieren (Pfeil von Von links nach rechts kopieren (Pfeil von
rechts links auf der rechten Seite der Produktion LHS der Produktion zu RHS)

E → T E' E → T E'
A→ α B β A→αBβ

E → T E' Regel 2 nicht anwendbar E T E'

A→αBβ A→α B β

E1→ + T E' E'→ + T E'

A → α B β A→αBβ

E1→ + T E' Regel 2 nicht anwendbar E'→ + T E'

A→ α B β A→ α B β

T → F T' T F T'
A→αBβ A→αBβ

T → F T' Regel 2 nicht anwendbar T → F T'

A→αBβ Aα B β

T'→ *F T' T'→* F T'

A→ α B β A→αBβ

T'→ * F T' Regel 2 nicht anwendbar T'→ * F T'

A→ α B β A→ α B β

F → ( E ) F → ( E )
A→ αB β Regel 3 nicht anwendbar
A → αB β
 Systematischer Ansatz zur Compiler-Entwicklung - 2.53

Lassen Sie uns jetzt sehen: "Welche Schritte sind beim Aufbau des prädiktiven Modells zu beachten?"
„Die verschiedenen Schritte, die beim Erstellen des prädiktiven Parsers befolgt werden müssen, sind
unten dargestellt:
Wenn die Grammatik mehrdeutig ist, beseitigen Sie die Mehrdeutigkeit aus der Grammatik.
Wenn die Grammatik linke Rekursion hat, eliminieren Sie die linke Rekursion.
Wenn die Grammatik zwei oder mehr Alternativen mit gemeinsamer Präfix hat, dann führe Links-
Faktorisierung
Die resultierende Grammatik ist geeignet, um eine prädiktive Parsing-Tabelle zu erstellen.

2.9.3 Konstruktion der prädiktiven Parsing-Tabelle

Jetzt können wir mit den FIRST- und FOLLOW-Mengen die prädiktive Analyse leicht erstellen.
Tabelle und die Produktionen werden in die Tabelle M[A, a] eingegeben, wo
M ist ein zweidimensionales Array, das die prädiktive Parsing-Tabelle darstellt
A ist ein Nichtterminal, das die Zeilenwerte darstellt.
ais ein Terminal oder $ , welches als Endmarkierung dient und die Spaltenwerte darstellt

Nun, lassen Sie uns "Den Algorithmus zum Konstruieren der prädiktiven Analyse-Tabelle schreiben". Das vollständige
Der Algorithmus ist unten dargestellt:

ALGORITHMPredictive_Parsing_Tabelle(G, M)
Eingabe Grammatik G
Ausgabe Vorhersage-Parsing-Tabelle M
Procedure Für jede Produktion A → α der Grammatik G wenden Sie die folgenden Regeln an

1) Für jeden Terminal A FIRST(α) hinzufügen A→ α zu M[A, a]

2) Wenn FIRST(α) enthält , für jedes Symbol bin FOLLOW(A) füge A→ α zu M[A,b] hinzu

Beispiel 2.27: Erhalten Sie die prädiktive Parsing-Tabelle für die folgende Grammatik
E → TE'
E'→+TE'|
T → FT'
T→*FT'|
1

F → (E) | id

Lösung: Die FIRST- und FOLLOW-Mengen jedes Nicht-Terminals der gegebenen Grammatik sind
unten gezeigt: (Siehe Beispiel 2.26 für Einzelheiten)
E E' T T' F
ERSTE (, id +, ϵ (, id *,ϵ (, id
FOLGEN ), $ ), $ +, ), $ +, ), $ +, *, ), $
2,54 Syntax-Analyzer
Für jede Produktion der Form A → α berechnen wir FIRST(α) und die Einträge von
Die Analyse der Tabelle kann wie unten gezeigt durchgeführt werden:

Productions a = ERSTE( ) M[A, a] = A→α Regel

A→α
E → TE' (, id M [ E, ( ] = E → TE' 1
A M [ E, id ] = E→ TE'

E'→+TE' + M [ E', + ] = E'→+TE' 1

Ein
E'→ M [ E', ) ] = E' 2
Ein M [ E', $ ] = E'→

T → FT' (,id M [ T, ( ] = T → FT' 2

A M [ T, id] = T → FT'

T'→ *FT' * M [ T', *] = T'→ *FT' 2

A
T'→ M [ T', + ] = T'→ 3
A M [ T', ) ] = T'→
M [ T', $ ] = T'→

F → (E) ( M [ W, ( ] = F → ( E ) 2
Ein
F → id id M [ F,id] = F →id 2
A

The parsing table is shown below:

id + * ( ) $
E E→TE' E→TE'
E' E'→+TE' E'→ E'→
T T→FT' T→FT'
T' T'→ T'→*FT' T'→ T'→
F F→id F→(E)
 Systematischer Ansatz zur Compiler-Entwicklung - 2.55

Hinweis: Da es keine mehreren Einträge in der Analyse-Tabelle gibt, wird die gegebene Grammatik als bezeichnet
LL(1)-Grammatik. Wenn mehrere Einträge in der Parsing-Tabelle vorhanden sind, ist die Grammatik nicht
LL(1). Der prädiktive Parser akzeptiert nur die Sprache, die aus LL(1)-Grammatik erzeugt wird.

2.10 LL (1) Grammars

In diesem Abschnitt lassen Sie uns sehen: "Was ist eine LL(1)-Grammatik?"

Definition: Die Grammatik, aus der ein prädiktiver Parser, das heißt ein rekursiver Abstieg-Parser, stammt.
ohne Rückverfolgung ist konstruiert wird als LL(1)-Grammatik bezeichnet, wo
Das erste L steht für einen von links nach rechts gerichteten Scan der Eingabe.
The second L stands for leftmost derivation. So, the predictive parsers always mimic
die linksseitige Ableitung.
Die Ziffer 1 gibt die Anzahl der Tokens an, die vorausgeschaut werden sollen.

Bei der LL(1)-Parsing-Technik oder der prädiktiven Analyse, wenn zwei oder mehr alternative Produktionen
Der prädiktive Parser, auch LL(1)-Parser genannt, wählt die korrekte Produktion aus, indem er
guessing using one lookahead token.
Lass uns jetzt sehen: "Welche Grammatiken sind nicht LL(1)?" Die folgenden Grammatiken sind nicht LL(1)
grammars:
Mehrdeutige Grammatik ist nicht LL(1)
Linksrekursive Grammatik ist nicht LL(1)
Die Grammatik, die nicht links faktorisiert ist (das heißt, wenn zwei oder mehr alternative Produktionen
haben einen gemeinsamen Präfix), ist die Grammatik nicht LL(1)
Die Grammatik, die zu mehreren Einträgen in der Parsing-Tabelle führt, ist nicht LL(1).
Jetzt stellt sich die Frage: "Wie überprüft man, ob eine gegebene Grammatik LL(1) ist oder nicht, ohne
„Der grammatische Parser wird konstruiert?“ Die Grammatik wird als LL(1) bezeichnet, wenn die folgenden zwei
Bedingungen sind erfüllt:
Für jede Produktion der Form A→ α1| α2|α3|…….αn:
ERSTE(αich) ∩ ERSTE(αj) must be empty for all i, j n wobei i ≠ j
Für jedes Nichtterminal A, dessen FIRST(A) ϵ enthält:
FIRST(A) ∩ FOLLOW(A) muss leer sein

Beispiel 2.28: Berechnen Sie die FIRST- und FOLLOW-Symbole sowie die prädiktive Parsing-Tabelle für
die folgende Grammatik:
S→iCtS | iCtSeS | a
C→b
Ist die folgende Grammatik LL(1)?
2.56 Syntax-Analyzer
Lösung: Wir wissen, dass die Grammatik nicht linksfaktorisiert ist, da zwei Produktionen haben
Gemeinsames Präfix „iCtS“. Daher ist es notwendig, die Linksfaktorisierung für die gegebene Grammatik durchzuführen.
Die linksfaktorierte Grammatik (für Einzelheiten siehe Abschnitt 2.8.5, Beispiel 2.19) ist unten dargestellt:

S → iCtSS'| a
S'→ ϵ | eS
C→b

Das folgende Verfahren wird verwendet:

Compute FIRST sets and FOLLOW sets
Überprüfen Sie, ob die Grammatik LL(1) ist oder nicht
Erhalten Sie die Parsing-Tabelle

Schritt 1: Die ersten Symbole können wie unten gezeigt berechnet werden:

Regel 1: S → i CtSS' S'→ e S C→b

S→a

Regel 2: S'→ ϵ

ich, ein e,ϵ b

Regel 3: Diese Regel wird nicht angewendet, da alle Produktionen bereits berücksichtigt werden, wenn wir
Wenden Sie die ersten beiden Regeln an. Die endgültigen FIRST-Mengen sind unten angezeigt:

S S' C
ERSTE ich, ein e,ϵ b

FOLLOW sets:
S S' C
FOLGEN $, e $, e t

Regel 1: $ wird in FOLLOW(S) platziert, da S das Startsymbol ist.

Regel 2 und 3: Wenden Sie Regel 2 und 3 auf jede Produktion der Form A → αBβ an, wobei B
ist ein Nichtterminal. In der ersten Spalte, die unten gezeigt wird, kopieren Sie von FIRST(β) bis
FOLLOW(B) und in der zweiten Spalte von FOLLOW(A) nach FOLLOW(B) kopieren.
 Systematischer Ansatz zur Compiler-Entwicklung - 2.57

Rule 2(β ≠ ϵ)FOLLOW(B)←FIRST(β) -ϵRule 3(β ϵ) FOLLOW(A)→FOLLOW(B)

t
S → i C t S S' Regel 3 nicht anwendbar
A → αBβ

S → i C t S S' S → ich C t S S'

A→αBβ A→α B β

S → i C t S S' Regel 2 nicht anwendbarS → i C t S S'

A→α B β A→ α B β

S'→e S Regel 2 nicht anwendbarS'→ e S

A→ α B β A→αBβ

Hinweis: Die Produktionen S → a und C → b werden beim Berechnen von FOLLOW nicht berücksichtigt.
Da es in diesen Produktionen keine Variablen gibt. Daher sind die FIRST- und FOLLOW-Mengen für
Die linksfaktorisierte Grammatik ist unten dargestellt:

S S' C
ERSTE a, i e, ϵ b
FOLLOW $, e $, e t
Um zu überprüfen, ob die Grammatik LL(1) ist oder nicht: Ohne den prädiktiven Parser zu konstruieren
Parser können wir auch überprüfen, ob die Grammatik LL(1) ist oder nicht. Wenn die Grammatik LL(1) ist,
Die folgenden beiden Bedingungen müssen erfüllt sein:

Bedingung 1: Für eine gegebene Produktion Bedingung, die erfüllt sein muss
A→ α1| α2|α3|…….αn ERSTE(α1) ∩ FIRST(α2)∩….ERSTE(αn) = ϕ

S → i C t S S'| a FIRST(iCtSS')∩ FIRST(a)

{i} ∩ {a}= ϕ
S'→ ϵ | eS FIRST(ϵ)∩ FIRST(eS)
{ ϵ } ∩ {e} = ϕ

Hinweis:Bedingung 1 ist erfüllt

2,58 Syntax-Analysator
Bedingung 2: Wenn FIRST(A) ϵ enthält Bedingung, die erfüllt sein muss, ist
FIRST(A)∩ FOLLOW(A) = ϕ

ERSTE(S') hatϵ ERSTER(S')∩ FOLLOW(S')

{ e, ϵ}∩{$, e} = {e}

Hinweis:Condition 2 is not satisfied:

Da eine der Bedingungen nicht erfüllt ist, ist die gegebene Grammatik nicht LL(1). Damit eine Grammatik ...
LL(1), müssen beide Bedingungen erfüllt sein.

Konstruktion der prädiktiven Parsing-Tabelle: Für jede Produktion der Form A → α, wir
Die Berechnung von FIRST(α) und die Einträge der Abgleichtabelle können wie unten gezeigt durchgeführt werden:

{"Productions":"Produktionen"}
a = ERSTE( ) M[A, a] = A→α Rule
A→α
S→iCtSS' Ich M [ S, i ] = S→iCtSS' 1
A
S→a a M [ S, a ] = S→a 1
A
S' → eS e M [ S', e ] = S'→eS 1
A
S'→ M [ S', e ] = S'→ 2
Ein M [ S', $ ] = S'→

C→b b M [ C, b ] = C→b 1
A

Die Analyse-Tabelle ist unten gezeigt:

a b e Ich t $
S S→a S → iCtSS'
S1 S'→eS S'→
S'→
C C→b
 Systematischer Ansatz zur Compiler-Entwicklung - 2.59

Beispiel 2.29: Gegeben die folgende Grammatik:

S → a | (L)
L→L , S | S
a) Ist die Grammatik für einen prädiktiven Parser geeignet?
b) Nehmen Sie die notwendigen Änderungen vor, um es für einen LL(1)-Parser geeignet zu machen.
c) Berechnen Sie die FIRST- und FOLLOW-Mengen für jedes Nicht-Terminal
d) Erstellen Sie die Parsing-Tabelle und überprüfen Sie, ob die resultierende Grammatik LL(1) ist oder nicht.
e) Zeigen Sie die Züge des prädiktiven Parsers für die Eingabe „( a , ( a , a ) )“

Lösung: Die gegebene Grammatik ist unten dargestellt:

S → a | (L)
L→L , S | S

a) Betrachten Sie die Produktion: L→ L , S

Da das erste Symbol auf der rechten Seite der Produktion dasselbe ist wie das Symbol auf der linken Seite der
Die gegebene Grammatik hat eine linke Rekursion und ist daher nicht geeignet.
für den prädiktiven Parser.

b) Um es für den LL(1)-Parser oder den prädiktiven Parser geeignet zu machen, müssen wir die linke Eliminierung entfernen.
Rekursion wie unten gezeigt: (Für Einzelheiten siehe Abschnitt 2.8.4)

Links rekursive Produktionen Rechtsrekursive Produktionen

A→ A 1|A 2|A 3|……|A n|β1| β2| β3| ……..| βm A→ β1A'| β2A'|β3A'| ……..|βmA'
A'→ 1A'| 2A'| 3A'|……| nA'| ϵ

1) S →a | (L) S→a | (L)

2) L →L , S | S L→SL'
↓ ↓ ↓ ↓ L'→, S L'|ϵ
A→A 1| β1

Die endgültige Grammatik, die nach der Eliminierung der linken Rekursion erhalten wurde, kann wie folgt geschrieben werden.

darunter:
S → a | (L)
L → SL'
L'→ , S L'| ϵ
2,60 Syntax-Analyse
c) Berechnung von FIRST und FOLLOW: Die First-Menge kann wie unten dargestellt berechnet werden:

Regel 1: S → ( L ) L'→ , S L'

S→a

Rule 2: L'→ ϵ

S a, ( L L' ,ϵ

Regel 3: Berücksichtigen Sie die zuvor nicht betrachteten Produktionen und erhalten Sie die FIRST-Mengen, wie gezeigt.
unten:
a) L →S L' FÜHRE(S) -ϵ zu FÜHRE(L) hinzu

Über der Abbildung, übertrage FIRST(S) zu FIRST(L). Die finalen FIRST-Mengen werden angezeigt.
unten:
S L L'
ERSTE a, ( a, ( ,ϵ

FOLLOW sets:
S L L'
FOLGEN
$ ) )

Regel 1: $ wird in FOLLOW(S) platziert, da S das Startsymbol ist.

Regel 2 & 3: Wenden Sie Regel 2 und 3 für jede Produktion der Form A → αBβ an, wobei B
ist ein Nicht-Terminal. In der ersten Spalte, die unten gezeigt wird, kopiere von FIRST(β) nach
FOLLOW(B) und in der zweiten Spalte von FOLLOW(A) nach FOLLOW(B) kopieren.

Regel 2(β ≠ ϵ)FOLLOW(B)←FIRST(β) -ϵRegel 3(β ϵ) FOLLOW(A)→FOLLOW(B)

)
S→(L) rule 3 not applicable
A → αBβ

L → S L'
L→S L'
A→αBβ
A→αBβ
 Systematischer Ansatz zur Compiler-Entwicklung - 2.61

L → S L' Regel 2 nicht anwendbar L → S L'

A→αBβ A→αBβ

L1→ S, L' L'→ , S L'

A→αBβ A→αBβ

L1→ S, L-Regel 2 nicht anwendbar L'→ , S L' führt zu einer Selbstschleife

A→α B β A → α B βund daher verwerfen

Hinweis: Die Produktionen S → a und L' → ϵ werden bei der Berechnung nicht berücksichtigt.

FOLLOW, da sie in diesen Produktionen keine Nichtterminals haben. Deshalb das FIRST
and FOLLOW sets for the left-factored grammar are shown below:
S L L'
ERSTE a ein ,ϵ
FOLGEN ,$) ) )
d) Konstruktion der Parsing-Tabelle: Für jede Produktion der Form A → α, wir
Die Berechnung von FIRST(α) und die Einträge der Parsing-Tabelle können wie unten gezeigt durchgeführt werden:

Produktionen a = ERSTE( ) M[A, a] = A→α Regel

A→α
S→a a M [ S, a ] = S →a 1
Ein
S→(L) ( M [ S, ( ] = S →( L ) 1
Ein
L→ SL' ein M [ L, a ] = L→SL' 1
M [ L, ( ] = L→SL'
A
L'→ M [ L', ) ] = L' 2
Ein
L'→, SL' , M [ L',„,‟] = L'→, SL' 1

Ein
2,62 Syntaxanalyse
Die oben genannten Einträge können in die Parsing-Tabelle wie unten gezeigt eingegeben werden:

( ) a , $
S S → (L) S→a
LL→SL1 L→SL1
L1 L1→ L1→,SL1

Da es keine mehrfachen Einträge in der Parser-Tabelle gibt, ergibt sich die resultierende Grammatik nach
Die Beseitigung von linker Rekursion ist LL(1).

e) Die Züge, die der prädiktive Parser am Eingabewert „( a , ( a , a ) )“ vornimmt, sind gezeigt
darunter:

Stapel Eingang Ausgabe Aktion

$S (a,(a,a))$ S → (L) [S entfernen und (L) umgekehrt drücken]

$)L( (a,(a,a))$ Spiel Pop (und Inkremet i/p Zeiger

$)L a,(a,a))$ L→SL' [Entfernen Sie L und pushSL in umgekehrter Reihenfolge]

$ ) L'S a,(a,a))$ S→a [Entfernen Sie S und schieben Sie umgekehrt]

$ ) L'a a,(a,a))$ Spiel ein Popa und i/p Zeiger inkrementieren

$ ) L' ,(a,a))$ L'→,SL' Entfernen Sie L'und drücken Sie, SL'in umgekehrt

$ ) L'S , ,(a,a))$ Spiel Pop „,‟ und inkrementiere den i/p-Zeiger

$ ) L'S (a,a))$ S → (L) Entferne S und drücke (L) rückwärts

$ ) L') L ( (a,a))$ Spiel Pop (und Inkrement i/p Zeiger

$ ) L') L a,a))$ L→SL' Entferne L und drücke SL rückwärts

$ ) L') L'S a,a))$ S→a Entferne S und drücke rückwärts

$ ) L') L'a a,a))$ S →a Popa und den i/p-Pointer erhöhen

$ ) L') L' ,a))$ L'→,SL' Entfernen Sie L' und schieben Sie, SL' in umgekehrter Richtung
 Systematischer Ansatz zur Compiler-Entwicklung - 2.63

$ ) L') L'S , ,a))$ Spiel Pop, und den i/p-Zeiger erhöhen

$ ) L') L'S a))$ S→a Entferne S und pusha

$ ) L') L'a a))$ Matcha Popa und den i/p-Zeiger inkrementieren

$ ) L') L' ))$ L' Pop L'

$ ) L') ))$ Match ) Pop ) und i/p Zeiger inkrementieren

$ ) L' )$ L' Pop L'

$) )$ Passend) Pop ) und Inkrement des i/p Zeigers

$ $ Akzeptieren
Hinweis: Da der Stapel leer ist und der Eingabepointer ebenfalls auf $ zeigt, was ein Endmarker ist, wird die Analyse durchgeführt.

erfolgreich

Beispiel 2.30: Gegeben die folgende Grammatik:

E → 5 + T | 3 - T
T→V | V*V | V+V
V→ a | b
a) Ist die Grammatik für einen prädiktiven Parser geeignet?
b) Was ist der Nutzen von Left-Factoring? Führen Sie das Left-Factoring für die obige Grammatik durch.
c) Berechne die FIRST- und FOLLOW-Mengen für jedes Nichtterminal
d) Ohne die Parsing-Tabelle zu erstellen, überprüfen Sie, ob die Grammatik LL(1) ist oder
not.
e) Durch den Bau der Parsing-Tabelle überprüfen, ob die Grammatik LL(1) ist oder nicht.

Lösung: Die gegebene Grammatik ist unten dargestellt:

E → 5 + T | 3–T
T→V | V*V | V+V
V→ a | b
a) Die E-Produktionen und V-Produktionen sind für das Parsen geeignet. Aber, betrachten Sie die
production:
T→ V | V*V | V+V
In der T-Produktion haben eine oder mehrere Produktionen ein gemeinsames Präfix V und daher die
Die gegebene Grammatik ist keine links faktorisierte Grammatik. Daher ist die gegebene Grammatik nicht geeignet.
für prädiktiven Parser.
2.64 Syntax-Analyzer
b) Um es für den LL(1)-Parser oder den prädiktiven Parser geeignet zu machen, müssen wir die linke Faktorisierung durchführen.
(Für Einzelheiten siehe Abschnitt 2.8.5). Wenn eine A-Produktion zwei oder mehr Alternativen hat.
Produktionen und sie haben ein gemeinsames Präfix, dann hat der Parser einige Verwirrung in
Auswahl der geeigneten Produktion zur Erweiterung des Nichtterminal A. Also, links
Faktorisierung ist ein Muss für einen Top-Down-Parser. Dies kann wie folgt durchgeführt werden:

Gegebene Produktionen Linksfaktorierte Produktionen

A→ α A'| γ
A → αβ1| αβ2|αβ3|….. αβn| γ A'→ β1 | β2|β3|….. βn

1)E → 5 + T | 3–T E → 5 + T | 3–T

2) T → V ϵ | V * V | V + V T→V T'
A → α β1|α β 2|α β3 T'→ ϵ | * V | + V

3) V → a | b V→ a | b

Die endgültige Grammatik, die nach dem Left-Factoring erhalten wird, ist unten dargestellt:
E → 5 + T | 3–T
T→ V T'
T' → ϵ | * V | + V
V→a|b
c) Berechnung von FIRST und FOLLOW: Die FIRST-Menge kann wie unten gezeigt berechnet werden:

Regel 1: E→5 + T T'→* V V→a

E→3 - T T'→+ V E→b

Rule 2: T'→ ϵ

E 53 T T' * + ϵ V ab

Regel 3: Berücksichtigen Sie die zuvor nicht berücksichtigten Produktionen und erhalten Sie die FIRST-Mengen wie gezeigt.
unten
b) T →V T' Fügen Sie "FIRST(V) -ϵ" zu FIRST(T) hinzu

Über der Abbildung, übertrage FIRST(V) nach FIRST(T). Die endgültigen FIRST-Mengen sind angezeigt.
darunter:
 Systematischer Ansatz für das Compiler-Design - 2.65

ERSTE E 5, 3 T a, b T1 *, +,ϵ V a, b

FOLLOW-Mengen:

FOLLOWE $ T $ T1 $ V *, + ,$

Regel 1: Fügen Sie $ zu FOLLOW(S) hinzu, da S das Startsymbol ist.

Regel 2 & 3: Wenden Sie Regel 2 und 3 für jede Produktion der Form A → αBβ an, wobei B
ist ein Nichtterminal. In der ersten Spalte, die unten gezeigt wird, kopiere von FIRST(β) nach
FOLLOW(B) und kopiere in der zweiten Spalte von FOLLOW(A) nach FOLLOW(B).

Regel 2(β ≠ ϵ)FOLLOW(B)←FIRST(β) -ϵRegel 3(β ϵ) FOLLOW(A)→FOLLOW(B)

E→5+T Regel 2 nicht anwendbar E → 5 + T

A→ α Bβ A→ αBβ

E→3–T Regel 2 nicht anwendbar E → 3 – T

A→ α Bβ A→ α Bβ

T → V T1 T V T1
A→αBβ A → αBβ

T → V T1 Regel 2 nicht anwendbar T V T1

A→αBβ A→αBβ

T1→ * V Regel 2 nicht anwendbar T1→ * V

A→αBβ A→αBβ

T1→ + V Regel 2 nicht anwendbar T1→ + V

A→αBβ A→αBβ
2,66 Syntaxanalysator
Hinweis: Die Produktionen T1→ und V → a | bloß nicht berücksichtigt bei der Berechnung
FOLLOW, da es in diesen Produktionen keine Nichtterminale gibt.

Die FIRST- und FOLLOW-Mengen für die links faktorisierte Grammatik sind nachfolgend dargestellt:

E T T1 V
ERSTE 5, 3 a, b *,+ ,ϵ a,b
FOLGEN $ $ $ *,+,$

d) Damit die Grammatik LL(1) ist, müssen die folgenden zwei Bedingungen erfüllt sein:

a. Die erste Bedingung muss erfüllt sein:

Produktion Bedingung, die erfüllt werden muss

A→ α1| α2| α3| ……. ERSTE(αich) ∩ ERSTE(αj) = ϕ

E → 5 + T | 3 – T ERSTE (5 + T) ∩ ERSTE (3 - T) = ϕ

V→a|b FIRST (a) ∩ FIRST(b) = ϕ

Beobachten Sie, dass die erste Bedingung erfüllt ist

b. Die zweite Bedingung muss erfüllt sein:

Wenn FIRST(A) = ϵ Bedingung, die erfüllt werden muss

FIRST(A) ∩ FOLLOW(A) = ϕ

Wenn ERSTE(T1) =ϵ ERSTE(T1) ∩ FOLGEN(T1)

{*, +, ϵ }∩ {$} = ϕ

Beachten Sie, dass die zweite Bedingung erfüllt ist.

Since, both conditions are satisfied,the resulting grammar is LL(1)

e) Konstruktion der Parsing-Tabelle: Für jede Produktion der Form A → α, haben wir
Berechne FIRST(α) und die Einträge der Parsing-Tabelle können wie unten gezeigt erledigt werden:

Productions a = ERSTE( ) M[A, a] = A→α Regel

A→ α
E→5+T 5 M [ E, 5 ] = E→5+T 1
A
 Systematischer Ansatz zur Compiler-Entwicklung - 2.67

E → 3 –T 3 M [ E, 3 ] = E → 3 –T 1
Ein
T→ VT1 a, b M [ T, a ] = T→ VT1 1
A M [ T, b ] = T→ VT1
T→
1
M [ T1, $ ] = T→
1
2
Ein
T1→ *V * M [ T1, * ] = T1→ *V 1
A
T1→ +V + M [ T1, + ] = T1→ +V 1
Ein
V→a a M [ V, a ] = V→a 1
Ein
V→b b M [ V, b ] = V→b 1
Ein

Die Parsing-Tabelle ist unten dargestellt:

5 3 a b * + $
E E→5+T E → 3 –T
T T → VT1 T → VT1
T1 T1→ *V T1→ +V T 1→
V V→a V →b

Since there are no multiple entries in the parse table, the resulting grammar obtained after
Linksfaktorisierung ist LL(1).

Beispiel 2.31: Gegeben ist die folgende Grammatik:

Z → d | XYZ
Y→ ϵ | c
X→ Y | a
a) Berechnen Sie die FIRST- und FOLLOW-Mengen für jedes Nicht-Terminal.
b) Überprüfen Sie, ob die Grammatik LL(1) ist, ohne die Parsing-Tabelle zu erstellen.
nicht.
c) Durch den Aufbau der Analyse-Tabelle überprüfen, ob die Grammatik LL(1) ist oder nicht.

Lösung: Die gegebene Grammatik ist unten dargestellt:

Z → d | XYZ
Y→ ϵ | c
X→ Y | a
2,68 Syntax-Analyse
a) Die FIRST- und FOLLOW-Mengen werden wie unten gezeigt berechnet:

Schritt 1: Die ersten Symbole können wie unten gezeigt berechnet werden:

Rule 1: Z → d X→a Y→ c

Regel 2: Y→ ϵ

Z d X a Y c,ϵ

Regel 3: Berücksichtigen Sie die zuvor nicht berücksichtigten Produktionen und erhalten Sie die FIRST-Mengen als
unten gezeigt:

1)Z → XYZ Füge „FIRST(X)-ϵ“ zu FIRST(Z) hinzu

2)Z → XYZ Da FIRST(X) ϵ enthält, füge „FIRST(Y)-ϵ“ zu FIRST(Z) hinzu.

3)Z → XYZ Da FIRST(X) und FIRST(Y) ϵ haben, füge "FIRST(Z)-ϵ" hinzu

zu FIRST(Z)

4)X → Y Fügen Sie „FIRST(Y)-ϵ“ zu FIRST(X) hinzu

5)X → Y Seit Y ϵ, add ϵ to FIRST(X)

Die endgültigen FIRST-Mengen sind unten aufgeführt:

FIRST Z a, c, d X a, c,ϵ Y c,ϵ

FOLLOW-Mengen:

FOLLOWZ $ X a, c, d Y a, c, d

Regel 1: Platziere $ in FOLLOW(Z), da Z das Startsymbol ist.

 Systematischer Ansatz zum Compiler-Design - 2.69
Regel 2 und 3: Wenden Sie Regel 2 und 3 für jede Produktion der Form A → αBβ an, wobei B
ist ein Nichtterminal. In der ersten Spalte, die unten angezeigt wird, kopiere von FIRST(β) nach
FOLGE(B) und in der zweiten Spalte von FOLGE(A) nach FOLGE(B) kopieren.

Regel 2(β ≠ ϵ) FOLLOW(B)←FIRST(β) -ϵ Regel 3(β ϵ) FOLLOW(A)→FOLLOW(B)

β
Z→XYZ β = ERSTE(Y)-ϵ + Regel 3 ist nicht anwendbar
A→ α Bβ ERSTE(Z) -ϵ
β
Z→XYZ β = ERSTE(Z) - ϵ Regel 3 ist nicht anwendbar
A→ α B β

Z→XYZ rule 2 not applicable Z→XYZ

A→ α B β A→ α Bβ

X→ Y Regel 2 nicht anwendbar X → Y

A→ αB β A→ α Bβ

Hinweis: Die Produktionen Z → d, Y → ϵ | c und X → awerden nicht berücksichtigt, während

Berechnung von FOLLOW, da es in diesen Produktionen keine Nichtterminals gibt. Also, die
Die FIRST- und FOLLOW-Mengen für die linksfaktorisierte Grammatik sind unten dargestellt:

Z X Y
ERSTE a,c,d a,c, ϵ c ,ϵ
FOLGEN $ a,c,d a,c,d
b) Damit die Grammatik LL(1) ist, müssen die folgenden zwei Bedingungen erfüllt sein:

a. The first condition to be satisfied:

Produktion Bedingung zu erfüllen

A→ α1|α2| α3| ……. ERSTE(αich) ∩ ERSTE(αj) = ϕ

Z → d | XYZ FIRST (d) ∩ FIRST( XYZ)

{d}∩ {a,c,d} = d

Bedingung 2 ist nicht erfüllt. Daher ist die Grammatik nicht LL(1).
2,70 Syntax-Analyse
c) Konstruktion der Parsingtabelle: Sie kann wie unten gezeigt konstruiert werden:

Produktionen a = ERSTE( ) M[A, a] = A→α Regel

A→α
Z→d d M [ Z, d ] = Z→d 1
Ein
Z XYZ a, c, d M [ Z, a ] = Z → XYZ 1
Ein M [ Z, c ] = Z → XYZ
M [ Z, d ] = Z → XYZ
Y→ c c M [ Y, c ] = Y→c 1
Ein
Y→ M [ Y, a ] = Y→
Ein M [ Y, c ] = Y→ 2
M [ Y, d ] = Y→

FOLGEN (X)
X→a a M [ X, a ] = X→a 1
A
X→Y c M [ X, c ] = X→Y 1
A
M [ X, a ] = X→Y
M [ X, c ] = X→Y
M [ X, d ] = X→Y
2
FOLGEN (X)
Die Parser-Tabelle ist unten dargestellt:

ein c d $
Z Z→ XYZ Z→ XYZ Z→d
Z→ XYZ
XX → a X→Y X→Y
X→Y
Y Y → Y→c Y→
Y→
Da es mehrere Einträge in der Parse-Tabelle gibt, ist die gegebene Grammatik nicht LL(1).

Beispiel 2.32: Faktorisieren Sie die folgende Grammatik links und erstellen Sie die LL(1)-Parsing-Tabelle
E→T+E|T
T → float | float * T | (E)
 Systematischer Ansatz zur Compiler-Entwicklung - 2.71

Lösung: Da die rechte Seite der E-Produktion und der T-Produktion gemeinsame
Präfixe, diese Grammatik eignet sich nicht zum Parsen. Daher müssen wir eine linke Faktorisierung durchführen und sehen
dass zwei oder mehr Produktionen kein gemeinsames Präfix haben. Left-Factoring kann wie folgt durchgeführt werden
unten gezeigt:

Die linke Faktorisierung kann an der gegebenen Grammatik wie unten gezeigt durchgeführt werden:

Gegebene Produktionen Links faktorisierte Produktionen

A → α A1 | γ
A → αβ1| αβ2|αβ3|….. αβn| γ A→
1
β1| β2|β3|….. βn

1) E → T + E | T E → T E1
A→ α β1|α β2 E1→ + E |

2) T →float | float * T | (E) T→float T1( E )

A→ α β1|α β 2| γ T1→ | *T

Die nach dem Links-Factoring erhaltene Grammatik ist unten dargestellt:

E → T E1
E1→ + E |
T → float T1 ( E )
T1→ | *T

a) Die FIRST- und FOLLOW-Mengen können wie unten gezeigt berechnet werden:
FIRST-Mengen: werden wie unten gezeigt berechnet:

Schritt 1: Die ersten Symbole können wie unten gezeigt berechnet werden:

Regel 1: E1→ + E T → float T1 T1→ * T

T→(E)

Regel 2: E1→ T1 → ϵ

E E1 +, T Float, ( T1 *,

Regel 3: Betrachten Sie die Produktionen, die zuvor nicht berücksichtigt wurden, und erhalten Sie die FIRST-Mengen als

unten gezeigt:
E→T E1FÜGE “FIRST(T)-ϵ” ZU FIRST(E) HINZU
2,72 Syntaxanalyse
Übertragen Sie in der obigen Abbildung FIRST(T) auf FIRST(E). Die endgültigen FIRST-Mengen sind
unten gezeigt:

ERSTE E float, ( E1 +, T float, ( T1 *,

FOLLOW-Mengen:

FOLLOWE $, ) E1 $, ) T +, $, ) T1 +,$, )

Regel 1: Setze $ in FOLLOW(S), da S das Startsymbol ist.

Regel 2 & 3: Wenden Sie Regel 2 und 3 auf jede Produktion der Form A → αBβ an, wobei B
ist ein Nichtterminal. In der ersten Spalte, die unten angezeigt wird, kopiere von FIRST(β) nach
FOLGEN(B) und in der zweiten Spalte COPY von FOLLOW(A) nach FOLLOW(B).

Rule 2(β ≠ ϵ)FOLLOW(B)←FIRST(β) -ϵRule 3(β ϵ) FOLLOW(A)→FOLLOW(B)

E → T E1 E → T E1
A→ αBβ A → αBβ

E → T E1 Regel 2 nicht anwendbar E → T E1

A→ α Bβ A→ α Bβ

E → + E1 Regel 2 nicht anwendbar E → + E1

A→ α Bβ A→ α Bβ

T → float T1 Regel 2 nicht anwendbar T → float T1

A→ α Bβ A→ αBβ

T → ( E ) T → ( E )
A → αB β Regel 3 nicht anwendbar
A → αB β

T1→ * T Regel 2 nicht anwendbar T1→ * T

A→ α Bβ A→ α Bβ
 Systematic approach to Compiler Design - 2.73
Note:The productions T1→ und E1→ werden bei der Berechnung nicht berücksichtigt
FOLLOW, da es in diesen Produktionen keine Nichtterminals gibt. Daher die FIRST und
Die FOLLOW-Mengen für die links-faktorisierten Grammatik sind unten dargestellt:

E E1 T T1
ERSTE Float, ( +, float, ( *,
FOLLOW $,) $, ) +,$,) +,$,)
b) Konstruktion der Parsing-Tabelle: Für jede Produktion der Form A → α, haben wir
Berechnen Sie FIRST(α) und die Einträge der Parsing-Tabelle können wie folgt durchgeführt werden:

Productions a = ERSTE( ) M[A, a] = A→α Regel

A→α
E → T E1 Float, ( M [ E, float ] = E → T E1 1
Ein M [ E, „(„ ] = E → T E1
1
E →+E + M [ E1, + ] = E1→ + E 1
A
E→
1
M [ E1, $ ] = E→
1
2
Ein M [ E,1 „)‟ ] = E→
1

T → float T1 float M [ T, float ] = T → float T1 1

A
T→(E) ( M [ T, ( ] = T→(E) 1
Ein
T→
1
M [ T1, $ ] = T→
1
2
Ein M [ T, „)‟ ] =
1
T→
1

M [ T1, + ] = T→
1

1 1
T →*T * M[T , * ] = T1→ * T 1
A
Die Parsing-Tabelle ist unten dargestellt:

float * + ( ) $
E E → T E1 E → T E1
E1 E1→ + E E→
1
E→
1

T T → float T1 T→(E)
1
T1 T→ * T T→ 1
T→
1
T→
1

2.11 Fehlerbehebung beim prädiktiven Parsen

Jetzt wollen wir sehen, wie die Fehlerrückgewinnung beim prädiktiven Parsen durchgeführt wird. Ein Fehler wird erkannt.
Während des prädiktiven Parsens treten die folgenden beiden Situationen auf:
2,74 Syntax-Analyse
Das Terminal an der Spitze des Stapels stimmt nicht mit dem nächsten Eingabesymbol überein
Wenn das Nicht-Terminal A oben auf dem Stapel ist, ist a das nächste Eingabesymbol und M[A, a]
hat leere Eingabe (leer bedeutet einen Fehler)

Die Fehlerbehebung erfolgt mithilfe von Panic-Modus und phrasenweise Wiederherstellung, wie unten gezeigt:

Panikmodus: Bei diesem Ansatz wird die Fehlerbehebung durchgeführt, indem Symbole übersprungen werden von den
Geben Sie Eingaben ein, bis ein Token mit den synchronisierenden Token übereinstimmt. Die synchronisierenden Token sind
so ausgewählt, dass der Parser schnell von den Fehlern, die wahrscheinlich auftreten werden, sich erholen kann.
In der Praxis vorkommen. Einige der Wiederherstellungstechniken sind unten aufgeführt:
1) Für ein Nichtterminal A, betrachte die Symbole in FOLLOW(A). Diese Symbole können
als synchronisierende Tokens betrachtet werden und in die Parsing-Tabelle eingefügt werden, wobei
nur leere Einträge. Jetzt, wann immer es eine Diskrepanz gibt, überspringen Sie die Tokens weiterhin
bis wir eines der synchronisierenden Zeichen erhalten und A vom Stapel entfernen. Es ist
Wahrscheinlich kann das Parsing fortgesetzt werden.
2) Für ein Nicht-Terminal A betrachten Sie die Symbole in FIRST(A). Diese Symbole können auch
be considered as synchronizing characters and add to the parsing table replacing
nur leere Einträge. Jetzt, wann immer es eine Diskrepanz gibt, überspringe die Tokens einfach
bis wir eines der synchronisierenden Zeichen erhalten und A vom Stapel entfernen. Es ist
Es ist auch wahrscheinlich, dass das Parsen fortgesetzt werden kann.
3) Wenn ein Terminal ganz oben auf dem Stapel nicht übereinstimmt, entfernen Sie das Terminal vom
Stapeln und melden Sie "Fehlermeldung" und fügen Sie das entsprechende Terminal ein.
Fahre mit dem Parsen fort.

Zum Beispiel betrachten Sie die Parsing-Tabelle, die synchronisierende Tokens enthält und
Folge von Bewegungen, die vom Parser im Beispiel 2.33 gemacht wurden, das später in diesem Abschnitt gegeben wird.

Phrasenebenenwiederherstellung: Diese Wiederherstellungsmethode wird umgesetzt, indem die leeren Einträge ausgefüllt werden.
im prädiktiven Parsing-Tabelle mit Zeigern auf Fehlerbehandlungsroutinen. Diese Routinen können sich ändern,
insert, replace or delete symbols from the input and issue appropriate error messages.
Sie können auch vom Stapel entfernt werden.

Beispiel 2.33: Betrachten Sie die folgende Grammatik

E → TE1
E→+TE|
1 1

T → FT 1
T→*FT
1
| 1
F → (E) | id
und die Parsing-Tabelle (Siehe Beispiel 2.27 für Details)
 Systematischer Ansatz zur Compiler-Entwicklung - 2.75

id + * ( ) $
EE → TE1 E→ TE1
E1 E1→ +TE1 E1→ E1→
TT → FT1 T → FT1
T1 T1→ T1→ *FT1 T1→ T1→
F F →id F → (E)

Fügen Sie die Synchronisationstoken für die obige Parsing-Tabelle hinzu und zeigen Sie die Sequenz von
Bewegungen des Parsers für die Zeichenfolge „) id * +id“

Die synchronisierenden Zeichen sind die Zeichen, die in FIRST oder FOLLOW vorhanden sind.
Mengen jedes Nichtterminal. In unserem Beispiel fügen wir Synchronisierungszeichen hinzu durch
Berücksichtigung von FOLLOW jeder Nichtterminal, um jeden leeren Eintrag in der Analyse zu ersetzen
Tabelle. Die FOLLOW-Mengen jedes Nichtterminals sind unten aufgeführt (siehe Beispiel 2.26 für
Details):

E E1 T T1 F
Folgen $, ) $, ) +, $, ) +, $, ) +, *, $, )

Jetzt ist FOLLOW(E) = { $, ) }. Also ist M[E, $] = M[E,)] = Synchronisation nur für leere Einträge.
Ebenso ist FOLLOW(F) = {+, *, $, ) }. Daher gilt M[F,+] = M[F,*] = M[F, $] = M[F,) = synch.
In ähnlicher Weise fügen wir Synchronisationszeichen zur Parsing-Tabelle hinzu, wie unten gezeigt:

id + * ( ) $
EE → TE1 E→ TE1 Synchronisieren
synchronisieren
E1 E1→ +TE1 1
E→ E1→
TT → FT1 Synchronisieren T → FT1 Synchronisieren
synchronisieren
T1 T1→ 1
T → *FT 1 1
T→ T1→
F F →id synchron synchron F → (E) synchron Synchronisieren

Nun wird die Folge von Zügen, die der Parser für den String „) id * +id“ gemacht hat, angezeigt
darunter:

Stapel Input Ausgabe Aktion

$E ) id * + id$ error, skip Entfernen Sie ) aus der Eingabe

$E id * + id$ E → TE1 1
Entfernen Sie E und schieben Sie TE in umgekehrter Reihenfolge

$ E1T id * + id$ T → FT1 Entferne T und schiebe FT1reverse in

2,76 Syntax-Analyzer
$ E1T1F id * + id$ F →id Entferne F und drücke die ID umgekehrt

$ E1T1id id * + id$ Match id Pop-ID und Inkrement des i/p-Zeigers

$ E1T1 * + id$ T1→ *FT1Remove T1und schiebe *FT1rückwärts

$ E1T1F * * + id$ Übereinstimmen * Pop * und inkrementiere den i/p-Zeiger

$ E1T1F + id$ error, skip Pop + aus dem Eingang

$ E1T1F id$ F → id Entferne F und schiebe id rückwärts

$ E1T1id id$ Match id Pop-ID und Inkrement des Eingabepointers

$ E1T1 $ Match id Pop-ID und inkrementiere den i/p-Zeiger

$ E1T1 $ T1 → Entferne T1vom Stapel

$ E1 $ E1→ Entferne E1 vom Stapel

$ $ AKZEPTIEREN
Hinweis: Beachten Sie, dass das Parsen erfolgreich war und der Parser auch zwei Fehler erkannt hat.
Wenn der Programmierer das Programm anhand dieser Fehler korrigiert, ist die Parsing-Aktion
erfolgreich ohne irgendwelche Fehler.

Berechnung der FIRST-Mengen: Die FIRST-Mengen der linken Seite der Produktion sind nichts anderes als die
Terminals, die aus den ersten Symbolen auf der rechten Seite der Produktion gewonnen wurden.

Also, FIRST(E) = FIRST(T) = FIRST(F) = (, id

Berechnung von FOLLOW-Mengen: Die FOLLOW-Mengen eines Nichtterminals A auf der rechten Seite der
Die Produktion erfolgt nach den folgenden Regeln:
1) Mengen von Terminalsymbolen, die unmittelbar nach A folgen, oder Mengen von Erstsymbolen, die aus der
Nicht-Terminals, die unmittelbar auf A folgen
2) Wenn A auf der linken Seite der Produktion ist und B das rechts äußerste Symbol auf der rechten Seite ist.
Produktion dann FOLLOW(B) = FOLLOW(A)

Übungen
{"context_free_grammar":"Was ist eine kontextfreie Grammatik?","derivation":"Was ist Ableitung?","two_types":"Was sind die zwei Arten von"}

Ableitungen?
2) Define the terms: leftmost derivation, rightmost derivation, sentence
 Systematischer Ansatz zum Compiler-Design - 2.77
3) Was sind die verschiedenen Satzformen? Was ist die linksseitige Satzform? Was ist rechtsseitig?
Satzform?
4) Define the terms: Language, derivation tree, yield of a tree, ambiguous grammar
5) Zeigen Sie, dass die folgende Grammatik mehrdeutig ist
E→E + E
E→E - E
E→E * E
E→E / E
E→(E)|I
Ich id
6) Ist die folgende Grammatik mehrdeutig? (wenn-Anweisung oder wenn-dann-sonst)
S→iCtS | iCtSeS | a
C→b
{"text":"7) Was ist das Problem mit dem schwebenden Else? Wie kann das Problem mit dem schwebenden Else gelöst werden?"}

8) Beseitigen Sie die Mehrdeutigkeit aus der folgenden mehrdeutigen Grammatik:

S→iCtS | iCtSeS | a
C→b
9) Wandeln Sie die folgende mehrdeutige Grammatik in eine eindeutige Grammatik um, indem Sie die normale verwenden.
Vorrang und Assoziativität der Operatoren
E→E * E | E - E
E→E ^ E | E / E
E→E + E
E→(E)| id
10) Convert the following ambiguous grammar into unambiguous grammar
E→E+E
E → E –E
E→E^E
E→E*E
E→E/E
E →(E) | id
unter Berücksichtigung von * und – Operatoren mit der niedrigsten Priorität und sie sind linksassoziativ, / und +
Operatoren haben die höchste Priorität und sind rechtsassoziativ, und der ^ Operator hat
Präzedenz zwischen und es ist linksassoziativ.
11) Was ist Parsing? Was sind die verschiedenen Arten von Parsern?
2,78 Syntaxanalysator
12) Was sind die Fehlerbehebungsstrategien des Parsers (oder Syntaxanalysators)?
13) Was ist ein Top-Down-Parser? Zeigen Sie den Top-Down-Parsing-Prozess für die Zeichenfolge id + id *
ID für die Grammatik
i.E → E + E
ii.E → E * E
iii.E → (E)
iv.E → id
14) Was ist ein rekursiver Abwärtsparser? Schreiben Sie den Algorithmus für den rekursiven Abwärtsparser.

15) Schreiben Sie den rekursiven Abstieg-Parser für die folgende Grammatik
E→T
T→F
F → (E) | id
16) Was sind die verschiedenen Typen von rekursiven Abstiegsgeneratoren? Was ist die Notwendigkeit für
Backtracking im rekursiven Abwärts-Parser
17) Zeigen Sie die Schritte, die bei einem rekursiven Abwärtsparser mit Backtracking für den Eingabewert beteiligt sind.
Stringcad für die folgende Grammatik
S → cAd
A → ab | a
18) Für welche Art von Grammatiken kann kein rekursiver Abwärts-Parser erstellt werden? Was ist
Die Lösung?
19) Was ist linke Rekursion? Welche Probleme treten auf, wenn ein rekursiver Abstieg-Parser verwendet wird?
konstruiert für eine Grammatik mit linker Rekursion?
20) Schreiben Sie das Verfahren zur Eliminierung der linken Rekursion

21) Beseitigen Sie die linke Rekursion aus der folgenden Grammatik
E→E+T|T
T→T*F|F
F → (E) | id
22) Schreiben Sie den rekursiven Abstiegssyntaxanalysator für die folgende Grammatik:
E → TE1
E1→ +TE1| ϵ
T → FT1
T1→ *FT1| ϵ
F → (E) | id
23) Erhalten Sie eine Top-Down-Analyse für den String id+id*id für die folgende Grammatik.
E → TE1
 Systematischer Ansatz zur Compiler-Entwicklung - 2.79

E1→+ TE 1|
T → FT1
T1→*FT1|
F → (E) | id
24) Beseitigen Sie die linke Rekursion aus der folgenden Grammatik:
S → Aa | b
A → Ac | Sd | ϵ
25) Schreibe den Algorithmus zur Beseitigung der linken Rekursion

26) What is left factoring? What is the need for left factoring? How to do left factoring?
Schreiben Sie den Algorithmus zum Durchführen von Left-Factoring

27) Führen Sie die linke Faktorisierung für die folgende Grammatik durch:

S →iCtS | iCtSeS | a
C → b
28) Erläutern Sie kurz die Probleme, die mit einem Top-Down-Parser verbunden sind?

29) Was ist ein prädiktiver Parser? Erklären Sie die Funktionsweise eines prädiktiven Parsers.

30) Was sind die verschiedenen Komponenten eines prädiktiven Parsers? Wie funktioniert er?

31) Definieren Sie die FIRST- und FOLLOW-Mengen und schreiben Sie die Regeln zum Berechnen von FIRST und
FOLLOW-Mengen
32) Betrachten Sie die folgende Grammatik:
E → TE1
E1→+ TE 1|
T → FT1
T1→*FT1|
F → (E) | id
a) Berechnen Sie die FIRST- und FOLLOW-Mengen für die folgende Grammatik:
b) Beschaffen Sie die prädiktive Parsing-Tabelle
c) Zeigen Sie die Abfolge der Züge, die der Parser für die Zeichenfolge id+id*id gemacht hat
d) Fügen Sie die synchronisierenden Tokens für die obige Parsing-Tabelle hinzu und zeigen Sie die Reihenfolge.
von Zügen, die der Parser für die Zeichenkette „) id * + id“ gemacht hat

33) Was ist LL(1) Grammatik? Wie überprüft man, ob eine gegebene Grammatik LL(1) ist oder nicht
ohne den prädiktiven Parser zu konstruieren
2,80 Syntax-Analyzer
34) Berechnen Sie die FIRST- und FOLLOW-Symbole sowie die prädiktive Parsing-Tabelle für die
Überprüfen Sie die folgende Grammatik und ob die Grammatik LL(1) ist oder nicht.
S → iCtS | iCtSeS | a
C→b
35) Gegeben folgende Grammatik:
S → a | (L)
L→L,S|S
a. Ist die Grammatik für einen prädiktiven Parser geeignet?
b. Nehmen Sie die notwendigen Änderungen vor, um es für einen LL(1)-Parser geeignet zu machen.
c. Berechnen Sie die FIRST- und FOLLOW-Mengen für jedes Nichtterminal
d. Erstellen Sie die Parse-Tabelle und überprüfen Sie, ob die resultierende Grammatik LL(1) ist oder nicht.
e. Zeigen Sie die Züge, die der prädiktive Parser an der Eingabe "( a , ( a , a ) )" gemacht hat

36) Angesichts der folgenden Grammatik:

E → 5 + T | 3–T
T → V | V*V | V+V
V→a|b
a. Ist die Grammatik für einen prädiktiven Parser geeignet?
b. Was ist der Nutzen von Left-Factoring? Führen Sie das Left-Factoring für die obige Grammatik durch.
c. Berechnen Sie die FIRST- und FOLLOW-Mengen für jedes Nichtterminal
d. Ohne die Parsing-Tabelle zu erstellen, prüfen Sie, ob die Grammatik LL(1) ist.
e. Durch die Erstellung der Parsing-Tabelle überprüfen, ob die Grammatik LL(1) ist.

37) Gegeben die folgende Grammatik:

Z → d | XYZ
Y → ϵ | c
X→Y|a
a. Berechnen Sie die FIRST- und FOLLOW-Mengen für jedes Nichtterminal.
b. Ohne die Ableitungstabelle zu erstellen, überprüfen Sie, ob die Grammatik LL(1) ist.
c. Durch den Aufbau der Parsing-Tabelle überprüfen, ob die Grammatik LL(1) ist.
38) Faktorisieren Sie die folgende Grammatik nach links und erstellen Sie eine LL(1) Parsing-Tabelle

E→T+E|T
T → float | float * T | (E)
39) Wie wird die Fehlerbehandlung beim prädiktiven Parsen durchgeführt?