prologdcgleft-recursion

Remove Ambiguity in abstract syntax in other to write DCG parser Prolog

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.

Solution

  • 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.

    B ::= E Bx | not B | (B)
Bx ::= = E | > E | < E | != E | and B | or B

    E is harder, because the miss mul token introduces still more ambiguity. Tentatively

    E ::= − E | (E) | I | N | El
El ::= Ex E | epsilon
Ex ::= + El | − El | div El | mod El

    epsilon (empty production) in DCG can be written this way

    epsilon --> [].

    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.