Ejemplos de Lenguajes (Teoría de Lenguajes)
Ambigüedad
Una gramática es ambigua cuando hay mas de un árbol de derivación para un mismo string. Por ejemplo, en la gramática de las expresiones con un solo no terminal, hay ambiguedad tanto por la precedencia de operadores como por la asociatividad entre terminos con un mismo operador.
E -> E + E E -> E * E E -> id
En este caso, puede solucionarse introduciendo mas no terminales:
E -> E + T | T T -> T * F | F F -> (E) | id
Vale que si la gramática es no ambigua, entonces las leftmost derivations y las rightmost derivations son únicas. De hecho, un string tiene dos árboles de derivacion distintos sii tiene dos leftmost (o rightmost) derivations distintas.
Notar que hay casos donde no es posible salvar la ambiguedad. Hay lenguajes que son inherentemente ambiguos, es decir, no hay gramatica no ambigua que los pueda representar. Por ejemplo:
En este lenguaje strings con la misma cantidad de a, b, c y d no pueden derivarse de manera no ambigua por ninguna gramática libre de contexto.
Una gramática ambigua que surge frecuentemente en los lenguajes de programacion es la del if then else. La ambiguedad proviene de que el if then puede no tener una clausula else cerrandolo:
S -> if E then S S -> if E then S else S
Por ejemplo, la cadena "if A then if B then C else D" es ambigua pues no se especifica si el else pertenece al primer if o al segundo. Esto generalmente puede resolverse modificando la tabla SLR a mano, eliminando el conflicto shift reduce para que siempre opte por el shift. Esto hace que un else se vincule al if mas cercano.
Parsers
LR(0) no LL(1)
Notar que primeros de C y de D ambos incluyen a a, lo que hace que no pueda saberse por qué derivación tomar estando en S.
S -> C | D C -> aC | b D -> aD | c
NOTA: cuidado, el título dice "ejemplos de lenguajes". La gramática no es LL(1), pero el lenguaje generado (a*(b|c)) sí, porque se podría escribir con otra gramática LL(1).
Otro ejemplo más sencillo:
S -> aSb S -> ab
NOTA: Está mal, esta gramática no es LL(1) pero tampoco es LR(0), es SLR.
LR(0) no Precedencia simple
Vale que es LR(0) por no generar conflictos, y no es de precedencia simple porque se dan las relaciones b > b (segun la primer produccion) y b = b (segun la segunda).
S -> aSb | bb
No LR(1)
Genera conflicto shift-reduce con las dos últimas producciones, y en ambas el lookahead es el mismo.
S -> aSb S -> ab S -> abb
No LR(k)
Una gramática recursiva a izquierda cualquiera no es LR(k) para ningún k.
S -> Ab | Bc A -> Aa | LAMBDA B -> Ba | LAMBDA
Nota: Eso está mal. Es cierto para LL(k) pero los parsers LR si soportan recursión a izquierda y derecha.
Referencias:
- http://compilers.iecc.com/comparch/article/06-07-072
- http://seclab.cs.sunysb.edu/sekar/cse504/Parse.pdf
Además, si ese fuera el caso alcanzaría con la gramática
S -> Ab A -> Aa | LAMBDA
Pero su autómata LR(1) es bastante simple. Es más, creo que es LR(0).
LR(2) no LR(1)
Si bien la siguiente gramática no es LR(1), notar que siempre es posible generar una gramática LR(1) a partir de una LR(k) que capture el mismo lenguaje.
S -> AB A -> a B -> CD | aE C -> ab D -> bb E -> bba
LR(0)
Gramática LR(0) común y corriente.
S -> X$ X -> (X) X -> ()
SLR no LR(0)
Ejemplo de gramática SLR no LR(0), similar a la anterior.
S -> X$ X -> (X) X -> LAMBDA
LR(1) no SLR
Similar a la anterior, pero esta además de matchear igual nro de paréntesis abiertos y cerrados, matchea un único paréntesis abierto.
S -> X$ X -> Y | ( Y -> (Y)| LAMBDA
LR(1) no LALR
Mismo ejemplo que el apunte de definiciones.
S' -> S S -> aAd | bBd | aBe | bAe A -> c B -> c
Que genera el lenguaje {acd, ace, bcd, bce}. Esta gramática es LR(1). Si construímos el autómata LR(1), obtenemos el conjunto de items {[A→c.,d],[B→c.,e]} para el prefijo ac y {[A→c.,e],[B→c.,d]} para bc. Si los unimos:
A -> c., d/e B -> c., d/e
Vemos que introdujimos un conflicto reduce/reduce, dado que tanto [A→c] como [B→c] pueden ser utilizadas para reducir para los caracteres d y e.
