¿Qué tipo de analizador se necesita para esta gramática? - análisis, gramática

Tengo una gramática que no sé qué tipo deanalizador que necesito para analizarlo de otra manera que no creo que la gramática sea LL (1). Estoy pensando que necesito un analizador con retroceso o LL (*) de algún tipo. La gramática que he creado (que puede necesitar alguna reescritura) es:

S: Rules
Rules: Rule | Rule Rules
Rule: id "=" Ids
Ids: id | Ids id

El lenguaje que estoy tratando de generar se ve algo como esto:

abc = def g hi jk lm
xy = aaa bbb ccc ddd eee fff jjj kkk
foo = bar ha ha

Cero o más Regla que contiene un identificador izquierdoseguido de un signo igual seguido de uno o más identificadores. La parte para la que creo que tendré un problema al escribir un analizador es que la gramática permite cualquier cantidad de id en una Regla y que la única manera de saber cuándo comienza una nueva Regla es cuando encuentra id =, lo que requeriría un retroceso.

¿Alguien sabe la clasificación de esta gramática y el mejor método de análisis, para una escrito a mano analizador?

Respuestas

La gramática que genera un identificador seguido de un signo igual seguido de una secuencia finita de identificadores es regular. Esto significa que las cadenas en el lenguaje se pueden analizar utilizando un DFA o una expresión regular. No hay necesidad de fantasía no determinista o LL(*) analizadores.

Para ver que el idioma es regular, deja Carné de identidad = U {un : un ∈ Γ}, donde Γ ⊂ Σ es el conjunto de símbolos que pueden aparecer en los identificadores. El lenguaje que intenta generar se indica mediante la expresión regular

• Carné de identidad⁺ = ( Carné de identidad⁺)^* Carné de identidad⁺

Ajuste Γ = {un, segundo, ..., z}, ejemplos de cadenas en el lenguaje de la expresión regular son:

• mira = estoy en un lenguaje regular
• hey = eso significa que puedo ser reconocido por un dfa
• cool = o incluso una expresión regular

No es necesario analizar su lenguaje usando técnicas de análisis potentes. Este es un caso en el que el análisis con expresiones regulares o DFA es tanto apropiado como óptimo.

editar:

Llame a la expresión regular anterior R. Analizar R^*, generar un DFA reconociendo el lenguaje de R^*. Para ello, genera un NFA reconociendo el lenguaje de R^* utilizando el algoritmo que se puede obtener del teorema de Kleene. Luego convierta la NFA en una DFA utilizando la construcción del subconjunto. La DFA resultante reconocerá todas las cadenas en R^*. Dada una representación del DFA construido en su lenguaje de implementación, las acciones requeridas, por ejemplo,

• Agregue el último identificador analizado en el lado derecho de la declaración de la declaración actual que se está analizando
• Agregue la última declaración de declaración analizada a una lista de declaraciones analizadas y use el último identificador analizado para comenzar a analizar una nueva declaración de declaración

Puede ser codificado en los estados de la DFA. En realidad, usar el teorema de Kleene y la construcción del subconjunto es probablemente innecesario para un lenguaje tan simple. Es decir, probablemente solo pueda escribir un analizador con las dos acciones anteriores sin implementar un autómata. Dado un lenguaje común más complicado (por ejemplo, , la estructura léxica de un lenguaje de programación), la conversión sería la mejor opción.