Analisador sintático LL

Um analisador sintático LL é um algoritmo de análise sintática para um sub-conjunto de gramáticas livre de contexto. Ele é dito um analisador sintático descendente (top-down) pois tenta deduzir as produções da gramática a partir do nó raíz. Ele lê a entrada de texto da esquerda para a direita, e produz uma derivação mais à esquerda (por isso LL, do termo em inglês left-left, diferente do analisador sintático LR). As gramáticas que podem ser analisadas sintaticamente usando esse tipo de analisador são chamadas gramáticas LL. Outro termo usado é analisador sintático LL(x), no qual refere-se à quantidade de tokens posteriores ao símbolo atual (ainda não consumidos da entrada) que são usados para tomar decisões na análise. Se tal analisador sintático existe para uma dada gramática, e ele pode analisar sentenças nessa gramática sem o uso de backtracking, então essa gramática é chamada gramática LL(x). Dessas gramáticas com análise posterior, as gramáticas LL(1) são as mais populares, pela necessidade de verificar somente o token posterior para a análise. Linguagens mal desenvolvidas tipicamente possuem gramáticas com um valor alto de , e necessitam de bastante esforço computacional para serem analisadas.