Programación JS

En este post explicaré paso a paso como crear un autómata finito determinista a partir de una expresión regular. Primero necesitaremos esta tabla para el cálculo de la primerpos y la ultimapos: Ejemplo: De la expresión regular crear su autómata finito determinista: a(bc*)*+a primero se concatena el símbolo # al final de la expresión regular como delimitador. a(bc*)*+a# Ahora al trabajar el árbol sintáctico se debe tener en cuenta la prioridad de los operadores: Paréntesis cerradura de klein (*), cerradura positiva (+) concatenación (.) disyunción (|) Según estas prioridades se procede a crear el árbol sintáctico de la expresión regular. y se enumeran los nodos hojas (nodos que no tienen hijos). Cálculo de anulables, primerapos y ultimapos usando la tabla anterior: pp: primerapos up: ultimapos Ahora hallamos la siguientepos(i): Si n es un nodo concatenación (.) con hijo izquierdo c1 e hijo derecho c2, e i es una posición dentro de la ...

Pre-requisisto: Gramáticas Según Chomsky los tipos de gramáticas son: GRÁMATICAS TIPO 0 Son no restringidas Reconocidas por la máquina de Turing. Solo cumplen la definición de gramática. Sus reglas de producción tiene la forma: α → ꞵ , α y ꞵ ∈ (N U Z) * Tanto el lado derecho como izquierdo pueden contener símbolos terminales como no terminales. GRAMATICAS TIPO 1 Sensitivas al contexto. Son reconocidos por el autómata linealmente acotado. α → ꞵ , |ꞵ| >= |α| En la regla de producción la longitud del lado izquierdo es mayor o igual que la longitud del lado derecho. GRAMÁTICAS TIPO 2 Libre de contexto. Reconocidas por el autómata de pila. Usado en los lenguajes de programación para definir su estructura sintáctica. A → ꞵ, A ∈ N , ꞵ ∈ (N U Z) * En el lado izquierdo de la producción solo existe un símbolo no terminal y en el lado izquierdo puede existir una combinación de símbolos terminales como no terminales. GRAMÁTICAS TIPO 3 Gramáticas regu...

La gramática es un mecanismo que nos permite generar lenguajes y tiene la forma: G=(∑ , N , R , S) donde: ∑ = Alfabeto (conjunto de terminales). N = Conjunto de no terminales. R = Reglas de producción. S = Simbolo inicial. Ejemplo: G =({a,b,c,1,2} , {S,A,B} , R , S) Donde ∑ ={a , b , c , 1 , 2} N ={S , A , B} R :         S → aA2         A → B21         B → c         B → b S : simbolo inicial Enlaces relacionados: Clasificación de las gramáticas

En este post explicaré paso a paso el proceso de análisis sintáctico usando el Simple LR, más fácil de implementar y basandose en el LR0 INTRODUCCIÓN Se compone de 3 partes: El conjunto de elementos LR(0). El conjunto de tablas de análisis La rutina del controlador. (PARSER) Un parser es una máquina lógica que reconoce el lenguaje generado a partir de una gramática. En este trabajo, implementaremos un generador de analizador sintáctico para una clase particular de gramáticas sin contexto. Conocidas como gramáticas simples de LR (K) [SLR (K)]. LR(0) L: Proceso de la entrada de izquierda a derecha R: Derivación más a la derecha 0: Símbolo para decidir la producción a aplicar. Aunque es el menos potente de la familia LR, tiene la ventaja de ser fácilmente comprensible y servir de base para entender el resto. Pero demasiado trabajo construir un analizador sintáctico LR. FASES: Se obtiene la colección canónica de conjuntos de elemento. Se obtiene...