LL-Parser

2021-04-06T17:55:49Z

77.21.252.61: /* Beispiel Implementierung in Python */

Im [[Compilerbau]] ist ein '''LL-Parser''' ein Top-Down-[[Parser]], der die Eingabe von '''L'''inks nach rechts abarbeitet, um eine [[Linksableitung|'''L'''inksableitung]] der Eingabe zu berechnen.<ref>Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman: ''Compilers, Principles, Techniques, and Tools''. ISBN 0-201-10088-6, S. 191</ref>

Ein LL-Parser heißt '''LL(k)-Parser''', wenn er während des Parsens ''k'' [[Token (Übersetzerbau)|Tokens]] vorausschauen kann und im Gegensatz zum [[LF-Parser]] den Kellerinhalt benutzt. ''k'' wird dabei als ''[[Lookahead]]'' bezeichnet. Diesem Parsertyp liegen die [[LL(k)-Grammatik]]en zu Grunde.

Obwohl die LL(k)-Grammatiken relativ eingeschränkt sind, werden LL(k)-Parser oft benutzt. Die Entscheidung, nach welcher Regel expandiert wird, kann allein durch Analyse des Lookahead getroffen werden. Eine einfache Möglichkeit zur Implementierung dieser Parsertechnik bietet die Methode des [[Rekursiver Abstieg|rekursiven Abstiegs]].

== Funktionsweise ==
Ausgangspunkt ist eine Grammatik <math>G = (N, \Sigma, P, S)</math>.
Der Parser arbeitet mit einer Zustandsmenge <math>Q = (N \cup \Sigma)^* \times \Sigma^* \times \mathbb{N}^*</math>, wobei sich ein Zustand <math>q = (k, w, z) \in Q</math> so zusammensetzt:
* <math>k</math> ist der aktuelle Inhalt eines [[Stapelspeicher|Laufzeitkellers]], der für die Speicherung der aktuellen Symbole verwendet wird. <math>k</math> kann sowohl Terminal- als auch Nichtterminalsymbole beinhalten.
* <math>w</math> ist der Teil der Eingabe, der noch nicht gelesen wurde.
* <math>z</math> ist die Ausgabe, eine Folge natürlicher Zahlen, die die Nummern der Regeln der Linksableitung enthält.

Der [[Nichtdeterminismus|nichtdeterministische]] [[Automat (Informatik)|Automat]] für die LL(k)-Analyse ist dann:

* <math>\mathcal{A} = (Q, \delta, q_0, F)</math>
* <math>q_0 = (S, w, \epsilon)</math> (Anfangszustand)
* <math>F = (\epsilon, \epsilon, z)</math> (Endzustand)

Dabei ist <math>S</math> das Startsymbol der zugrundeliegenden Grammatik und <math>z</math> die Linksanalyse der Eingabe <math>w</math>.

Die Transitionen <math>\delta</math> setzen sich so zusammen:
* <math>(a\alpha, aw, z) \vdash (\alpha, w, z)</math> (Shift- oder Verschiebeschritt)
* <math>(A\beta, w, z) \vdash (\alpha\beta, w, zi)</math> (Expansions- oder Ableitungsschritt), wobei die Regel <math>A\rightarrow\alpha</math> in der Regelmenge <math>P</math> enthalten sein muss und <math>i</math> die Nummer dieser Regel ist.

== LL(1)-Parser ==
Dieser Parsertyp verwendet einen Lookahead von einem Zeichen.
Auf Grund dieser Einschränkung kann einfach ein deterministischer Parser erstellt werden.

Die oben genannten nichtdeterministischen Schritte werden dabei durch den Lookahead determiniert.

=== Beispiel Implementierung in Python ===

In einem Beispiel soll ein LL(1) Parser die folgende einfache Grammatik abbilden:

S → F
S → ( S + F )
F → n

Die folgende Python-Implementierung des LL(1)-Parsers zu dieser Grammatik wird auf den Eingabestring ''((n+n)+n)'' angewendet:

<syntaxhighlight lang="python">
# Parse table
table = {'@S': {'n': 0, '(': 1},
'@F': {'n': 2}}

rules = [['@F'],
['(', '@S', '+', '@F', ')'],
['n']]

def syntactic_analysis(string):
print('Syntactic analysis of input string:', string)
stack = ['\n', '@S']
tokens = list(string) + ['\n']
position = 0
while len(stack) > 0:
stackvalue = stack.pop()
token = tokens[position]
if not stackvalue.startswith('@'):
if stackvalue == token:
# print('pop', repr(stackvalue))
position += 1
if token == '\n':
print('input accepted')
break
else:
print('syntax error at input:', repr(token))
break
else:
rule = table[stackvalue].get(token, -1)
print('at pos', position, 'found rule', repr(stackvalue +
' -> ' + ' '.join(rules[rule])))
for r in reversed(rules[rule]):
stack.append(r)
# print('stack:', repr(', '.join(reversed(stack))))

syntactic_analysis('((n+n)+n)')
</syntaxhighlight>

Die Ausgabe des Skripts ergibt bei korrekter Syntax direkt den serialisierten Syntax-Baum:

Syntactic analysis of input string: ((n+n)+n)
at pos 0 found rule '@S -> ( @S + @F )'
at pos 1 found rule '@S -> ( @S + @F )'
at pos 2 found rule '@S -> @F'
at pos 2 found rule '@F -> n'
at pos 4 found rule '@F -> n'
at pos 7 found rule '@F -> n'
input accepted

== Siehe auch ==
* [[LR-Parser]]

== Einzelnachweise ==
<references />

[[Kategorie:Compilerbau]]

Wikipedia (Deutsch) – Lokale Kopie - Benutzerbeiträge [de]

LL-Parser