Preguntas sobre algoritmos que deciden si una cadena dada pertenece a un lenguaje formal fijo.
La gente suele decir que los analizadores LR (k) son más potentes que los analizadores LL (k) . Estas declaraciones son vagas la mayor parte del tiempo; en particular, ¿deberíamos comparar las clases para una fija o la unión sobre todas las k ? Entonces, ¿cómo es realmente la situación? En...
EPAL, el lenguaje de incluso palíndromos, se define como el lenguaje generado por la siguiente gramática libre de contexto inequívoca: S→ a aS→aaS \rightarrow a a S→ b bS→bbS \rightarrow b b S→ a SunaS→aSaS \rightarrow a S a S→ b SsiS→bSbS \rightarrow b S b EPAL es la "ruina" de...
Quiero analizar idiomas específicos de dominio definidos por el usuario. Estos lenguajes suelen estar cerca de las notaciones matemáticas (no estoy analizando un lenguaje natural). Los usuarios definen su DSL en una notación BNF, así: expr ::= LiteralInteger | ( expr ) | expr + expr | expr *...
Aparentemente, los ataques ReDos explotan las características de algunas expresiones regulares (de otro modo útiles) ... esencialmente causando una explosión de posibles caminos a través del gráfico definido por la NFA. ¿Es posible evitar tales problemas escribiendo una expresión regular 'no...
Si tengo una gramática de tipo 3, se puede representar en un autómata pushdown (sin realizar ninguna operación en la pila) para poder representar expresiones regulares utilizando lenguajes libres de contexto. Pero, ¿puedo saber si una gramática de tipo 3 es , , , etc. sin construir tablas de...
Es posible analizar un documento con una sola pasada desde una máquina de estado. ¿Cuál es el beneficio de tener dos pases, es decir. ¿Tiene un lexer para convertir texto en tokens y un analizador para probar las reglas de producción en esos tokens? ¿Por qué no tener una sola pasada que aplique las...
Según el artículo de Wikipedia , la L en significa "exploración de izquierda a derecha", y la "R" significa "derivación más a la derecha". Sin embargo, en el artículo original de Knuth sobre las gramáticas L R ( k ) , define L R ( k ) (en la página 610) como un lenguaje que es "traducible de...
Trato de enseñarme el uso del bisonte. La página de manual bison (1) dice acerca de bison: Genere un analizador determinista LR o generalizado LR (GLR) empleando tablas LALR (1), IELR (1) o analizador canónico LR (1). ¿Qué es un analizador IELR? Todos los artículos relevantes que encontré en...
Estaba pensando en gramáticas para lenguajes sensibles a la indendación y parece que las gramáticas CF funcionarían si se combinaran con parámetros. Como ejemplo, considere este fragmento para la gramática simplificada de Python en formato ANTLR: // on top-level the statements have empty...
A menudo trabajo con lexer / parsers , a diferencia de un combinador de analizadores y veo personas que nunca tomaron una clase de análisis, preguntan sobre el análisis de datos binarios. Por lo general, los datos no solo son binarios, sino también sensibles al contexto. Básicamente, esto lleva a...
Tengo un problema con este ejercicio: Sea G la siguiente gramática ambigua para el cálculo λ: E → v | λv.E | EE | (E) donde E es el símbolo único no terminal, λv.E representa la abstracción wrt la variable v en E, y EE representa la aplicación. Defina una gramática LL (1) G 'tal que...
Estoy tratando de entender qué se entiende por "determinista" en expresiones como "gramática determinista sin contexto". (Hay "cosas" más deterministas en este campo). ¡Agradecería un ejemplo más que la explicación más elaborada! Si es posible. Mi principal fuente de confusión es no poder decir...
Esta es una pregunta del Libro del Dragón. Esta es la gramática: S→AaAb∣BbBaS→AaAb∣BbBaS \to AaAb \mid BbBa B → εA→εA→εA \to \varepsilon B→εB→εB \to \varepsilon La pregunta pregunta cómo mostrar que es LL (1) pero no SLR (1). Para demostrar que es LL (1), intenté construir su tabla de...
Recientemente estoy estudiando sobre el diseño de compiladores. Llegué a conocer dos tipos de gramática, una es la gramática LL y la otra es la gramática LR. También conocemos los hechos de que cada gramática LL es LR, es decir, la gramática LL es un subconjunto adecuado de la gramática LR. El...
Quiero convertir una expresión regular ingresada por el usuario en un NFA para que luego pueda ejecutar el NFA en una cadena con fines coincidentes. ¿Cuál es la máquina mínima que se puede usar para analizar las expresiones regulares? Supongo que debe ser un autómata push down porque la presencia...
¿Puede alguien aclararme por qué un analizador de descenso recursivo con retroceso que prueba las producciones y (en ese orden) no reconoce el lenguaje formado por la gramática .S→aSaS→unSunS \rightarrow aSaS→aaS→ununS \rightarrow aaS→aSa | aaS→unSun El | ununS \rightarrow aSa\ |\ aa Parece que...
En un analizador LR (0), cada estado consta de una colección de elementos LR (0), que son producciones anotadas con una posición. En un analizador LR (1), cada estado consta de una colección de elementos LR (1), que son producciones anotadas con una posición y un carácter anticipado. Se sabe que...
Hay una manera de realizar un análisis difuso (acepta cadenas incluso con errores tipográficos a una cierta distancia de edición), con un DFA y un Autómata Levenshtein construido en tiempo de ejecución de la palabra de entrada. ¿Se puede hacer algo similar con un analizador Earley? Me resulta...
Usar el vector Earley como un reconocedor es bastante sencillo: cuando se alcanza el final de la cadena, solo tiene que verificar si la producción axiomática completa comenzó en la posición 0. Si tiene al menos una, entonces se acepta la cadena. Usar el vector Earley para reconstruir los árboles...
En la universidad hemos estado aprendiendo sobre la teoría de la computación en general y las máquinas de Turing más específicamente. Uno de los grandes resultados teóricos es que, a costa de un alfabeto (símbolos) potencialmente grande, puede reducir el número de estados a solo 2. Estaba buscando...