¿Qué tipo de analizador se necesita para esta gramática?

Question

Tengo una gramática que no sé qué tipo de analizador necesito para analizarlo aparte de 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 He ocurrió (que puede necesitar algo de reescritura) es:

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

El lenguaje que estoy tratando de generar 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 la izquierda identificador seguido de un signo igual seguido de uno o más identificadores. La parte 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 forma de saber cuándo se inicia una nueva regla es cuando encuentra id =, lo que requeriría retroceder.

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

Answer 1

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 es necesario para sofisticados no deterministas o LL (*) analizadores.

ver que el lenguaje es regular, vamos Id = T {un: un ∈ Γ}, donde Γ ⊂ Σ es el conjunto de símbolos que pueden ocurrir en los identificadores. El idioma que está tratando de generar es denotado por la expresión regular

• Id⁺ = (Id⁺) ^*Id⁺

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

• mirada = Estoy en un lenguaje regular
• ey = Eso significa que puede ser reconocido por una DFA
• fresco = o incluso una expresión regular

no hay necesidad de analizar su idioma utilizando técnicas de análisis de gran alcance. Este es un caso en el que el análisis mediante expresiones regulares o DFA es apropiado y óptimo.

edición:

llamada la expresión regular anterior R.Para analizar R^*, generar un DFA que reconoce el lenguaje de R^*. Para hacer esto, genere un NFA que reconozca el lenguaje de R^* usando el algoritmo que se puede obtener del teorema de Kleene. Luego convierta el NFA en un DFA usando la construcción del subconjunto. El DFA resultante reconocerá todas las cadenas en R^*. Dada una representación de la DFA construida en su lenguaje de implementación, las acciones necesarias - por ejemplo,

• Añadir el último identificador analizada a la parte derecha de la instrucción de declaración actual que está siendo analizada
• Añadir la última declaración instrucción analizada en una lista de declaraciones analizadas, y utilice el último identificador analizado para comenzar a analizar una nueva declaración declaración

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