"Kézi" elemzők

Adott a következő nyelvtan:

S -> '+' A A | '*' A A
A -> szam | S
szam -> szamjegy | szamjegy szam
szamjegy -> '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

ami egy decimális számleírást, valamint az összeadás és szorzás műveletét tartalmazó prefix kifejezés nyelvtanát adja meg. Készítsünk egy elemzőt (lexer + parser), ami kiszámolja egy ilyen kifejezés értékét.

A lexer felfogható egyfajta "előfeldolgozóként": karaktersorozatokból tokensorozatot gyárt. Maga a parser pedig ezt a tokensorozatot fogja elemezni a nyelvtan alapján. Bizonyos szempontból a token a parser terminális szimbólumának tekinthető, de az eredeti karaktersorozathoz is hozzáférünk.

Token példák

A fenti nyelvtanban például a +, * és 0 ... 9 karakterek terminális szimbólumoknak látszanak. De ha jobban megnézzük akkor az is látszik, hogy a szam tulajdonképpen tokennek tekinthető, ami leírható a [0-9]+ reguláris kifejezéssel. Így a nyelvtan terminális szimbólumai a +, * és a szam lesznek (a szamjegy-et pedig megspóroltuk).

De akár a + és * is összevonható lenne mondjuk egy muvelet tokenné. Így a + 40 * 1 2 karaktersorozatból a lexer muvelet('+') szam('40') muvelet('*') szam('1') szam('2') tokensorozatot csinálna, ahol a zárójelbe írt konkrét értékek az elemzést magát nem befolyásolnák.

1. kérdés

Mit kell tudjon a lexer ahhoz, hogy valóban használható elemzőt tudjunk írni? Milyen tokensorozatot kellene kapni az alábbi karaktersorozatok alapján?

• +40*21
• * 2 +*4 5 1
• +7hat*+2x3@5

A lexer alapvetően reguláris kifejetésekkel operál, mohó módon dolgozik, és fogalma sincs a nyelvtanról, viszont minden karaktert feldolgoz! Éppen ezért, ha két token egymás után írva egyetlen tokenként is értelmezhető (pl. '2'-t és '1'-et összeírva '21'-et kapunk), akkor a lexernek szüksége lesz valamilyen elválasztó karakterekre, amik viszont a nyelvtanban már nem fognak megjelenni. Ezek tipikusan a whitespace karakterek (amik közül néhány olykor mégis speciális jelentéssel bír és így mégsem eldobható; ennek a legszélsőségesebb esete talán a Whitespace programozási nyelv).

A parser maga az elemző, ami tokensorozaton dolgozik, a tokenek konkrét értékei elemzési szempontból lényegtelenek. Persze ha valami miatt a tokenek konkrét értékeire is szükség van (mert mondjuk elemzés közben ki is szeretnénk számolni a kifejezés értékét, vagy szebb formában vissza szeretnénk írni), hozzájuk lehet férni.

2. kérdés

A nyelvtan egy egyszerű LL(k) nyelvtan, vagyis véges számú (jelen esetben 1) token előrenézésével eldönthető, hogy a lehetséges nyelvtani szabályok közül melyiket kell alkalmazni. Mi legyen az elemző működési elve?

3. kérdés

Ha már megvan a működési elv, ebbe hogyan tudjuk belerakni azt, hogy a megadott kifejezés értéke ki is legyen számolva?

Feladat (f01)

Adott az

S -> '+' A A | '*' A A
A -> szam | S
szam = [0-9]+

nyelvtan. Készíts hozzá egy elemzőt (lexer + parser páros), ami nem csak leelemzi a nyelvtannak megfelelő kifejezéseket, de ki is értékeli azokat! Az elemző a whitespace karaktereket hagyja figyelmen kívül, de bármilyen más, a nyelvben nem szereplő karakter esetén jelezzen hibát!

Bővítsd az alábbi osztályokat:

BaseLexer.java

public interface BaseLexer {
    String nextToken();
}

Lexer.java

public class Lexer implements BaseLexer {
    public Lexer(String source) {
        // TODO
    }
    public String nextToken() {
        // TODO
        return null;
    }
}

BaseParser.java

import java.util.LinkedList;

public class BaseParser {
    private LinkedList<String> tokens;
    public BaseParser(BaseLexer lexer) {
        tokens = new LinkedList<String>();
        String token;
        while ((token = lexer.nextToken()) != null) {
            tokens.add(token);
        }
    }
    public String lookAhead(int dist) {
        return (0 < dist && dist <= tokens.size()) ? tokens.get(dist - 1) : null;
    }
    public void readToken() {
        tokens.remove();
    }
}

Parser.java

public class Parser extends BaseParser {
    public Parser(BaseLexer lexer) {
        super(lexer);
    }
    public void start() {
        try {
            // TODO
            throw new ParserErrorException("Not yet implemented.");
        } catch (ParserErrorException e) {
            System.err.println(e);
        }
    }
    public static void main(String[] args)
    {
        for (int i = 0; i < args.length; ++i) {
            System.out.println("Parsing: " + args[i]);
            Parser p = new Parser(new Lexer(args[i]));
            p.start();
        }
    }
}

ParserErrorException.java

public class ParserErrorException extends Exception {
    public ParserErrorException(String s) {
        super(s);
    }
}

A forráskód egyben.

Lehetséges megoldás: csak elemzés (m01-1)

Lexer.java

public class Lexer implements BaseLexer {
    private String source;
    private int tokenBeginPosition = 0;
    private int tokenEndPosition = 0;

    public Lexer(String source) {
        this.source = source;
    }
    public String nextToken() {
        tokenBeginPosition = tokenEndPosition;
        while (tokenBeginPosition < source.length()) {
            char nxt = '\0';
            while (tokenBeginPosition < source.length() && ((nxt = source.charAt(tokenBeginPosition)) == ' '
                    || nxt == '\n')) {
                ++tokenBeginPosition;
            }
            if (tokenBeginPosition >= source.length()) {
                break;
            }
            tokenEndPosition = tokenBeginPosition + 1;
            if (nxt == '+' || nxt == '*') {
                return source.substring(tokenBeginPosition, tokenEndPosition);
            } else if ('0' <= nxt && nxt <= '9') {
                while (tokenEndPosition < source.length() && '0' <= (nxt = source.charAt(tokenEndPosition))
                        && nxt <= '9') {
                    ++tokenEndPosition;
                }
                return source.substring(tokenBeginPosition, tokenEndPosition);
            } else {
                System.err.println("Skipping invalid token at " + tokenBeginPosition + ": '" +
                        source.substring(tokenBeginPosition, tokenEndPosition) + "'");
                tokenBeginPosition = tokenEndPosition;
                continue;
            }
        }
        return null;
    }
}

Parser.java

public class Parser extends BaseParser {
    public Parser(BaseLexer lexer) {
        super(lexer);
    }
    public void start() {
        try {
            S();
            String token = lookAhead(1);
            if (token != null) {
                throw new ParserErrorException("Parse error: '" + token + "' found while EOF is expected.");
            }
        } catch (ParserErrorException e) {
            System.err.println(e);
        }
    }
    public void S() throws ParserErrorException {
        long value = 0;
        String token = lookAhead(1);
        if (token == null) {
            throw new ParserErrorException("Parse error: EOF found while expecting '+' or '*'.");
        }
        switch (token) {
          case "+":
            readToken();
            A();
            A();
            break;
          case "*":
            readToken();
            A();
            A();
            break;
          default:
            throw new ParserErrorException("Parse error at '" + token + "': tokens '+' or '*' not found.");
        }
    }
    public void A() throws ParserErrorException {
        String token = lookAhead(1);
        if (token == null) {
            throw new ParserErrorException("Parse error: EOF found while expecting '+', '*', or a number.");
        }
        switch (token) {
          case "+":
          case "*":
            S();
            break;
          default:
            readToken();
            break;
        }
    }
    public static void main(String[] args)
    {
        for (int i = 0; i < args.length; ++i) {
            System.out.println("Parsing: " + args[i]);
            Parser p = new Parser(new Lexer(args[i]));
            p.start();
        }
    }
}

Lehetséges megoldás: elemzés és számolás (m01-2)

Parser.java

public class Parser extends BaseParser {
    public Parser(BaseLexer lexer) {
        super(lexer);
    }
    public void start() {
        try {
            long value = S();
            System.out.println("Computed value: " + value);
            String token = lookAhead(1);
            if (token != null) {
                throw new ParserErrorException("Parse error: '" + token + "' found while EOF is expected.");
            }
        } catch (ParserErrorException e) {
            System.err.println(e);
        }
    }
    public long S() throws ParserErrorException {
        long value = 0;
        String token = lookAhead(1);
        if (token == null) {
            throw new ParserErrorException("Parse error: EOF found while expecting '+' or '*'.");
        }
        switch (token) {
          case "+":
            readToken();
            value = A();
            value += A();
            break;
          case "*":
            readToken();
            value = A();
            value *= A();
            break;
          default:
            throw new ParserErrorException("Parse error at '" + token + "': tokens '+' or '*' not found.");
        }
        return value;
    }
    public long A() throws ParserErrorException {
        long value = 0;
        String token = lookAhead(1);
        if (token == null) {
            throw new ParserErrorException("Parse error: EOF found while expecting '+', '*', or a number.");
        }
        switch (token) {
          case "+":
          case "*":
            value = S();
            break;
          default:
            try {
                value = Long.parseLong(token);
            } catch (NumberFormatException e) {
                throw new ParserErrorException("Parse error at '" + token + "': Wrong number format.");
            }
            readToken();
            break;
        }
        return value;
    }
    public static void main(String[] args)
    {
        for (int i = 0; i < args.length; ++i) {
            System.out.println("Parsing: " + args[i]);
            Parser p = new Parser(new Lexer(args[i]));
            p.start();
        }
    }
}

A megoldások egyben.

---

Utolsó frissítés: 2023-02-14 12:58:16