Hay una forma sencilla de determinar si una gramática es LL(1), LR(0) Y SLR(1)… acabo de mirar en la gramática, sin hacer ningún análisis complejo?

Por ejemplo: decidir si un BNF Gramática es LL(1) se tiene que calcular Primero y Siga conjuntos, que pueden consumir mucho tiempo en algunos casos.

Ha alguien tiene una idea de cómo hacerlo más rápido?
Cualquier ayuda sería muy apreciada!

InformationsquelleAutor Chris | 2009-01-24

7 Comentarios

  1. 34

    Primero, un poco de dedicación. Usted no puede determinar si un idioma es LL(1) de la inspección de una gramática para ello, sólo se pueden hacer declaraciones acerca de la gramática sí mismo. Es perfectamente posible escribir no LL(1) las gramáticas de los idiomas para los que de LL(1), la gramática existe.

    Con que de la forma:

    • Podría escribir un analizador sintáctico de la gramática y tener un programa que calcule primero y siga conjuntos y otras propiedades para usted. Después de todo, esa es la gran ventaja de la BNF gramáticas, son la máquina comprensible.

    • Inspeccionar la gramática y buscar violaciones de las limitaciones de los diferentes tipos de gramática. Por ejemplo: LL(1) permite el derecho, pero no deja de recursividad, por lo tanto, una gramática que contiene a la izquierda de la recursividad no es LL(1). (Por otra gramática propiedades que vamos a tener que pasar algún tiempo de calidad con las definiciones, porque no puedo recordar nada más lejos de la parte superior de mi cabeza ahora mismo :).

    • Buen punto sobre la distinción entre el lenguaje y la gramática. Si la gramática no es LL(1), todavía puede ser posible construir una LL(1) gramática de la lengua.
    • +1 para pedante. Es una distinción clave, y el hecho de que es generalmente pasado por alto, es un obstáculo para la comprensión.
    • Ídem.
  2. 15

    En respuesta a tu pregunta principal: Para una gramática simple, puede ser posible determinar si es LL(1) sin la construcción de PRIMERO y SIGA establece, por ejemplo,

    A → a + a | a

    no es LL(1), mientras que

    A → a | b

    es.

    Pero cuando usted consigue más complejo que eso, tendrás que hacer algún tipo de análisis.

    A → B | a

    B → A + A

    Esto no es LL(1), pero puede no ser inmediatamente obvio

    Las reglas de la gramática para la aritmética obtener rápidamente muy complejo:

    expr → término { ‘+’ término }

    plazo → factor de { ‘*’ factor }

    factor → número de | ‘(‘ expr ‘)’

    Esta gramática se ocupa sólo de la multiplicación y la suma, y ya no es inmediatamente claro si la gramática es LL(1). Todavía es posible evaluar al mirar a través de la gramática, pero como la gramática crece, se vuelve menos factible. Si nos vamos a la definición de una gramática de un lenguaje de programación, es casi seguro que va a tomar algún complejo análisis.

    Que dijo, hay un par de evidentes signos reveladores de que la gramática no es LL(1) — como la de Un → A + a — y si usted puede encontrar cualquiera de estos en su gramática, sabrá que debe escribirse si estás escribiendo un descenso recursivo analizador. Pero no hay atajo para verificar que la gramática de es LL(1).

    • Por CIERTO, no es necesario calcular SEGUIR para LL(1), ya que sólo está definido en términos de la PRIMERA.
    • En realidad, usted necesita SEGUIR los conjuntos de LL(1) en caso de que el nonterminals se aceptan valores null. De esa manera, usted puede «mirar más allá» el no terminal a ver que la producción para el uso.
  3. 9

    Directamente desde el libro «Compiladores: Principios, Técnicas, & Herramientas» por Aho, et. al.

    Página 223:

    Una gramática G es LL(1) si y sólo si siempre Un -> alfa | beta son dos distintas producciones de G, las siguientes condiciones:

    1. Para el no terminal «a» hacer tanto alfa y beta derivar las cadenas que comienzan con «a»
    2. En la mayoría de los una de alfa y beta puede derivar la cadena vacía
    3. Si beta puede alcanzar el vacío de la transición a través de cero o más transiciones, entonces alfa no se deriva ningún tipo de cadena que comienza con un terminal en SEGUIR(a). Del mismo modo, si alfa puede alcanzar el vacío de la transición a través de cero o más transiciones, entonces beta no se deriva ningún tipo de cadena que comienza con un terminal en SEGUIR(a)

    Es esencialmente un asunto de la verificación de la gramática pasa el Pares Disjointness Prueba y no involucrar a la Izquierda de la Recursión. O de forma más sucinta una gramática G que está a la izquierda-recursiva o ambigua no puede ser LL(1).

  4. 2

    Comprobar si la gramática es ambigua o no. Si es así, entonces la gramática no es LL(1) porque no ambigua de la gramática es LL(1).

  5. 0

    ya hay atajos de teclado para ll(1), la gramática

    1) si a->B1|B2|…….|Bn
    luego la primera a(B1)intersección first(B2)intersección .primero(Bn)=conjunto vacío, entonces es ll(1), la gramática

    2) si a->B1|epsilon
    entonces B1 intersección seguir(a)es el conjunto vacío

    3) si G es cualquier gramática de tal forma que cada no terminal se deriva sólo de producción, a continuación, la gramática es LL(1)

  6. -2
    p0 S' → E
    p1 E → id
    p2 E → id ( E )
    p3 E → E + id
    
    • Construir el LR(0) DFA, el SEGUIMIENTO que se establezca para el Correo y el SLR acción/goto tablas.
    • Es este un LR(0) de la gramática? Demostrar tu respuesta.
    • Utilizando el SLR tablas muestran los pasos (turnos, reducciones, aceptar) de un analizador LR análisis:
      id ( id + id )

Dejar respuesta

Please enter your comment!
Please enter your name here