O reconhecimento de sentenças, ou parsing, é o procedimento que verifica se uma dada sentença pertence à linguagem gerada por uma gramática. Este procedimento é essencial para um compilador, que deve reconhecer e validar expressões de diversos tipos -- declarações, expressões aritméticas, construções de controle de execução -- no processo de construção de um código executável equivalente à expressão reconhecida.
Considere uma gramática que define um subconjunto de expressões aritméticas aceitas por alguma linguagem de programação, apresentada na Figura 3.7.
A primeira regra dessa gramática determina que a soma de uma expressão e um termo é também uma expressão. Pela segunda regra, um único termo é também uma expressão. Pela terceira regra, o produto de um termo e um fator é um termo válido. A quarta regra estabelece que um único fator é também um termo válido. Pela quinta regra, uma expressão entre parênteses é um fator. Finalmente, a sexta regra estabelece que um identificador é um fator.
Nessa gramática, é um símbolo terminal, ou seja, um token, assim como os símbolos , , ( e ). Através de uma gramática regular seria possível determinar o que é um identificador para a linguagem; por exemplo,
Considere o procedimento para o reconhecimento da expressão . No procedimento de análise léxica, a expressão sob análise seria traduzida para . O procedimento de análise sintática deve então aplicar as regras da gramática para verificar se a sentença é válida ou não. Se é possível derivar a sentença a partir do símbolo sentencial (no caso, ), então a sentença é reconhecida. Caso contrário, a sentença é inválida e deve ser rejeitada.
Usando inicialmente um procedimento informal para esse reconhecimento, é possível estabelecer que a sentença pode ser obtida a partir de pela aplicação da sexta regra, ou seja,
Por outro lado, para a sentença , o analisador reconheceria como uma sentença válida:
Nesse caso, a sentença é reconhecida como válida pois foi possível derivar a sentença a partir do símbolo sentencial usando a aplicação das regras 2, 3, 4, 5, 1, 2, 4, 4, 6, 6, e 6. Essa seqüência de regras aplicadas na derivação da sentença sob análise é conhecida como a seqüência de reconhecimento da sentença.