Parser und Übersetzer

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

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 nachnumber (+ number | - number)*
number geht über nach0  |  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9
 die Produktionen und
S  = expr das Startsymbol.

Programm

Die Grammatik lässt sich unmittelbar in folgendes Programm umsetzen. Die Klasse SimpleExpressionParser ist von der Basisklasse Parser abgeleitet..

 

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

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

    private void number()
    {
        if (comes("0"))
            match("0");
        else if (comes("1"))
            match("1");
        else if (comes("2"))
            match("2");
        else if (comes("3"))
            match("3");
        else if (comes("4"))
            match("4");
        else if (comes("5"))
            match("5");
        else if (comes("6"))
            match("6");
        else if (comes("7"))
            match("7");
        else if (comes("8"))
            match("8");
        else if (comes("9"))
            match("9");
        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: [Übersetzer für Additions-/Subtraktions-Ausdrücke]   oder   [up]

 

H.W. Lang   mail@hwlang.de   Impressum   Datenschutz
Created: 02.12.2011   Updated: 17.02.2023
Diese Webseiten sind während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden