¿Cómo determinar si un idioma es LL (1)?

Question

Tengo una gramática y puedo verificar si LL (1) es o no. Sin embargo, ¿hay alguna manera de verificar si el lenguaje generado por la gramática es LL (1)? ¿Y cuál es exactamente la diferencia entre las gramáticas LL (1) y los lenguajes LL (1)?

Answer 1

Cualquier gramática LL (1) define un lenguaje LL (1). Por definición, un lenguaje es LL (1) si hay alguna gramática que lo genera que es LL (1), por lo que el hecho de que tenga una gramática LL (1) para el idioma automáticamente significa que el lenguaje es LL (1) .

Para elaborar, un lenguaje es un conjunto de cadenas y una gramática para ese lenguaje es un medio para describir ese idioma. Algunos lenguajes tienen gramáticas LL (1) mientras que otros no. Sin embargo, el hecho de que una gramática no sea LL (1) no significa que el lenguaje que describe no lo es. Por ejemplo, considere esta gramática:

A -> ab | ac 

Esta gramática no es LL (1), ya que contiene un primer primer conflicto/cuando se trata de predecir la producción de A al ver el terminal a. Sin embargo, se describe un (1) Idioma LL, ya que el lenguaje también es descrito por la gramática

A -> aX 
X -> b | c 

Así que el lenguaje generado por estas gramáticas (que solo contiene AB y AC) es de hecho LL (1).

Determinar si el lenguaje descrito por una gramática arbitraria es LL (1) es mucho más difícil y, a mi leal saber y entender, la única forma de hacerlo sería explicitar una gramática LL (1) para el lenguaje generado por la gramática inicial (que es engañosa) o para demostrar matemáticamente que no existe tal gramática.

Espero que esto ayude!