Guia docent Escola Tècnica Superior d'Enginyeria |
català |
Grau d'Enginyeria Informàtica (2010) |
Assignatures |
LLENGUATGES FORMALS |
Continguts |
DADES IDENTIFICATIVES | 2017_18 |
Assignatura | LLENGUATGES FORMALS | Codi | 17234110 | |||||
Ensenyament |
|
Cicle | 1r | |||||
Descriptors | Crèd. | Tipus | Curs | Període | ||||
6 | Obligatòria | Tercer | 2Q |
Competències | Resultats d'aprenentage | Continguts |
Planificació | Metodologies | Atenció personalitzada |
Avaluació | Fonts d'informació | Recomanacions |
Tema | Subtema |
1. Introducció | 1.1. Els llenguatges de programació com a llenguatges formals. 1.2. Nocions bàsiques de llenguatges formals: definició, descripció, i reconeixement de llenguatges formals. 1.3. Estructura bàsica d'un compilador. |
2. Llenguatges regulars | 2.1. Expressions regulars. 2.2. Autòmats finits: deterministes, no deterministes i amb lambda-moviments. 2.3. Equivalència entre expressions regulars i autòmats finits. 2.4. Generadors d'analitzadors lèxics: flex. |
3. Llenguatges independents del context | 3.1. Gramàtiques independents del context. 3.2. Autòmats de pila. 3.3. Equivalència entre gramàtiques independents del context i autòmats de pila. 3.4. Generadors d'analitzadors sintàctics: bison. |
4. Altres llenguatges formals | 4.1. Classificació dels llenguatges formals: jerarquia de Chomsky. 4.2. Màquines de Turing. 4.3. Llenguatges recursius i llenguatges recursivament enumerables. |
5. Calculabilitat i complexitat | 5.1. Tesi de Church-Turing. 5.2. Màquina de Turing universal. 5.3. Problemes indecidibles: problema de l'aturada. 5.4. Introducció a la teoria de la complexitat. 5.5. Els problemes P, NP i NP-complets. |
6. Processadors de llenguatges formals | 6.1. Taula de símbols. 6.2. Anàlisi lèxica. 6.3. Anàlisi sintàctica. 6.4. Anàlisi semàntica. 6.5. Generació de codi intermedi. 6.6. Generació de codi objecte. |