Qual é a relação entre linguagens de programação, expressões regulares e linguagens formais

Procurei na net uma resposta para essa pergunta e parece que todo mundo sabe implicitamente a resposta, exceto eu. Presumivelmente, isso ocorre porque as únicas pessoas que se importam são aquelas que tiveram educação superior sobre o assunto. Eu, por outro lado, fui jogado no fundo do poço por um trabalho no ensino médio.

Minha pergunta é: como exatamente as linguagens de programação estão relacionadas às linguagens formais? Em todo lugar que leio, algo como "linguagens formais são usadas para definir a gramática das linguagens de programação" é dito.

Agora, pelo que pude reunir, uma linguagem formal é uma série de regras de produção que se aplicam a um conjunto específico de símbolos (o alfabeto da linguagem). Essas regras de produção definem um conjunto de transformações, como:

b -> a

aaa->c

Isso pode ser aplicado de modo que:

abab->aaaa aaaa-> ca

Apenas como uma observação lateral, se definirmos que o alfabeto da nossa linguagem formal como {a, b, c}, então aeb são não terminais ec é terminal, pois não pode ser transformado (por favor, corrija-me se estiver errado sobre aquele).

Então, considerando tudo isso, como isso se aplica às linguagens de programação? Muitas vezes, também é declarado que o regex é usado para analisar um idioma em sua forma de texto para garantir que a gramática esteja correta. Isso faz sentido. Em seguida, afirma-se que o regex é definido por linguagens formais. Regex retorna true ou false (pelo menos em minha experiência), dependendo se o autômato de estado finito que representa o regex atinge o ponto do objetivo. Tanto quanto posso ver, isso não tem nada a ver com transformações *.

Para a compilação do próprio programa, suponho que uma linguagem formal seria capaz de transformar código em código consecutivamente de nível inferior, chegando a um assembly por meio de um conjunto complexo de regras, que o hardware poderia entender.

Então isso é coisas do meu ponto de vista confuso. Provavelmente há muitas coisas fundamentalmente erradas com o que eu disse, e é por isso que estou pedindo ajuda.

* A menos que você considere algo como (a|b)*b*c->trueuma regra de produção, nesse caso, a regra exige um autômato de estado finito (por exemplo: regex). Isso não faz sentido, como acabamos de dizer que

Quem quer que tenha dito que expressões regulares são usadas para analisar código estava espalhando desinformação. Classicamente (não sei até que ponto isso é verdade nos compiladores modernos), a análise de código - conversão de código de texto em uma árvore de sintaxe - é composta de dois estágios:

1. Análise lexical: processa o texto bruto em pedaços , como palavras-chave , constantes numéricas , seqüências de caracteres , identificadores e assim por diante. Isso é implementado classicamente usando algum tipo de máquina de estados finitos, semelhante em espírito a um autômato finito determinístico (DFA).

2. Analisador: execute uma análise lexical e converte o texto bruto em uma árvore de sintaxe anotada. A gramática das linguagens de programação é (para primeira aproximação) livre de contexto (na verdade, é preciso um subconjunto ainda mais rigoroso), e isso permite que certos algoritmos eficientes analisem o código lexificado em uma árvore de sintaxe. Isso é semelhante ao problema de reconhecer se uma determinada string pertence a alguma gramática livre de contexto, a diferença é que também queremos a prova na forma de uma árvore de sintaxe.

Gramáticas para linguagens de programação são escritas como gramáticas livres de contexto, e essa representação é usada pelos geradores de analisadores para construir analisadores rápidos para eles. Um exemplo simples teria alguma declaração não terminal e, em seguida, regras no formato STATEMENT IF-STATEMENT, onde IF-STATEMENT se CONDITION então BLOCK endif, ou similar (onde BLOCK STATEMENT | BLOCK; STATEMENT, para exemplo). Geralmente essas gramáticas são especificadas na forma Backus-Naur (BNF).→ $\to$$\to$$\to$

As especificações reais das linguagens de programação não são livres de contexto. Por exemplo, uma variável não pode aparecer se não tiver sido declarada em muitos idiomas, e idiomas com digitação estrita podem não permitir que você atribua um número inteiro a uma variável de sequência. O trabalho do analisador é apenas converter o código bruto em um formulário mais fácil de processar.

Devo mencionar que existem outras abordagens, como a análise descendente recursiva, que na verdade não gera uma árvore de análise, mas processa seu código à medida que o analisa. Embora não se preocupe em gerar a árvore, em todos os outros aspectos, ela opera no mesmo nível descrito acima.

Isso é algo pesado para uma tarefa do ensino médio.

A resposta de Yuval Filmus é realmente boa, então essa é mais uma resposta suplementar para esclarecer alguns dos pontos que ele fez.

Uma linguagem formal é uma construção matemática. Seu uso para linguagens de programação é apenas um dos muitos usos possíveis; de fato, o linguista Noam Chomsky fez contribuições significativas para a teoria inicial das línguas formais. Ele inventou a hierarquia de Chomsky, que classifica os idiomas formais em regular, sem contexto etc. Os idiomas formais também são aplicados na linguística para descrever a sintaxe de idiomas naturais como o inglês. Pense nisso como os números reais: podemos usar os números reais para descrever coisas concretas, como a distância de Los Angeles a Nova York, e coisas abstratas, como a razão entre a circunferência de um círculo e seu diâmetro. Embora essas duas coisas existam independentemente dos números reais, os números reais são um sistema útil para descrevê-los. Linguagens formais são um sistema útil para descrever o inglês e o Python, porque ambos têm um formato estruturado semelhante.

Linguagens formais são apenas manipulações de símbolos; eles não dizem nada sobre o significado dos símbolos. Pense em um problema de álgebra como . Essa equação não tem significado inerente, mas ainda podemos manipular os símbolos de acordo com as regras da álgebra; por exemplo, podemos reescrevê-lo como , mesmo que não tenhamos idéia do significado dos símbolos. Uma maneira de dar significado aos símbolos dentro de um sistema é chamada de semântica (nas linguagens natural e de programação). Assim, poderíamos interpretar , e como valores em dólares, por exemplo, e então a equação tem significado.a + b = d - c a b $a + b + c = d$$a + b = d - c$$a$$b$$c$

Classicamente, uma linguagem de programação terá duas gramáticas: uma gramática lexical e uma gramática sintática. A gramática lexical lida com caracteres como letras, ponto e vírgula, chaves e parênteses. Geralmente, é uma gramática comum, portanto pode ser expressa com expressões regulares ou um DFA ou NFA. (Existem provas na teoria formal da linguagem mostrando que as três são equivalentes em poder - o que significa que aceitam o mesmo conjunto de línguas.) A fase de lexing do compilador ou intérprete é uma espécie de mini-intérprete para a gramática regular da linguagem. Ele lê as regras da gramática e, seguindo essas regras, agrupa caracteres individuais em tokens. Por exemplo, se o idioma tiver uma ifdeclaração que se pareça mais com Cs, o lexer poderá agrupar os caracteres ie fno token únicoIF, procure um parêntese de abertura e faça a saída de um token OPEN_PAREN, manipule o que estiver entre parênteses e encontre o parêntese de fechamento e faça a saída a CLOSE_PAREN. Quando o lexer termina de criar tokens, ele os entrega sobre o analisador, que determina se os tokens realmente formam instruções válidas da linguagem de programação. Portanto, se você escrever ip a == bem Python, o lexer fará o possível para adivinhar que tipo de token ip(provavelmente seria usado como identificador pela maioria dos lexers) e o passará para o analisador, que reclama porque você não pode ter um identificador nessa posição.

O analisador implementa a gramática sintática, que geralmente é livre de contexto, embora, como menciona a resposta de Yuval, a maioria das linguagens de programação atualmente não use todas as habilidades das gramáticas sem contexto para tornar a análise mais simples e eficiente. Aqui está a gramática sintática do Python , escrita em uma variante da forma Backus-Naur, que é uma ligeira variante do formato a no OP. A especificação da linguagem Java também possui exemplos das gramáticas lexicais e sintáticas de Java.$a \rightarrow b$

Vejamos as regras gramaticais para a ifdeclaração do Python . Esta é a regra:

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

Essa regra nos diz como o analisador descobrirá se uma sequência de tokens enviados do lexer é uma ifdeclaração. Qualquer palavra entre aspas simples precisa aparecer, assim, no código fonte, para que o analisador procure a palavra simples if. O analisador tentará corresponder alguns tokens à regra para test:

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

testé definido em termos de outras regras na gramática. Observe como testtambém se inclui em sua definição; isso é chamado de definição recursiva. É o grande poder das linguagens livres de contexto que as linguagens regulares não possuem e permite que coisas como loops aninhados sejam definidas para a sintaxe da linguagem de programação.

Se o analisador conseguir corresponder alguns tokens test, ele tentará corresponder dois pontos. Se isso der certo, ele tentará combinar mais alguns tokens usando a regra para suite. A seção ('elif' test ':' suite)*significa que podemos ter qualquer número de repetições do texto literal elif, seguido de algo que corresponda test, seguido de dois pontos, seguido de algo que corresponda suite. Também podemos ter zero repetições; o asterisco no final significa "zero ou quantos quisermos".

No final é ['else' ':' suite]. Essa parte está entre colchetes; isso significa que podemos ter zero ou um, mas não mais. Para corresponder a isso, o analisador precisa corresponder ao texto literal else, dois pontos e depois a suite. Aqui está a regra para suite:

suite: simple_stmt | NEWLINE INDENT stmt+ DEDENT

É basicamente um bloco em idiomas do tipo C. Desde Python usa novas linhas e recuo para coisas ruins, as saídas lexer NEWLINE, INDENTe DEDENTfichas para contar o analisador, onde uma nova linha iniciada, em que o código começou a ser recuado, e onde ele foi devolvido ao nível exterior de recuo.

Se alguma dessas tentativas de correspondência falhar, o analisador sinaliza um erro e para. Se a análise de todo o programa for bem-sucedida, o analisador geralmente criará uma árvore de análise conforme Yuval abordou em sua resposta, e possivelmente uma tabela de símbolos e outras estruturas de dados que armazenam informações semânticas. Se o idioma for digitado estaticamente, o compilador percorrerá a árvore de análise e procurará por erros de tipo. Ele também percorre a árvore de análise para gerar código de baixo nível (linguagem assembly, Java bytecode, .Net Intermediate Language ou algo semelhante), que é o que realmente é executado.

Como exercício, eu recomendo pegar a gramática de alguma linguagem de programação com a qual você esteja familiarizado (novamente, Python , Java e aqui está C # , Javascript , C ) e tente analisar manualmente algo simples, como talvez x = a + b;ou if (True): print("Yay!"). Se você está procurando algo mais simples, há também uma boa gramática para JSON , que basicamente cobre apenas a sintaxe para literais de objetos em Javascript (como {'a': 1, 'b': 2}). Boa sorte, isso é uma coisa que mexe com o cérebro, mas acaba sendo realmente interessante quando você não está em um prazo louco.

Em poucas palavras

As linguagens de programação são compostas por uma sintaxe que representa o programa como cadeias de caracteres e uma semântica que é o significado pretendido do programa.

Linguagens formais são sintaxe sem significado. Destina-se a estudar a estrutura de conjuntos de cadeias definidas formalmente, sem geralmente atribuir significado a essas cadeias.

Expressão regular e outros formalismos (como Gramáticas livres de contexto) são usados ​​para definir linguagens formais, usadas como componente sintático da programação e linguagens naturais, isto é, para representar sentenças de maneira estruturada. Outros mecanismos são usados ​​para relacionar essa estrutura com a semântica das linguagens de programação.

Muito aqui é consideravelmente simplificado, principalmente em relação à linguagem natural.

Com muito mais detalhes

Para responder sua pergunta, devemos começar do começo. Uma linguagem no sentido usual é, informalmente, um meio de transmitir informações ou idéias. Em um idioma, geralmente se distingue entre sintaxe e semântica. Semântica é o que você quer falar / escrever. as informações que você deseja transmitir. Sintaxe é o meio que você usa para transmiti-lo, ou seja, uma representação convencional que pode ser trocada entre pessoas, e agora também entre pessoas e dispositivos, ou entre dispositivos (computadores).

Normalmente, você usará a palavra dogpara transmitir a idéia de um cachorro. A palavra dogé composta de três letras, ou algum som equivalente, e pretende ser a representação de algum tipo de animal. A idéia principal é que a comunicação seja feita através da representação do que deve ser comunicado. As estruturas de representação são geralmente chamadas de sintaxe, enquanto o que é representado é chamado de semântica. Isso vale mais ou menos para a linguagem natural e também para as linguagens de programação.

As palavras são entidades sintáticas para representar conceitos semânticos mais ou menos elementares. Mas esses conceitos elementares precisam ser reunidos de várias maneiras para dar um significado mais complexo. Escrevemos the dogpara transmitir que queremos dizer um cão específico e the dog bites the catpara transmitir uma ideia mais complexa. Mas a maneira como as palavras são organizadas deve ser fixada por regras, para que possamos dizer qual cão e gato está mordendo o outro.

Portanto, temos regras como as sentence -> subject verb complementque devem corresponder às frases e nos dizem como as idéias associadas a cada parte são articuladas. Essas regras são regras sintáticas, pois nos dizem como a representação de nossa mensagem deve ser organizada. O subjectpróprio pode ser definido por uma regra subject -> article noune assim por diante.

$2x+1=23$$x$$1$$23$

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

A estrutura das linguagens de programação é a mesma. As linguagens de programação são semanticamente especializadas em expressar cálculos a serem executados, em vez de expressar problemas a serem resolvidos, prova de teoremas ou relações amigáveis ​​entre animais. Mas essa é a principal diferença.

As representações usadas na sintaxe são geralmente cadeias de caracteres ou sons para idiomas falados. A semântica geralmente pertence ao domínio abstrato, ou possivelmente à realidade, mas ainda abstrata em nossos processos de pensamento, ou ao domínio comportamental dos dispositivos. A comunicação implica a codificação da informação / idéia na sintaxe, que é transmitida e decodificada pelo receptor. O resultado é então interpretado de qualquer maneira pelo receptor.

Então, o que vemos da linguagem é principalmente sintaxe e sua estrutura. O exemplo acima é apenas uma das formas mais comuns de definir cadeias sintáticas e sua organização estrutural. Há outros. Para um determinado idioma, algumas strings podem ser atribuídas a uma estrutura e dizem pertencer ao idioma, enquanto outras não.

O mesmo vale para as palavras. Algumas seqüências de letras (ou som) são palavras legítimas, enquanto outras não.

Linguagens formais são apenas sintaxe sem semântica. Eles definem com um conjunto de regras quais seqüências podem ser construídas, usando os elementos básicos de um alfabeto. O que são as regras podem ser muito variáveis, às vezes complexas. Mas as linguagens formais são usadas para muitos propósitos matemáticos, além da comunicação lingüística, seja para linguagens naturais ou de programação. O conjunto de regras que define as seqüências de caracteres em um idioma é chamado de gramática. Mas há muitas outras maneiras de definir idiomas.

Na prática, uma linguagem é estruturada em dois níveis. O nível lexical define palavras construídas a partir de um alfabeto de caracteres. O nível sintático define sentenças ou programas construídos a partir de um alfabeto de palavras (ou mais precisamente de famílias de palavras, para que ele permaneça um alfabeto finito). Isso é necessariamente um pouco simplificado.

A estrutura das palavras é bastante simples na maioria das linguagens (programação ou natural), de modo que elas geralmente são definidas com o que geralmente é considerado o tipo mais simples de linguagem formal: as linguagens regulares. Eles podem ser definidos com expressões regulares (regexp) e são facilmente identificados com dispositivos programados chamados autômatos de estados finitos. Nos casos de linguagens de programação, exemplos de uma palavra são um identificador, um número inteiro, string, um número real, uma palavra reservada como if or repeat, um símbolo de pontuação ou um parêntese aberto. Exemplos de famílias de palavras são identificador, sequência, número inteiro.

O nível sintático é geralmente definido por um tipo de linguagem formal um pouco mais complexa: as linguagens sem contexto, usando as palavras como alfabeto. As regras que vimos acima são regras sem contexto para a linguagem natural. No caso das linguagens de programação, as regras podem ser:

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

Com essas regras, você pode escrever:

while aaa /= bbb do aaa = aaa + bbb / 6 o que é uma afirmação.

E a maneira como foi produzida pode ser representada por uma estrutura de árvore chamada árvore de análise ou árvore de sintaxe (não concluída aqui):

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

Os nomes que aparecem à esquerda de uma regra são chamados de não terminais, enquanto as palavras também são chamadas de terminais, pois estão no alfabeto do idioma (acima do nível lexical). Não terminal representa as diferentes estruturas sintáticas, que podem ser usadas para compor um programa.

Essas regras são chamadas livres de contexto, porque um não terminal pode ser substituído arbitrariamente usando qualquer uma das regras correspondentes, independentemente do contexto em que aparece. O conjunto de regras que define o idioma é chamado de gramática livre de contexto.

Na verdade, existem restrições quanto a isso, quando os identificadores precisam ser declarados primeiro ou quando uma expressão deve atender às restrições de tipo. Mas essa restrição pode ser considerada semântica, e não sintática. Na verdade, alguns profissionais os colocam no que chamam de semântica estática .

Dada qualquer sentença, qualquer programa, o significado dessa sentença é extraído analisando a estrutura dada pela árvore de análise para essa sentença. Portanto, é muito importante desenvolver algoritmos, chamados analisadores, que podem recuperar a estrutura em árvore correspondente a um programa, quando determinado.

O analisador é precedido pelo analisador lexical que reconhece as palavras e determina a família à qual elas pertencem. Em seguida, a sequência de palavras, ou elementos lexicais, é fornecida ao analisador que recupera a estrutura da árvore subjacente. A partir dessa estrutura, o compilador pode determinar como gerar código, que é a parte semântica do processamento do programa no lado do compilador.

O analisador de um compilador pode realmente construir uma estrutura de dados correspondente à árvore de análise e passá-la para os estágios posteriores do processo de compilação, mas não precisa. A execução do algoritmo de análise equivale a desenvolver uma estratégia computacional para explorar a árvore de sintaxe implícita no texto do programa. Essa árvore de sintaxe / análise pode ou não ser explicitada no processo, dependendo da estratégia de compilação (número de estágios). O que é necessário, porém, é que, em última instância, exista pelo menos uma exploração de baixo para cima da árvore de análise, explicitada ou deixada implícita na estrutura de computação.

A razão disso, intuitivamente, é que uma maneira formal padrão de definir semântica associada a uma estrutura de árvore sintática é por meio do que é chamado de homomorfismo. Não tema a grande palavra. A idéia é apenas considerar o significado do todo que é construído a partir do significado das partes, com base no operador que as conecta

Por exemplo, a sentença the dog bites the catpode ser analisada com a regra sentence -> subject verb complement. Conhecer o significado dos 3 sub-árvores subject, verbe complement, a regra que compõe-los nos diz que o sujeito está fazendo a ação, e que o gato é o único que está mordido.

Essa é apenas uma explicação intuitiva, mas pode ser formalizada. A semântica é construída para cima a partir dos constituintes. Mas isso esconde muita complexidade.

O trabalho interno de um compilador pode ser decomposto em vários estágios. O compilador real pode funcionar etapa por etapa, usando representações intermediárias. Também pode mesclar algumas etapas. Isso depende da tecnologia usada e da complexidade da compilação do idioma em questão.

Existem diferenças significativas. O principal deles, eu diria, é que analisar as linguagens de programação reais tem tudo a ver com o tratamento de erros de sintaxe. Com uma linguagem formal, você diria "bem, não está na linguagem", mas um compilador que diz que isso não é muito útil - deve informar o que está errado e, se foi um pequeno erro, continue analisando o ideal para que ele possa relatar mais erros. Muita pesquisa (e esforço de implementação) entra nisso. Então, na verdade, você nem se importa tanto com o resultado verdadeiro / falso, apenas deseja analisar a estrutura da entrada. As linguagens formais são usadas como uma ferramenta e há muita sobreposição, mas você está realmente resolvendo um problema diferente.

Além disso, na maioria dos idiomas, optou-se por não aplicar certas coisas na gramática , por exemplo, o exemplo que você mencionou, "uma variável não pode aparecer se não tiver sido declarada". Isso normalmente é algo que seria completamente ignorado pelo analisador e, em seguida, capturado em uma análise separada (análise semântica) que analisa esse tipo de coisa e não é afetada por considerações como ausência de contexto. Mas nem sempre - por exemplo, para analisar C, o lexer hack é frequentemente usado, e C ++ é um exemplo famoso de uma linguagem que não pode ser analisada sem fazer simultaneamente uma análise semântica séria (na verdade, analisar C ++ é indecidível, porque os modelos são Turing completos ) Em idiomas mais simples, ele tende a ser dividido, porém é mais fácil.

Uma linguagem formal é um conjunto de palavras - onde uma palavra é uma sequência de símbolos de algum alfabeto.

Isso significa que seu acoplamento das regras de produção e da linguagem formal é muito forte. Não é correto que a linguagem formal seja as regras de produção. Em vez disso, as regras de produção definem a linguagem formal. A linguagem formal são as palavras que podem ser produzidas pela regra de produção. (Isso requer que a linguagem formal seja do tipo que possa ser definida pelas regras de produção, por exemplo, linguagens regulares podem ser definidas por uma gramática livre de contexto)

Portanto, a linguagem regular correspondente à expressão (a|b)*c*dé definida pelas regras de produção;

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

As palavras que essas regras de produção geram a partir do símbolo inicial S são exatamente aquelas que a expressão regular aceita.

Há outra relação entre expressões regulares e linguagens de programação que tem a ver com semântica. As construções básicas de controle de uma linguagem imperativa são composição seqüencial (faça A e B), escolha (faça A ou B) e repetição (faça A de novo e de novo).

As mesmas três maneiras de combinar comportamentos são encontradas em expressões regulares. Faça chamadas de sub-rotina e você terá uma analogia com o EBNF.

Portanto, há muita semelhança entre a álgebra de expressões regulares e a álgebra de comandos. Isso é explorado em detalhes por Dijkstra em "A unificação dos três cálculos". É também a base do CCS de Milner, que fornece uma resposta para a pergunta: e se adicionarmos paralelismo?