Parser und Übersetzer

Recursive-Descent-Parser für mehrstellige Zahlen

 aufwärts

Die sehr einfache Grammatik für einstellige ganze Zahlen mit oder ohne negatives Vorzeichen aus Teil 1 wird nun auf mehrstellige ganze Zahlen erweitert. Dabei werden mögliche Probleme bei der Umsetzung einer Grammatik in einen Recursive-Descent-Parser angesprochen und ent­sprechende Lösungs­möglichkeiten angegeben.

Mehrstellige ganze Zahlen

Die Grammatik G mit folgenden Produktionen beschreibt mehrstellige ganze Zahlen ohne Vorzeichen.

integer geht über nachinteger digit  |  digit
digit geht über nach0  |  ...  |  9

Diese Grammatik ist aus zwei Gründen nicht für einen Recursive-Descent-Parser geeignet. Zum einen kann anhand des jeweils nächsten Zeichens des Eingabe­wortes nicht unter­schieden werden, welche der beiden Alternativen der Produktion für integer anzuwenden ist. Zum anderen ist die Produktion integer geht über nachinteger digit links­rekursiv. In der Implementierung ruft die Funktion integer sich selbst auf, ohne dass ein Zeichen des Eingabe­wortes abgearbeitet wird. Dies führt zu einer unendlichen Aufrufkette.

Grammatiken, die sich unmittelbar nicht für einen Recursive-Descent-Parser eignen, lassen sich in den meisten Fällen umformen. Einige Methoden hierfür sind im Folgenden angegeben.

Linksrekursion durch Rechtsrekursion ersetzen

Die Grammatik G soll so umgeformt werden, dass sie keine linksrekursiven Produktionen enthält.

Die allgemeine Vorgehens­weise hierfür besteht darin, dass jede Produktion der Form

Xgeht über nachXw  |  u

ersetzt wird durch die Produktionen

Xgeht über nachuR
Rgeht über nachwR  |  ε

Hierbei ist R eine neu eingeführte Variable.

Angewandt auf die Grammatik G führt dies zu folgenden Produktionen. Hierbei steht integer für X, digit für u und w sowie moredigits für die neu eingeführte Variable R.

integer geht über nachdigit moredigits
moredigits geht über nachdigit moredigits  |  ε

Faktorisierung

Offenbar beschreibt integer eine nichtleere Folge von Ziffern. Dies lässt sich auch direkt durch eine Grammatik mit einer rechts­rekursiven Produktion für integer ausdrücken:

integer geht über nachdigit integer  |  digit
digit geht über nach0  |  ...  |  9

Hier tritt das schon erwähnte Problem auf, dass beide Alternativen der Produktion für integer mit digit beginnen. Somit ist anhand des nächsten Zeichens des Eingabe­wortes nicht zu unter­scheiden, welche der beiden Alternativen anzuwenden ist.

Da aber beide Alternativen mit digit beginnen, lässt sich digit ausklammern. Dies führt zu folgender Grammatik:

integer geht über nachdigit (integer  |  ε)
digit geht über nach0  |  ...  |  9

Diese Vorgehens­weise des Ausklammerns wird als Faktorisierung bezeichnet.1) Die so umgeformte Grammatik lässt sich als Recursive-Descent-Parser implementieren.

Rekursion durch Iteration ersetzen

Eine andere Möglichkeit, Links- oder Rechts­rekursionen zu beseitigen, besteht darin, diese durch Iterationen zu ersetzen. Hierzu wird die Grammatik umgeformt und in erweiterter Backus-Naur-Form (EBNF) dargestellt.

Die allgemeine Vorgehens­weise für Links­rekursionen ist die folgende. Jede Produktion der Form

Xgeht über nachXw  |  u

wird ersetzt durch die Produktion

Xgeht über nachuw*

Ausgehend von der ursprüng­lichen links­rekursiven Produktion für integer ergibt sich folgende umgeformte Produktion:

integer geht über nachdigit digit*

Hierbei steht wieder integer für X sowie digit für u und w. Diese Produktion lässt sich in einem Recursive-Descent-Parser implementieren.

 

Für Rechts­rekursionen gilt eine ähnliche Vorgehens­weise. Jede Produktion der Form

Xgeht über nachwX  |  u

wird ersetzt durch die Produktion

Xgeht über nachw*u

Aufgaben

Aufgabe 1:  Schreiben Sie einen Parser für mehrstellige ganze Zahlen mit oder ohne Vorzeichen. Auch ein positives Vorzeichen soll erlaubt sein.

Entwickeln Sie zunächst eine Grammatik, die sich für einen Recursive-Descent-Parser eignet. Passen Sie hierzu die Grammatik für einstellige Zahlen entsprechend an.

Programmieren Sie anschließend ein Modul NumberParser, in dem Sie schulmäßig die Produktionen Ihrer Grammatik in ent­sprechende Funktionen umsetzen.

Testen Sie den Parser mit den Eingabe­wörtern +456, 007 und ++5.

Aufgabe 2:  Erweitern Sie die Grammatik in der Weise, dass auch Zahlen mit mehreren Vorzeichen zulässig sind, also beispiels­weise -++53.

Passen Sie das Modul NumberParser entsprechend an.


1)  Der Begriff Faktorisierung wird daneben auch für die Zerlegung einer ganzen Zahl in Faktoren verwendet.

 

Weiter mit:   [Recursive-Descent-Parser für einfache Ausdrücke]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 16.08.2012   Updated: 10.06.2018
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik