Analisi in Prolog senza taglio?

Question

Ho trovato questo bel frammento per l'analisi Lisp in Prolog (da qui):

ws --> [W], { code_type(W, space) }, ws.
ws --> [].

parse(String, Expr) :- phrase(expressions(Expr), String).

expressions([E|Es]) -->
    ws, expression(E), ws,
    !, % single solution: longest input match
    expressions(Es).
expressions([]) --> [].

% A number N is represented as n(N), a symbol S as s(S).

expression(s(A))         --> symbol(Cs), { atom_codes(A, Cs) }.
expression(n(N))         --> number(Cs), { number_codes(N, Cs) }.
expression(List)         --> "(", expressions(List), ")".
expression([s(quote),Q]) --> "'", expression(Q).

number([D|Ds]) --> digit(D), number(Ds).
number([D])    --> digit(D).

digit(D) --> [D], { code_type(D, digit) }.

symbol([A|As]) -->
    [A],
    { memberchk(A, "+/-*><=") ; code_type(A, alpha) },
    symbolr(As).

symbolr([A|As]) -->
    [A],
    { memberchk(A, "+/-*><=") ; code_type(A, alnum) },
    symbolr(As).
symbolr([]) --> [].

Tuttavia, le espressioni utilizzano un taglio. Suppongo che questo sia per l'efficienza. È possibile scrivere questo codice in modo che funzioni in modo efficiente senza taglio?

Sarebbe anche nelle risposte interessate che coinvolgono la scelta del taglio soft / impegnato di Mercurio.

Answer 1

Il taglio non viene utilizzato per l'efficienza, ma per impegnarsi nella prima soluzione (vedere il commento accanto al!/0: "Soluzione singola: corrispondenza di input più lunga"). Se commenta il!/0, ottieni ad esempio:

?- parse("abc", E).
E = [s(abc)] ;
E = [s(ab), s(c)] ;
E = [s(a), s(bc)] ;
E = [s(a), s(b), s(c)] ;
false.

È chiaro che solo la prima soluzione, costituita dalla sequenza più lunga di personaggi che formano un token, è desiderata in tali casi. Dato l'esempio sopra, quindi non sono d'accordo con "false": l'espressione // 1 è ambigua, perché il numero // 1 e il simbolo // 1 sono. In Mercurio, è possibile utilizzare la dichiarazione di determinismo CC_NONDET per impegnarsi in una soluzione, se presente.

Answer 2

Stai toccando un problema abbastanza profondo qui. Nel luogo del taglio hai aggiunto il commento "corrispondenza più lunga". Ma quello che hai effettivamente fatto è stato impegnarsi nella prima soluzione che produrrà la "corrispondenza di input più lunga" per il non terminale ws//0 ma non necessariamente per expression//1.

Molti linguaggi di programmazione definiscono i loro token in base alla corrispondenza di input più lunga. Questo spesso porta a effetti molto strani. Ad esempio, un numero può essere immediatamente seguito da una lettera in molti linguaggi di programmazione. Questo è il caso di Pascal, Haskell, Prolog e molte altre lingue. Per esempio if a>2then 1 else 2 è valido Haskell. Valido Prolog: X is 2mod 3.

Detto questo, potrebbe essere una buona idea definire un linguaggio di programmazione in modo tale che non dipenda affatto da tali caratteristiche.

Certo, vorresti quindi ottimizzare la grammatica. Ma posso solo raccomandare di iniziare con una definizione inequivocabile in primo luogo.

Per quanto riguarda l'efficienza (e la purezza):

eos([],[]).

nows --> call(eos).
nows, [W] --> [W], { code_type(W, nospace) }.

ws --> nows.
ws --> [W], {code_type(W, space)}, ws.

Answer 3

È possibile utilizzare un costrutto che ha già trovato il suo posto in Grammars (PEG) di analisi ma che è disponibile anche in DCGS. Vale a dire la negazione di un obiettivo DCG. In PEGS il marchio esclamativo (!) Con un argomento viene usato per la negazione, cioè! e. In DCG la negazione di un obiettivo DCG è espressa dall'operatore (+), che è già utilizzato per la normale negazione come fallimento nelle normali clausole e domande.

Quindi spiegiamo prima come (+) funziona in DCGS. Se hai una regola di produzione del modulo:

 A --> B, \+C, D.

Quindi questo viene tradotto in:

 A(I,O) :- B(I,X), \+ C(X,_), D(X,O).

Ciò significa che viene fatto un tentativo di analizzare l'obiettivo C DCG, ma senza consumare effettivamente l'elenco di input. Ora questo può essere usato per sostituire il taglio, se lo si desidera, e dà un po 'più di sensazione dichiarativa. Per spiegare l'idea, supponiamo che con una grammatica senza WS // 0. Quindi il set di espressioni della clausola originale // 1 sarebbe:

expressions([E|Es]) --> expression(E), !, expressions(Es).
expressions([]) --> [].

Con la negazione possiamo trasformarlo nella seguente forma senza taglio:

expressions([E|Es]) --> expression(E), expressions(Es).
expressions([]) --> \+ expression(_).

Sfortunatamente la variante di cui sopra è abbastanza non efficiente, poiché un tentativo di analizzare un'espressione viene fatto due volte. Una volta nella prima regola, e poi di nuovo nella seconda regola per la negazione. Ma potresti fare quanto segue e verificare solo la negazione dell'inizio di un'espressione:

expressions([E|Es]) --> expression(E), expressions(Es).
expressions([]) --> \+ symbol(_), \+ number(_), \+ "(", \+ "'".

Se provi la negazione, vedrai che ottieni un parser relativamente rigoroso. Questo è importante se si tenta di analizzare il massimo prefisso di input e se si desidera rilevare alcuni errori. Prova questo:

?- phrase(expressions(X),"'",Y).

Dovresti ottenere un fallimento nella versione di negazione che controlla il primo simbolo dell'espressione. Nel taglio e nella versione gratuita avrai successo con l'elenco vuoto di conseguenza.

Ma potresti anche affrontare un altro modo di errori, ho fatto solo l'esempio di errore per evidenziare un po 'di come funziona la versione di negazione.

In altre impostazioni, ad esempio cyk parser, si può rendere la negazione abbastanza efficiente, può utilizzare le informazioni che sono già inserite nel grafico.

Distinti saluti