Edición de «Definiciones y teoremas (Teoría de Lenguajes)»
De Cuba-Wiki
Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
Revisión actual | Tu texto | ||
Línea 41: | Línea 41: | ||
SD(N \to \beta) = | SD(N \to \beta) = | ||
\begin{cases} | \begin{cases} | ||
\textrm{PRIMEROS}(\beta) & si\ \beta\ \textrm{no es anulable} \\ | \textrm{PRIMEROS}(\beta) & si\ \beta\ \textrm{no\ es\ anulable} \\ | ||
\textrm{PRIMEROS}(\beta) \cup \textrm{SIGUIENTES}(N) & \textrm{ | \textrm{PRIMEROS}(\beta) \cup \textrm{SIGUIENTES}(N) & \textrm{sino} | ||
\end{cases} | \end{cases} | ||
</math> | </math> | ||
Línea 107: | Línea 107: | ||
Pasa a ser: | Pasa a ser: | ||
<br>A --> β1 <font color=blue>A'</font> | ... | βK <font color=blue>A'</font> | <br>A --> β1 <font color=blue>A'</font> | ... | βK <font color=blue>A'</font> | ||
<br><font color=blue>A'</font> --> <font color=red>α1</font> A' | ... | <font color=red>αN</font> A' | | <br><font color=blue>A'</font> --> <font color=red>α1</font> <font color=blue>A'</font> | ... | <font color=red>αN</font> <font color=blue>A'</font> | lambda | ||
= Gramáticas y parsers LR = | = Gramáticas y parsers LR = | ||
Línea 132: | Línea 132: | ||
=== Los distintos algoritmos LR === | === Los distintos algoritmos LR === | ||
Construir el AFND ideal o necesario una gramática cualquiera no es fácil y puede llegar a tener miles de estados, ya que cada estado del AFND representa un momento determinado en el parsing de una cadena de entrada cualquiera, y tiene que tener implícita la información de todo lo se leyó hasta el momento. | Construir el AFND ideal o necesario una una gramática cualquiera no es fácil y puede llegar a tener miles de estados, ya que cada estado del AFND representa un momento determinado en el parsing de una cadena de entrada cualquiera, y tiene que tener implícita la información de todo lo se leyó hasta el momento. | ||
Hay entonces formas de construir AFND más simples y que sirven en muchas situaciones (aunque no todas). | Hay entonces formas de construir AFND más simples y que sirven en muchas situaciones (aunque no todas). | ||
Línea 155: | Línea 155: | ||
Para los detalles de estas funciones en cada parser recomiendo altamente leer este ppt: | Para los detalles de estas funciones en cada parser recomiendo altamente leer este ppt: | ||
[http://oscarbonilla.com/courses/compilers/materials/09_Parser_Engines.ppt Algoritmos LR0, SLR, LR1 y LALR | [http://oscarbonilla.com/courses/compilers/materials/09_Parser_Engines.ppt Algoritmos LR0, SLR, LR1 y LALR] | ||
Es didáctico, con ejemplos paso a paso y si bien parece largo por tener cientos de slides, la mayoría son por los ejemplos paso a paso. Recomiendo en serio leerlo si quieren ver como construir los AFND en detalle. | Es didáctico, con ejemplos paso a paso y si bien parece largo por tener cientos de slides, la mayoría son por los ejemplos paso a paso. Recomiendo en serio leerlo si quieren ver como construir los AFND en detalle. | ||
= Gramaticas de Precedencia Simple = | |||
=== Relaciones de precedencia === | |||
<math>X \dot = Y \Leftrightarrow A \rightarrow \ldots X Y \ldots</math> | |||
<math>X \dot < Y \Leftrightarrow A \rightarrow \ldots X Y' \ldots \wedge Y' \rightarrow ^+ Y \ldots</math> | |||
<math>X \dot > Y \Leftrightarrow A \rightarrow \ldots X' Y' \ldots \wedge X' \rightarrow ^+ \ldots X \wedge Y' \rightarrow ^* Y \ldots</math> | |||
=== Gramatica === | |||
G = (''N'', Σ, ''P'', ''S'') is a simple precedence grammar if all the production rules in ''P'' comply with the following constraints: | |||
* There are no erasing rules (ε-productions) | |||
* There are no useless rules (unreacheable symbols or unproductives rules) | |||
* For each pair of symbols ''X'', ''Y'' (''X'', ''Y'' <math>\in</math> (''N'' <math>\cup</math> Σ)) there is only one precedence relation. | |||
* G is uniquely inversible | |||
=== Ejemplo parseo === | |||
Dado el lenguaje: | |||
E --> E + T' | T' | |||
T' --> T | |||
T --> T * F | F | |||
F --> ( E' ) | num | |||
E' --> E | |||
Y la tabla de parsing: | |||
{|border="1" cellpadding="2" | |||
| ||E|| E' || T || T' || F || + ||*||(||)||num || $ | |||
|- | |||
| E || || || || || ||<math>\dot =</math>|| || ||<math>\dot ></math> || ||<math>\dot ></math> | |||
|- | |||
| E'|| || || || || || || || ||<math>\dot =</math>|| || | |||
|- | |||
| T || || || || || ||<math>\dot ></math>||<math>\dot =</math>|| ||<math>\dot ></math>|| ||<math>\dot ></math> | |||
|- | |||
| T'|| || || || || ||<math>\dot ></math>|| || ||<math>\dot ></math>|| ||<math>\dot ></math> | |||
|- | |||
| F || || || || || ||<math>\dot ></math>||<math>\dot ></math>|| ||<math>\dot ></math>|| ||<math>\dot ></math> | |||
|- | |||
| + || || ||<math>\dot <</math>||<math>\dot =</math>||<math>\dot <</math>|| || ||<math>\dot <</math>|| ||<math>\dot <</math> || | |||
|- | |||
| * || || || || ||<math>\dot =</math>|| || ||<math>\dot <</math>|| ||<math>\dot <</math> || | |||
|- | |||
| ( ||<math>\dot <</math>||<math>\dot =</math>||<math>\dot <</math>||<math>\dot <</math>||<math>\dot <</math>|| || ||<math>\dot <</math>|| ||<math>\dot <</math> || | |||
|- | |||
| ) || || || || || ||<math>\dot ></math>||<math>\dot ></math>|| ||<math>\dot ></math>|| ||<math>\dot ></math> | |||
|- | |||
| num|| || || || || ||<math>\dot ></math>||<math>\dot ></math>||||<math>\dot ></math>|| ||<math>\dot ></math> | |||
|- | |||
| $ ||<math>\dot <</math>|| ||<math>\dot <</math>||<math>\dot <</math>||<math>\dot <</math>|| || ||<math>\dot <</math>|| ||<math>\dot <</math> || | |||
|} | |||
El input ''2 * ( 1 + 3 )$'' se parsea: | |||
<pre> | |||
STACK PRECEDENCE INPUT ACTION | |||
$ < 2 * ( 1 + 3 )$ SHIFT | |||
$ < 2 > * ( 1 + 3 )$ REDUCE (F -> num) | |||
$ < F > * ( 1 + 3 )$ REDUCE (T -> F) | |||
$ < T = * ( 1 + 3 )$ SHIFT | |||
$ < T = * < ( 1 + 3 )$ SHIFT | |||
$ < T = * < ( < 1 + 3 )$ SHIFT | |||
$ < T = * < ( < 1 > + 3 )$ REDUCE 4 times (F -> num) (T -> F) (T' -> T) (E ->T ') | |||
$ < T = * < ( < E = + 3 )$ SHIFT | |||
$ < T = * < ( < E = + < 3 )$ SHIFT | |||
$ < T = * < ( < E = + < 3 > )$ REDUCE 3 times (F -> num) (T -> F) (T' -> T) | |||
$ < T = * < ( < E = + = T > )$ REDUCE 2 times (E -> E + T) (E' -> E) | |||
$ < T = * < ( < E' = )$ SHIFT | |||
$ < T = * < ( = E' = ) > $ REDUCE (F -> ( E' )) | |||
$ < T = * = F > $ REDUCE (T -> T * F) | |||
$ < T > $ REDUCE 2 times (T' -> T) (E -> T') | |||
$ < E > $ ACCEPT | |||
</pre> | |||
= Gramaticas de Atributos = | = Gramaticas de Atributos = |