DCG's (Definite Clause Grammars)

Gramáticas

Em Prolog é possível gerar analisadores sintácticos através das DCG's (Definite Clause Grammars). Neste formalismo, o fragmento de gramática 
    <expressão-booleana> ::= <booleano> or <booleano>
    <booleano> ::= true | false
seria representado por 
    expressão_booleana --> booleano, [or], booleano.

    booleano --> [true].
    booleano --> [false].
onde os símbolos não terminais são representados por átomos e os símbolos terminais aparecem como elementos de uma lista. Cada produção da gramática é traduzida pelo interpretador de Prolog para uma cláusula que sucede quando recebe como argumento uma lista de símbolos terminais (tokens) correspondentes a uma expressão sintacticamente correcta: 
    expressão-booleana(A, B) :- booleano(A, C), C = [or|D], booleano(D, B).

    booleano([true|A], A).
    booleano([false|A], A).
Deste modo, a query 
    ?- phrase(expressão_booleana, [true,or,false]).
que é traduzida internamente para 
    ?- expressão_booleana([true,or,false], []).
sucede, indicando que a expressão true or false está sintacticamente correcta.

Acções semânticas

É possível associar atributos (argumentos) aos símbolos não terminais e incluir acções semânticas (golos Prolog) nas produções, e.g.: 
    expressão_booleana(Valor) -->
        booleano(OpEsq), [or], booleano(OpDir), { ou(OpEsq, OpDir, Valor) }.

    booleano(true)  --> [true].
    booleano(false) --> [false].
Tudo o que aparece entre chavetas é incluído literalmente na cláusula: 
    expressão_booleana(Valor, A, B) :-
        booleano(OpEsq, A, C),
        C = [or|D],
        booleano(OpDir, D, B),
        ou(OpEsq, OpDir, Valor).

    booleano(true, [true|A], A).
    booleano(false, [false|A], A).
Se ou/3 for um predicado com a definição adequada, o cálculo do valor de uma expressão poderia ser feito através da query 
    ?- phrase(expressão_booleana(Valor), [true,or,false]).
que sucederia com Valor = true.

Produções-λ

Uma produção-λ escreve-se 
    não-terminal --> [].