Search code examples
parsingprologgrammardcg

How do I create a DCG rule inverse to another in Prolog?


I am writing a Commodore BASIC interpreter in Prolog, and I am writing some DCGs to parse it. I have verified the DCGs below to work except for the variable one. My goal is this: for anything which isn't a boolean, integer, float, or a string, it's a variable. However, anything that I give it via phrase just results in no.

bool --> [true].
bool --> [false].
integer --> [1]. % how to match nums?
float --> [0.1].
string --> [Str], {atom_chars(Str, ['"' | Chars]), last(Chars, '"')}.
literal --> bool; integer; float; string.

variable --> \+ literal.

I ran a stack trace like this (with gprolog)

main :- trace, phrase(variable, [bar]).

Looking at this, I cannot figure out why variable fails, given that it fails for each case in literal. I'm guessing that the error is pretty simple, but I'm still stumped, so does anyone who's good at Prolog have an idea of what I'm doing wrong?

| ?- main.
The debugger will first creep -- showing everything (trace)
      1    1  Call: phrase(variable,[bar]) ? 
      2    2  Call: variable([bar],_321) ? 
      3    3  Call: \+literal([bar],_348) ? 
      4    4  Call: literal([bar],_348) ? 
      5    5  Call: bool([bar],_348) ? 
      5    5  Fail: bool([bar],_348) ? 
      5    5  Call: integer([bar],_348) ? 
      5    5  Fail: integer([bar],_348) ? 
      5    5  Call: float([bar],_348) ? 
      5    5  Fail: float([bar],_348) ? 
      5    5  Call: string([bar],_348) ? 
      6    6  Call: atom_chars(bar,['"'|_418]) ? 
      6    6  Fail: atom_chars(bar,['"'|_418]) ? 
      5    5  Fail: string([bar],_348) ? 
      4    4  Fail: literal([bar],_348) ? 
      3    3  Exit: \+literal([bar],_348) ? 
      2    2  Exit: variable([bar],[bar]) ? 
      1    1  Fail: phrase(variable,[bar]) ? 

(2 ms) no
{trace}

Solution

  • To expand a bit on the other answer, the key problem is that a DCG rule like \+ literal does not consume items from the input. It only checks that the next item, if any, is not a literal.

    To actually consume an item, you need to use a list goal, similarly to how you use a goal [1] to consume a 1 element. So:

    variable -->
        \+ literal,  % if there is a next element, it's not a literal
        [_Variable]. % consume this next element, which is a variable
    

    For example:

    ?- phrase(variable, [bar]).
    true.
    
    ?- phrase((integer, variable, float), [I, bar, F]).
    I = 1,
    F = 0.1.
    

    Having that singleton variable _Variable is a bit strange -- when you parse like this, you lose the name of the variable. When your parser is expanded a bit, you will want to use arguments to your DCG rules to communicate information out of the rules:

    variable(Variable) -->
        \+ literal,  
        [Variable].
    

    For example:

    ?- phrase((integer, variable(Var1), float, variable(Var2)), [I, bar, F, foo]).
    Var1 = bar,
    Var2 = foo,
    I = 1,
    F = 0.1.