btyacc - Online en la nube

PROGRAMA:

NOMBRE

btyacc - un LALR(1) generador de analizador sintáctico con soporte para retroceso

SINOPSIS

btyacc [-B prefijo] [-d] [-dNOMBRE ...] [-E] [-l] [-r] [-S x.ske] [-televisor]
nombrearchivo.y

Descripción

btyacc es una versión modificada de byacc (Berkeley YACC), que a su vez es de dominio público
versión del generador analizador original de AT&T YACC.

btyacc lee la especificación gramatical en el archivo nombrearchivo.y y genera un LR(1)
analizador para ello. El analizador consta de un conjunto de LALR(1) tablas de análisis y una rutina de controlador
escrito en el lenguaje de programación C. btyacc normalmente escribe las tablas de análisis y el
rutina del controlador al archivo prefijo.tab.c, donde el prefijo por defecto es 'y'.

Para obtener una descripción detallada del formato de una especificación gramatical y una excelente
tutorial sobre cómo usar herramientas similares a YACC, consulte el manual de información para GNU bisonte. btyacc
Las extensiones específicas se explican a continuación.

Nota: El esqueleto del analizador proporcionado por el autor ascendente de btyacc solo se compila como C ++. Usar
el esqueleto /usr/doc/btyacc/examples/btyacc-c.ske para generar un analizador que compile tanto
como C y C ++. (Desafortunadamente, este esqueleto alternativo actualmente no marca malloc ()
valores de retorno.)

De Seguros

-b prefijo Cambie el prefijo antepuesto a los nombres de los archivos de salida a la cadena indicada por
prefijo. El prefijo predeterminado es el carácter 'y'.

-d Crea un archivo de encabezado llamado prefijo.tab.h para cada año fiscal junto con la prefijo.tab.c,
que contiene las definiciones de los símbolos y una declaración para YYSTYPE y yylval.

-DNOMBRE Definir la variable del preprocesador btyacc NOMBRE, para usar con % ifdef NOMBRE
directivas en el archivo de gramática.

-E Imprime la gramática preprocesada en salida estándar.

-l No insertar #línea directivas en el código del analizador generado.

-r Escribe el código del analizador y las tablas asociadas en diferentes archivos. Mientras que el
las tablas se pueden encontrar en prefijo.tab.c como antes, el código ahora se escribe
a prefijo.código.c.

-S x.ske Seleccione un esqueleto de analizador diferente. El esqueleto predeterminado está cableado en el
programa, pero se puede encontrar una copia en el archivo btyaccpa.ske.

-t Hace que el código de depuración se compile en el analizador generado.

-v Escribe una descripción legible por humanos del analizador generado para y.salida. Lo
incluye estados del analizador, acciones para un token de anticipación e información sobre cualquier
conflictos.

BTYACC extensiones

Retroceso SOPORTE
Siempre que un analizador generado por btyacc se encuentre con un error shift-reduce o reduce-reduce en el
tabla de análisis, recuerda el punto de análisis actual (estado de la pila y del flujo de entrada), y va
en modo de análisis sintáctico. Luego continúa analizando, ignorando la mayoría de las acciones de reglas. Si corre
en un error (ya sea a través de la tabla de análisis o mediante una acción que llame YERROR), eso
retrocede hasta el punto de conflicto más reciente y prueba una alternativa diferente. Si se
encuentra una ruta exitosa (llega al final de la entrada o una acción llama YYVÁLIDO), eso
retrocede hasta el punto en el que entró por primera vez en el modo de análisis de prueba y continúa con un
parse (ejecutando todas las acciones), siguiendo la ruta de la prueba exitosa.

Las acciones en btyacc vienen en dos sabores: {} acciones, que solo se ejecutan cuando no están en
modo de prueba, y [] acciones, que se ejecutan independientemente del modo.

Ejemplo: en las gramáticas YACC para C, un truco estándar conocido como "truco de retroalimentación de lexer" es
utilizado para encontrar nombres typedef. El lexer usa información semántica para decidir si alguna
identifier es un nombre typedef o no y devuelve un token especial. Con btyacc, no
ya es necesario hacer esto; el lexer siempre debería devolver un identificador. El btyacc
la gramática entonces necesita una regla de la forma:

escribe un nombre: ID [ if (! IsTypeName (LookupId ($ 1))) YERROR; ]

Sin embargo, tenga en cuenta que agregar reglas de retroceso ralentiza el analizador. En la práctica, usted
Debería intentar restringir el número de conflictos en la gramática a lo que es absolutamente
necesario. Considere usar el "truco de retroalimentación de Lexer" si es una solución limpia, y
reserva el retroceso para algunos casos especiales.

btyacc ejecuta sus pruebas con la regla "intente cambiar primero, luego intente reducir en el orden
que las reglas en conflicto aparecen en el archivo de entrada ". Esto significa que puede implementar
reglas de desambiguación semántica como, por ejemplo: (1) Si parece una declaración, lo es,
de lo contrario (2) Si parece una expresión, lo es, de lo contrario (3) es un error de sintaxis
[Ellis & Stroustrup, Manual de referencia de C ++ anotado, p93]. Para lograrlo, ponga todos los
reglas para declaraciones antes que las reglas para expresiones en el archivo de gramática.

El retroceso solo se activa cuando el análisis realiza un cambio / reducir o reducir / reducir
conflicto en la mesa. Si no tiene conflictos gramaticales, no hay ningún costo adicional,
que no sea un código adicional que nunca se invocará.

Actualmente, el analizador generado realiza no poda de rutas de análisis alternativas. Para evitar
una explosión exponencial de posibles caminos (y tiempo de análisis), necesita decir manualmente
el analizador cuando puede deshacerse de las rutas guardadas utilizando el YYVÁLIDO declaración. En
práctica, resulta bastante fácil de hacer. Por ejemplo, un analizador de C ++ puede simplemente
que no contengo [YYVÁLIDO;] después de cada declaración completa y regla de declaración, lo que resulta en la
el estado de retroceso se poda después de ver un ';' o '}' - nunca habrá un
situación en la que es útil retroceder más allá de cualquiera de estos.

Mejora de ficha posición manipulación
Los compiladores a menudo necesitan construir AST (árboles de sintaxis abstracta) de modo que cada nodo de un árbol
puede relacionarse con la fuente del programa analizado del que proviene. los YPOSN mecanismo apoyado
by btyacc le ayuda a automatizar el cálculo de la posición del texto y a asignar la
posiciones de texto calculadas a los nodos AST.

En los YACC estándar, cada token y cada no terminal tiene un YYSTYPE valor semántico
adjunto a. Con btyacc, cada token y cada no terminal también tiene un YPOSN texto
posición adjunta a él. YPOSN es un tipo definido por el usuario.

btyacc mantiene una pila de valores de posición de texto de la misma manera que mantiene una pila
de valores semánticos. Para hacer uso de la función de posición del texto, debe #definir los
siguientes:

YYPOSN Símbolo de preprocesador para el tipo C / C ++ de la posición del texto adjunta a cada
token y no terminal.

yyposn Variable global de tipo YPOSN. El lexer debe asignar la posición del texto del
token devuelto a yyposn, al igual que asigna el valor semántico de la
token devuelto a yylval.

YYREDUCEPOSNFFUN
Símbolo de preprocesador para una función que se llama inmediatamente después de la
Se ha realizado la reducción de reglas gramaticales para reducir las posiciones del texto ubicadas en
la pila.

Normalmente, esta función extrae posiciones de texto de la regla del lado derecho
componentes y los asigna a la estructura / árbol $$ devuelto o, si no
$$ se devuelve el valor, los coloca en la posición de texto ret donde estará
recogido por otras reglas más tarde. Su prototipo es:

vacío ReducirPosn(
YYPOSN y retirado,
YYPOSN * term_posns,
YYSTYPE * valores_terminos,
int término_no,
int stk_pos,
int ychar,
YYPOSN y yyposn,
Tipo de usuario trabajo);

ret Referencia a la posición del texto devuelta por la regla. Debes sobrescribir
esto con la posición de texto calculada que la regla produce, análoga a
el valor semántico $$.

term_posns
Matriz de los componentes de la regla del lado derecho ' YPOSN posiciones de texto,
análogo a $ 1, $ 2, ..., $ N para los valores semánticos.

term_vals Matriz de los componentes de la regla del lado derecho ' YYSTYPE valores. Estos son
los $ 1, ..., $ N mismos.

term_no Número de componentes en el lado derecho de la regla reducida, es decir, el
tamaño de las matrices term_posns y term_vals. También igual a N en $ 1, ...,
$ N.

stk_pos YYSTYPE/YPOSN posición de la pila antes de la reducción.

yychar Token de anticipación que sigue inmediatamente al lado derecho reducido
componentes.

yyposn YPOSN de la ficha que sigue inmediatamente al lado derecho reducido
componentes.

extra Argumento extra definido por el usuario pasado a ReducePosn.

YYREDUCEPOSNFUNCARG
Se pasa un argumento adicional a la función ReducePosn. Este argumento puede ser cualquier
variable definida en btyaccpa.ske.

Token desasignación during error recuperación
Para la mayoría de los generadores de analizadores sintácticos similares a YACC, la acción del analizador generado al encontrar
un error de análisis es desechar los valores semánticos y los tokens de entrada hasta que una regla que contiene
el especial no terminal error se puede combinar. El descarte de tokens se realiza simplemente mediante
sobrescribir variables y entradas de matriz de tipo YYSTYPE con nuevos valores.

Desafortunadamente, este enfoque conduce a una pérdida de memoria si YYSTYPE es un tipo de puntero. btyacc
le permite proporcionar funciones para limpiar los valores de posición semántica y de texto, por
#definiring los siguientes símbolos en el preámbulo de su archivo de gramática:

YDELETEVAL
Símbolo de preprocesador para que una función llame antes del valor semántico de un token
o no terminal se descarta.

YYDELETEPOSN
Símbolo de preprocesador para que una función llame antes de la posición del texto de un token
o no terminal se descarta.

Ambas funciones se llaman con dos argumentos. El primer argumento de tipo YYSTYPE or YPOSN
es el valor que se descartará. El segundo argumento es de tipo int y es uno de
tres valores:

0 descartando el token de entrada

1 estado de descarte en la pila

2 limpieza de pila al abortar

Hay una sintaxis error la presentación de informes
Si #definir la variable del preprocesador YYERROR_DETALLADO en su archivo de gramática, debe
también defina la siguiente función de procesamiento de errores:

vacío yyerror_detallado(
char * texto,
int error,
YYSTYPE y
valor_errt,
YYPOSN y error_posn);

mensaje de error de texto

código errt del token que causó el error

valor_errt
valor del token que causó el error

errt_posn posición de texto del token que causó el error

Preprocesador directivas
btyacc admite la definición de símbolos y actuar sobre ellos con directivas condicionales dentro
archivos de gramática, no muy diferente al preprocesador de C.

%definir NOMBRE
Definir el símbolo del preprocesador NOMBRE. Equivalente al conmutador de línea de comando
-DNOMBRE.

% ifdef NOMBRE
Si la variable de preprocesador NOMBRE está definido, procese el texto de este % ifdef a
el cierre %terminara si, de lo contrario, omítalo.

% endif Directiva de cierre para % ifdef. % ifdefs no se pueden anidar.

%incluir NOMBRE DEL ARCHIVO
Procesar el contenido del archivo denominado NOMBRE DEL ARCHIVO. Solo un nivel de anidación de %incluir
esta permitido.

% ident CADENA
Inserte un `#identificación CADENA'directiva en el archivo de salida. CADENA debe ser un
constante de cadena encerrada entre "".

Heredado atributos
Los atributos heredados no están documentados. (Ver el README y el código fuente de btyacc para un
poca información.) Si averigua cómo funcionan, contácteme en[email protected]>!

Errores

La complejidad del análisis sintáctico en el peor de los casos es exponencial para cualquier gramática que permita
retroceso para tener lugar. En otras palabras, un analizador generado por btyacc constituye un
error de denegación de servicio si se utiliza en aplicaciones en las que un atacante puede suministrar
datos especialmente diseñados como entrada para el analizador. (Para todos los datos de entrada "normales", el
la complejidad potencialmente exponencial no suele ser un problema).

bisontes %suponer La directiva no es compatible.

No hay %demás y % ifndef. % ifdefs y %incluirs no se pueden anidar.

Escritores

Robert Corbett[email protected]> /[email protected]> fue uno de los
autores originales de Berkeley byacc. Chris Dodd[email protected]> tenía el brillante
idea de agregar capacidades de retroceso, y es responsable del retroceso inicial
cambios. Vadim Maslov[email protected]> mejoró aún más el código.

Esta documentación fue escrita por Richard Atterer[email protected]> para Debian
Distribución GNU / Linux, pero se dona al dominio público y, por lo tanto, se puede usar libremente
para cualquier propósito.

archivos

/usr/doc/btyacc/examples/btyaccpa.ske

/usr/doc/btyacc/examples/btyacc-c.ske

/ usr / doc / btyacc / README

See also

bisonte(1) (o 'info bisonte'), poracc(1), yacc(1), hormiga(1)

btyacc(1)

Utilice btyacc en línea utilizando los servicios de onworks.net