Implementar "*?" patrón de expresión regular (perezoso “*”) en los analizadores GLR combinatorias

Question

He implementado analizadores GLR combinatorias. Entre ellos se encuentran:

• analizador char(·) que consume especifican carácter o rango de caracteres.
• combinator many(·) que repite especifica analizador de cero a infinitas veces.

Ejemplo:. "char('a').many()" coincidirá con una cadena con cualquier número de "a"-s

Pero combinador many(·) es codicioso, así que, por ejemplo, char('{') >> char('{') >> char('a'..'z').many() >> char('}') >> char('}') (donde ">>" es el encadenamiento secuencial de analizadores) consumirá con éxito toda la cadena "{{foo}}some{{bar}}".

Quiero poner en práctica la versión lenta de many(·) que, al ser utilizado en el ejemplo anterior, sólo se consumirá "{{foo}}". ¿Cómo puedo hacer eso?

Editar

Puede ser confuso ya que todos. En mi programa de un programa de análisis es una función (o "funtor" en términos de C ++) que acepta un "paso" y el bosque retornos de "pasos". Un "paso" puede ser de tipo OK (Esto significa que parser ha consumido parte de entrada con éxito) y el tipo FAIL (que significa que el analizador ha encontrado error). Hay más tipos de pasos, pero que son auxiliares.

Parser = f(Step) -> Collection of TreeNodes of Steps.

Así que cuando la entrada de análisis, I:

• sencilla Componer funciones predefinidas analizador para obtener función del analizador complejo que representa la gramática necesaria.

• Formulario de paso inicial de la entrada.

• Dar el paso inicial para la función del analizador complejo.

• TreeNodes de filtro con pasos, dejando los sólo aceptable (o con un mínimo FALLO-S si hubo errores en la entrada).

• Recopilar información de los pasos que habían quedado.

Answer 1

Tenga en cuenta la <.*?> expresión regular y la <a>bc<d>ef entrada. Esto debe encontrar <a>, y no hay otros partidos, ¿verdad?

Ahora considere la <.*?>e expresión regular con la misma entrada. Esto debe encontrar <a>bc<d>e, ¿verdad?

Esto plantea un dilema. Por el bien del usuario, queremos que el comportamiento de la >> combinador a ser entendida en términos de sus dos operandos. Sin embargo, no hay manera de producir el comportamiento del segundo programa de análisis en términos de lo que los primeros hallazgos uno.

Una respuesta es para cada analizador para producir un secuencia de todas las analiza, ordenados por preferencia, más que el conjunto no ordenado de todos los programas de análisis. juego Greedy volvería partidos ordenadas largo al más corto; no expansivo, corto al más largo.

Answer 2

Me han puesto en marcha y se han utilizando analizadores GLR durante 15 años como extremos delanteros de idiomas para un sistema de transformación de programas.

No sé lo que es un "analizador GLR combinatoria" es, y estoy familiarizado con su notación, así que estoy muy seguro de cómo interpretarlo. Asumo que esto es una especie de notación de función al curry? Estoy imaginando sus reglas de combinadores son equivalentes a definining una gramática en términos de caracteres terminales, en los que corresponde a las reglas gramaticales "char ( 'a') muchos.":

 char = "a" ;
 char = char "a" ;

analizadores GLR, de hecho, producen todos los análisis sintácticos posibles. La idea clave de GLR análisis sintáctico es su procesamiento pseudo-paralelo de todos los análisis sintácticos posibles. Si sus "combinadores" se proponen múltiples análisis sintácticos (es decir, que producen reglas gramaticales especie de equivalente a la anterior), y que de hecho tenerlos conectados a un analizador de GLR, todos ellos son juzgados, y sólo las secuencias de producciones que azulejos el texto va a sobrevivir (es decir, todos parsess válida, por ejemplo, análisis sintácticos ambiguas) sobrevivirán.

Si de hecho ha puesto en marcha un programa de análisis de GLR, esta colección de todos los análisis sintácticos posibles debería haber sido extremadamente claro. El hecho de que no es lo que sugiere que haya implementado no es un analizador GLR.

La recuperación de errores con un analizador GLR es posible, al igual que con cualquier otra tecnología de análisis. Lo que hacemos es mantener el conjunto de análisis sintácticos en directo antes del punto del error; cuando se encuentra un error, se intenta (en pseudo-paralelo, el GLR analizar la maquinaria hace fácil si se perdía correctamente) todo lo siguiente: a) la supresión de la ofender modo, b) la inserción de todas las fichas que esencialmente son SEGUIMIENTO (x) donde x es de análisis en vivo. En esencia, eliminar el token, o insertar una espera por un análisis sintáctico en vivo. Pasamos luego el analizador GLR suelta de nuevo. Sólo los análisis sintácticos válidos (por ejemplo, reparaciones) sobrevivirán. Si el token actual no se puede procesar, el analizador procesamiento de la corriente con el token suprimido sobrevive. En el peor de los casos, los extremos de recuperación de errores GLR analizador hasta tirar todas las fichas a EOF. Un grave inconveniente de esto es el tiempo de funcionamiento del analizador GLR crece bastante radicalmente durante el análisis de los errores; si hay muchos en un solo lugar, el tiempo de recuperación de errores puede ir a través del techo.

Answer 3

no un analizador GLR producir todos los posibles análisis sintácticos de la entrada? A continuación, la resolución de la ambigüedad es una cuestión de escoger el análisis sintáctico lo prefiere. Para hacer eso, supongo que los elementos de la necesidad bosque de análisis a ser etiquetados de acuerdo a qué tipo de combinador ellos, ansiosos o perezoso producido. (No se puede resolver la ambigüedad de forma incremental antes de haber visto toda la entrada, en general.)

(Esta respuesta basada en mi memoria y tenue posible malentendido vaga de GLR análisis. Esperemos que alguien experto va a conseguir.)

Answer 4

funcionalidad no expansivo es nada más que un mecanismo de desambiguación. Si realmente tiene un analizador generalizada (que no requiere desambiguación para producir sus resultados), entonces "no voraz" no tiene sentido; los mismos resultados serán devueltos si o no un operador es "no expansivo".

comportamiento de desambiguación no expansivo podría aplicarse a todo el conjunto de resultados proporcionados por un programa de análisis generalizado. Trabajando de izquierda a derecha, filtro de los subgrupos ambiguas que corresponden a un operador no codicioso de usar la más corta que todavía dio lugar a un análisis sintáctico con éxito de la entrada restante.