P => Program K => Block
S => Single-command
C => Commands
E => Expression
B => Boolean-expr
I => Identifier
N > Numeral
P ::= K.
K ::= begin C end
C ::= C1 ; C2 | S
S ::= I := E | if (B) then S | if (B) then S1 else S2 | while (B) do S | repeat C until (B) | K | print E
E ::= − E | E1 + E2 | E1 − E2 | E1 E2 | E1 div E2 | E1 mod E2 | (E) | I | N
B ::= E1 = E2 | E1 > E2 | E1 < E2 | E1 != E2 | not B | B1 and B2 | B1 or B2 | (B)
I am supposed to remove ambiguities in E and B so that I can write a DCG parser in prolog.
Prolog evaluates top down, then LL grammar techniques can be adapted. DCG are more powerful than LL(1), but left recursion must still be eliminated.
B
is easier to handle: left factor the production.E is harder, because the miss
mul
token introduces still more ambiguity. Tentativelyepsilon (empty production) in DCG can be written this way
If you need to handle precedence and associativity (in both B and E) you will need more work. You can refer to this older answer for a working schema.
@chac already gave you quite a good answer, showing you the usual way to resolve this.
Let me take another way to read your question: You are "supposed to remove ambiguities in E and B so that" you "can write a DCG parser in Prolog". That means, you need to remove ambiguity only that far that you can write a DCG parser in Prolog. There is good news: You do not need to remove any ambiguities at all to write a DCG parser! Here is how:
The source of ambiguity are productions like
C ::= C ; C
or the other operators + - juxtapositioning div mod and
Let me stick to a simplified grammar:
E ::= E + E | "1"
We could encode this as
Unfortunately, Prolog does not terminate for a query like
Actually, it terminates, but only because my computer's memory is finite...
Not even for:
Is this a problem of ambiguity? No! It is just a procedural problem of Prolog which cannot handle left-recursions directly. Here is a way to make Prolog handle it:
For the moment we have only defined a grammar, most of the times you are also interested to see the corresponding syntax tree:
Now, we see that there is an ambiguity with
plus
! Your original grammar both accepted it as (1+1)+1 and 1+(1+1) which itself is not a problem as long as the corresponding semantics guarantees that associativity is observed. Most of the time this is disambiguated to be left-associative, thus meaning (1+1)+1, but this is not the case for all infix operators.