A Very Simple Parser

In this file we implement a very simple parser, that transforms a string in prefix notation into an expression tree.

444⟨* 13⟩+≡ ⊲429 449 ⊳
-------------------------------------------------------------------
----
---- Combinat
---- Copyright (C) Ralf Hemmecke <ralf@hemmecke.de>
---- Copyright (C) Martin Rubey <martin.rubey@univie.ac.at>
---- svn co svn://svn.risc.uni-linz.ac.at/hemmecke/combinat/
----
-------------------------------------------------------------------
#include "combinat"
⟨pkg: MyParser 445⟩

In the following we implement a very simple parser. It is intended to be replaced with something more intelligent, if the concept itself proves useful. In fact, maybe one could implement an interpreter for a subset of Aldor using the ideas in this package.

Type Constructor

MyParser

Description

Provides a function to transform a string into an ExpressionTree

MyParser provides a function to transform a string into an ExpressionTree

Remarks

We really should use the parsers provided by libaldor.

ToDo ⊲ 71 ⊳

mrx ⊲ 18 ⊳ It is not clear whether we shouldn’t parse into SpeciesExpressions immediately.

445⟨pkg: MyParser 445⟩≡   (444)
MyParser: with {
        ⟨exports: MyParser 446⟩
} == add {
        ⟨implementation: MyParser 447⟩
}

Defines:
MyParser, used in chunks 730–32.

Export of MyParser

parse: String -> ExpressionTree

Usage

parse("f(a, b, g(c,d))");

Description

Translates a string describing a functional expression into an ExpressionTree

parse translates a well-formed functional expression into an ExpressionTree. Blanks to the left or right of an argument is tripped. However, f(a b) would be parsed as an operator f applied to a single argument a b. Currently, no error checking is done.

446⟨exports: MyParser 446⟩≡ (445)
parse: String -> ExpressionTree;

Uses ExpressionTree 624a and String 65.

447⟨implementation: MyParser 447⟩≡   (445)
local parse!(g: Generator Character): List ExpressionTree == {
        import from Character, String, Symbol, ExpressionTree, ExpressionTreeLeaf;
        local trim(s: List Character): String == {
                rightTrim(leftTrim(
                        [generator reverse s],
                        char " "),
                    char " ");
        }
        opOrLeaf: List Character := [];
        result: List ExpressionTree := [];
        throwAway: Boolean := false;
        for c in g repeat {
                (c = char "(") => {
                        op := ExpressionTreePrefix( - trim opOrLeaf);
                        opOrLeaf := [];
                        args := parse! g;
                        result := cons(op.args, result);
                        throwAway := true;
                }
                (c = char ",") => {
                        if throwAway
                        then throwAway := false;
                        else result := cons(extree leaf trim opOrLeaf, result);
                        opOrLeaf := [];
                }
                (c = char ")") => {
                        if not throwAway
                        then result := cons(extree leaf trim opOrLeaf, result);
                        return reverse result;
                }
                opOrLeaf := cons(c, opOrLeaf);
        }
        if not throwAway
        then result := cons(extree leaf trim opOrLeaf, result);
        reverse result;
}

parse(s: String): ExpressionTree == {
        import from List ExpressionTree;
        first parse! generator s;
}

Uses ExpressionTree 624a, ExpressionTreeLeaf 623, ExpressionTreePrefix 622, Generator 617, and String 65.

Note that all leaves are left as strings, it is not possible to do type inference or checking here. There are three special symbols: the comma, and the open and closing parentheses. Text before an open parenthesis is interpreted as an operator name. Text between a close parenthesis and a comma or another close parenthesis is thrown away.

15 A Very Simple Parser