I'm working to develop a small parser for an imperative language, but I'm stuck with the definition of the grammars not left recursive.
I read this post about the solution, but I'm not able to realize it, I move the call with the terminal on top of my declaration but I'm confused with the different syntax used to express the same meaning.
My input tokens is the following one [word(x),punct(:),punct(=),number(1)]
And this is the code that I used to parse this list
parse(ListTokens, ListStmt) :-
phrase(commands(ListStmt), ListTokens).
commands([]) --> [].
commands(Command) --> command(Command).
commands(Commands) --> [punct("(")], commands(Commands), [punct(")")].
commands([Command | Commands]) --> command(Command), [punct(";")], commands(Commands).
command(Skip) --> [keyword("skip")],
{Skip = skip()}.
command(Assign) --> a_expr(X), !, [punct(":")], [punct("=")], a_expr(Y), !,
{Assign = assign(X, Y)}.
command(While) --> [keyword("while")], b_expr(X), !, [keyword("do")], command(Commands), !,
{While = while(X, Commands)}.
a_expr(word(Name)) --> [var(Name)].
a_expr(number(Val)) --> [Val].
a_expr(Expr) --> a_expr(X), !, [punct("+")], a_expr(Y), !, {Expr = increment(X, Y)}.
a_expr(Expr) --> a_expr(X), !, [punct("-")], a_expr(Y), !, {Expr = decrement(X, Y)}.
a_expr(Expr) --> a_expr(X), !, [punct("*")], a_expr(Y), !, {Expr = multipl(X, Y)}.
b_expr(Expr) --> [punct("(")], b_expr(Expr), [punct(")")].
b_expr(True) --> [keyword("true")], {True = bool(1)}.
b_expr(False) --> [keyword("false")], {False = bool(0)}.
b_expr(Cmp) --> a_expr(X), !, [punct("=")], a_expr(Y), !, {Cmp = cmp(X, Y)}.
b_expt(Gt) --> a_expr(X), !, [punct(">")], a_expr(Y), !, {Gt = gt(X, Y)}.
The result is reported below but I would like to have the following one assign(x,1)
assign(number(word(x)),number(number(1)))
I think that the problem is the following lines, but I'm not able to find the error, because this is a solution that came from this post that use a different sintax
a_expr(word(Name)) --> [var(Name)].
a_expr(number(Val)) --> [Val].
Can you help me to find an escape from this problem?
Basically, there are two problems with your code.
One is the bang operator ! that stops the backtracking. It is an antipattern, so I suggest to don't use it.
I'm a big fan of readable code and I think you need to accept the left recursion in your grammar, basically because the syntax that you use is very readable.
I suggest changing
parse(ListTokens, ListStmt) :-
phrase(commands(ListStmt), ListTokens).
commands([]) --> [].
commands(Command) --> command(Command).
commands(Commands) --> [punct("(")], commands(Commands), [punct(")")].
commands([Command | Commands]) --> command(Command), [punct(";")], commands(Commands).
command(Skip) --> [keyword("skip")],
{Skip = skip()}.
command(Assign) --> a_expr(X), !, [punct(":")], [punct("=")], a_expr(Y), !,
{Assign = assign(X, Y)}.
command(While) --> [keyword("while")], b_expr(X), !, [keyword("do")], command(Commands), !,
{While = while(X, Commands)}.
a_expr(word(Name)) --> [var(Name)].
a_expr(number(Val)) --> [Val].
a_expr(Expr) --> a_expr(X), !, [punct("+")], a_expr(Y), !, {Expr = increment(X, Y)}.
a_expr(Expr) --> a_expr(X), !, [punct("-")], a_expr(Y), !, {Expr = decrement(X, Y)}.
a_expr(Expr) --> a_expr(X), !, [punct("*")], a_expr(Y), !, {Expr = multipl(X, Y)}.
b_expr(Expr) --> [punct("(")], b_expr(Expr), [punct(")")].
b_expr(True) --> [keyword("true")], {True = bool(1)}.
b_expr(False) --> [keyword("false")], {False = bool(0)}.
b_expr(Cmp) --> a_expr(X), !, [punct("=")], a_expr(Y), !, {Cmp = cmp(X, Y)}.
b_expt(Gt) --> a_expr(X), !, [punct(">")], a_expr(Y), !, {Gt = gt(X, Y)}.
To this one, basically, add the following line :- table a_expr//1. to use tabling and accept the left recursion. (Alert, you need to remove all the bang operator)
:- table a_expr//1.
% other rules
% add this one, it is left recursion, but tanks to tabling
a_expr(Var) --> [word(Name)], {Var = var(Name)}.
a_expr(Val) --> [number(X)], {Val = X}.
a_expr(Expr) --> a_expr(X), [punct("+")], a_expr(Y), {Expr = increment(X, Y)}.
a_expr(Expr) --> a_expr(X), [punct("-")], a_expr(Y), {Expr = decrement(X, Y)}.
a_expr(Expr) --> a_expr(X), [punct("*")], a_expr(Y), {Expr = multipl(X, Y)}.
P.S: As one comment suggests, you need to make a typing mistake with the following rules
b_expt(Gt) --> a_expr(X), !, [punct(">")], a_expr(Y), !, {Gt = gt(X, Y)}.
it is b_expr