parsing - Analizando en Prolog sin corte?

lisp dcg

Question

Encontré este buen fragmento de código para analizar lisp en Prolog (desde here ):

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. Estoy asumiendo que esto es por eficiencia. ¿Es posible escribir este código para que funcione eficientemente sin cortes?

También estaría en las respuestas de interés que involucren la opción de corte suave / compromiso de Mercury.

Answer 1

El corte no se usa para la eficiencia, sino para comprometerse con la primera solución (vea el comentario al lado de! / 0: "solución única: coincidencia de entrada más larga"). Si comentas 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, por lo tanto no estoy de acuerdo con "falso": la expresión // 1 es ambigua, porque el número // 1 y symbolr // 1 son. En Mercury, podría usar la declaración de determinismo cc_nondet para comprometerse con una solución, si la hubiera.

Answer 2

Estás tocando un problema bastante profundo aquí. En el lugar del corte, ha agregado el comentario "coincidencia 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 ws//0 no terminal, pero no necesariamente para la expression//1 .

Muchos lenguajes de programación definen sus tokens según 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 letra en muchos lenguajes de programación. Ese es el caso de Pascal, Haskell, Prolog y muchos otros idiomas. Por ejemplo, if a>2then 1 else 2 es Haskell válido. Prólogo válido: X is 2mod 3.

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

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

En cuanto a la eficiencia (y 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 un constructo que ya haya encontrado su lugar en las gramáticas de expresión de análisis (PEG), pero que también está disponible en los DCG. Es decir, la negación de un gol de DCG. En los PEG, el signo 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 se expresa mediante el operador (/ +), que ya se utiliza para la negación ordinaria como fallo en las cláusulas y consultas de Prolog ordinarias.

Entonces vamos a explicar primero cómo (/ +) funciona en DCGs. Si tienes 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 de C DCG, pero sin consumir realmente la lista de entrada. Ahora, esto se puede usar para reemplazar el corte, si se desea, y da un poco más de sentimiento declarativo. Para explicar la idea, supongamos que con una gramática sin ws // 0. Así que el conjunto de cláusulas original de expresiones // 1 sería:

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

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

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 otra vez en la segunda regla para la negación. Pero podría hacer lo siguiente y solo verificar la negación del principio de una expresión:

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

Si intenta la 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).

Debería obtener un error 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 libre de corte obtendrás éxito con la lista vacía como resultado.

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

En otras configuraciones, por ejemplo el analizador CYK, uno puede hacer que la negación sea bastante eficiente, puede usar la información que ya está colocada en el gráfico.

Atentamente