Ver el código de «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]] [[analizador sintáctico ascendente|ascendente]] para [[gramáticas libres de contexto]] que pueden ser utilizados para reconocer [[gramática de precedencia simple|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 <math>\lessdot</math>, <math>\dot =</math> y <math>\gtrdot</math> 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 <Math> \dot  =</math> o <Math>\lessdot</math> 
*** '''Desplazar''': 
*** Apilar(Pila, relación)
*** Apilar(Pila, PróximoSímbolo(Entrada))
*** SacarPróximoSímbolo(Entrada)
** Si la relación es <Math>\gtrdot</math>
*** '''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 <Math>\lessdot</math> más cercano del tope
* busca en las producciones de la gramática cual tiene el mismo lado derecho que el '''Pivote'''

== Ejemplo ==

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

</pre>

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

y la tabla de análisis:

{|border="1" cellpadding="2"
|   ||E|| E' ||  T   ||      T' ||        F   ||     +             ||*||(||)||num || $
|-
| E || || || || || ||<math>\dot =</math>|| || ||<math>\gtrdot</math> || ||<math>\gtrdot</math> 
|-
| E'|| || ||  || || || || || ||<math>\dot =</math>|| || 
|-
| T || || ||  || || ||<math>\gtrdot</math>||<math>\dot =</math>|| ||<math>\gtrdot</math>|| ||<math>\gtrdot</math> 
|-
| T'|| || ||  || || ||<math>\gtrdot</math>|| || ||<math>\gtrdot</math>|| ||<math>\gtrdot</math> 
|-
| F || || ||  || || ||<math>\gtrdot</math>||<math>\gtrdot</math>|| ||<math>\gtrdot</math>|| ||<math>\gtrdot</math> 
|-
| + || || ||<math>\lessdot</math>||<math>\dot =</math>||<math>\lessdot</math>||                    || ||<math>\lessdot</math>|| ||<math>\lessdot</math> || 
|-
| * || || ||  || ||<math>\dot =</math>|| || ||<math>\lessdot</math>|| ||<math>\lessdot</math> || 
|-
| ( ||<math>\lessdot</math>||<math>\dot =</math>||<math>\lessdot</math>||<math>\lessdot</math>||<math>\lessdot</math>|| || ||<math>\lessdot</math>|| ||<math>\lessdot</math> || 
|-
| ) || || ||  || || || ||<math>\gtrdot</math>|| ||<math>\gtrdot</math>|| ||<math>\gtrdot</math> 
|-
| num|| || ||  || || ||<math>\gtrdot</math>||<math>\gtrdot</math>||||<math>\gtrdot</math>|| ||<math>\gtrdot</math> 
|-
| $ ||<math>\lessdot</math>|| ||<math>\lessdot</math>||<math>\lessdot</math>||<math>\lessdot</math>|| || ||<math>\lessdot</math>|| ||<math>\lessdot</math> || 
|}


<pre>

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
</pre>

== Véase también ==
* [[Analizador sintáctico]]
* [[Analizador sintáctico LL]]
* [[Analizador sintáctico LR]]

{{Control de autoridades}}
[[Categoría:Analizadores sintácticos]]