Парсеры

11.2. Анализ арифметических выражений

Рассмотрим арифметические выражения вида:

-2 + 3 * x; 
-2^2 * 3 + 2 * 4 / (3 - 1) + (sin(pi/6 + pi/3)) ^ 2 - ln (2 * e^3 - 1); 
2^3^2 - 3 * (4 + 10^2) * (3 - 10^2); 
7.

В следующей программе выполняется синтаксический анализ таких выражений. Разбор выполняется в соответствии с праворекурсивной грамматикой, которая имеет следующий вид:

expr  ::=  addSignOpt  item  items
item  ::=  deg  potens
deg  ::=  elem  elems
elem  ::=  fun  [(]  expr  [)]  |  [(]  expr  [)]  |  [pi]  |  [e]  |  num  |  var
items  ::=  addSign  item  items  |  none
potens   ::=  multSign  deg  potens |  none
elems  ::=  [^]  elem  elems  |  none
addSignOpt  ::=  addSign  |  none
addSign   ::=  [+]  |  [-]
multSign  ::=  [*]  |  [\]
fun  ::=  [cos]  |  [sin]  |  [exp]  |  [ln]

Сначала программа строит терм дерева разбора. Если выражение не содержит переменных, то по терму вычисляется его значение. Затем выполняется обратное преобразование терма в строку. Предикат parser/4 по входному списку токенов и нетерминальному символу грамматики (expr, item, deg или elem) возвращает подтерм дерева разбора и остаток списка токенов. Предикат parser/5 имеет еще один аргумент — терм, который соответствует первому аргументу бинарной операции (сложения, вычитания, умножения, деления или возведения в степень). Он рекурсивно строит терм для последовательности аргументов этой операции (см. правила для символов items, potens и elems).

class predicates
    scan: (string) -> string*.
clauses
    scan(Str) = [Tok | scan(RestStr)]:-
        string::frontToken(Str, Tok, RestStr),
        !.
    scan(_) = [].

domains                                                 % парсер
    term = un(string Op, term); bin(string Op, term, term);
        func(string Op, term); var(string); r(real); pi(); e().
    nt = expr; item; items; deg; potens; elem; elems.
class predicates
    parser: (nt, string*, term [out], string* [out]) determ.
    parser: (nt, string*, term, term [out], string* [out]).
clauses
    parser(expr, [S | L], Term, Rest):-
        addOp(S),
        !,
        parser(item, L, Term1, L1),
        parser(items, L1, un(S, Term1), Term, Rest).
    parser(expr, L, Term, Rest):-
        parser(item, L, Term1, L1),
        parser(items, L1, Term1, Term, Rest).
    parser(item, L, Term, Rest):-
        parser(deg, L, Term1, L1),
        parser(potens, L1, Term1, Term, Rest).
    parser(deg, L, Term, Rest):-
        parser(elem, L, Term1, L1),
        parser(elems, L1, Term1, Term, Rest).
    parser(elem, [S, "(" | L], func(S, Term), Rest):-
        fun(S),
        !,
        parser(expr, L, Term, L1),
        L1 = [")" | Rest].
    parser(elem, ["(" | L], un("()", Term), Rest):- !,
        parser(expr, L, Term, L1),
        L1 = [")" | Rest].
    parser(elem, ["pi" | L], pi(), L):- !.
    parser(elem, ["e" | L], e(), L):- !.
    parser(elem, [S | L], r(R), L):-
        (R = tryToTerm(unsigned, S); R = tryToTerm(real, S)),
        !.
    parser(elem, [S | L], var(S), L):-
        string::isName(S).

    parser(items, [S | L], Term1, Term, Rest):-
        addOp(S),
        parser(item, L, Term2, L1),
        !,
        parser(items, L1, bin(S, Term1, Term2), Term, Rest).
    parser(potens, [S | L], Term1, Term, Rest):-
        multOp(S),
        parser(deg, L, Term2, L1),
        !,
        parser(potens, L1, bin(S, Term1, Term2), Term, Rest).
    parser(elems, ["^" | L], Term1, bin("^", Term1, Term2), Rest):-
        parser(deg, L, Term2, Rest),
        !.
    parser(_, L, Term, Term, L).

class facts
    addOp: (string).
    multOp: (string).
    fun: (string).
clauses
    addOp("+").
    addOp("-").

    multOp("*").
    multOp("/").

    fun("sin").
    fun("cos").
    fun("exp").
    fun("ln").

class predicates        % вычислитель
    calc: (term) -> real determ.
clauses
    calc(r(R)) = R.
    calc(pi()) = math::pi.
    calc(e()) = math::e.
    calc(un("-", X)) = - calc(X):- !.
    calc(un(_, X)) = calc(X).
    calc(bin("+", X, Y)) = calc(X) + calc(Y).
    calc(bin("-", X, Y)) = calc(X) - calc(Y).
    calc(bin("*", X, Y)) = calc(X) * calc(Y).
    calc(bin("/", X, Y)) = calc(X) / R:-
        R = calc(Y),
        R <> 0.
    calc(bin("^", X, Y)) = calc(X) ^ calc(Y).
    calc(func("sin", X)) = math::sin(calc(X)).
    calc(func("cos", X)) = math::cos(calc(X)).
    calc(func("exp", X)) = math::exp(calc(X)).
    calc(func("ln", X)) = math::ln(R):-
        R = calc(X),
        R > 0.

class predicates  % преобразование в строку
    toStr: (term) -> string.
clauses
    toStr(pi()) = "pi".
    toStr(e()) = "e".
    toStr(r(R)) = toString(R).
    toStr(var(V)) = V.
    toStr (un("()", X)) = string::format("(%)", toStr(X)):- !.
    toStr(un(S, X)) = string::format("% %", S, toStr(X)).
    toStr(bin(S, X, Y)) = string::format("% % %", toStr(X), S,
        toStr(Y)).
    toStr(func(S, X)) = string::format("%(%)", S, toStr(X)).

    run():-
        S = "-2^3^2 + 3 * (10 - 3) + 20 ^2 + sin(pi / 3)",
        write(S), nl, nl,
        L = scan(S),
        parser(expr, L, Term, Rest),
        write(Rest), nl, nl,
        write(Term), nl, nl,
        write(toStr(Term)),
        R = calc(Term),
        write(" = ", R),
        fail;
        _ = readLine().

Предикат isName проверяет, удовлетворяет ли строка синтаксическим требованиям, предъявляемым к переменным (и ключевым словам). Предикат tryToTerm конвертирует элемент домена string в элемент другого домена. Предикаты exp и ln вычисляют значения экспоненты и натурального логарифма действительного числа (домена real и ureal, соответственно).

Программа не требует, чтобы строка полностью удовлетворяла грамматике. Выполняется разбор максимального префикса строки, который ей удовлетворяет. Неразобранная часть строки в виде токенов остается в списке Rest.

В определении предиката calc не используется хвостовая рекурсия. С помощью анонимных предикатов вычисления можно существенно ускорить:

domains
    operation = (real, real) -> real.
    unOperation = (real) -> real.
class predicates
    op : (string) -> operation.
    unop : (string) -> unOperation.
    calc: (term) -> real determ.
clauses
    op("+") = {(X, Y) = X + Y}:- !.
    % …

    unop("-") = {(X) = -X}:- !.
    unop("sin") = {(X) = math::sin(X)}:- !.
    % …

    calc(bin(S, X, Y)) = op(S)(X, Y).
    % …

Упражнение. Завершите определение вычислителя.

11.3. Поиск наибольшего общего унификатора

В данном параграфе реализуется алгоритм поиска наибольшего общего унификатора двух термов (или атомарных формул). Формулы подаются программе в виде двух строк. Парсер преобразует их в термы специального вида, которые и поступают на вход алгоритма.

Грамматика исходных формул описывается следующим образом:

term      ::= var  |  const  |  fun [(] termlist [)]
termlist  ::= term  |  term [,] termlist

Переменные пишутся с прописной буквы, а константы, предикатные и функциональные символы — со строчной, например, $$p(X, f(a, Y, g(b)), h(1, Z))$$.

Алгоритм поиска наибольшего общего унификатора термов $$T_1$$ и $$T_2$$ с помощью двух стеков $$L$$ и $$S$$ описан в [9]. Он заключается в следующем. Вначале в $$L$$ помещается пара термов $$(T_1, T_2)$$, стек $$S$$ пуст. Алгоритм начинается с шага 1.

    open core, console, string

domains
        term = var(string Var); c(string Const); f(string Name, term*).

% парсер
class predicates
    scan: (string) -> string*.
    parser: (string*, term [out], string* [out]) determ.
    parser: (string*, term* [out]) -> string* determ.
    checkName: (string) determ.
clauses
    scan(Str) = [Tok | scan(RestStr)]:-
        frontToken(Str, Tok, RestStr),
        !.
    scan(_) = [].

    parser([S, "(" | L], f(S, TermList), Rest):- !,
        checkName(S),
        [")" | Rest] = parser(L, TermList).
    parser([S | L], var(S), L):-
        isName(S),
        Ch = frontChar(S), 
        Ch = charUpper(Ch),
        !.
    parser([S | L], c(S), L):-
        (_ = tryToTerm(unsigned, S); _ = tryToTerm(real, S);
        checkName(S)),
        !.

    parser(["," | L], TermList) = parser(L, TermList):- !.
    parser(L, [Term | TermList]) = parser(Rest, TermList):-
        parser(L, Term, Rest),
        !.
    parser(L, []) = L.

    checkName(S):-
        Ch = charToString(frontChar(S)),
        hasAlpha(Ch),
        isLowerCase(Ch).

% поиск наибольшего общего унификатора
class predicates
    unify: (term, term) -> term*  determ.
    unif: (term*, term*) -> term* determ.
    subterm: (term, term) determ.
    replace: (term*, term, term) -> term*.
    delete: (term*) -> term*.
    put: (term*, term*, term*) -> term* determ.
clauses
    unify(X, Y) = unif([X, Y], []).

    unif([var(X), var(X) | L], Subst) = unif(L, Subst):- !.
    unif([c(X), c(X) | L], Subst) = unif(L, Subst):- !.
    unif([var(X), Y | L], Subst) = unif(replace(L, var(X), Y),
            [var(X), Y | delete(replace(Subst, var(X), Y))]):- !,
        not(subterm(var(X), Y)).
    unif([Y, var(X) | L], Subst) = unif([var(X), Y | L], Subst):- !.
    unif([f(N, TL1), f(N, TL2) | L], Subst) = unif(L1, Subst):-
        L1 = put(TL1, TL2, L).
    unif([], Subst) = Subst.

    subterm(X, X):- !.
    subterm(X, f(_, L)):-
        list::exists(L, {(H):- subterm(X, H)}).

    replace([X | L], X, Y) = [Y | replace(L, X, Y)]:- !.
    replace([H | L], X, Y) = [H | replace(L, X, Y)].
    replace([], _, _) = [].

    delete([X, X | L]) = delete(L):- !.
    delete([X, Y | L]) = [X, Y | delete(L)]:- !.
    delete(_) = [].

    put([X | L1], [Y | L2], L) = put(L1, L2, [X, Y | L]).
    put([], [], L) = L.

% преобразование в строку
class predicates
    s: (term) -> string.
    toStr: (term*) -> string*.
clauses
    s(var(X)) = X:- !.
    s(c(X)) = X:- !.
    s(f(N, L)) = format("%(%)", N, 
            concatWithDelimiter(list::map(L, {(T) = s(T)}), ", ")).

    toStr([X, Y | L]) = [format("% = %", s(X), s(Y)) | toStr(L)]:- !.
    toStr(_) = [].

    run():-
        S1 = "p(X, f(b, Y), g(a, a), k(h(1, 2, 3)), U)",
        S2 = "p(a, f(b, a), g(a, Y), k(Z), V)",
        parser(scan(S1), Term1, _),
        parser(scan(S2), Term2, _),
        Subst = unify(Term1, Term2),
        writef("%\n%\n\n%", s(Term1), s(Term2), 
            concatWithDelimiter(toStr(Subst), ", ")),
        fail;
        _ = readLine().

Предикат charToString преобразует символ (char) в строку (string), предикат isLowerCase истинен, если все символы строки имеют нижний регистр, предикат hasAlpha истинен, если строка состоит только из букв, предикат exists проверяет, имеется ли в списке элемент, удовлетворяющий заданному условию.

Упражнение 2. Реализуйте в программе, приведенной в листинге 11.3, возможность использования анонимных переменных (напомним, что они унифицируются с любыми термами, но не принимают значений).

Упражнения