¿Cuál es la relación entre lenguajes de programación, expresiones regulares y lenguajes formales?

25

He buscado en la red una respuesta a esta pregunta y parece que todos saben implícitamente la respuesta, excepto yo. Presumiblemente esto se debe a que las únicas personas que se preocupan son aquellas que han recibido educación terciaria sobre el tema. Yo, por otro lado, he sido arrojado al fondo para una tarea de secundaria.

Mi pregunta es, ¿cómo se relacionan exactamente los lenguajes de programación con los lenguajes formales? En todas partes que leo, se dice algo parecido a "los lenguajes formales para definir la gramática de los lenguajes de programación".

Ahora, por lo que he podido reunir, un lenguaje formal es una serie de reglas de producción que se aplican a un conjunto específico de símbolos (el alfabeto del idioma). Estas reglas de producción definen un conjunto de transformaciones, tales como:

b -> a

aaa->c

Esto se puede aplicar de manera que:

abab->aaaa aaaa-> ca

Solo como una nota al margen, si definimos que el alfabeto de nuestro lenguaje formal es {a, b, c}, entonces a y b son terminales yc es terminal, ya que no se puede transformar (corríjame si me equivoco ese).

Entonces, dado todo eso, ¿cómo se aplica esto a los lenguajes de programación? A menudo también se afirma que regex se usa para analizar un idioma en su forma de texto para garantizar que la gramática sea correcta. Esto tiene sentido. Luego se afirma que las expresiones regulares se definen por lenguajes formales. Regex devuelve verdadero o falso (al menos en mi experiencia) dependiendo de si el autómata de estado finito que representa la expresión regular alcanza el punto objetivo. Hasta donde puedo ver, eso no tiene nada que ver con las transformaciones *.

Para la compilación del programa en sí, supongo que un lenguaje formal podría transformar el código en código de nivel consecutivamente más bajo, llegando finalmente al ensamblaje a través de un complejo conjunto de reglas, que el hardware podría entender.

Así que eso es algo desde mi punto de vista confuso. Probablemente hay muchas cosas fundamentalmente incorrectas con lo que he dicho, y es por eso que estoy pidiendo ayuda.


* A menos que considere algo como (a|b)*b*c->trueuna regla de producción, en cuyo caso la regla requiere un autómata de estado finito (es decir, regex). Esto no tiene sentido ya que acabamos de decir que

Zwander
fuente
2
Confiesas gramáticas formales con lenguajes formales . Una gramática es un conjunto de reglas de reescritura que describe un idioma. El lenguaje es el conjunto de cadenas descrito por la gramática. Entonces, una gramática es una alternativa a una expresión regular: es una forma de describir un lenguaje.
reinierpost
@reinierpost Tienes toda la razón, después de leer las notas de la conferencia de la universidad de donde obtuve parte de esta información, veo mi error.
Zwander
Compartí tu confusión cuando empecé. Por supuesto, las gramáticas también forman un lenguaje, al igual que las expresiones regulares. Pero la teoría formal del lenguaje se dedica a estudiar cómo se puede describir la sintaxis (forma) de los lenguajes, por lo que generalmente usa el término 'lenguaje' para lo que se describe, no para describirlo.
reinierpost

Respuestas:

24

Quien le dijo que las expresiones regulares se utilizan para analizar el código estaba difundiendo desinformación. Clásicamente (no sé en qué medida esto es cierto en los compiladores modernos), el análisis del código (conversión de código de texto a árbol de sintaxis) se compone de dos etapas:

  1. Análisis léxico: procesa el texto sin procesar en fragmentos como palabras clave , constantes numéricas , cadenas , identificadores , etc. Esto se implementa clásicamente utilizando algún tipo de máquina de estados finitos, similar en espíritu a un autómata finito determinista (DFA).

  2. Analizador: se ejecuta después del análisis léxico y convierte el texto sin formato en un árbol de sintaxis anotado. La gramática de los lenguajes de programación es (a primera aproximación) libre de contexto (en realidad, uno necesita un subconjunto aún más estricto), y esto permite que ciertos algoritmos eficientes analicen el código lexificado en un árbol de sintaxis. Esto es similar al problema de reconocer si una cadena dada pertenece a alguna gramática libre de contexto, la diferencia es que también queremos la prueba en forma de un árbol de sintaxis.

Las gramáticas para lenguajes de programación se escriben como gramáticas libres de contexto, y los generadores de analizadores utilizan esta representación para construir analizadores rápidos para ellos. Un ejemplo simple tendría una DECLARACIÓN no terminal y luego reglas de la forma DECLARACIÓN DECLARACIÓN DE IF, donde DECLARACIÓN DE IF si CONDITION entonces BLOCK endif, o similar (donde BLOCK STATEMENT | BLOCK; STATEMENT, por ejemplo). Por lo general, estas gramáticas se especifican en forma Backus-Naur (BNF).

Las especificaciones reales de los lenguajes de programación no están libres de contexto. Por ejemplo, una variable no puede aparecer si no se ha declarado en muchos idiomas, y los idiomas con escritura estricta podrían no permitirle asignar un entero a una variable de cadena. El trabajo del analizador es solo convertir el código sin formato en un formulario que sea más fácil de procesar.

Debo mencionar que hay otros enfoques, como el análisis de descenso recursivo que en realidad no genera un árbol de análisis, sino que procesa su código a medida que lo analiza. Aunque no se molesta en generar el árbol, en todos los demás aspectos funciona al mismo nivel que el descrito anteriormente.

Yuval Filmus
fuente
Gracias por su respuesta, sin duda aclaró algunas cosas. También trajo muchas más preguntas. ¿Debo agregarlos a mi pregunta o preguntarlos aquí?
Zwander
55
@Zwander - en realidad, tampoco. En este sitio, queremos que escriba una pregunta por pregunta. No es un foro de discusión: es un sitio de preguntas y respuestas, y queremos que cada pregunta esté en un hilo separado. Si esta respuesta plantea una nueva pregunta, dedique un tiempo a investigar esa pregunta de seguimiento, y si no puede encontrar una respuesta en ninguna de las fuentes estándar, publique una nueva pregunta. (Pero asegúrese de mirar primero los recursos estándar).
DW
1
@DW Gotcha, saludos.
Zwander
3
La primera de las dos etapas que menciona generalmente se realiza mediante expresiones regulares. El formato de cada token generalmente viene dado por una expresión regular. Esas expresiones regulares se compilan en un solo DFA, el DFA se aplica al código real.
Kasperd
2
El análisis de descenso recursivo de @Zwander es solo una técnica de análisis. Puede o no generar un árbol de análisis. En general, el algoritmo de análisis equivale a desarrollar una estrategia computacional para explorar el árbol de sintaxis implícito en el texto del programa. Este árbol de sintaxis / análisis puede o no ser explicitado en el proceso, dependiendo de la estrategia de compilación (número de etapas). Sin embargo, lo que es necesario es que finalmente haya al menos una exploración ascendente del árbol de análisis, ya sea explícito o dejado implícito en la estructura de cálculo.
babou
12

Esto es algo pesado para una tarea de secundaria.

La respuesta de Yuval Filmus es realmente buena, por lo que es más una respuesta complementaria para aclarar algunos de los puntos que hizo.

Un lenguaje formal es una construcción matemática. Su uso para lenguajes de programación es solo uno de los muchos usos posibles; de hecho, el lingüista Noam Chomsky hizo contribuciones significativas a la teoría inicial de los idiomas formales. Inventó la Jerarquía Chomsky, que clasifica los idiomas formales en regulares, sin contexto, etc. Los idiomas formales también se aplican en lingüística para describir la sintaxis de los idiomas naturales como el inglés. Piénselo como los números reales: podemos usar los números reales para describir cosas concretas como la distancia de Los Ángeles a Nueva York, y cosas abstractas como la razón de la circunferencia de un círculo a su diámetro. Aunque ambas cosas existen independientemente de los números reales, los números reales son un sistema útil para describirlos. Los lenguajes formales son un sistema útil para describir tanto inglés como Python, porque ambos tienen un formato estructurado similar.

una+si+do=reuna+si=re-dounasido como cantidades en dólares, por ejemplo, y luego la ecuación tiene significado.

Clásicamente, un lenguaje de programación tendrá dos gramáticas: una gramática léxica y una gramática sintáctica. La gramática léxica trata con caracteres como letras, punto y coma, llaves y paréntesis. Por lo general, es una gramática regular, por lo que se puede expresar con expresiones regulares o un DFA o NFA. (Hay pruebas en la teoría del lenguaje formal que muestran que los tres son equivalentes en potencia, lo que significa que aceptan el mismo conjunto de idiomas). La fase lexing del compilador o intérprete es una especie de mini intérprete para la gramática del lenguaje regular. Lee las reglas de la gramática y, siguiendo esas reglas, agrupa los caracteres individuales en fichas. Por ejemplo, si el lenguaje tiene una ifdeclaración que se parece más o menos a las C, el lexer podría agrupar los caracteres iy fconvertirlos en una sola fichaIF, luego busque un paréntesis de apertura y genere un token OPEN_PAREN, luego maneje lo que esté entre paréntesis y luego encuentre el paréntesis de cierre y genere a CLOSE_PAREN. Cuando el lexer termina de hacer tokens, los entrega al analizador, lo que determina si los tokens realmente forman declaraciones válidas del lenguaje de programación. Entonces, si escribe ip a == ben Python, el lexer hace todo lo posible para adivinar qué tipo de token ipes (probablemente la mayoría de los lexers lo tomaría como un identificador), y lo pasa al analizador, que se queja porque no puede tener un token identificador en esa posición.

unasi

Veamos las reglas gramaticales para la ifdeclaración de Python . Esta es la regla:

if_stmt: 'if' test ':' suite ('elif' test ':' suite)* ['else' ':' suite]

Esa regla nos dice cómo el analizador determinará si una cadena de tokens enviados desde el lexer es una ifdeclaración. Cualquier palabra entre comillas simples debe aparecer, así, en el código fuente, por lo que el analizador buscará la palabra simple if. El analizador intentará hacer coincidir algunos tokens con la regla para test:

test: or_test ['if' or_test 'else' test] | lambdef

testse define en términos de otras reglas en la gramática. Observe cómo testtambién se incluye a sí mismo en su definición; Eso se llama una definición recursiva. Es el gran poder de los lenguajes libres de contexto que los lenguajes normales no tienen, y permite definir cosas como bucles anidados para la sintaxis del lenguaje de programación.

Si el analizador logra hacer coincidir algunas fichas test, intentará hacer coincidir dos puntos. Si eso tiene éxito, intentará hacer coincidir algunos tokens más usando la regla para suite. La sección ('elif' test ':' suite)*significa que podemos tener cualquier número de repeticiones del texto literal elif, seguido de algo que coincida test, seguido de dos puntos, seguido de algo que coincida suite. También podemos tener cero repeticiones; el asterisco al final significa "cero o tantos como queramos".

Al final es ['else' ':' suite]. Esa parte está encerrada entre corchetes; eso significa que podemos tener cero o uno, pero no más. Para hacer coincidir esto, el analizador debe coincidir con el texto literal else, dos puntos y luego a suite. Aquí está la regla para un suite:

suite: simple_stmt | NEWLINE INDENT stmt+ DEDENT

Básicamente es un bloque en lenguajes tipo C. Como Python utiliza saltos de línea y el sangrado para cosas malas, las salidas analizadoras NEWLINE, INDENTy DEDENTfichas para comunicar al analizador, donde una nueva línea comenzado, donde se inició el código tenga una sangría, y en la que se volvió al nivel exterior de sangría.

Si alguno de estos intentos de coincidencia falla, el analizador señala un error y se detiene. Si el análisis de todo el programa tiene éxito, el analizador generalmente habrá construido un árbol de análisis como Yuval cubrió en su respuesta, y posiblemente una tabla de símbolos y otras estructuras de datos que almacenan información semántica. Si el idioma se escribe estáticamente, el compilador recorrerá el árbol de análisis y buscará errores de tipo. También recorre el árbol de análisis para generar código de bajo nivel (lenguaje ensamblador, código de bytes Java, lenguaje intermedio .Net o algo similar) que es lo que realmente se ejecuta.

Como ejercicio, recomendaría tomar la gramática de algún lenguaje de programación con el que esté familiarizado (nuevamente, Python , Java , y aquí está C # , Javascript , C ) e intente analizar a mano algo simple, como quizás x = a + b;o if (True): print("Yay!"). Si está buscando algo más simple, también hay una buena gramática para JSON , que básicamente cubre solo la sintaxis de los literales de objetos en Javascript (como {'a': 1, 'b': 2}). Buena suerte, esto es algo increíble, pero resulta ser realmente interesante cuando no estás en una fecha límite loca.

tsleyson
fuente
Sé que se supone que no debo publicar "gracias" aquí, pero me alegro por tomarse el tiempo para explicar todo esto. "Esto es algo pesado para una tarea de secundaria". La intención de la tarea es pasar por encima y hablar sobre expresiones regulares, pero como un ávido estudiante de ciencias de la computación, quería tener una idea completa. Todo el tema es fascinante.
Zwander
1
@Zwander Me acabo de graduar de la universidad, y la mayoría de mis asignaturas optativas eran cosas como esta. Recuerdo estar totalmente confundido y, sin embargo, totalmente absorto. También le pueden gustar los documentos sobre diseño de compiladores mencionados en este blog , o los libros Introducción a la teoría de la computación , de Michael Sipser, y John C. Martin, Introducción a los lenguajes y la teoría de la computación . Puede encontrar copias usadas baratas en Amazon. Ambos hacen que la teoría del lenguaje formal sea lo más simple posible.
tsleyson
10

En una palabra

Los lenguajes de programación se componen de una sintaxis que representa el programa como cadenas de caracteres y una semántica que es el significado previsto del programa.

Los lenguajes formales son sintaxis sin significado. Su objetivo es estudiar la estructura de conjuntos de cadenas definidas formalmente, sin por lo general atribuir significado a esas cadenas.

La expresión regular y otros formalismos (como las gramáticas sin contexto) se utilizan para definir lenguajes formales, utilizados como componentes sintácticos de programación y lenguajes naturales, es decir, para representar oraciones de forma estructurada. Se utilizan otros mecanismos para relacionar esa estructura con la semántica de los lenguajes de programación.

Mucho aquí se simplifica considerablemente, particularmente con respecto al lenguaje natural.

Con muchos mas detalles

Para responder a su pregunta, debemos comenzar desde el principio. Un lenguaje en el sentido habitual es, informalmente, un medio para transmitir información o ideas. En un lenguaje, generalmente se distingue entre sintaxis y semántica. La semántica es de lo que quieres hablar / escribir. la información que quieres transmitir. La sintaxis es el medio que utiliza para transmitirla, es decir, una representación convencional que se puede intercambiar entre personas, y ahora también entre personas y dispositivos, o entre dispositivos (computadoras).

Por lo general, usará la palabra dogpara transmitir la idea de un perro. La palabra dogestá hecha de tres letras, o algún sonido equivalente, y está destinada a ser la representación de algún tipo de animal. La idea clave es que la comunicación se realiza a través de la representación de lo que se debe comunicar. Las estructuras de representación generalmente se llaman sintaxis, mientras que lo que se representa se llama semántica. Esto va más o menos para el lenguaje natural, así como para los lenguajes de programación.

Las palabras son entidades sintácticas para representar conceptos semánticos más o menos elementales. Pero estos conceptos elementales tienen que reunirse de varias maneras para dar un significado más complejo. Escribimos the dogpara transmitir que nos referimos a un perro específico, y the dog bites the catpara transmitir una idea más compleja. Pero la forma en que se organizan las palabras tiene que estar fijada por reglas, de modo que podamos saber cuál de los perros y gatos realmente muerde al otro.

Por lo tanto, tenemos reglas como esas sentence -> subject verb complementque se supone que coinciden con las oraciones y nos dicen cómo se articulan las ideas asociadas con cada parte. Estas reglas son reglas sintácticas, ya que nos dicen cómo se debe organizar la representación de nuestro mensaje. El subjectmismo puede ser definido por una regla subject -> article noun, y así sucesivamente.

2X+1=23X123

equation -> expression "=" expression  
expression -> expression "+" expression 
expression -> number

La estructura de los lenguajes de programación es la misma. Los lenguajes de programación están semánticamente especializados en expresar cálculos a realizar, en lugar de expresar problemas a resolver, prueba de teoremas o relaciones amistosas entre animales. Pero esa es la principal diferencia.

Las representaciones utilizadas en la sintaxis suelen ser cadenas de caracteres o de sonidos para los idiomas hablados. La semántica generalmente pertenece al dominio abstracto, o posiblemente a la realidad, pero aún se abstrae en nuestros procesos de pensamiento, o al dominio conductual de los dispositivos. La comunicación implica codificar la información / idea en sintaxis, que es transmitida y decodificada por el receptor. El resultado se interpreta de cualquier manera por el receptor.

Entonces, lo que vemos del lenguaje es principalmente la sintaxis y su estructura. Los ejemplos anteriores son solo una de las formas más comunes de definir cadenas sintácticas y su organización estructural. Hay otros. Para un idioma dado, a algunas cadenas se les puede asignar una estructura, y se dice que pertenecen al idioma, mientras que otras no.

Lo mismo es cierto para las palabras. Algunas secuencias de letras (o sonido) son palabras legítimas, mientras que otras no lo son.

Los lenguajes formales son solo sintaxis sin semántica. Definen con un conjunto de reglas qué secuencias se pueden construir, utilizando los elementos básicos de un alfabeto. Cuáles son las reglas pueden ser muy variables, a veces complejas. Pero los lenguajes formales se usan para muchos propósitos matemáticos más allá de la comunicación lingüística, ya sea para lenguajes naturales o de programación. El conjunto de reglas que definen las cadenas en un idioma se llama gramática. Pero hay muchas otras formas de definir idiomas.

En la práctica, un lenguaje está estructurado en dos niveles. El nivel léxico define palabras construidas a partir de un alfabeto de caracteres. El nivel sintáctico define oraciones o programas construidos a partir de un alfabeto de palabras (o más precisamente de familias de palabras, para que siga siendo un alfabeto finito). Esto es necesariamente algo simplificado.

La estructura de las palabras es bastante simple en la mayoría de los lenguajes (de programación o naturales), por lo que generalmente se definen con lo que generalmente se considera el tipo más simple de lenguaje formal: los lenguajes regulares. Se pueden definir con expresiones regulares (regexp) y se identifican con bastante facilidad con dispositivos programados llamados autómatas de estado finito. En los casos de lenguajes de programación, los ejemplos de una palabra son un identificador, un número entero, una cadena, un número real, una palabra reservada comoif o repeat, un símbolo de puntuación o un paréntesis abierto. Ejemplos de familias de palabras son identificador, cadena, entero.

El nivel sintáctico generalmente se define por un tipo de lenguaje formal un poco más complejo: los lenguajes libres de contexto, que usan las palabras como alfabeto. Las reglas que hemos visto anteriormente son reglas sin contexto para el lenguaje natural. En el caso de los lenguajes de programación, las reglas pueden ser:

statement -> assignment
statement -> loop
loop ->  "while" expression "do" statement
assignment -> "identifier" "=" expression
expression -> "identifier"
expression -> "integer"
expression -> expression "operator" expression

Con tales reglas puedes escribir:

while aaa /= bbb do aaa = aaa + bbb / 6 Que es una declaración.

Y la forma en que se produjo puede representarse mediante una estructura de árbol llamada árbol de análisis o árbol de sintaxis (no completo aquí):

                          statement
                              |
            _______________  loop _______________
           /      /                 \            \
      "while" expression           "do"       statement
       __________|_________                       |
      /          |         \                  assignment
 expression "operator" expression          _______|_______
     |           |          |             /       |       \
"identifier"   "/="   "identifier" "identifier"  "="   expression
     |                      |            |                 |
    aaa                    bbb          aaa             ... ...

Los nombres que aparecen a la izquierda de una regla se llaman no terminales, mientras que las palabras también se llaman terminales, ya que están en el alfabeto del idioma (por encima del nivel léxico). Los no terminales representan las diferentes estructuras sintácticas que se pueden usar para componer un programa.

Dichas reglas se denominan libres de contexto, porque un no terminal puede reemplazarse arbitrariamente utilizando cualquiera de las reglas correspondientes, independientemente del contexto en el que aparece. El conjunto de reglas que definen el lenguaje se llama gramática libre de contexto.

En realidad, existen restricciones al respecto, cuando los identificadores deben declararse por primera vez, o cuando una expresión debe satisfacer las restricciones de tipo. Pero dicha restricción puede considerarse semántica, en lugar de sintáctica. En realidad, algunos profesionales los ubican en lo que llaman semántica estática .

Dada cualquier oración, cualquier programa, el significado de esa oración se extrae analizando la estructura dada por el árbol de análisis para esta oración. Por lo tanto, es muy importante desarrollar algoritmos, llamados analizadores, que puedan recuperar la estructura de árbol correspondiente a un programa, cuando se les da el programa.

El analizador léxico precede al analizador que reconoce las palabras y determina la familia a la que pertenecen. Luego, la secuencia de palabras, o elementos léxicos, se le da al analizador que recupera la estructura de árbol subyacente. A partir de esta estructura, el compilador puede determinar cómo generar código, que es la parte semántica del procesamiento del programa en el lado del compilador.

El analizador de un compilador puede construir una estructura de datos correspondiente al árbol de análisis y pasarlo a las etapas posteriores del proceso de compilación, pero no es necesario. Ejecutar el algoritmo de análisis equivale a desarrollar una estrategia computacional para explorar el árbol de sintaxis implícito en el texto del programa. Este árbol de sintaxis / análisis puede o no ser explicitado en el proceso, dependiendo de la estrategia de compilación (número de etapas). Sin embargo, lo que es necesario es que finalmente haya al menos una exploración ascendente del árbol de análisis, ya sea explícito o dejado implícito en la estructura de cálculo.

La razón de esto, intuitivamente, es que una forma formal estándar para definir la semántica asociada a una estructura de árbol sintáctico es por medio de lo que se llama homomorfismo. No temas a la gran palabra. La idea es considerar que el significado del todo se construye a partir del significado de las partes, sobre la base del operador que las conecta.

Por ejemplo, la oración the dog bites the catse puede analizar con la regla sentence -> subject verb complement. Conocer el significado de los 3 subárboles subject, verby complementla regla que los compone nos dice que el sujeto está haciendo la acción y que el gato es el que es mordido.

Esta es solo una explicación intuitiva, pero se puede formalizar. La semántica se construye hacia arriba a partir de los constituyentes. Pero esto esconde mucha complejidad.

El funcionamiento interno de un compilador se puede descomponer en varias etapas. El compilador real puede trabajar etapa por etapa, utilizando representaciones intermedias. También puede fusionar algunas etapas. Esto depende de la tecnología utilizada y de la complejidad de compilar el idioma en cuestión.

babou
fuente
Impresionante, muy útil. Entiendo que la expresión regular se usa en el proceso de tokenización (por ejemplo, un literal de cadena se puede definir "[^"]*"en su forma más simple, ignorando los caracteres de escape, etc.), pero ¿también se usa para crear el árbol de sintaxis (Hablar en términos de lenguajes de programación)? Supongo que no, como un autómata de estado finito es, por definición, finito. Un árbol de sintaxis, incluso para una sola ifdeclaración, puede ser teóricamente infinito debido a la anidación. Por lo tanto, regex, al ser un autómata de estado finito, no puede usarse con el propósito de generar un árbol de sintaxis.
Zwander
@Zwander thx 4 edición: su ejemplo de expresión regular es correcto (debería haber dado algunos ejemplos). Por cierto, Regex es también un lenguaje, con su propia semántica en el mundo de los conjuntos de cadenas, y con una sintaxis sin contexto ( CF ). Se usa solo para la tokenización de cadenas de lenguaje, al menos para lenguajes de programación, no generalmente para definir la sintaxis más grande utilizada para los árboles de sintaxis, excepto como abreviatura en BNF extendido (EBNF). Agregar Regex de alguna forma a formalismos más complejos no cambia su poder expresivo en la mayoría de los casos. Sus comentarios sobre el infinito no son del todo correctos. Ver siguiente comentario.
babou
@Zwander Todos los formalismos (lenguajes formales) se describen detalladamente. Esa es una hipótesis fundamental. Incluso si está interesado, por ejemplo, en la gramática CF con un número infinito de reglas, debe dar una descripción finita de ese infinito de reglas. También el infinito te juega trucos (no hay espacio para eso). Una ifdeclaración es ilimitada (arbitrariamente grande) pero siempre finita. Un infinito finitamente definido ifes a while. La diferencia entre CF y regular es que CF controla / permite el anidamiento (es decir, paréntesis) mientras que regular no lo hace. Pero ambos se describen de forma finita y permiten cadenas ilimitadas.
babou
1
@Zwander El formalismo debe ser capaz de representar cualquier oración bien formada (programa), pero solo oraciones bien formadas. Para decirlo (también) simplemente, FSA no puede contar sin límites. Por lo tanto, no pueden saber cuántos paréntesis se han abierto que deberían cerrarse, o anidan correctamente dos tipos diferentes de paréntesis. Muchas estructuras lingüísticas tienen paréntesis "ocultos". No es simplemente una cuestión de verificación de sintaxis, sino que implica principalmente que la estructura de árbol apropiada no se puede expresar y construir, de la cual derivar la semántica. Recuperar una estructura de árbol adecuada requiere hacer el recuento.
babou
1
@Zwander Una observación que luego puede serle útil es que los árboles se pueden linealizar simplemente como una cadena usando paréntesis. Por lo general, eso es lo que se hace cuando se escribe entre paréntesis una expresión aritmética, como(((UNA-si)+3)×do)para asegurarse de que cada operador obtenga el subárbol adecuado (subexpresión). Existe una estrecha relación entre las pilas de pashdown (ver autómatas pushdown), los lenguajes sin contexto y los árboles.
babou
2

Hay diferencias significativas El principal de ellos, diría, es que analizar lenguajes de programación reales se trata de manejar errores de sintaxis. Con un lenguaje formal, simplemente diría "bueno, no está en el idioma", pero un compilador que dice que no es muy útil: debería decirle qué está mal y, si fue un pequeño error, idealmente siga analizando para que pueda Informar más errores. Se requiere mucha investigación (y esfuerzo de implementación). Entonces, realmente no te importa tanto el resultado verdadero / falso, solo quieres analizar la estructura de la entrada. Los lenguajes formales se usan como una herramienta allí, y hay mucha superposición, pero realmente estás resolviendo un problema diferente.

Además, en la mayoría de los idiomas se ha elegido no aplicar ciertas cosas en la gramática , por ejemplo, el ejemplo que mencionó, "una variable no puede aparecer si no se hubiera declarado". Por lo general, eso es algo que el analizador ignoraría por completo, y luego quedaría atrapado en un análisis separado (análisis semántico) que analiza ese tipo de cosas y no se ve afectado por consideraciones como la libertad de contexto. Pero no siempre: por ejemplo, para analizar C, a menudo se usa el truco lexer , y C ++ es un ejemplo famoso de un lenguaje que no se puede analizar sin hacer simultáneamente un análisis semántico serio (en realidad, analizar C ++ es indecidible, porque las plantillas son Turing completo ) Sin embargo, en idiomas más simples tiende a dividirse, es más fácil de esa manera.

harold
fuente
1

Un lenguaje formal es un conjunto de palabras, donde una palabra es una cadena de símbolos de algún alfabeto.

Esto significa que su acoplamiento de las reglas de producción y el lenguaje formal es demasiado fuerte. No es correcto que el lenguaje formal sea las reglas de producción. Más bien, las reglas de producción definen el lenguaje formal. El lenguaje formal son las palabras que puede producir la regla de producción. (Esto requiere que el lenguaje formal sea del tipo que se puede definir mediante reglas de producción, por ejemplo, los lenguajes regulares se pueden definir mediante una gramática libre de contexto)

Entonces, el lenguaje regular correspondiente a la expresión (a|b)*c*destá definido por las reglas de producción;

S->ACd
A->
A->aA
A->bA
C->
C->cC

Las palabras que generan estas reglas de producción a partir del símbolo de inicio S son precisamente aquellas cadenas que acepta la expresión regular.

Taemyr
fuente
0

Existe otra relación entre las expresiones regulares y los lenguajes de programación que tiene que ver con la semántica. Las construcciones de control básicas de un lenguaje imperativo son la composición secuencial (hacer A y luego B), la elección (hacer A o B) y la repetición (hacer A una y otra vez).

Las mismas tres formas de combinar comportamientos se encuentran en expresiones regulares. Agregue llamadas de subrutina y tendrá una analogía con EBNF.

Entonces, hay mucha similitud entre el álgebra de expresiones regulares y el álgebra de comandos. Esto es explorado en detalle por Dijkstra en "La unificación de tres cálculos". También es la base del CCS de Milner, que proporciona una respuesta a la pregunta: ¿qué pasa si agregamos paralelismo?

Theodore Norvell
fuente