Automatas

UNIVERSIDAD DE CÓRDOBA
ESCUELA POLITÉCNICA SUPERIOR
DEPARTAMENTO DE INFORMÁTICA Y ANÁLISIS NUMÉRICO

INGENIERÍA TÉCNICA EN INFORMÁTICA DE SISTEMAS
SEGUNDO CURSO, SEGUNDO CUATRIMESTRE

TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES

Tema 8.- Gramáticas de Contexto Libre
8.-

Teoría de Autómatas y Lenguajes Formales

Tema 8.- Gramáticas de Contexto Libre

Ejemplo de Gramática de ContextoLibre
G 1 = (VN, VT, P1, S)
P1={
(1) S → identificador = E
(2) E → E + E
(3) E → E ∗ E
(4) E → ( E )
(5) E → identificador
(6) E → número
}
2

Teoría de Autómatas y Lenguajes Formales

Tema 8.- Gramáticas de Contexto Libre

Ejemplo de Gramática de Contexto Libre
G 2= (VN, VT, P2, S)
P 2= {
S → mientras C hacer S fin mientras
S → si C entonces S fin si
si entonces fin
S → siC entonces S si no S fin si
S → Asignación
C → Condición
}
3

Teoría de Autómatas y Lenguajes Formales

Tema 8.- Gramáticas de Contexto Libre

Ejemplo de Derivación con la gramática G 1
S ⇒1 identificador = E

⇒2 identificador = E + E
identificador
⇒3 identificador = E + E ∗ E
⇒6 identificador = E + número ∗ E
⇒5 identificador = E + número ∗ identificador
⇒5 identificador =identificador + número ∗ identificador

4

Teoría de Autómatas y Lenguajes Formales

Tema 8.- Gramáticas de Contexto Libre

Árbol sintáctico de derivación

5

Teoría de Autómatas y Lenguajes Formales

Tema 8.- Gramáticas de Contexto Libre

Lenguaje generado por una gramática de
contexto libre
G 3= (VN, VT, P3, S)
P 3= {
(1) S → a A a
(2) A → a A a
(3) A → b B b
(4) B → b B b(5) B → c
}
6

Teoría de Autómatas y Lenguajes Formales

Tema 8.- Gramáticas de Contexto Libre

Lenguaje generado por una gramática de
contexto libre
L(G 3) = { a i b j c b j a i| i, j , > 0 } , palíndromo impar

S ⇒1 a A a

⇒2 a a A a a
⇒3 a a b B b a a
⇒4 a a b b B b b a a
⇒5 a a b b c b b a a
7

Teoría de Autómatas y Lenguajes Formales

Tema 8.- Gramáticas de ContextoLibre

Ambigüedad

• Definición
• Gramática de las expresiones aritméticas
• Problema del “else danzante”
• Lenguajes “intrínsecamente” ambiguos

8

Teoría de Autómatas y Lenguajes Formales

Tema 8.- Gramáticas de Contexto Libre

Ambigüedad
• Definición
G es una gramática ambigua si ∃ x ∈ VT* que posee
o dos derivaciones por la izquierda diferentes
o dos derivaciones por laderecha diferentes
o dos árboles sintácticos diferentes

9

Teoría de Autómatas y Lenguajes Formales

Tema 8.- Gramáticas de Contexto Libre

Ambigüedad: expresiones aritméticas
Gramática ambigua
G 1 = (VN, VT, P1, S)
P1={
(1) S → identificador = E
(2) E → E + E
(3) E → E ∗ E
(4) E → ( E )
(5) E → identificador
(6) E → número
}
10

Teoría de Autómatas y Lenguajes FormalesTema 8.- Gramáticas de Contexto Libre

Ambigüedad: expresiones aritméticas
Primera derivación por la izquierda
S ⇒1 identificador = E

⇒2 identificador = E + E
⇒5 identificador = identificador + E
⇒3 identificador = identificador + E ∗ E
⇒6 identificador = identificador + número ∗ E
⇒5 identificador = identificador + número ∗ identificador

11

Teoría de Autómatas y Lenguajes FormalesTema 8.- Gramáticas de Contexto Libre

Ambigüedad: expresiones aritméticas
Segunda derivación por la izquierda
S ⇒1 identificador = E

⇒2 identificador = E ∗ E
⇒3 identificador = E + E ∗ E
⇒5 identificador = identificador + E ∗ E
⇒5 identificador = identificador + número ∗ E
⇒5 identificador = identificador + número ∗ identificador

12

Teoría de Autómatas y Lenguajes FormalesTema 8.- Gramáticas de Contexto Libre

Ambigüedad: expresiones aritméticas
Árbol de la primera derivación por la izquierda

13

Teoría de Autómatas y Lenguajes Formales

Tema 8.- Gramáticas de Contexto Libre

Ambigüedad: expresiones aritméticas
Árbol de la segunda derivación por la izquierda

14

Teoría de Autómatas y Lenguajes Formales

Tema 8.- Gramáticas de Contexto Libre...