[SOLVED] Grammar involving braces

Grammar involving braces

I'm trying to solve DCG grammar in prolog and succeeded upto a point, i'm stuck in evaluating the expressions involving braces like these. expr( T, [’(’, 5, +, 4, ’)’, *, 7], []),

expr(Z) --> num(Z).
expr(Z) --> num(X), [+], expr(Y), {Z is X+Y}.
expr(Z) --> num(X), [-], expr(Y), {Z is X-Y}.
expr(Z) --> num(X), [*], expr(Y), {Z is X*Y}.
num(D) --> [D], {number(D)}.

eval(L, V, []) :- expr(V, L, []).

Solution

The parsers implemented by Prolog's DCG grammars are recursive-descent LL(something) (predictive) grammars. It walks the input from left to right and produces a leftmost derivation as it goes. They're easy to craft but the grammar's must conform to a few restrictions:

They cannot be left-recursive. Infinite recursion can/will result. This means that at least one symbol (token) has to be removed from the input stream prior to following a recursive path. Refactoring grammars to remove left-recursion is a fairly mechanical exercise, albeit tedious. See any decent compiler book on how to do that.

Operator precedence is typically built into the structure of the grammar itself. Here's BNF notation showing one way of defining a recursive descent grammar for the parsing/evaluation of simple arithmetic expressions:

ArithmeticExpression     : AdditiveExpression
                         ;

AdditiveExpression       : MultiplicativeExpression
                         | MultiplicativeExpression '+' AdditiveExpression
                         | MultiplicativeExpression '-' AdditiveExpression
                         ;

MultiplicativeExpression : ExponentialExpression
                         | ExponentialExpression '*' MultiplicativeExpression
                         | ExponentialExpression '/' MultiplicativeExpression
                         | ExponentialExpression '%' MultiplicativeExpression
                         ;

ExponentialExpression    : UnaryExpression
                         | UnaryExpression '^' ExponentialExpression
                         ;

UnaryExpression          : '-' UnaryExpression
                         | AtomicExpression
                         ;

AtomicExpression         : '(' ArithmeticExpression ')'
                         | ['0'..'9']+
                         ;

The term at each level of operator precedence is built from expressions of the next higher order of precedence. So an arbitrary arithmetic expression is just a single additive expression.

Each additive expression is 1 or more multiplicative expressions, joined by addition and subtraction operators.

Each multiplicative expression is 1 or more exponential expressions, joined by multiplication, division and remainder operators.

Each exponential expression is a unary expression with an option exponent operator followed by another unary expression.

Each unary expression is either an atomic expression, or a unary minus followed by another unary expression.

Each atomic expression is either an arbitrary arithmetic expression, enclosed in parentheses, or an unsigned integer token.

Translation of the above into Prolog's DCG syntax should be trivial. How to evaluate the term represented by each clause in the grammar should be self-evident.