Prolog sans Parsing coupe?

Question

J'ai trouvé ce bel extrait pour l'analyse syntaxique Lisp Prolog (de ):

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([]) --> [].

Cependant les expressions utilise une coupe. Je suppose que c'est l'efficacité. Est-il possible d'écrire ce code afin qu'il fonctionne efficacement sans coupure?

Seraient également dans les réponses qui impliquent des intéressés de Mercury soft-coupe / choix engagé.

Answer 1

La coupe ne sert pas à l'efficacité, mais de s'engager à la première solution (voir le commentaire suivant à la / 0: « seule solution: match d'entrée le plus long »). ! Si vous commentez le / 0, vous obtenez par exemple:

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

Il est clair que seule la première solution, constituée de la plus longue séquence de caractères qui forment un jeton, on souhaite dans de tels cas. Compte tenu de l'exemple ci-dessus, je suis en désaccord donc avec « faux »: l'expression // 1 est ambigu, car le nombre // 1 // et symbolr 1 sont. Dans Mercury, vous pouvez utiliser la cc_nondet déclaration de déterminisme à engager à une solution, le cas échéant.

Answer 2

Vous touchez un problème assez profond ici. Au lieu de la coupe que vous avez a ajouté le commentaire « match d'entrée le plus long ». Mais ce que vous avez fait était de commettre à la première solution qui produira le « match d'entrée le plus long » pour la ws//0 non terminal, mais pas nécessairement pour expression//1.

De nombreux langages de programmation définissent leurs jetons en fonction de la correspondance d'entrée plus longue. Cela conduit souvent à des effets très étranges. Par exemple, un certain nombre peut être immédiatement suivi d'une lettre dans de nombreux langages de programmation. C'est le cas pour Pascal, Haskell, Prolog et bien d'autres langues. Par exemple. if a>2then 1 else 2 est valide Haskell. Valable Prolog: X is 2mod 3.

Étant donné que, il pourrait être une bonne idée de définir un langage de programmation telle qu'elle ne dépend pas de ces caractéristiques du tout.

Bien sûr, alors vous souhaitez optimiser la grammaire. Mais je ne peux que recommander de commencer par une définition sans ambiguïté en premier lieu.

En ce qui concerne l'efficacité (et la pureté):

eos([],[]).

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

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

Answer 3

Vous pouvez utiliser une construction qui a déjà trouvé sa place dans Parsing Expression Grammaires (PEGs), mais qui est également disponible en DCG. À savoir la négation d'un objectif DCG. Dans le point d'PEGs exclamation (!) Avec un argument est utilisé pour la négation, à savoir! e. En DCG la négation d'un but DCG est exprimé par le (\ +) opérateur, qui est déjà utilisé pour la négation ordinaire comme un échec dans les clauses Prolog ordinaires et des requêtes.

permet donc d'expliquer d'abord comment (\ +) fonctionne en DCG. Si vous avez une règle de production de la forme:

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

Ensuite, cela se traduit à:

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

Ce qui signifie que l'on tente d'analyser l'objectif C DCG, mais sans consommer réellement la liste d'entrée. Maintenant, cela peut être utilisé pour remplacer la coupe, si on le souhaite, et il donne un peu plus déclarative sentiment. Pour expliquer l'idée laisse supposer que, avec une grammaire sans ws // 0. Ainsi, l'ensemble de la clause originale des expressions // 1 serait:

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

Avec la négation, nous pouvons transformer cela en forme de coupe moins suivant:

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

Malheureusement, la variante ci-dessus est tout à fait non efficace, car une tentative pour analyser une expression est faite deux fois. Une fois dans la première règle, puis à nouveau dans la deuxième règle de la négation. Mais vous pouvez faire ce qui suit et seulement vérifier la négation du début d'une expression:

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

Si vous essayez négation, vous verrez que vous obtenez un analyseur relativement stricte. Ceci est important si vous essayez d'analyser le préfixe maximum entrée et si vous voulez détecter des erreurs. Essayez que:

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

Vous devriez obtenir l'échec dans la version de négation qui vérifie le premier symbole de l'expression. Dans la coupe et la coupe version gratuite, vous obtiendrez le succès avec la liste vide en conséquence.

Mais vous pouvez aussi traiter d'une autre manière avec des erreurs, je n'ai fait l'exemple d'erreur pour mettre en évidence un peu comment fonctionne la version de négation.

Dans d'autres contextes, par exemple analyseur CYK, on ??peut faire la négation tout à fait efficace, il peut utiliser l'information qui est déjà placé dans le tableau.

Cordialement