Ml-Yacc es un generador del programa de análisis para el ml estándar modelado
después del generador del programa de análisis de Yacc. Genera los programas de
análisis para las idiomas de LALR, como Yacc, y tiene un sintaxis similar. Los
programas de análisis generados utilizan un diverso algoritmo para recuperarse
de errores del sintaxis que los programas de análisis generados por Yacc. El
algoritmo es una puesta en práctica parcial de un algoritmo descrito adentro. Un
programa de análisis intenta recuperarse de un error del sintaxis haciendo una
sola inserción, canceladura, o substitución simbólica cerca del punto en el
flujo de entradas en el cual el error fue detectado. Los programas de análisis
retrasan la evaluación de acciones semánticas hasta que analiza se terminan con
éxito. Esto permite para que los programas de análisis se recuperen de los
errores del sintaxis que ocurren antes del punto de la detección de error, pero
evita que los programas de análisis afecten lexers de cualquier manera
significativa. Los programas de análisis pueden insertar símbolo con valores y
símbolo substituto con los valores para el otro símbolo. Todos los símbolos
llevan los valores izquierdos y derechos de la posición que están disponibles
para las acciones semánticas y se utilizan en mensajes de error sintácticos.
Ml-Yacc utiliza gramáticas independientes del contexto para especificar el
sintaxis de las idiomas que se analizarán. Repasamos brevemente una cierta
terminología aquí. Una gramática independiente del contexto es definida por un
sistema de los terminales T , un sistema de NT de los nonterminals
, un sistema de las producciones P , y un comienzo S no terminal .
Los terminales se refieren alternativamente como símbolo. El terminal y los
sistemas no terminales se asumen para ser desunen. El sistema de símbolos es la
unión de los sistemas no terminales y del terminal. Utilizamos letras griegas
minúsculas para denotar una cadena de símbolos. Utilizamos letras romanas
mayúsculas cerca del principio del alfabeto para denotar nonterminals. Cada
producción da una derivación de una cadena de símbolos de un no terminal, que
escribiremos como ® a de A . Definimos una
relación entre las cadenas de los símbolos a y b , escritas a |- b y leído como a deriva b , si y solamente si existe a = d A g , b = d f g y allí un
cierto ® f de la producción A . Escribimos el
encierro transitivo de esta relación como|- * .
Decimos que una cadena de los terminales a es una
oración válida de la lengua, es decir. es derivable, si el símbolo de
inicio S |- * a . La secuencia de derivaciones se visualiza a menudo como árbol del
análisis.
Ml-Yacc utiliza un esquema de la gramática de la cualidad con cualidades
sintetizadas. Cada símbolo en la gramática puede tener un valor (es decir
cualidad) asociado a él. Cada producción tiene una acción semántica asociada a
ella. Una producción con una acción semántica se llama una regla. Los programas
de análisis realizan evaluaciones bottom-up, de izquierda a derecha de analizan
árboles usando acciones semánticas para computar valores como lo hacen tan. Dado
una producción el ® a de P = de A , la
acción semántica correspondiente se utiliza para computar un valor para A
de los valores de los símbolos en a . Si A no
tiene ningún valor, la acción semántica todavía se evalúa pero se no hace caso
el valor. Cada uno analiza vueltas que el valor se asoció al símbolo de inicio
S de la gramática. Un análisis vuelve un valor nullary si el símbolo de
inicio no lleva un valor.
El esquema sintetizado de la cualidad se puede adaptar fácilmente a las
cualidades heredadas. Una cualidad heredada es un valor que propaga de un no
terminal a los símbolos producidos por el no terminal según una cierta regla.
Puesto que las funciones son valores en el ml, las acciones semánticas para los
símbolos derivados pueden volver funciones que toma el valor heredado como
discusión.
Ml-Yacc utiliza la facilidad de los módulos del ml para especificar el
interfaz entre un programa de análisis que genere y un analizador léxico que se
deba proveer por usted. También utiliza la facilidad de los módulos del ml al
factor fuera de un sistema de los módulos que son comunes a cada programa de
análisis generado. Estos módulos comunes incluyen una estructura del análisis,
que contiene un programa de análisis error-correcting 1
, una estructura de la tabla de LR, y una
estructura de LR que defina la representación de terminales. Ml-Yacc produce un
functor para un programa de análisis particular dado parámetros por la
estructura de la tabla de LR y la representación de terminales. Este functor
contiene los valores específicos al programa de análisis, tal como la tabla de
LR para el programa de análisis
2 , las acciones semánticas para el
programa de análisis, y una estructura que contiene los terminales para el
programa de análisis. Ml-Yacc produce una firma para la estructura producida
aplicando este functor y otra firma para la estructura que contiene los
terminales para el programa de análisis. Usted debe proveer un functor para el
módulo lexing dio parámetros esta estructura.
El cuadro 1 es un diagrama de la dependencia de los módulos que resume esta
información. Un módulo en el jefe de una flecha es dependiente en el módulo en
la cola.
estructura del análisis ¾® valores para un programa de análisis particular valores para un programa de análisis particular ¾® analizador léxico estructura del análisis, ¾® programa de análisis particular valores para un programa de análisis particular, analizador léxico
Cuadro 1: Dependencias Del Módulo
El algoritmo de la recuperación de error puede recuperarse exactamente de
muchos solos errores simbólicos del sintaxis. Intenta hacer una sola corrección
simbólica en el símbolo en el flujo de entradas en el cual el error del sintaxis
fue detectado y cualquiera de los 15 símbolos
3 antes que símbolo. El algoritmo comprueba
correcciones antes del punto de la detección de error porque un error del
sintaxis no se detecta a menudo hasta vario símbolo más allá del símbolo que
causó el error.
4
El algoritmo trabaja intentando correcciones en cada uno de los 16 símbolos
hasta e incluyendo el símbolo en el cual el error fue detectado. En cada símbolo
en el flujo de entradas, intentará suprimir el símbolo, substituir el otro
símbolo para el símbolo, o insertar algún otro símbolo antes del símbolo.
El algoritmo utiliza un cheque del análisis para evaluar correcciones. Un cheque
del análisis es un cheque de cómo una corrección permite lejos que un programa
de análisis analice sin encontrar un error del sintaxis. Usted pasa un límite
superior en cuánto símbolo más allá del punto del error puede leer un programa
de análisis mientras que hace un cheque del análisis como discusión al programa
de análisis. Esto permite que usted controle la cantidad de lookahead que un
programa de análisis lee para diversas clases de sistemas. Para un sistema
interactivo, usted debe fijar el lookahead a cero. Si no, un programa de
análisis puede colgar para la entrada que espera en el caso de un error del
sintaxis. Si el lookahead es cero, no se corregirá ningunos errores del
sintaxis. Para un sistema de hornada, usted debe fijar el lookahead a 15.
El algoritmo selecciona el sistema de correcciones que permite que el análisis
proceda el más lejano y analice a través por lo menos del símbolo del error.
Entonces quita esas correcciones que implican las palabras claves que no
resuelven un mínimo más largo analizan el cheque. Si hay más de una corrección
posible después de esto, utiliza un esquema heurístico simple de la prioridad
para pedir las correcciones, y después elige arbitrariamente una de las
correcciones con la prioridad más alta. Usted tiene cierto control sobre el
esquema de la prioridad pudiendo nombrar un sistema de inserciones preferidas y
un sistema de substituciones preferidas. Las prioridades para las correcciones,
ordenadas de lo más arriba posible a la prioridad más baja, son inserciones
preferidas, substituciones preferidas, inserciones, canceladuras, y
substituciones.
El algoritmo de la recuperación de error está garantizado para terminar puesto
que selecciona siempre arreglos cuál analiza a través del símbolo del error.
El programa de análisis error-correcting de LR pone el algoritmo en ejecucio'n
guardando una coleta de sus apilados del estado antes de cambiar de puesto
símbolo y de usar una corriente perezosa para el lexer. Esto permite recomenzar
el análisis antes de un punto del error e intentar varias correcciones. El
programa de análisis error-correcting de LR no difiere acciones semánticas. En
lugar, Ml-Yacc crea las acciones semánticas que están libres de efectos
secundarios y terminan siempre. Ml-Yacc utiliza funciones higher-order para
diferir la evaluación de todas las acciones semánticas del usuario hasta que el
análisis se termina con éxito sin construir un explícito analiza el árbol. Usted
puede declarar si sus acciones semánticas están libres de los efectos
secundarios y terminar siempre, en los cuales el caso Ml-Yacc no necesita
diferir la evaluación de sus acciones semánticas.
Ml-Yacc utiliza el mismo esquema de la precedencia que está en conflicto Yacc
para resolver shift/reduce. Cada terminal se puede asignar una precedencia y un
associativity. Cada regla entonces se asigna la precedencia de su terminal de
derecha. Si ocurre un conflicto de shift/reduce, el conflicto se resuelve
silenciosamente si el terminal y la regla en el conflicto tienen precedences. Si
el terminal tiene la precedencia más alta, se elige la cambio. Si la regla tiene
la precedencia más alta, se elige la reducción. Si el terminal y la regla tienen
la misma precedencia, entonces el associativity del terminal se utiliza para
resolver el conflicto. Si el terminal se sale sociable, se elige la reducción.
Si el terminal es sociable derecho, se elige la cambio. Los terminales se pueden
declarar para ser nonassociative, también, en que caso se produce un mensaje de
error si el associativity es necesidad de resolver el conflicto del análisis.
Si un terminal o una regla en un conflicto de shift/reduce no tiene una
precedencia, entonces un mensaje de error se produce y se elige la cambio.
En conflictos de reduce/reduce, un mensaje de error se produce siempre y la
primera regla enumerada en la especificación se elige para la reducción.
El texto rodeado por los soportes denota el meta-notation. Si usted ve algo
como { nombre del programa de análisis }, usted debe substituir el nombre real
de su programa de análisis para el meta-notation. El texto en una fuente de la
máquina de escribir de la negrilla ( como esto
) denota el texto en una
especificación o código del ml.