Análisis en prólogo sin corte?

Question

Encontré este bonito fragmento para analizar el lisp en prólogo (de aquí):

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

Sin embargo, las expresiones usan un corte. Supongo que esto es para la eficiencia. ¿Es posible escribir este código para que funcione de manera eficiente sin corte?

También estaría en respuestas interesadas que involucren la elección de corte suave / comprometido de Mercury.

Answer 1

El corte no se usa para la eficiencia, sino para comprometerse con la primera solución (vea el comentario junto al!/0: "Solución única: coincidencia de entrada más larga"). Si comenta el!/0, obtienes por ejemplo:

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

Está claro que solo la primera solución, que consiste en la secuencia más larga de caracteres que forman un token, se desea en tales casos. Dado el ejemplo anterior, no estoy de acuerdo con "False": la expresión // 1 es ambigua, porque el número // 1 y el Symbolr // 1 son. En Mercurio, puede usar la declaración del determinismo cc_nondet para comprometerse con una solución, si la hay.

Answer 2

Estás tocando un problema bastante profundo aquí. En el lugar del corte, ha agregado el comentario "Match de entrada más larga". Pero lo que realmente hizo fue comprometerse con la primera solución que producirá la "coincidencia de entrada más larga" para el no terminal ws//0 pero no necesariamente para expression//1.

Muchos lenguajes de programación definen sus tokens en función de la coincidencia de entrada más larga. Esto a menudo conduce a efectos muy extraños. Por ejemplo, un número puede ser seguido inmediatamente por una carta en muchos lenguajes de programación. Ese es el caso de Pascal, Haskell, Prolog y muchos otros idiomas. P.ej if a>2then 1 else 2 es válido Haskell. Prólogo válido: X is 2mod 3.

Dado eso, podría ser una buena idea definir un lenguaje de programación de modo que no dependa de tales características.

Por supuesto, le gustaría optimizar la gramática. Pero solo puedo recomendar comenzar con una definición que sea inequívoca en primer lugar.

En cuanto a la eficiencia (y la pureza):

eos([],[]).

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

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

Answer 3

Podría usar una construcción que ya ha encontrado su lugar en el análisis de gramatrices de expresión (PEG) pero que también está disponible en DCGS. A saber, la negación de un objetivo de DCG. En las clavijas, la marca de exclamación (!) Con un argumento se usa para la negación, es decir! mi. En DCG, la negación de un objetivo de DCG es expresada por el operador (+), que ya se usa para la negación ordinaria como falla en las cláusulas y consultas de Prolog ordinarios.

Así que primero explicemos cómo (+) funciona en DCGS. Si tiene una regla de producción del formulario:

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

Entonces esto se traduce a:

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

Lo que significa que se intenta analizar el objetivo C DCG, pero sin consumir realmente la lista de insumos. Ahora, esto se puede usar para reemplazar el corte, si lo desea, y da un poco más de sensación declarativa. Para explicar la idea, supongamos que con tener una gramática sin WS // 0. Entonces, el conjunto de expresiones de la cláusula original // 1 sería:

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

Con la negación podemos convertir esto en la siguiente forma sin corte:

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

Desafortunadamente, la variante anterior es bastante poco eficiente, ya que un intento de analizar una expresión se realiza dos veces. Una vez en la primera regla, y luego nuevamente en la segunda regla para la negación. Pero podría hacer lo siguiente y solo verificar la negación del comienzo de una expresión:

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

Si intenta negación, verá que obtiene un analizador relativamente estricto. Esto es importante si intenta analizar el prefijo máximo de entrada y si desea detectar algunos errores. Trata eso:

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

Debe obtener una falla en la versión de negación que verifica el primer símbolo de la expresión. En el corte y en la versión gratuita, tendrá éxito con la lista vacía como resultado.

Pero también podría tratar de otra manera con errores, solo he hecho el ejemplo de error para resaltar un poco cómo funciona la versión de negación.

En otros entornos, por ejemplo, Cyk Parser, uno puede hacer que la negación sea bastante eficiente, puede usar la información que ya se coloca en el gráfico.

Saludos