Parser und Übersetzer

Parser für Additions-/Subtraktions-Ausdrücke

 aufwärts

Im zweiten Beispiel soll ein Recursive-Descent-Parser für Additions-/Subtraktions-Ausdrücke erstellt werden. Die Ausdrücke liegen als Strings vor, die Zahlen in den Ausdrücken bestehen zunächst nur aus einzelnen Ziffern. Beispiele für solche Ausdrücke sind etwa "9-3-4" oder "3-5+0-1" oder auch "2".

Eine kontextfreie Grammatik G = (V, T, P, S) für die Ausdrücke ist wie folgt gegeben. Es sind

V  = { expr, number }  die Menge der Variablen,
T  = { 0, ..., 9, +, - }  die Menge der Terminal­zeichen,
P : 
expr geht über nachexpr + number  |  expr - number  |  number
number geht über nach0  |  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9
 die Produktionen und
S  = expr das Startsymbol.

Leider verträgt sich aber die gegebene Grammatik nicht ohne Weiteres mit der Recursive-Descent-Methode. Denn die Umsetzung der Alternative expr geht über nachexpr + number würde zu folgendem Programm führen:

void expr()
{
    expr();
    match("+");
    number();
}

Hier tritt in der ersten Anweisung bereits wieder ein rekursiver Aufruf von expr auf, ohne dass ein Zeichen des Eingabe­wortes verarbeitet wurde. Dies führt zu einer unendlichen Kette von Aufrufen von expr und damit irgendwann zum Abbruch des Programms mit der Fehler­meldung "stack overflow".

Derartige Links­rekursionen müssen also vermieden werden. Es gibt aber Möglich­keiten, die Grammatik entsprechend umzuformen.

Ersetzen von Linksrekursion durch Rechtsrekursion

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

Die allgemeine Vorgehens­weise besteht darin, jede Produktion der Form

Xgeht über nachXw  |  u

durch die Produktionen

Xgeht über nachuR
Rgeht über nachwR  |  ε

zu ersetzen. Hierbei ist R eine neu eingeführte Variable.

Angewandt auf die Grammatik G führt dies zu folgenden Produktionen; hierbei steht expr für X, number für u, + number bzw. - number für w sowie rest für die neu eingeführte Variable R.

expr geht über nachnumber rest
rest geht über nach+ number rest  |  - number rest  |  ε

Die so umgeformte Grammatik lässt sich unmittelbar in einen Recursive-Descent-Parser umsetzen (Aufgabe 1).

Ersetzen von Rekursion durch Iteration

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

Rgeht über nachuw*

Ausgehend von der ursprüng­lichen links­rekursiven Grammatik ergibt sich folgende umgeformte Grammatik:

expr geht über nachnumber (+ number | - number)*
number geht über nach0  |  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9

Hierbei steht wieder expr für X, number für u und + number bzw. - number für w.

 

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

Rgeht über nachwR  |  u

wird ersetzt durch die Produktion

Rgeht über nachw*u

Programm

Die umgeformte Grammatik aus dem vorigen Abschnitt lässt sich unmittelbar in folgendes Programm umsetzen:

 

public class SimpleExpressionParser extends Parser
{
    @Override
    protected void startSymbol()
    {
        expr();
    }

    // expr -> number (+ number | - number)*
    private void expr()
    {
        number();
        while (comesAnyOf("+-"))
            if (comes("+"))
            {
                match("+");
                number();
            }
            else if (comes("-"))
            {
                match("-");
                number();
            }
    }

    // number -> 0 | 1 | ... | 9
    private void number()
    {
        if (comesDigit())
            consume(1);
        else
            throw new RuntimeException("Ziffer erwartet");
    }

    // Test
    public static void main(String[] args)
    {
        Parser p=new SimpleExpressionParser();
        String x="9-5+3";
        p.parse(x);
        System.out.println(x);
        System.out.println(p.errorPointer());
        System.out.println(p.errormessage);
    }

}    // end class SimpleExpressionParser 

Aufgaben

Aufgabe 1:  Erweitern Sie den Parser um Ausdrücke mit Multi­plikation und Division sowie Klammerung. Legen Sie dabei die Grammatik mit folgenden Produktionen zugrunde:

expr geht über nachterm (+ term | - term)*
term geht über nachfactor (* factor | / factor)*
factor geht über nachnumber  |  ( expr )
number geht über nach0  |  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9

 

Testen Sie den Parser mit folgendem Ausdruck:

2*(3+4)-4-5

 

Weiter mit:   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 02.12.2011   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