lexers vs analisadores

Question

Lexers e analisadores são realmente tão diferentes em teoria?

Parece moda odiar expressões regulares: codificação de terror, outra postagem no blog.

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

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

Alguém já usou os tokens produzidos por esses lexers com geradores de analisador bison ou antlr?

Answer 1

O que analisa e Lexers têm em comum:

1. Eles leem símbolos de alguns alfabeto de sua contribuição.

   • Dica: o alfabeto não precisa necessariamente ter letras. Mas tem que ser de símbolos que são atômico Para o idioma compreendido por Parser/Lexer.
   • Símbolos para os caracteres Lexer: ASCII.
   • Símbolos para o analisador: os tokens específicos, que são símbolos terminais de sua gramática.

2. Eles analisam isso símbolos e tente combiná -los com o gramática da linguagem que eles entendiam.
   

   • Aqui é onde está a diferença real geralmente. Veja abaixo para mais.
   • Gramática entendida por Lexers: gramática regular (nível 3 de Chomsky).
   • Gramática entendida por analisadores: gramática livre de contexto (nível 2 de Chomsky).

3. Eles se anexam semântica (Significado) para as peças do idioma que encontram.

   • Lexers atribui significado classificando lexemes (cordas de símbolos da entrada) como o particular Tokens. Por exemplo, todos esses lexemes: *, ==, <=, ^ será classificado como token "operador" pelo C/C ++ Lexer.
   • Os analisadores anexam significado classificando seqüências de fichas da entrada (frases) como o particular não terminais e construindo o Parse árvore. Por exemplo, todas essas cordas simbólicas: [number][operator][number], [id][operator][id], [id][operator][number][operator][number] será classificado como "expressão" não terminal pelo analisador 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, ele pode convertê -lo em seu valor binário e armazenar com o token "número".
   • 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 um adequado frases do idioma que eles reconhecem.

   • Lexers produz Tokens, que são frases do idioma regular Eles reconhecem. Cada token pode ter uma sintaxe interna (embora o nível 3, não o 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 frases do linguagem livre de contexto Eles reconhecem. Geralmente é apenas uma grande árvore para todo o documento/arquivo de origem, porque todo o documento/arquivo de origem é adequado frase para eles. Mas não há razões pelas quais o Parser não conseguiu produzir uma série de árvores de sintaxe em sua saída. Por exemplo, pode ser um analisador que reconhece tags SGML coladas em texto simples. Então vai tokenize O documento SGML em uma série de tokens: [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 (os tokens são simplesmente símbolos de algum alfabeto) da mesma maneira que as frases de um idioma podem ser símbolos alfabéticos de outros outros níveis mais altos Língua. Por exemplo, se * e - são os símbolos do alfabeto M (Como "símbolos de código morse"), você pode construir um analisador que reconheça seqüências 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 estes Tokens são símbolos atômicos de sua linguagem (por exemplo, linguagem "palavras em inglês"). E essas "palavras em inglês" podem ser tokens (símbolos do alfabeto) para um 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á sobre esses "níveis gramaticais de Chomsky"? Bem, o 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, ou seja, podem consistir apenas nos símbolos do alfabeto (a,b), suas concatenações (ab,aba,bbb Etd.), ou alternativas (por exemplo a|b).
  Eles podem ser implementados como autômatos estaduais finitos (FSA), como o NFA (autômato finito não determinístico) ou melhor DFA (autômato finito determinístico).
  As gramáticas regulares não podem lidar com Sintaxe aninhada, por exemplo, parênteses adequadamente aninhados/correspondentes (()()(()())), tags html/bbcode aninhadas, blocos aninhados etc. É porque os autômatos estaduais lidar com isso devem ter que ter infinitamente muitos estados para lidar com infinitamente muitos níveis de nidificação.

• Nível 2: gramáticas sem contexto

  Eles podem ter ramos aninhados, recursivos e auto-semelhantes em suas árvores de sintaxe, para que possam lidar bem com estruturas aninhadas.
  Eles podem ser implementados como autômato estadual com pilha. Essa pilha é usada para representar o nível de nidificação da sintaxe. Na prática, eles geralmente são implementados como um analisador de descendência recursiva e de cima para baixo, que usa a pilha de chamadas do procedimento da Machine para rastrear o nível de nidificação e usar procedimentos/funções de maneira recursiva para cada símbolo não terminal em sua sintaxe.
  Mas eles não conseguem lidar com um sensível ao contexto sintaxe. Por exemplo, quando você tem uma expressão x+3 E em um contexto isso x Pode 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 chamado de gramáticas recursivamente enumeráveis.

Answer 2

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

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

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 "analisar", sensíveis ao contexto "para extrair essa estrutura.Os analisadores sensíveis ao contexto são difíceis de construir; portanto, o compromisso de engenharia é usar gramáticas "sem 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 de lexing nem de análise desapareçam em breve.

Eles poderia 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ê está aplicando um maquinário mais geral ao que geralmente é um problema que não precisa dele, e geralmente você paga por isso em despesas gerais.Onde você tem muitos ciclos livres, essa sobrecarga pode não importar.Se você processar muito texto, a sobrecarga será importante e os analisadores clássicos de expressões regulares continuarão a ser usados.

Answer 3

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

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

S --> A | B

você pode conseguir no CNF apenas 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 conseguir em CNF usando um anulável produção, isto é, aquela que pode ser substituída por uma string vazia (denotado apenas por produção vazia aqui;outros usam épsilon ou 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 formato como a anterior B acima é chamado de "apagamento", porque pode apagar tudo o que representa em outras produções (produzindo uma string vazia em vez de outra coisa).

Zero ou mais repetições da EBNF:

S --> A*

você pode obter usando recursivo produção, isto é, aquela que se insere em algum lugar nela.Isso pode ser feito de duas maneiras.O primeiro é recursão à esquerda (o que geralmente deve ser evitado, porque os analisadores descendentes recursivos de cima para baixo não podem analisá-lo):

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 de zero ou mais As, a mesma string (mas não a mesma língua!) pode ser expresso usando recursão à direita:

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 + para uma ou mais repetições da EBNF:

S --> A+

isso pode ser feito fatorando um A e usando * como antes:

S --> A A*

que você pode expressar em CNF como tal (eu uso recursão correta aqui;tente descobrir o outro sozinho como um 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 (isto é, gramática regular) como aquele que pode ser expresso em uma única produção EBNF composta apenas por símbolos terminais.De forma 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.

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

Mas quando sua sintaxe usa recursão de uma forma não trivial, para produzir estruturas aninhadas semelhantes a árvores, 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 EBNF de forma alguma;você acabará substituindo S indefinidamente, o que sempre adicionará outro aareia bestá em ambos os lados.Lexers (mais especificamente:Autômatos de Estados Finitos usados ​​por lexers) não podem contar para números arbitrários (eles são finitos, lembra?), então eles não sabem quantos aestavam lá para combiná-los uniformemente com tantos bS.Gramáticas como esta são chamadas gramáticas livres de contexto (no mínimo) e exigem um analisador.

Gramáticas livres de contexto são bem conhecidas para análise, portanto são amplamente utilizadas para descrever a sintaxe de linguagens de programação.Mas há mais.Às vezes é necessária uma gramática mais geral – quando você tem mais coisas para contar ao mesmo tempo, de forma independente.Por exemplo, quando você deseja descrever uma linguagem onde se pode usar parênteses redondos e colchetes intercalados, mas eles devem ser emparelhados corretamente entre si (colchetes com colchetes, redondo com redondo).Esse tipo de gramática é chamado sensível ao contexto.Você pode reconhecê-lo pelo fato de 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.Pode haver algumas pré-condições, pós-condições, etc.Por exemplo, a regra acima substituirá R em S, mas apenas quando estiver no meio A e B, deixando aqueles A e B eles mesmos inalterados.Esse tipo de sintaxe é realmente difícil de analisar, porque precisa de uma máquina de Turing completa.É uma outra história, então vou terminar aqui.

Answer 4

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

Lexers e analisadores não são muito diferentes, como sugerido pela resposta aceita.Ambos são baseados em formalismos de linguagem simples:Idiomas regulares para Lexers e, quase sempre, idiomas livres de contexto (CF) para analisadores.Ambos estão associados a modelos computacionais razoavelmente simples, o Autômato Finito do Estado e o Autômato de Push-Down Stack.Idiomas regulares são um caso especial de idiomas livres de contexto, de modo que A Lexers poderia ser produzida com a tecnologia CF um pouco mais complexa.Mas não é uma boa ideia por pelo menos dois motivos.

Um ponto fundamental na programação é que um componente do sistema deve ser o Buit com a tecnologia mais apropriada, para que seja fácil produzir, entender e manter.A tecnologia não deve ser exagerada (usando técnicas muito mais complexas e caras do que o necessário), nem deve estar no limite de seu poder, exigindo assim contorções técnicas para atingir a meta desejada.

É por isso que “Parece moda odiar expressões regulares”.Embora possam fazer muito, às vezes exigem codificação muito ilegível para alcançá -lo, 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.Utilizar os analisadores CF para o token seria um exagero, embora seja possível.

Outra razão para não usar o formalismo CF para lexers é que ele pode em seguida, ser tentador para utilizar a potência total CF.Mas isto pode aumentar problemas estruturais em relação à leitura de programas.

Fundamentalmente, a maior parte da estrutura do texto do programa, a partir do qual o significado é extraído, é uma estrutura de árvore.Ele expressa como o parse sentence (programa) é gerada a partir de regras de sintaxe.A semântica é derivadas de técnicas composicionais (homomorfismo para o matematicamente orientadas) da forma como as regras de sintaxe são compostas construir a árvore de análise.Portanto, a estrutura da árvore é essencial.O facto de os tokens serem identificados com um conjunto regular de lexer baseado não altera a situação, porque a FC composta com regular ainda dá CF (Estou a falar muito frouxamente sobre transdutores regulares, que transformar um fluxo de caracteres num fluxo de token).

No entanto, CF composto com CF (via transdutores CF ...desculpa para o matemática), não dá necessariamente CF, e pode tornar as coisas mais geral, mas menos tratável na prática.Portanto, CF não é o adequado ferramenta para lexers, mesmo que possa ser utilizada.

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

(Note que os transdutores regulares podem ter outros usos, tais como formalização de algumas técnicas de manipulação de erros de sintaxe.)

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

EBNF é um açúcar sintático para BNF, utilizando as instalações de regular notação para dar a versão terser das gramáticas BNF.Pode ser sempre transformado num equivalente de BNF puro.

No entanto, a notação regular é muitas vezes utilizada no EBNF apenas para enfatizar estas partes da sintaxe que correspondem à estrutura do léxico elementos, e deve ser reconhecido com o lexer, enquanto o resto com apresentar-se em BNF linear.Mas não é uma regra absoluta.

Para resumir, A estrutura mais simples do token é melhor analisada com a tecnologia mais simples de idiomas regulares, enquanto a estrutura orientada para a árvore do idioma (da sintaxe do programa) é melhor tratada pelas gramáticas da CF.

Eu sugeriria também olhar A resposta da AHR.

Mas isso deixa uma questão em aberto: Por que árvores?

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

• eles dão uma estrutura simples ao texto

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

Trata-se, portanto, de uma boa representação intermédia, como mostra o sucesso de Abstract Syntax Trees (AST).Note-se que os AST são frequentemente diferente da árvore de análise porque a tecnologia de análise utilizada por muitos profissionais (Tal como LL ou LR) aplica-se apenas a um subconjunto de CF gramáticas, forçando assim distorções gramaticais que são mais tarde corrigido em AST.Isto pode ser evitado com uma análise mais geral tecnologia (baseada na programação dinâmica) que aceita qualquer gramática CF.

Declaração sobre o facto de as linguagens de programação serem contextual-sensitive (CS) em vez de CF são arbitrárias e discutíveis.

O problema é que a separação entre sintaxe e semântica é arbitrárias.As declarações de verificação ou o acordo de tipo podem ser vistos como parte da sintaxe, ou parte da semântica.O mesmo seria verdadeiro de acordo de género e número em línguas naturais.Mas há naturais linguagens em que a concordância plural depende da semântica real significado das palavras, de modo que não se encaixam bem com a sintaxe.

Muitas definições de linguagens de programação na semântica denotacional Coloque declarações e digite a verificação na semântica.Portanto, afirmando-se como feito por Ira Baxter que os analisadores CF estão a ser hackeados para obter um contexto a sensibilidade requerida pela sintaxe é, na melhor das hipóteses, uma vista arbitrária do situação.Pode ser organizado como um hack nalguns compiladores, mas não tem de ser.

Também não é apenas que os analisadores CS (no sentido usado noutras respostas aqui) são difíceis de construir, e menos eficaz.São também inadequados para exprimir de forma perspicaz a tipo de sensibilidade ao contexto que possa ser necessário.E não o fazem produzir naturalmente uma estrutura sintática (tal como árvores de parse) que é conveniente derivar a semântica do programa, i.e.para gerar o código compilado.

Answer 5

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

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

recurso___Compiladores (2ª edição) Escrito By-Alfred V. Abo Columbia University Monica S. Lam Stanford University Ravi Sethi Avaya Jeffrey D. Ullman Stanford University