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 {=}}$ ${\dot {=}}$ o $\lessdot$ $\lessdot$
  - Desplazar:
  - Apilar(Pila, relación)
  - Apilar(Pila, PróximoSímbolo(Entrada))
  - SacarPróximoSímbolo(Entrada)
- Si la relación es $\gtrdot$ $\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

Datos: Q7520826