Analizador sintáctico LR

Carta Común · N.º 441247

Los analizadores sintácticos LR, también conocidos como Parser LR, son un tipo de dispositivos para manipular algunas gramáticas libres de contexto. Pertenecen a la familia de los analizadores ascendentes, ya que constituyen el árbol sintáctico de las hojas hacia la raíz. Utilizan la técnica de análisis por desplazamiento de reducción. Existen tres tipos de parsers LR: SLR (K), LALR (K) y LR (K) canónico. Un analizador LR consta de: Un programa conductor Una entrada Una salida Una tabla de análisis sintáctico, compuesta de dos partes (ACCIÓN y GOTO). Cabe acotar que el programa conductor es siempre igual, variando solo la tabla de análisis sintáctico para cada lenguaje. El algoritmo para reconocer cadenas es el siguiente: dado el primer carácter de la cadena y el estado inicial de la tabla, buscar qué acción corresponde en la tabla de acción. Si el estado es shiif n (n ∈ N), se coloca el carácter y el número de estado n en la pila, se lee el siguiente carácter y se repite el procedimiento…

Leer en Wikipedia