Erstens, im Allgemeinen, wofür steht die Spalte $. Also gibt es eine konkrete Eingabe, die mit $ bezeichnet wird und wie sieht die aus?
Das Zeichen $ ist weder ein Terminal- noch ein Nichtterminalzeichen der angegebenen Grammatik und wird als neues Terminalzeichen hinzugefügt, um technische Probleme beim Parsing zu lösen.
Um ein Wort w zu parsen, d.h. um eine Ableitung von w zu bestimmen, beginnt ein Top-Down-Parser mit dem Stack $S (wobei $ auf dem Boden des Stacks liegt und S darauf liegt) und dem Wort w$ und versucht dann eine Ableitung S->w zu generieren, wobei das Wort w von links nach rechts konsumiert wird. Hierfür hat der Top-Down-Parser zwei Möglichkeiten:
- Match: Falls das oberste Element des Stacks ein Terminalsymbol ist, welches dem Anfang des Restwortes w entspricht, so kann dieses Terminalsymbol sowohl auf dem Stack als auch am Anfang des Wortes entfernt werden.
- Expand: Falls das oberste Element des Stacks ein Nichtterminalsymbol A ist und die Grammatik eine Regel A->u hat, so kann dieses Nichtterminalsymbol A durch das gespiegelte Wort u' ersetzt werden.
Das Problem bei einem Expand-Schritt besteht darin, dass es mehrere Regeln A->u geben kann und dass dann zunächst nicht klar ist, welche Regel man für den Expand-Schritt wählen sollte. Eine Lösung besteht darin, dass einfach alle Regeln der Reihe nach ausprobiert werden, wobei die nächste Regel verwendet wirde, falls mit den anderen Regel keine Ableitung zustande kommt (backtracking). Damit ist aber keine Ableitung mehr in linearer Laufzeit möglich.
Um Backtracking zu vermeiden und eine lineare Laufzeit beim Parsing zu erzielen, braucht man eine deterministische Auswahl der Produktionsregel A->u beim Expand-Schritt. Dies wird bei LL(1)-Grammatiken durch die Betrachtung des ersten Zeichens von w erzielt (was die Definition von LL(1)-Grammatiken darstellt).
Die Auswahl einer Regel erfolgt durch die Parse-Tabelle, welche eine Tabelle ist, die für jedes Nichtterminalzeichen A und jedes Terminalzeichen a die Produktionsregel T(A,a) angibt, welche für einen Expand-Schritt zu verwenden ist. Eine Grammatik ist daher genau dann LL(1), wenn kein Eintrag T(A,a) der Parse-Tabelle mehr als eine Regel enthält.
Zweitens, warum sollten die markierten Regeln unten rechts geschrieben werden, obwohl das leere Wort kein Teil der First Mengen für U, V ist
Diese Regeln stehen in den Einträgen T(A,$) und sollen daher verwendet werden, wenn das oberste Element des Stacks ein Nichtterminalzeichen A ist und das Wort mit $ beginnt. Da $ ein neues Terminalzeichen ist, welches wir rechts dem Wort hinzugefügt haben, heißt das, dass das Wort an dieser Stelle nur noch aus $ besteht und wir aus dem Rest des Stacks das Wort $ ableiten müssen. Besteht der Stack aus $v, so müsste aus v das leere Wort abgeleitet werden.
Drittens, unterschiedet sich die Parsing Tabellen zwischen LL1 und nicht LL1 Grammatiken und falls ja warum und wie sieht der Unterschied aus?
Wie bereits erwähnt, ist eine Grammatik genau dann LL(1), wenn kein Eintrag T(A,a) der Parse-Tabelle mehr als eine Regel enthält. Die obige Grammatik ist daher nicht LL(1) und erlaubt kein deterministisches Parsen mit einem Top-Down-Parser mit einem Lookahead von einem Zeichen.
Apropos: Leider erzwingt der CSS-Style des Uni-Layouts, dass Titel groß geschrieben werden, so dass man bei den Parse-Tabellen aufpassen muss, da die Groß-/Kleinschreibung für Nichtterminal- bzw. Terminalsymbole hier versagt.
<><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><>
English Translation (www.DeepL.com/Translator (free version))
<><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><>
First, in general, what does the $ column stand for? So there is a concrete input that is denoted by $ and what does it look like?
The $ character is neither a terminal nor a non-terminal character of the given grammar, and is added as a new terminal character to solve technical parsing problems.
To parse a word w, i.e., to determine a derivation of w, a top-down parser starts with the stack $S (where $ is at the bottom of the stack and S is on top of it) and the word w$ and then tries to generate a derivation S->w, consuming the word w from left to right. For this, the top-down parser has two options:
- Match: if the top element of the stack is a terminal symbol corresponding to the beginning of the residue word w, then this terminal symbol can be removed from both the stack and the beginning of the word.
- Expand: If the top element of the stack is a non-terminal symbol A and the grammar has a rule A->u, then this non-terminal symbol A can be replaced by the mirrored word u'.
The problem with an expand step is that there may be multiple rules A->u and then it is not initially clear which rule to choose for the expand step. One solution is to simply try all the rules in turn, using the next rule if no derivation is obtained with the other rules (backtracking). With it, however, no derivation in linear runtime is possible any longer.
To avoid backtracking and to achieve a linear runtime in parsing, one needs a deterministic selection of the production rule A->u at the expand step. This is achieved in LL(1) grammars by considering the first character of w (which is the definition of LL(1) grammars).
The selection of a rule is done by the parse table, which is a table that specifies, for each non-terminal character A and each terminal character a, the production rule T(A,a) to be used for an expand step. Therefore, a grammar is LL(1) if and only if no entry T(A,a) of the parse table contains more than one rule.
Second, why should the marked rules be written at the bottom right, although the empty word is not part of the ridge sets for U, V.
These rules are in the entries T(A,$) and therefore should be used when the top element of the stack is a non-terminal character A and the residue word begins with $. Since $ is a new terminal character that we added to the right of the word, this means that the word at this point consists only of $ and we must derive the word $ from the rest of the stack. If the stack consists of $v, then the empty word would have to be derived from v.
Third, the parsing tables differ between LL1 and non LL1 grammars and if so why and what is the difference?
As mentioned earlier, a grammar is LL(1) exactly when no entry T(A,a) of the parse table contains more than one rule. Therefore, the above grammar is not LL(1) and does not allow deterministic parsing with a top-down parser with a lookahead of one character.
Apropos: Unfortunately the CSS style of the Uni layout forces titles to be capitalized, so you have to be careful with the parse tables, as case sensitivity for non-terminal or terminal symbols fails here.
