Gramaticas posicionales
Páginas: 8 (1938 palabras)
Publicado: 8 de enero de 2012
Gramáticas posicionales
Verónica Ortega Infante Edgar Alfredo López Orduña
Teoría Computacional
Gramáticas posicionales
Son sistemas de reescritura de trabajo en conjuntos de símbolos localizados en una posición en una red. Su ha sido fuertemente influenciada por la necesidad de tener un analizador sintáctico eficiente capaz de procesar los lenguajes generados.
Fueron concebidas comouna extensión simple de las gramáticas independientes del contexto para el caso de los lenguajes simbólicos de dos dimensiones. Han estado en constante evolución, con el fin de representar clases de lenguajes visuales cada vez más extensos.
Las sentencias generadas eran matrices de símbolos con las que se podían describir expresiones aritméticas simples de dos dimensiones. Dada la analogíacon las gramáticas de cadenas, es muy natural la utilización de las técnicas LR. El resultado fue la definición del análisis sintáctico posicional pLR.
Una producción de la gramática posicional tiene la forma: → … Donde: A es un no terminal xi es un terminal o no terminal Ri es una relación espacial de la forma (k,l) indicando que xi+1 debería ser encontrada en la posición (i + k,j + l) si xifue localizada en (i,j).
El conjunto de producciones correspondientes de G’ es obtenido por remplazar cada producción de la PG de la forma de una producción de CMG. ̅, ∷ where: And p ̅ ̅ , , , ̅ , ,…, , ̅ , ̅ , , ̅ , ,…, , ̅ , , ̅ ,
Cuando: Cuando:
, , , , , , ↔ ∧
Gramática posicional extendida
La gramática posicional extendida (XPG) es formalmente una gramática poderosa para modelaruna clase general de lenguajes visuales.
Una XPG es el par (G, PE), donde: PE es un evaluador posicional G puede ser un tipo particular de gramática de cadenas libre de contexto (N, T ᴜ POS, S, P) donde: N es un conjunto finito no vacío de símbolos visuales no terminales.
T es un conjunto finito no vacío de símbolos visuales terminales, con " ∩ $ ∅. POS es un conjunto finito de identificadorde relaciones binarias, con &'( ∩ " ∅ y &'( ∩ $ ∅.
S Є N denota el símbolo visual inicial. P es un conjunto finito no vacío de producciones que tienen el siguiente formato: A → x1 R1 x2 R2 ... xm-1 Rm-1 xm , Δ , Γ Donde A es un símbolo visual no terminal, x1 R1 x2 R2 … xm-1 Rm-1 xm es una representación lineal con respecto a POS donde cada xi es un símbolo visual en " ∪ $ y cada Rj estapartido en dos subsecuentes:
(⟨ RELj1h1,..., RELjkhk ⟩ , ⟨ RELjk+1hk+1,..., RELjnhn ⟩) with 1 ≤ k ≤ n Para cada RELj1h1 se relacionan atributos sintácticos de xj+1 con atributos sintácticos de xj-hi con 0 - . - /. Para simplificar, denotamos REL10 como REL1. Los identificadores de relación en la primera subsecuencia de un Rj son llamadas relaciones de manejo, mientras los primeros y los segundossubsecuentes son llamados relaciones de prueba.
Durante el análisis de la sintaxis de las relaciones de manejo son usadas para determinar el siguiente símbolo visual que será escaneado. Mientras las relaciones de prueba son usadas para checar si el ultimo símbolo visual escaneado (Terminal o no Terminal) esta correctamente relacionado al símbolo visual escaneado previamente.
Δ es unconjunto de reglas usadas para sintetizar el valor de los atributos sintácticos de una de las de x1, x2, …., xm. Γ es conjunto de triples (Nj, Condj, Δj) j=1...t, t ≥ 0, usado para insertar dinámicamente nuevos símbolos terminales en la sentencia general de entrada durante el proceso del análisis. Nj Es un símbolo visual terminal para ser insertado en la sentencia generalizada de entrada. Condj Es unaprecondición para ser verificado en orden para insertar Nj.
Δj Es una regla usada para calcular los valores de los atributos sintácticos de Nj de uno de los x1,x2, …., xm. Por otra parte, una propiedad que garantiza la convergencia de algoritmos de análisis, basado en XPGs, es: “para cada producción A → x1 ... xm, Δ, Γ el número de triples en Γ las cuales las condiciones pueden evaluar...
Verónica Ortega Infante Edgar Alfredo López Orduña
Teoría Computacional
Gramáticas posicionales
Son sistemas de reescritura de trabajo en conjuntos de símbolos localizados en una posición en una red. Su ha sido fuertemente influenciada por la necesidad de tener un analizador sintáctico eficiente capaz de procesar los lenguajes generados.
Fueron concebidas comouna extensión simple de las gramáticas independientes del contexto para el caso de los lenguajes simbólicos de dos dimensiones. Han estado en constante evolución, con el fin de representar clases de lenguajes visuales cada vez más extensos.
Las sentencias generadas eran matrices de símbolos con las que se podían describir expresiones aritméticas simples de dos dimensiones. Dada la analogíacon las gramáticas de cadenas, es muy natural la utilización de las técnicas LR. El resultado fue la definición del análisis sintáctico posicional pLR.
Una producción de la gramática posicional tiene la forma: → … Donde: A es un no terminal xi es un terminal o no terminal Ri es una relación espacial de la forma (k,l) indicando que xi+1 debería ser encontrada en la posición (i + k,j + l) si xifue localizada en (i,j).
El conjunto de producciones correspondientes de G’ es obtenido por remplazar cada producción de la PG de la forma de una producción de CMG. ̅, ∷ where: And p ̅ ̅ , , , ̅ , ,…, , ̅ , ̅ , , ̅ , ,…, , ̅ , , ̅ ,
Cuando: Cuando:
, , , , , , ↔ ∧
Gramática posicional extendida
La gramática posicional extendida (XPG) es formalmente una gramática poderosa para modelaruna clase general de lenguajes visuales.
Una XPG es el par (G, PE), donde: PE es un evaluador posicional G puede ser un tipo particular de gramática de cadenas libre de contexto (N, T ᴜ POS, S, P) donde: N es un conjunto finito no vacío de símbolos visuales no terminales.
T es un conjunto finito no vacío de símbolos visuales terminales, con " ∩ $ ∅. POS es un conjunto finito de identificadorde relaciones binarias, con &'( ∩ " ∅ y &'( ∩ $ ∅.
S Є N denota el símbolo visual inicial. P es un conjunto finito no vacío de producciones que tienen el siguiente formato: A → x1 R1 x2 R2 ... xm-1 Rm-1 xm , Δ , Γ Donde A es un símbolo visual no terminal, x1 R1 x2 R2 … xm-1 Rm-1 xm es una representación lineal con respecto a POS donde cada xi es un símbolo visual en " ∪ $ y cada Rj estapartido en dos subsecuentes:
(⟨ RELj1h1,..., RELjkhk ⟩ , ⟨ RELjk+1hk+1,..., RELjnhn ⟩) with 1 ≤ k ≤ n Para cada RELj1h1 se relacionan atributos sintácticos de xj+1 con atributos sintácticos de xj-hi con 0 - . - /. Para simplificar, denotamos REL10 como REL1. Los identificadores de relación en la primera subsecuencia de un Rj son llamadas relaciones de manejo, mientras los primeros y los segundossubsecuentes son llamados relaciones de prueba.
Durante el análisis de la sintaxis de las relaciones de manejo son usadas para determinar el siguiente símbolo visual que será escaneado. Mientras las relaciones de prueba son usadas para checar si el ultimo símbolo visual escaneado (Terminal o no Terminal) esta correctamente relacionado al símbolo visual escaneado previamente.
Δ es unconjunto de reglas usadas para sintetizar el valor de los atributos sintácticos de una de las de x1, x2, …., xm. Γ es conjunto de triples (Nj, Condj, Δj) j=1...t, t ≥ 0, usado para insertar dinámicamente nuevos símbolos terminales en la sentencia general de entrada durante el proceso del análisis. Nj Es un símbolo visual terminal para ser insertado en la sentencia generalizada de entrada. Condj Es unaprecondición para ser verificado en orden para insertar Nj.
Δj Es una regla usada para calcular los valores de los atributos sintácticos de Nj de uno de los x1,x2, …., xm. Por otra parte, una propiedad que garantiza la convergencia de algoritmos de análisis, basado en XPGs, es: “para cada producción A → x1 ... xm, Δ, Γ el número de triples en Γ las cuales las condiciones pueden evaluar...
Leer documento completo
Regístrate para leer el documento completo.