¿Es C un lenguaje regular?

8

¿Son C o C ++ lenguajes regulares ? Si no, ¿en qué categoría colocamos los lenguajes de programación como C / C ++, perl, Python?

programming-languages c++ c perl Robert Harvey
fuente
No, egrep es un lenguaje regular; C no lo es.
tchrist
La mayoría de los lenguajes de programación son algún tipo de lenguaje libre de contexto. Es por eso que generalmente se representan como árbol durante la compilación. en.wikipedia.org/wiki/Context-free_grammar
Laurent Bourgault-Roy
1
@ LaurentBourgault-Roy Creo que la mayoría ni siquiera estaban libres de contexto, ya que incluso si tienen un CFG, generalmente se aplican reglas adicionales fuera del CFG
jk.
Incluso las
expresiones

Respuestas:

30

La única definición universal que conozco para "lenguaje regular" es una que puede analizarse con un autómata finito determinista, o expresarse como una verdadera expresión regular (no los RE extendidos en muchas implementaciones actuales). Una expresión regular se puede escribir en una serie de caracteres, con repeticiones potencialmente infinitas y selecciones alternativas.

Dado que tanto C como C ++ permiten anidar llaves, corchetes y paréntesis a profundidades arbitrarias, no son lenguajes regulares (consulte el Lema de bombeo para obtener más detalles).

David Thornley
fuente
2
Agregaría que ningún lenguaje de programación de ningún uso puede ser regular porque ni siquiera permitiría ningún tipo de expresiones numéricas.
Giorgio
1
@Giorgio puede expresar una expresión numérica como un lenguaje regular (una secuencia alterna de operador y número inicial y final con un número) analizar (con prioridades) las necesita una gramática aunque
monstruo de trinquete
@ratchet freak: ¿Cómo manejarías los paréntesis, por ejemplo, en (1 + 2) * 6?
Giorgio
@Giorgio debería haber agregado "sin paréntesis"
monstruo de trinquete
1
@Giorgio: Es trivialmente cierto que las expresiones postfix sintácticamente correctas no forman un lenguaje regular. No importa. Un lenguaje puede ser tanto expresivo regular como arbitrario, incluidas las expresiones postfix, siempre que la verificación de la pila se difiera hasta el tiempo de ejecución. Forth es un excelente ejemplo, y DC sería otro.
david.pfx