Criando tokens para um lexer

Estou escrevendo um analisador para uma linguagem de marcação que eu criei (escrevendo em python, mas isso não é realmente relevante para essa pergunta - na verdade, se isso parece uma má idéia, eu adoraria uma sugestão para um caminho melhor) .

Estou lendo sobre analisadores aqui: http://www.ferg.org/parsing/index.html e estou trabalhando para escrever o lexer que, se entender corretamente, deve dividir o conteúdo em tokens. O que estou tendo problemas para entender é quais tipos de token devo usar ou como criá-los. Por exemplo, os tipos de token no exemplo ao qual vinculei são:

• CORDA
• IDENTIFICADOR
• NÚMERO
• WHITESPACE
• COMENTE
• EOF
• Muitos símbolos como {e (contam como seu próprio tipo de token

O problema que estou tendo é que os tipos de token mais gerais parecem um pouco arbitrários para mim. Por exemplo, por que STRING é seu próprio tipo de token separado vs. IDENTIFIER. Uma sequência pode ser representada como STRING_START + (IDENTIFIER | WHITESPACE) + STRING_START.

Isso também pode ter a ver com as dificuldades do meu idioma. Por exemplo, declarações de variáveis ​​são gravadas {var-name var value}e implementadas com {var-name}. Parece '{'e '}'devem ser seus próprios tokens, mas são os tipos de tokens elegíveis para VAR_NAME e VAR_VALUE, ou ambos se enquadram no IDENTIFIER? Além disso, o VAR_VALUE pode realmente conter espaço em branco. O espaço em branco depois var-nameé usado para significar o início do valor na declaração. Qualquer outro espaço em branco faz parte do valor. Esse espaço em branco se torna seu próprio token? Espaço em branco só tem esse significado neste contexto. Além disso, {pode não ser o início de uma declaração de variável. Depende do contexto (existe essa palavra novamente!). {:inicia uma declaração de nome e{ pode até ser usado como parte de algum valor.

Minha linguagem é semelhante ao Python, pois os blocos são criados com recuo. Eu estava lendo sobre como Python usa o lexer para criar TRAVESSÃO e fichas DEDENT (que servem mais ou menos como o que {e }iria fazer em um monte de outras línguas). O Python afirma ser livre de contexto, o que significa para mim que pelo menos o lexer não deve se preocupar com o local no fluxo ao criar tokens. Como o lexer do Python sabe que está construindo um token INDENT de um comprimento específico sem conhecer os caracteres anteriores (por exemplo, que a linha anterior era uma nova linha, então comece a criar os espaços para o INDENT)? Eu pergunto porque preciso saber disso também.

Minha pergunta final é a mais estúpida: por que um lexer é necessário? Parece-me que o analisador poderia ir caracter por caracter e descobrir onde está e o que espera. O lexer acrescenta o benefício da simplicidade?

Sua pergunta (como sugere o parágrafo final) não é realmente sobre o lexer, é sobre o design correto da interface entre o lexer e o analisador. Como você pode imaginar, existem muitos livros sobre o design de lexers e analisadores. Por acaso, gosto do livro analisador de Dick Grune , mas pode não ser um bom livro introdutório. Por acaso, detesto intensamente o livro baseado em C de Appel , porque o código não é útil para o seu próprio compilador (por causa dos problemas de gerenciamento de memória inerentes à decisão de fingir que C é como ML). Minha própria introdução foi o livro de PJ Brown , mas não é uma boa introdução geral (embora muito boa para intérpretes especificamente). Mas voltando à sua pergunta.

A resposta é: faça o máximo que puder no lexer sem a necessidade de usar restrições para a frente ou para trás.

Isso significa que (dependendo, é claro, dos detalhes do idioma), você deve reconhecer uma sequência como um "caractere seguido por uma sequência de não-" e depois outro "caractere. Retorne isso ao analisador como uma única unidade. Existem várias razões para isso, mas as importantes são

1. Isso reduz a quantidade de estado que o analisador precisa manter, limitando seu consumo de memória.
2. Isso permite que a implementação do lexer se concentre no reconhecimento dos blocos de construção fundamentais e libera o analisador para descrever como os elementos sintáticos individuais são usados ​​para criar um programa.

Muitas vezes, os analisadores podem executar ações imediatas ao receber um token do lexer. Por exemplo, assim que o IDENTIFIER é recebido, o analisador pode executar uma pesquisa na tabela de símbolos para descobrir se o símbolo já é conhecido. Se o seu analisador também analisar constantes de seqüência de caracteres como QUOTE (IDENTIFIER SPACES) * QUOTE, você realizará muitas pesquisas irrelevantes na tabela de símbolos ou acabará içando as pesquisas da tabela de símbolos mais acima na árvore de elementos de sintaxe do analisador, porque você só pode fazer agora você tem certeza de que não está olhando para uma string.

Para reafirmar o que estou tentando dizer, mas de maneira diferente, o lexer deve se preocupar com a ortografia das coisas e o analisador com a estrutura das coisas.

Você pode notar que minha descrição de como uma string se parece muito com uma expressão regular. Isso não é coincidência. Os analisadores lexicais são frequentemente implementados em pequenas linguagens (no sentido do excelente livro Programming Pearls, de Jon Bentley ), que usam expressões regulares. Estou acostumado a pensar em termos de expressões regulares ao reconhecer texto.

Em relação à sua pergunta sobre espaço em branco, reconheça-a no lexer. Se o seu idioma tiver um formato bastante livre, não devolva os tokens WHITESPACE para o analisador, pois ele terá apenas que jogá-los fora, para que as regras de produção do analisador sejam enviadas basicamente com spam - coisas para reconhecer apenas para jogar afastados.

Quanto ao que isso significa sobre como você deve lidar com o espaço em branco quando é sintaticamente significativo, não tenho certeza se posso julgar por você que realmente funcionará bem sem saber mais sobre o seu idioma. Meu julgamento instantâneo é evitar casos em que o espaço em branco às vezes é importante e outras não, e usar algum tipo de delimitador (como aspas). Mas, se você não pode projetar o idioma da maneira que preferir, essa opção pode não estar disponível para você.

Existem outras maneiras de criar sistemas de análise de linguagem de design. Certamente, existem sistemas de construção de compiladores que permitem especificar um sistema combinado de lexer e analisador (acho que a versão Java do ANTLR faz isso), mas nunca usei um.

Última uma nota histórica. Décadas atrás, era importante para o lexer fazer o máximo possível antes de entregá-lo ao analisador, porque os dois programas não cabiam na memória ao mesmo tempo. Fazer mais no lexer deixou mais memória disponível para tornar o analisador inteligente. Eu costumava usar o Whitesmiths C Compiler por vários anos e, se entendi corretamente, ele operaria em apenas 64 KB de RAM (era um programa de MS-DOS de modelo pequeno) e, mesmo assim, traduziu uma variante de C que foi muito, muito perto de ANSI C.

Aceito sua pergunta final, que não é de fato estúpida. Os analisadores podem construir construções complexas, caractere por caractere. Se bem me lembro, a gramática em Harbison e Steele ("C - A reference manual") possui produções que usam caracteres únicos como terminais e constroem identificadores, seqüências de caracteres, números etc. como não terminais dos caracteres únicos.

Do ponto de vista das linguagens formais, qualquer coisa que um lexer baseado em expressão regular possa reconhecer e categorizar como "literal de cadeia", "identificador", "número", "palavra-chave" e assim por diante, mesmo um analisador LL (1) pode reconhecer. Portanto, não há problema teórico em usar um gerador de analisador para reconhecer tudo.

Do ponto de vista algorítmico, um reconhecedor de expressão regular pode ser executado muito mais rápido do que qualquer analisador. Do ponto de vista cognitivo, é provavelmente mais fácil para um programador interromper o trabalho entre um lexer de expressão regular e um analisador escrito de gerador de analisador.

Eu diria que considerações práticas levam as pessoas a tomarem a decisão de separar lexers e analisadores.

Parece que você está tentando escrever um lexer / parser sem realmente entender as gramáticas. Normalmente, quando as pessoas escrevem um lexer e um analisador, elas as escrevem de acordo com alguma gramática. O lexer deve retornar os tokens na gramática, enquanto o analisador usa esses tokens para corresponder a regras / não terminais . Se você pudesse analisar facilmente sua entrada, passando byte a byte, um lexer e um analisador podem ser um exagero.

Lexers tornam as coisas mais simples.

Visão geral da gramática : uma gramática é um conjunto de regras para a aparência de alguma sintaxe ou entrada. Por exemplo, aqui está uma gramática de brinquedo (simple_command é o símbolo de início):

simple_command:
 WORD DIGIT AND_SYMBOL
simple_command:
     addition_expression

addition_expression:
    NUM '+' NUM

Essa gramática significa que: -
Um comando simples é composto por
A) PALAVRA seguida por DIGIT seguida por AND_SYMBOL (são "tokens" que eu defino))
B) Uma " expressão de adição" (essa é uma regra ou "não terminal")

Uma expressão de adição é composta por:
NUM seguido de um '+' seguido de um NUM (NUM é um "token" definido por mim, '+' é um sinal de mais literal).

Portanto, como simple_command é o "símbolo inicial" (o local onde eu começo), quando recebo um token, verifico se ele se encaixa no simple_command. Se o primeiro token na entrada for WORD e o próximo token for DIGIT e o próximo token for AND_SYMBOL, correspondi a um simple_command e posso executar alguma ação. Caso contrário, tentarei associá-lo à outra regra de simple_command, que é a adição de expressão. Portanto, se o primeiro token foi um NUM seguido de um '+' seguido de um NUM, correspondi a um comando simple_ e executei alguma ação. Se não for uma dessas coisas, tenho um erro de sintaxe.

Essa é uma introdução muito, muito básica às gramáticas. Para uma compreensão mais completa, consulte este artigo da wiki e pesquise na web tutoriais de gramática sem contexto.

Usando um arranjo lexer / parser, aqui está um exemplo de como seu analisador pode parecer:

bool simple_command(){
   if (peek_next_token() == WORD){
       get_next_token();
       if (get_next_token() == DIGIT){
           if (get_next_token() == AND_SYMBOL){
               return true;
           } 
       }
   }
   else if (addition_expression()){
       return true;
   }

   return false;
}

bool addition_expression(){
    if (get_next_token() == NUM){
        if (get_next_token() == '+'){
             if (get_next_token() == NUM){
                  return true;
             }
        }
    }
    return false;
}

Ok, então esse código é meio feio e eu nunca recomendaria declarações if aninhadas triplas. Mas o ponto é: imagine tentar fazer essa coisa acima de caractere por caractere, em vez de usar suas boas funções modulares "get_next_token" e "peek_next_token" . Sério, tente. Você não vai gostar do resultado. Agora, lembre-se de que a gramática acima é cerca de 30x menos complexa do que quase qualquer gramática útil. Você vê o benefício de usar um lexer?

Honestamente, lexers e analisadores não são os tópicos mais básicos do mundo. Recomendaria primeiro ler e entender as gramáticas, depois ler um pouco sobre lexers / parsers e depois mergulhar.

Minha pergunta final é a mais estúpida: por que um lexer é necessário? Parece-me que o analisador poderia ir caracter por caracter e descobrir onde está e o que espera.

Isso não é estúpido, é apenas a verdade.

Mas a praticabilidade de alguma forma depende um pouco de suas ferramentas e objetivos. Por exemplo, se você usa o yacc sem um lexer e deseja permitir letras unicode nos identificadores, precisará escrever uma regra grande e feia que explicitamente enumere todos os caracteres válidos. Enquanto, em um lexer, talvez você possa perguntar a uma rotina de biblioteca se um personagem é membro da categoria de letras.

Usar ou não um lexer é uma questão de ter um nível de abstração entre o seu idioma e o nível do personagem. Observe que atualmente o nível de caractere é outra abstração acima do nível de bytes, que é uma abstração acima do nível de bit.

Então, finalmente, você pode até analisar no nível de bits.

STRING_START + (IDENTIFIER | WHITESPACE) + STRING_START.

Não, não pode. Que tal "("? Segundo você, essa não é uma sequência válida. E escapa?

Em geral, a melhor maneira de tratar o espaço em branco é ignorá-lo, além de delimitar os tokens. Muitas pessoas preferem espaços em branco muito diferentes e a aplicação de regras para espaços em branco é controversa, na melhor das hipóteses.