Declarative Programming

Parsing

Parsing

Overview

Operator Precedence

Prolog Operators

:- op(precedence, fixity, operator).

e.g. Prolog imperative for loop

:- op(950, fx, for).
:- op(940, xfx, in).
:- op(600, xfx, '..').
:- op(1050, xfy, do).

for Generator do Body :-
    (   call(Generator),
        call(Body),
        fail
    ;   true
    ).

Var in Low .. High :-
    between(Low, High, Var).

Var in [H|T] :-
    member(Var, [H|T]).

Haskell Operators

e.g. define % as synonym for mod

infix 7 %

(%) :: Integral a => a -> a -> a
a % b = a `mod` b

Grammars

\[\text{expression} \rightarrow \text{expression} '+' \text{expression} \text{expression} \rightarrow \text{expression} '-' \text{expression} \text{expression} \rightarrow \text{expression} '*' \text{expression} \text{expression} \rightarrow \text{expression} '/' \text{expression} \text{expression} \rightarrow \text{number}\]

Definite Clause Grammars

expr --> expr, '+', expr.
expr --> expr, '*', expr.
expr --> expr, '-', expr.
expr --> expr, '/', expr.
expr --> number.
expr(E1+E2) --> expr(E1), '+', expr(E2).
expr(E1*E2) --> expr(E1), '*', expr(E2).
expr(E1-E2) --> expr(E1), '-', expr(E2).
expr(E1/E2) --> expr(E1), '/', expr(E2).
expr(N) --> number(N).

Recursive Descent Parsing

Left Recursion

expr(N) --> number(N).
% becomes
expr(E) --> number(N), expr_rest(N, E).
expr(E1+E2) --> expr(E1), '+', expr(E2).
% becomes
expr_rest(E1,R) --> '+', expr(E2), expr_rest(E1+E2, R).

Disambiguating a grammar

expr(E-F) --> expr(E), '-' factor(F)

Final Grammar

expr(E) --> factor(F), expr_rest(F, E).

expr_rest(F1, E) --> '+', factor(F2), expr_rest(F1+F2, E).
expr_rest(F1, E) --> '-', factor(F2), expr_rest(F1-F2, E).
expr_rest(F, F) --> [].

factor(F) --> number(N), factory_rest(N,F).

factor_rest(N1, F) --> '*', number(N2), factor_rest(N1*N2, F).
factor_rest(N1, F) --> '/', number(N2), factor_rest(N1/N2, F).
factor_rest(N, N) --> [].

Tokenisers

number(N) --> 
    [C], 
    { '0' =< C, C =< '9'},
    { N0 is C - '0'},
    number_rest(N0, N).

number_rest(N0, N) -->
    (   [C],
        { '0' =< C, C =< '9'}
    ->  { N1 is N0 *10 + C - '0' },
        number_rest(N1, N),
    ;   { N = N0}
    ).

Working parser

?- phrase(expr(E), '3+4*5'), Value is E.
E = 3+4*5,
Value = 23;
false.

Extras

flatten(empty) --> []
flatten(node(L, E, R)) --> 
    flatten(L),
    [E],
    flatten(R).

Edit this page.