Analisi sintattica

    L'idea iniziale di definire un interprete Prolog semplificato prevedeva la costruzione di un AS (classe Parser) molto specifico, cioè dipendente dagli operatori predefiniti. Era infatti legato ad una grammatica in cui si prevedeva che una clausola fosse data da un antecedente seguito dal simbolo :- e da un body che a sua volta era dato dall'or di termini and che a loro volta potevano essere costituiti da termini, da espressioni is, etc. La grammatica quindi esplicitava tutti gli operatori (vedi grammPrSempl.txt).
    Successivamente abbiamo trovato motivi validi per modificare radicalmente il Parser. L'osservazione principale è che in Prolog è possibile definire runtime nuovi operatori (tramite il predicato op/3) e dunque la grammatica dovrebbe essere modificata dinamicamente. Poiché abbiamo abbandonato l'idea iniziale di fare un interprete semplificato risultava a quel punto più semplice l'introduzione di tutti gli operatori built-in utilizzando un Parser generico e dinamicamente adattabile.
    La filosofia del nuovo Parser (classe NewParser) si basa sul fatto che tutti gli operatori Prolog sono essi stessi dei termini, perché in Prolog non vi è distinzione fra dati e programmi. Gli operatori Prolog possono essere binari o unari e questi ultimi possono essere prefissi o postfissi. Inoltre ogni operatore può essere o non essere associativo (i binari possono avere associatività a destra o a sinistra). Ciascun operatore ha poi una priorità (un intero compreso fra 0 e 1200) che serve a stabilire la precedenza degli operatori in modo da eliminare le ambiguità.
    L'operatore op/3 prevede di indicare il tipo dell'operatore come segue:
 

    in cui:

• f indica la posizione dell'operatore,
• x indica un argomento che è un atomo, un'espressione tra parentesi o un'espressione il cui operatore principale ha priorità strettamente minore di quella dell'operatore che si sta definendo,
• y indica un argomento che è un atomo, un'espressione tra parentesi o un'espressione il cui operatore principale ha priorità minore o uguale di quella dell'operatore che si sta definendo.

Clause ->

     Read(1200) .

Read(N) ->

     Op(N,M,fx) Read(M-1) Rest(N,M)

     Op(N,M,fx) Read(M-1)

     Op(N,M,fy) Read(M) Rest(N,0)

     Op(N,M,fy) Read(M)

     Term Rest(N,0)

     Term

Rest(N,M) ->

     Op(N,M1,xfx) Read(M1-1) Rest(N,M1) {M1>M}

     Op(N,M1,xfx) Read(M1-1) {M1>M}

     Op(N,M1,xfy) Read(M1) Rest(N,M1) {M1>M}

     Op(N,M1,xfy) Read(M1)

     Op(N,M1,yfx) Read(M1-1) Rest(N,M1)

     Op(N,M1,yfx) Read(M1-1)

     Op(N,M1,xf) Rest(N,M1) {M1>M}

     Op(N,M1,xf)

     Op(N,M1,yf) Rest(N,M1)

     Op(N,M1,yf)

Term ->

     Num

     Var

     List

     Ident

     Ident ( Args

     NoArgs

     ( Read(1200) )

Num ->

     un numero

Var ->

     una stringa che inizi con una lettera maiuscola o con un _

List ->

     [ ]

     [ RestList

RestList ->

     Read(999) , RestList

     Read(999) | Read(999) ]

     Read(999) ]

Ident ->

     tutte le stringhe che non sono variabili o numeri

Args ->

     Read(999) , Args

     Read(999) )

NoArgs ->

     !

     not

     nl

Op(N,M,T) ->

     operatore di tipo T e priorità M, con T Î {fx, fy, xfx, xfy, yfx, xf, yf} e con M<N

 

    Osservazioni.

•     La grammatica è di tipo 1 a causa per esempio dell'operatore ',' che può essere derivata da sostituzioni aventi significati diversi dipendenti dal contesto: la virgola può essere sia separatore di argomenti che l'operatore and. Stesso discorso per altri separatori come il punto e la chiusa parentesi. Inoltre ogni operatore può anche essere letto come operando in dipendenza dal contesto. Per come l'abbiamo definita noi, in maniera parametrica, sembrerebbe di tipo 0, ma è riconducibile ad una grammatica di tipo 1 eslicitando tutti i 1200 casi relativi ai 1200 livelli di priorità.
•    La grammatica non è LL(1) per la presenza di operatori infissi ad associatività arbitraria: leggendo un elemento non è possibile sapere se è un operando finché non si legge il secondo elemento. Se questo secondo elemento è sia operatore infisso che prefisso, ma con priorità diverse, si deve leggere anche un terzo elemento per sapere se il primo elemento era un operando o un operatore.

    La grammatica non è comunque LL(k) poiché ogni operando può essere in realtà costituito da una qualsiasi espressione e finché non si è letta tutta l'espressione può non essere classificabile il primo elemento. Bisogna notare che l'espressione può essere arbitrariamente lunga a causa della associatività degli operatori.