¿cuál es la diferencia entre la lex y yacc

Question

He trabajado con lex para ejecutar un código cada vez que se encontró una expresión regular, Puede Yacc hacer algo más que eso? Si es así, ¿entonces qué?

Answer 1

Lex es una herramienta para construir analizadores léxicos, que puede hacer algunas cosas léxica bastante estúpida (como encontrar palabras clave). Yacc es un generador de analizadores, que puede crear analizadores sintácticos para lenguajes de computadora reales. Su análisis se basa normalmente en la salida de lex (que es una secuencia de tokens) y de esto puede crear su árbol de análisis del lenguaje de programación, algo que es más que Lex.

Tradicionalmente, los constructores del compilador distinguir entre el análisis léxico y sintáctico - que son dos pasos importantes en un compilador (nuevos criterios que siguen por ejemplo, creación de código, optimización.).

Answer 2

Sí, YACC es un programa de análisis, Lex es un analizador léxico. Por lo general, se utilizan juntos: usted Lex la entrada de cadena, y YACC la entrada tokenizada proporcionada por Lex.

Ahora, una expresión regular solo puede representar idiomas regulares. Una de las limitaciones de un lenguaje regular es la falta de "memoria". No puede definir las reglas de aceptación más adelante en la cadena en función de lo que ha sucedido antes.

Esto se ve claramente en el caso de paréntesis. Un idioma normal no puede hacer coincidir los paréntesis anidados con el nivel correcto. O cualquier otra estructura similar. Las gramáticas de (la mayoría) de los lenguajes de computadora pueden y deben y, debido a eso, no se pueden analizar con un Lexer o una expresión regular. Ahí es donde entra en juego YACC.

Uno puede revertir la pregunta así. Si YACC puede hacer más, ¿por qué no usarlo para el análisis léxico? Bueno, sucede que puede verificar la validez de una expresión regular de manera muy eficiente, que no es el caso de las gramáticas generales, no al mismo nivel. Aún así, YACC puede hacer un análisis léxico básico, si las reglas léxicas del lenguaje son lo suficientemente simples.

Answer 3

lex es un lexical analyzer. Divide texto en tokens. Su poder es más o menos equivalente a la coincidencia de expresiones regulares. yacc es un parser generator. Toma una secuencia de tokens (por ejemplo, de lex) y los interpreta como series de enunciados. Su poder es más o menos equivalente a las gramáticas libres de contexto.

Una aplicación típica de lex y yacc es para implementar lenguajes de programación. lex tokenizes la entrada, dividiéndola en palabras clave, constantes, puntuación, etc. yacc implementa el lenguaje de la computadora real; reconocer una instrucción for, por ejemplo, o una definición de función.

En un sentido práctico, a menudo se utilizan para procesar la lex texto de entrada en trozos. Luego usas yacc para unir esos fragmentos y procesarlos en un significado más amplio.

Answer 4

lex es para entrada de tokenización. Es decir, separando su entrada en los objetos de nivel más bajo que define su gramática. Por ejemplo, usa lex para identificar palabras clave, identificadores, cadenas, comentarios, espacios en blanco, etc.

yacc es para analizar su gramática . Una gramática es una descripción de su idioma, típicamente definida en EBNF o alguna otra gramática libre de contexto. Una vez que describa su gramática para yacc, puede usarla para ejecutar las acciones de su herramienta cuando se reconocen elementos del idioma. Esto podría ser, por ejemplo, construir árboles de sintaxis para resolver expresiones, definir objetos de alcance, registrar definiciones de variables, etc.

Son productos complementarios.

Answer 5

lex y yacc se usan normalmente juntos. Así es como se suele construir una aplicación que utiliza tanto:

el flujo de entrada (caracteres) -> Lex (fichas) -> Yacc (sintaxis abstracta Árbol) -> Su applcation

De manera más general, lo Lex lo hará es leer un archivo fuente, desde el principio, e intentar hacer coincidir varias expresiones regulares (lex tiene su propia sintaxis especial para esto, que es un poco diferente de expresiones regulares perl o sed), y luego invocará otro programa con cada token que reconoce. Los tokens pueden ser simplemente un valor enumerado simple, como para una palabra clave u operador, o pueden tener algunos metadatos adjuntos, como un valor literal.

Lex suele utilizarse (aunque no necesariamente) para invocar a Yacc. Yacc utiliza un algoritmo de análisis LALR, que en términos generales funciona presionando cada ficha en una pila. Si la pila tiene una secuencia de tokens que reconoce, mostrará todos los tokens, realizará una acción y empujará otra ficha en la pila.

El vocabulario adecuado para lo que funciona en Yacc es en realidad terminales y no terminales. Una terminal es una ficha que obtuvo del programa de invocación (generalmente Lex), y una no terminal es el resultado de emparejar una secuencia en su pila.

Por lo general, las acciones tomadas por cada regla Yacc son para evaluar el resultado de un cálculo que corresponde a la regla o para producir una representación intermedia, como un árbol de sintaxis, para que otra capa de aplicación la procese.

Yacc, como Lex, se puede utilizar por separado del otro. Por ejemplo, puede usar Yacc pasándole caracteres individuales del texto fuente, y usar las reglas Yacc para reconocer cada tipo de token. Sin embargo, Yacc no está diseñado para ser muy fácil de usar de esa manera, por lo que el lexer resultante será mucho más complejo que un lexer equivalente en Lex. Un uso más típico sería hacer un lexer codificado a mano por razones de rendimiento o porque necesita un lexer más inteligente. Un ejemplo común del segundo caso es el utilizado en los lenguajes tipo C que deben conocer los usos previos de los identificadores para saber si se usan para describir tipos o variables.