lexers vs parsers

Os lexers e analisadores são realmente tão diferentes em teoria?

Parece moda odiar expressões regulares: horror de código , outro post do blog .

No entanto, ferramentas populares baseadas em lexing: pigmentos , geshi ou prettify , usam expressões regulares. Eles parecem lex qualquer coisa ...

Quando o lexing é suficiente, quando você precisa do EBNF?

Alguém usou os tokens produzidos por esses lexers com geradores bison ou antlr parser?

O que analisadores e lexers têm em comum:

1. Eles lêem símbolos de algum alfabeto a partir de suas entradas.

   • Dica: o alfabeto não precisa necessariamente ser de letras. Mas deve ser de símbolos atômicos para a linguagem compreendida pelo analisador / lexer.
   • Símbolos para o lexer: caracteres ASCII.
   • Símbolos para o analisador: os tokens específicos, que são símbolos terminais de sua gramática.

2. Eles analisam esses símbolos e tentam combiná-los com a gramática do idioma que entenderam.
   

   • Aqui é onde está a diferença real. Veja abaixo mais.
   • Gramática compreendida pelos lexers: gramática regular (nível 3 de Chomsky).
   • Gramática compreendida pelos analisadores: gramática livre de contexto (nível 2 de Chomsky).

3. Eles anexam semântica (significado) às peças de linguagem que encontram.

   • Os Lexers atribuem significado ao classificar lexemes (sequências de símbolos da entrada) como os tokens específicos . Por exemplo Todos estes lexemes: *, ==, <=, ^serão classificados como "operador" token lexer o C / C ++.
   • Os analisadores atribuem significado ao classificar seqüências de tokens da entrada (sentenças) como os não - terminais específicos e construir a árvore de análise . Por exemplo, todas estas token cordas: [number][operator][number], [id][operator][id], [id][operator][number][operator][number]serão classificadas como "expressão" não-terminal por analisador de C / C ++.

4. Eles podem anexar algum significado adicional (dados) aos elementos reconhecidos.

   • Quando um lexer reconhece uma sequência de caracteres que constitui um número adequado, pode convertê-lo em seu valor binário e armazenar com o token "number".
   • Da mesma forma, quando um analisador reconhece uma expressão, ele pode calcular seu valor e armazenar com o nó "expressão" da árvore de sintaxe.

5. Todos eles produzem em sua produção frases apropriadas do idioma que reconhecem.

   • Os Lexers produzem tokens , que são frases do idioma normal que reconhecem. Cada token pode ter uma sintaxe interna (embora no nível 3, não no nível 2), mas isso não importa para os dados de saída e para o que os lê.
   • Os analisadores produzem árvores de sintaxe , que são representações de sentenças da linguagem livre de contexto que reconhecem. Geralmente, é apenas uma grande árvore para todo o arquivo de documento / fonte, porque o arquivo inteiro de documento / fonte é uma sentença adequada para eles. Mas não há motivos para o analisador não produzir uma série de árvores de sintaxe em sua saída. Por exemplo, poderia ser um analisador que reconhece tags SGML coladas em texto sem formatação. Por isso vai tokenizar o documento SGML em uma série de fichas: [TXT][TAG][TAG][TXT][TAG][TXT]....

Como você pode ver, analisadores e tokenizadores têm muito em comum. Um analisador pode ser um tokenizador para outro analisador, que lê seus tokens de entrada como símbolos de seu próprio alfabeto (tokens são simplesmente símbolos de algum alfabeto) da mesma maneira que sentenças de um idioma podem ser símbolos alfabéticos de outro nível superior língua. Por exemplo, se *e -são os símbolos do alfabeto M(como "símbolos do código Morse"), você pode criar um analisador que reconheça cadeias desses pontos e linhas como letras codificadas no código Morse. As frases no idioma "Código Morse" podem ser tokens para algum outro analisador, para o qual esses tokenssão símbolos atômicos de seu idioma (por exemplo, idioma "Palavras em inglês"). E essas "palavras em inglês" podem ser símbolos (símbolos do alfabeto) para algum analisador de nível superior que entende o idioma "frases em inglês". E todas essas línguas diferem apenas na complexidade da gramática . Nada mais.

Então, o que há com esses "níveis gramaticais de Chomsky"? Bem, Noam Chomsky classificou as gramáticas em quatro níveis, dependendo de sua complexidade:

• Nível 3: gramáticas regulares

  Eles usam expressões regulares, isto é, eles podem consistir apenas dos símbolos do alfabeto ( a, b), seus concatenations ( ab, aba, bbbETD.), Ou alternativas (por exemplo a|b).
  Eles podem ser implementados como autômatos de estado finito (FSA), como NFA (autômato finito não determinístico) ou melhor DFA (autômato finito determinístico).
  Gramáticas regulares não podem lidar com sintaxe aninhada , por exemplo, parênteses aninhados / correspondidos corretamente (()()(()())), tags HTML / BBcode aninhadas, blocos aninhados etc.

• Nível 2: gramáticas livres de contexto

  Eles podem ter ramificações aninhadas, recursivas e auto-semelhantes em suas árvores de sintaxe, para que possam lidar bem com estruturas aninhadas.
  Eles podem ser implementados como autômatos de estado com pilha. Essa pilha é usada para representar o nível de aninhamento da sintaxe. Na prática, eles geralmente são implementados como um analisador descendente descendente recursivo que usa a pilha de chamadas de procedimento da máquina para rastrear o nível de aninhamento e usam procedimentos / funções chamados recursivamente para todos os símbolos não terminais em sua sintaxe.
  Mas eles não podem lidar com uma sintaxe sensível ao contexto . Por exemplo, quando você tem uma expressão x+3e em um contexto, esse xpode ser o nome de uma variável e, em outro contexto, pode ser o nome de uma função etc.

• Nível 1: gramáticas sensíveis ao contexto

• Nível 0: Gramáticas irrestritas
  Também chamadas gramáticas recursivamente enumeráveis.

Sim, eles são muito diferentes na teoria e na implementação.

Os Lexers são usados ​​para reconhecer "palavras" que compõem elementos da linguagem, porque a estrutura dessas palavras é geralmente simples. Expressões regulares são extremamente boas em lidar com essa estrutura mais simples e existem mecanismos de correspondência de expressões regulares de alto desempenho usados ​​para implementar lexers.

Os analisadores são usados ​​para reconhecer a "estrutura" de frases de um idioma. Essa estrutura geralmente está muito além do que as "expressões regulares" podem reconhecer, portanto, é necessário um analisador "sensível ao contexto" para extrair essa estrutura. Analisadores sensíveis ao contexto são difíceis de construir, portanto, o compromisso da engenharia é usar gramáticas "livres de contexto" e adicionar hacks aos analisadores ("tabelas de símbolos" etc.) para lidar com a parte sensível ao contexto.

É provável que nem a tecnologia lexing nem a análise desapareçam em breve.

Eles podem ser unificados ao decidir usar a tecnologia de "análise" para reconhecer "palavras", como é atualmente explorado pelos chamados analisadores GLR sem scanner. Isso tem um custo de tempo de execução, pois você aplica máquinas mais gerais ao que geralmente é um problema que não precisa, e geralmente você paga por isso em cima. Onde você tem muitos ciclos livres, essa sobrecarga pode não importar. Se você processar muito texto, a sobrecarga importa e os analisadores clássicos de expressões regulares continuarão sendo usados.

Quando o lexing é suficiente, quando você precisa do EBNF?

O EBNF realmente não acrescenta muito ao poder das gramáticas. É apenas uma notação de conveniência / atalho / "açúcar sintático" sobre as regras gramaticais padrão da Chomsky's Normal Form (CNF). Por exemplo, a alternativa EBNF:

S --> A | B

você pode obter no CNF listando cada produção alternativa separadamente:

S --> A      // `S` can be `A`,
S --> B      // or it can be `B`.

O elemento opcional do EBNF:

S --> X?

você pode obter no CNF usando uma produção anulável , ou seja, aquela que pode ser substituída por uma cadeia vazia (denotada apenas pela produção vazia aqui; outros usam epsilon, lambda ou círculo cruzado):

S --> B       // `S` can be `B`,
B --> X       // and `B` can be just `X`,
B -->         // or it can be empty.

Uma produção em uma forma como a última Bacima é chamada de "apagamento", porque pode apagar o que quer que seja em outras produções (produto uma cadeia vazia em vez de outra coisa).

Zero ou mais repetições de EBNF:

S --> A*

você pode obter usando a produção recursiva , ou seja, uma que se incorpora em algum lugar nela. Isso pode ser feito de duas maneiras. O primeiro é a recursão à esquerda (que geralmente deve ser evitada, porque os analisadores de descida recursiva de cima para baixo não podem analisá-la):

S --> S A    // `S` is just itself ended with `A` (which can be done many times),
S -->        // or it can begin with empty-string, which stops the recursion.

Sabendo que gera apenas uma string vazia (no final das contas) seguida por zero ou mais As, a mesma string ( mas não o mesmo idioma! ) Pode ser expressa usando a recursão correta :

S --> A S    // `S` can be `A` followed by itself (which can be done many times),
S -->        // or it can be just empty-string end, which stops the recursion.

E quando se trata +de uma ou mais repetições do EBNF:

S --> A+

isso pode ser feito fatorando um Ae usando *como antes:

S --> A A*

que você pode expressar no CNF como tal (eu uso a recursão correta aqui; tente descobrir o outro como exercício):

S --> A S   // `S` can be one `A` followed by `S` (which stands for more `A`s),
S --> A     // or it could be just one single `A`.

Sabendo disso, agora você provavelmente pode reconhecer uma gramática para uma expressão regular (ou seja, gramática regular ) como aquela que pode ser expressa em uma única produção EBNF que consiste apenas em símbolos terminais. De maneira mais geral, você pode reconhecer gramáticas regulares quando vê produções semelhantes a estas:

A -->        // Empty (nullable) production (AKA erasure).
B --> x      // Single terminal symbol.
C --> y D    // Simple state change from `C` to `D` when seeing input `y`.
E --> F z    // Simple state change from `E` to `F` when seeing input `z`.
G --> G u    // Left recursion.
H --> v H    // Right recursion.

Ou seja, usando apenas strings vazias, símbolos terminais, simples não terminais para substituições e alterações de estado, e usando recursão apenas para obter repetição (iteração, que é apenas recursão linear - aquela que não se ramifica como árvore). Nada mais avançado acima disso, então você tem certeza de que é uma sintaxe regular e pode usar apenas um pouco mais para isso.

Mas quando sua sintaxe usa a recursão de maneira não trivial, para produzir estruturas aninhadas semelhantes a árvores, auto-similares, como a seguinte:

S --> a S b    // `S` can be itself "parenthesized" by `a` and `b` on both sides.
S -->          // or it could be (ultimately) empty, which ends recursion.

então você pode ver facilmente que isso não pode ser feito com expressão regular, porque você não pode resolvê-lo em uma única produção de EBNF de forma alguma; você vai acabar com substituindo Sindefinidamente, o que será sempre adicionar mais as e bs em ambos os lados. Os Lexers (mais especificamente: Autômatos de Estado Finito usados ​​por lexers) não podem contar com um número arbitrário (eles são finitos, lembra-se?); Portanto, eles não sabem quantos as havia para combiná-los igualmente com tantos bs. Gramáticas como essa são chamadas de gramáticas sem contexto (no mínimo) e requerem um analisador.

As gramáticas livres de contexto são conhecidas por analisar, portanto são amplamente usadas para descrever a sintaxe das linguagens de programação. Mas tem mais. Às vezes, é necessária uma gramática mais geral - quando você tem mais coisas para contar ao mesmo tempo, independentemente. Por exemplo, quando você deseja descrever um idioma em que é possível usar parênteses redondos e chavetas entrelaçadas, mas elas precisam ser emparelhadas corretamente umas com as outras (chavetas com chavetas, arredondadas com arredondadas). Esse tipo de gramática é chamado sensível ao contexto . Você pode reconhecê-lo por ter mais de um símbolo à esquerda (antes da seta). Por exemplo:

A R B --> A S B

Você pode pensar nesses símbolos adicionais à esquerda como um "contexto" para aplicar a regra. Poderia haver algumas pré-condições, pós-condições, etc. Por exemplo, a regra acima irá substituir Rem S, mas apenas quando está no meio Ae B, deixando os Ae B-se inalterado. Esse tipo de sintaxe é realmente difícil de analisar, porque precisa de uma máquina de Turing completa. É uma história totalmente diferente, então vou terminar aqui.

Para responder à pergunta conforme solicitado (sem repetir indevidamente o que aparece em outras respostas)

Lexers e analisadores não são muito diferentes, conforme sugerido pela resposta aceita. Ambos são baseados em formalismos de linguagem simples: linguagens regulares para lexers e, quase sempre, linguagens sem contexto (CF) para analisadores. Ambos estão associados a modelos computacionais bastante simples, ao autômato de estado finito e ao autômato de pilha push-down. Linguagens regulares são um caso especial de linguagens sem contexto, para que os lexers possam ser produzidos com a tecnologia CF um pouco mais complexa. Mas não é uma boa ideia por pelo menos duas razões.

Um ponto fundamental da programação é que um componente do sistema deve ser adquirido com a tecnologia mais apropriada, para que seja fácil produzir, entender e manter. A tecnologia não deve ser um exagero (usando técnicas muito mais complexas e caras do que o necessário), nem deve estar no limite de sua potência, exigindo contorções técnicas para atingir o objetivo desejado.

É por isso que "Parece elegante odiar expressões regulares". Embora eles possam fazer muito, às vezes exigem codificação muito ilegível para alcançá-la, sem mencionar o fato de que várias extensões e restrições na implementação reduzem um pouco sua simplicidade teórica. Os Lexers geralmente não fazem isso e geralmente são uma tecnologia simples, eficiente e apropriada para analisar o token. O uso de analisadores CF para token seria um exagero, embora seja possível.

Outro motivo para não usar o formalismo da FC para os lexers é que pode ser tentador usar todo o poder da FC. Mas isso pode gerar problemas estruturais em relação à leitura de programas.

Fundamentalmente, a maior parte da estrutura do texto do programa, da qual o significado é extraído, é uma estrutura em árvore. Expressa como a frase de análise (programa) é gerada a partir de regras de sintaxe. A semântica é derivada de técnicas composicionais (homomorfismo para os orientados matematicamente) da maneira como as regras de sintaxe são compostas para construir a árvore de análise. Portanto, a estrutura da árvore é essencial. O fato de os tokens serem identificados com um lexer baseado em conjunto regular não muda a situação, porque o CF composto por regular ainda fornece CF (estou falando muito livremente sobre transdutores regulares, que transformam um fluxo de caracteres em um fluxo de token).

No entanto, o CF composto por CF (via transdutores de CF ... desculpe pela matemática), não fornece CF necessariamente e pode tornar as coisas mais gerais, mas menos tratáveis ​​na prática. Portanto, o CF não é a ferramenta apropriada para lexers, mesmo que possa ser usado.

Uma das principais diferenças entre regular e CF é que os idiomas regulares (e transdutores) compõem muito bem com quase qualquer formalismo de várias maneiras, enquanto os idiomas CF (e transdutores) não, nem mesmo consigo mesmos (com algumas exceções).

(Observe que transdutores regulares podem ter outros usos, como formalização de algumas técnicas de tratamento de erros de sintaxe.)

BNF é apenas uma sintaxe específica para apresentar gramáticas de CF.

EBNF é um açúcar sintático para BNF , usando as facilidades da notação regular para fornecer uma versão mais resumida das gramáticas do BNF. Ele sempre pode ser transformado em um BNF puro equivalente.

No entanto, a notação regular é frequentemente usada no EBNF apenas para enfatizar essas partes da sintaxe que correspondem à estrutura dos elementos lexicais, e deve ser reconhecida com o lexer, enquanto o restante é apresentado em um BNF direto. Mas não é uma regra absoluta.

Para resumir, a estrutura mais simples do token é melhor analisada com a tecnologia mais simples das linguagens regulares, enquanto a estrutura orientada em árvore da linguagem (da sintaxe do programa) é melhor manipulada pelas gramáticas CF.

Eu sugeriria também olhar para a resposta da AHR .

Mas isso deixa uma pergunta em aberto: por que árvores?

As árvores são uma boa base para especificar sintaxe porque

• eles dão uma estrutura simples ao texto

• é muito conveniente associar semântica ao texto com base nessa estrutura, com uma tecnologia matematicamente bem compreendida (composicionalidade via homomorfismos), como indicado acima. É uma ferramenta algébrica fundamental para definir a semântica dos formalismos matemáticos.

Portanto, é uma boa representação intermediária, como mostra o sucesso de Abstract Syntax Trees (AST). Observe que o AST geralmente é diferente da árvore de análise porque a tecnologia de análise usada por muitos profissionais (como LL ou LR) se aplica apenas a um subconjunto de gramáticas de CF, forçando assim distorções gramaticais que são posteriormente corrigidas no AST. Isso pode ser evitado com a tecnologia de análise mais geral (baseada em programação dinâmica) que aceita qualquer gramática de CF.

Declaração sobre o fato de que as linguagens de programação são sensíveis ao contexto (CS), em vez de CF, são arbitrárias e discutíveis.

O problema é que a separação de sintaxe e semântica é arbitrária. A verificação de declarações ou de acordo de tipo pode ser vista como parte da sintaxe ou da semântica. O mesmo se aplica ao acordo de gênero e número em idiomas naturais. Mas existem linguagens naturais em que o acordo plural depende do significado semântico real das palavras, de modo que não se encaixa bem na sintaxe.

Muitas definições de linguagens de programação na semântica denotacional colocam declarações e verificação de tipo na semântica. Assim, como afirma Ira Ira Baxter que os analisadores de CF estão sendo invadidos para obter uma sensibilidade ao contexto exigida pela sintaxe, é, na melhor das hipóteses, uma visão arbitrária da situação. Pode ser organizado como um hack em alguns compiladores, mas não precisa ser.

Também não é apenas que os analisadores de CS (no sentido usado em outras respostas aqui) sejam difíceis de construir e menos eficientes. Eles também são inadequados para expressar perspicazmente o kinf da sensibilidade ao contexto que pode ser necessária. E eles não produzem naturalmente uma estrutura sintática (como árvores de análise) que é conveniente para derivar a semântica do programa, ou seja, para gerar o código compilado.

Há várias razões pelas quais a parte de análise de um compilador é normalmente separada nas fases de análise e análise lexical (análise de sintaxe).

1. A simplicidade do design é a consideração mais importante. A separação das análises lexical e sintática geralmente nos permite simplificar pelo menos uma dessas tarefas. Por exemplo, um analisador que tivesse que lidar com comentários e espaços em branco como unidades sintáticas seria. Consideravelmente mais complexo do que aquele que pode assumir comentários e espaços em branco já foram removidos pelo analisador lexical. Se estamos projetando um novo idioma, separar preocupações lexicais e sintáticas pode levar a um design geral de linguagem mais limpo.
2. A eficiência do compilador é aprimorada. Um analisador lexical separado nos permite aplicar técnicas especializadas que servem apenas à tarefa lexical, não ao trabalho de analisar. Além disso, técnicas especializadas de buffer para leitura de caracteres de entrada podem acelerar significativamente o compilador.
3. A portabilidade do compilador foi aprimorada. As peculiaridades específicas do dispositivo de entrada podem ser restritas ao analisador lexical.

resource___ Compiladores (2ª Edição) escritos por- Alfred V. Abo Universidade Columbia Universidade Monica S. Lam Universidade Stanford Ravi Sethi Avaya Jeffrey D. Ullman Universidade Stanford