Analizador sintáctico de precedencia simple

Analizador sintáctico de precedencia simple

Analizador sintáctico de precedencia simple

En el área de los lenguajes formales, un analizador de sintaxis por precedencia simple es un tipo de analizador sintáctico ascendente para gramáticas libres de contexto que pueden ser utilizados para reconocer gramáticas de precedencia simple.

La implementación del parser es bastante similar al analizador sintáctico ascendente genérico. Una pila es utilizada para almacenar el prefijo viable de una forma sentencial de una derivación más a la derecha. Los símbolos \lessdot, \dot = y \gtrdot son utilizados para identificar el pivote, por lo tanto sabremos cuando Desplazar o cuando Reducir.

Implementación

  • Calcule la tabla de relación de precedencia de Wirth-Weber.
  • Comience con la pila conteniendo solamente la marca inicial $.
  • Comience con la cadena a ser analizada (Entrada) seguida de una marca final $.
  • Mientras no (Pila igual a $S y Entrada igual a $) (S = Símbolo inicial de la gramática)
    • Buscar en la tabla la relación entre Tope(Pila) y PróximoSímbolo(Entrada)
    • Si la relación es  \dot  = o \lessdot
      • Desplazar:
      • Apilar(Pila, relación)
      • Apilar(Pila, PróximoSímbolo(Entrada))
      • SacarPróximoSímbolo(Entrada)
    • Si la relación es \gtrdot
      • Reducir:
      • BuscarProducciónParaReducir(Pila)
      • SacarPivote(Pila)
      • Buscar en la tabla la relación entre el No terminal de la producción y PróximoSímbolo(Entrada)
      • Apilar(Pila, relación)
      • Apilar(Pila, No terminal)

BuscarProducciónParaReducir (Pila)

  • busca el Pivote en la pila, el \lessdot más cercano del tope
  • busca en las producciones de la gramática cual tiene el mismo lado derecho que el Pivote

Ejemplo

Dado el siguiente lenguaje:
E  --> E + T' | T'
T' --> T
T  --> T * F  | F
F  --> ( E' ) | num
E' --> E

num es un terminal, y el lexer interpreta cualquier número entero como num.

y la tabla de análisis:

E E' T T' F + * ( ) num $
E \dot = \gtrdot \gtrdot
E' \dot =
T \gtrdot \dot = \gtrdot \gtrdot
T' \gtrdot \gtrdot \gtrdot
F \gtrdot \gtrdot \gtrdot \gtrdot
+ \lessdot \dot = \lessdot \lessdot \lessdot
* \dot = \lessdot \lessdot
( \lessdot \dot = \lessdot \lessdot \lessdot \lessdot \lessdot
) \gtrdot \gtrdot \gtrdot
num \gtrdot \gtrdot \gtrdot \gtrdot
$ \lessdot \lessdot \lessdot \lessdot \lessdot \lessdot



STACK                   PRECEDENCE    INPUT            ACTION

$                            <        2 * ( 1 + 3 )$   DESPLAZAR
$ < 2                        >        * ( 1 + 3 )$     REDUCIR (F -> num)
$ < F                        >        * ( 1 + 3 )$     REDUCIR (T -> F)
$ < T                        =        * ( 1 + 3 )$     DESPLAZAR
$ < T = *                    <        ( 1 + 3 )$       DESPLAZAR
$ < T = * < (                <        1 + 3 )$         DESPLAZAR
$ < T = * < ( < 1            >        + 3 )$           REDUCIR 4 veces (F -> num) (T -> F) (T' -> T) (E ->T ') 
$ < T = * < ( < E            =        + 3 )$           DESPLAZAR
$ < T = * < ( < E = +        <        3 )$             DESPLAZAR
$ < T = * < ( < E = + < 3    >        )$               REDUCIR 3 veces (F -> num) (T -> F) (T' -> T) 
$ < T = * < ( < E = + = T    >        )$               REDUCIR 2 veces (E -> E + T) (E' -> E)
$ < T = * < ( < E'           =        )$               DESPLAZAR
$ < T = * < ( = E' = )       >        $                REDUCIR (F -> ( E' ))
$ < T = * = F                >        $                REDUCIR (T -> T * F)
$ < T                        >        $                REDUCIR 2 veces (T' -> T) (E -> T')
$ < E                        >        $                ACCEPTAR

Véase también

Obtenido de "Analizador sint%C3%A1ctico de precedencia simple"

Wikimedia foundation. 2010.

Игры ⚽ Нужен реферат?

Mira otros diccionarios:

  • Gramática de precedencia simple — Una gramática de precedencia simple es un tipo de Gramática libre de contexto que puede ser reconocida por un Analizador sintáctico de precedencia simple. Contenido 1 Definición formal 2 Ejemplos 2.1 Ejemplo 1 G = (N, Σ, P, S …   Wikipedia Español

  • Motor de Análisis Sintáctico — Este artículo o sección se refiere o está relacionado con un software futuro o en desarrollo. La información de este artículo puede cambiar frecuentemente. Por favor, no agregues datos especulativos y recuerda colocar referencias a fuentes… …   Wikipedia Español

  • Gramática del español — Estatua del gramático Antonio de Nebrija en la Biblioteca Nacional de Madrid, por Anselmo Nogués. En 1492, Nebrija fue el primer europeo en escribir una gramática de una lengua románica o neolatina, el español …   Wikipedia Español

  • Perl — Desarrollador(es) Larry Wall www.perl.org Información general Paradigma multiparadigma, funcional, im …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”