Compiladores/Aula Prática 03: Difference between revisions
From Wiki**3
< Compiladores
No edit summary |
|||
| Line 5: | Line 5: | ||
== Exercício 1 == | == Exercício 1 == | ||
Para cada uma das expressões regulares seguintes, calcular o autómato finito não-determinista (NFA) pelo algoritmo de Thompson. Para cada um dos casos, calcular o autómato determinista (DFA) mínimo. Em todos os casos, o alfabeto é '''Σ = { a, b }'''. | Para cada uma das expressões regulares seguintes, calcular o autómato finito não-determinista (NFA) pelo algoritmo de Thompson. Para cada um dos casos, calcular o autómato determinista (DFA) mínimo. Em todos os casos, o alfabeto é '''Σ = { a, b }'''. | ||
* [[Theoretical Aspects of Lexical Analysis/Exercise 1| | * [[Theoretical Aspects of Lexical Analysis/Exercise 1|Problema 1]]: <nowiki>(a|b)*</nowiki> | ||
* [[Theoretical Aspects of Lexical Analysis/Exercise 2| | * [[Theoretical Aspects of Lexical Analysis/Exercise 2|Problema 2]]: <nowiki>(a*|b*)*</nowiki> | ||
* [[Theoretical Aspects of Lexical Analysis/Exercise 3| | * [[Theoretical Aspects of Lexical Analysis/Exercise 3|Problema 3]]: <nowiki>((ε|a)b)*</nowiki> | ||
* [[Theoretical Aspects of Lexical Analysis/Exercise 4| | * [[Theoretical Aspects of Lexical Analysis/Exercise 4|Problema 4]]: <nowiki>(a|b)*abb(a|b)*</nowiki> | ||
== Exercício 2 == | |||
Para cada uma das seguintes sequências ordenadas seguintes, calcular o autómato finito não-determinista (NFA) pelo algoritmo de Thompson. Para cada um dos casos, calcular o autómato determinista (DFA) mínimo. Em todos os casos, o alfabeto é Σ = { a, b }. Indicar em quantos passos é processada a entrada apresentada. | |||
* [[Theoretical Aspects of Lexical Analysis/Exercise 5|Problema 1]]: <nowiki>G = { ab, ab*, a|b }</nowiki>, input string = abaabb | |||
* [[Theoretical Aspects of Lexical Analysis/Exercise 6|Problema 2]]: <nowiki>G = { aa, aaaa, a|b }</nowiki>, input string = aaabaaaaa | |||
== | == Resoluções == | ||
As ligações acima contêm as soluções para os exercícios propostos. | As ligações acima contêm as soluções para os exercícios propostos. | ||
Revision as of 15:21, 9 February 2015
Tópicos
Análise lexical: expressões regulares, algoritmo de Thompson (construção do NFA), determinização (construção do DFA), minimização de DFA, análise de entrada.
Analisadores lexicais (múltiplas expressões/tokens em simultâneo).
Exercício 1
Para cada uma das expressões regulares seguintes, calcular o autómato finito não-determinista (NFA) pelo algoritmo de Thompson. Para cada um dos casos, calcular o autómato determinista (DFA) mínimo. Em todos os casos, o alfabeto é Σ = { a, b }.
- Problema 1: (a|b)*
- Problema 2: (a*|b*)*
- Problema 3: ((ε|a)b)*
- Problema 4: (a|b)*abb(a|b)*
Exercício 2
Para cada uma das seguintes sequências ordenadas seguintes, calcular o autómato finito não-determinista (NFA) pelo algoritmo de Thompson. Para cada um dos casos, calcular o autómato determinista (DFA) mínimo. Em todos os casos, o alfabeto é Σ = { a, b }. Indicar em quantos passos é processada a entrada apresentada.
- Problema 1: G = { ab, ab*, a|b }, input string = abaabb
- Problema 2: G = { aa, aaaa, a|b }, input string = aaabaaaaa
Resoluções
As ligações acima contêm as soluções para os exercícios propostos.
Procurar resolver sem consultar.