¿C++ es libre de contexto o sensible al contexto?

A continuación se muestra mi demostración favorita (actual) de por qué el análisis de C++ es (probablemente) completo en Turing , ya que muestra un programa que es sintácticamente correcto si y solo si un entero dado es primo.

Así que afirmo que C++ no está libre de contexto ni es sensible al contexto .

Si permite secuencias de símbolos arbitrarias en ambos lados de cualquier producción, produce una gramática de tipo 0 ("sin restricciones") en la jerarquía de Chomsky , que es más poderosa que una gramática sensible al contexto; las gramáticas sin restricciones son Turing-completas. Una gramática sensible al contexto (Tipo 1) permite múltiples símbolos de contexto en el lado izquierdo de una producción, pero el mismo contexto debe aparecer en el lado derecho de la producción (de ahí el nombre "sensible al contexto"). [1] Las gramáticas sensibles al contexto son equivalentes a las máquinas de Turing acotadas linealmente .

En el programa de ejemplo, el cálculo de los primos podría realizarse mediante una máquina de Turing acotada linealmente, por lo que no prueba del todo la equivalencia de Turing, pero la parte importante es que el analizador necesita realizar el cálculo para poder realizar el análisis sintáctico. Podría haber sido cualquier cálculo expresable como una creación de instancias de plantilla y hay muchas razones para creer que la creación de instancias de plantillas de C++ es completa en Turing. Véase, por ejemplo, el artículo de 2003 de Todd L. Veldhuizen .

De todos modos, C++ puede ser analizado por una computadora, por lo que ciertamente podría ser analizado por una máquina de Turing. En consecuencia, una gramática ilimitada podría reconocerlo. En realidad, escribir una gramática así no sería práctico, razón por la cual el estándar no intenta hacerlo. (Vea abajo.)

El problema de la "ambigüedad" de ciertas expresiones es principalmente una pista falsa. Para empezar, la ambigüedad es una característica de una gramática particular, no de un idioma. Incluso si se puede demostrar que un idioma no tiene gramáticas inequívocas, si puede reconocerse mediante una gramática libre de contexto, está libre de contexto. De manera similar, si no puede ser reconocido por una gramática libre de contexto pero puede ser reconocido por una gramática sensible al contexto, es sensible al contexto. La ambigüedad no es relevante.

Pero en cualquier caso, como en la línea 21 (ie auto b = foo<IsPrime<234799>>::typen<1>();) del programa siguiente, las expresiones no son ambiguas en absoluto; simplemente se analizan de manera diferente según el contexto. En la expresión más simple del problema, la categoría sintáctica de ciertos identificadores depende de cómo han sido declarados (tipos y funciones, por ejemplo), lo que significa que el lenguaje formal tendría que reconocer el hecho de que dos cadenas de longitud arbitraria en el mismo programa son idénticos (declaración y uso). Esto se puede modelar mediante la gramática de "copia", que es la gramática que reconoce dos copias exactas consecutivas de la misma palabra. Es fácil demostrar con el lema del bombeo que este lenguaje no está libre de contexto. Es posible una gramática sensible al contexto para este idioma, y ​​​​en la respuesta a esta pregunta se proporciona una gramática de tipo 0: https://math.stackexchange.com/questions/163830/context-SENSITIVE-grammar-for-the- lenguaje de copia .

Si uno intentara escribir una gramática sensible al contexto (o sin restricciones) para analizar C++, muy posiblemente llenaría el universo de garabatos. Escribir una máquina de Turing para analizar C++ sería una tarea igualmente imposible. Incluso escribir un programa en C++ es difícil y, hasta donde yo sé, ninguno ha demostrado ser correcto. Esta es la razón por la que el estándar no intenta proporcionar una gramática formal completa y elige escribir algunas de las reglas de análisis en inglés técnico.

Lo que parece una gramática formal en el estándar C++ no es la definición formal completa de la sintaxis del lenguaje C++. Ni siquiera es la definición formal completa del lenguaje después del preprocesamiento, que podría ser más fácil de formalizar. (Sin embargo, ese no sería el lenguaje: el lenguaje C++ tal como lo define el estándar incluye el preprocesador, y el funcionamiento del preprocesador se describe algorítmicamente, ya que sería extremadamente difícil de describir en cualquier formalismo gramatical. Está en esa sección del estándar donde se describe la descomposición léxica, incluidas las reglas donde debe aplicarse más de una vez).

Las distintas gramáticas (dos gramáticas superpuestas para el análisis léxico, una que tiene lugar antes del preprocesamiento y la otra, si es necesario, después, más la gramática "sintáctica") se recogen en el Apéndice A, con esta importante nota (énfasis añadido):

Este resumen de la sintaxis de C++ pretende ser una ayuda para la comprensión. No es una declaración exacta del idioma . En particular, la gramática descrita aquí acepta un superconjunto de construcciones C++ válidas . Se deben aplicar reglas de desambiguación (6.8, 7.1, 10.2) para distinguir expresiones de declaraciones. Además, se deben utilizar reglas de control de acceso, ambigüedad y tipos para eliminar construcciones sintácticamente válidas pero sin sentido.

Finalmente, aquí está el programa prometido. La línea 21 es sintácticamente correcta si y sólo si la N in IsPrime<N>es prima. De lo contrario, typenes un número entero, no una plantilla, por lo que typen<1>()se analiza como (typen<1)>()sintácticamente incorrecto porque ()no es una expresión sintácticamente válida.

template<bool V> struct answer { answer(int) {} bool operator()(){return V;}};

template<bool no, bool yes, int f, int p> struct IsPrimeHelper
  : IsPrimeHelper<p % f == 0, f * f >= p, f + 2, p> {};
template<bool yes, int f, int p> struct IsPrimeHelper<true, yes, f, p> { using type = answer<false>; };
template<int f, int p> struct IsPrimeHelper<false, true, f, p> { using type = answer<true>; };

template<int I> using IsPrime = typename IsPrimeHelper<!(I&1), false, 3, I>::type;
template<int I>
struct X { static const int i = I; int a[i]; }; 

template<typename A> struct foo;
template<>struct foo<answer<true>>{
  template<int I> using typen = X<I>;
};
template<> struct foo<answer<false>>{
  static const int typen = 0;
};

int main() {
  auto b = foo<IsPrime<234799>>::typen<1>(); // Syntax error if not prime
  return 0;
}

[1] Para decirlo más técnicamente, cada producción en una gramática sensible al contexto debe tener la forma:

αAβ → αγβ

donde Aes un no terminal y αposiblemente βsean secuencias vacías de símbolos gramaticales y γes una secuencia no vacía. (Los símbolos gramaticales pueden ser terminales o no terminales).

Esto puede leerse A → γsólo en el contexto [α, β]. En una gramática libre de contexto (Tipo 2) αy βdebe estar vacío.

Resulta que también puedes restringir gramáticas con la restricción "monótona", donde cada producción debe ser de la forma:

α → βdonde |α| ≥ |β| > 0  ( |α|significa "la longitud de α")

Es posible demostrar que el conjunto de lenguajes reconocidos por gramáticas monótonas es exactamente el mismo que el conjunto de lenguajes reconocidos por gramáticas sensibles al contexto y, a menudo, es más fácil basar pruebas en gramáticas monótonas. En consecuencia, es bastante común ver "sensible al contexto" usado como si significara "monótono".

Jan 29 '2013 18:01 rici