PUERTA | PUERTA-CS-2002 | Pregunta 43

El lenguaje C es:
(A) Un lenguaje libre de contexto
(B) Un lenguaje sensible al contexto
(C) Un lenguaje regular
(D) Parasble completamente solo por una máquina de Turing

Respuesta: (B)
Explicación: C y C++ son lenguajes sensibles al contexto .

Hay varias razones:

1. Para analizar C y C++, comienza usando un preprocesador muy potente . Estos preprocesadores inevitablemente están escritos a mano (no se basan en una base teórica como las expresiones regulares o las gramáticas libres de contexto).
2. La gramática es ambigua: tiene conflictos LR, como el conflicto if-then-else. Los analizadores normalmente resuelven esto usando el contexto (un «else» coincide con el «if» más cercano).
3. Los lexers de C y C++ requieren retroalimentación léxica para diferenciar entre nombres e identificadores de typedef. Es decir, el lexer sensible al contexto necesita la ayuda del analizador «sin contexto» para distinguir entre un identificador «foo» y un nombre typedef «foo». En este fragmento,

   int foo;
   typedef int foo;
   foo x;

   el primer «foo» es un identificador, mientras que el segundo y el tercero son nombres typedef. Debe analizar las declaraciones typedef para resolver esto (y dado que los tipos tienen paréntesis anidados, esto es definitivamente al menos tan difícil como analizar un lenguaje sin contexto).
   Esto significa que el analizador y el lexer son mutuamente recursivos, por lo que no tiene sentido decir que el analizador no tiene contexto mientras que el lexer es sensible al contexto.

Ref: C y C++ no están libres de contexto

Cuestionario de esta pregunta