Por que separar lexing e análise?

15

É possível analisar um documento usando uma única passagem de uma máquina de estado. Qual é o benefício de ter dois passes, ie. tendo um lexer para converter texto em tokens e tendo um analisador para testar as regras de produção nesses tokens? Por que não ter uma única passagem que aplique regras de produção diretamente ao texto?

Brent
fonte
2
Isso já foi discutido no CS, stackexchange, com muitos comentários muito técnicos em uma resposta ao poder expressivo do lexer + parser . Mas pode haver espaço para mais respostas.
babou
Eu me pergunto se o paralelismo no estilo de pipeline (embora estágios altamente desequilibrados) possa ser uma vantagem colateral. O comportamento das instruções e do cache de dados também pode ser interessante. Quanto (se for o caso) reduziria o tempo de compilação dependeria do hardware específico.
Paul A. Clayton
Um motivo bastante óbvio (pelo menos para mim) é que você pode usar a ferramenta de scanner separadamente. Na prática, freqüentemente uso o flex para digitalizar as entradas, mas raramente preciso de toda a potência do yacc.
jamesqf

Respostas:

13

Você não precisa separá-los. As pessoas as combinam em analisadores sem scanner .

A principal desvantagem dos analisadores sem scanner parece ser que as gramáticas resultantes são bastante complicadas - mais complicadas do que a combinação correspondente de uma expressão regular fazendo lexing e uma gramática sem contexto fazendo análise no fluxo de token. Em particular, gramáticas para análise sem scanner tendem a ambiguidade. É mais fácil remover a ambiguidade das gramáticas que trabalham em um fluxo de token.

Um benefício pragmático do uso de uma fase de lexing inicial dedicada é que você não associa o analisador subsequente a detalhes lexicais. Isso é útil durante o desenvolvimento inicial da linguagem de programação, quando os detalhes lexicais e sintáticos ainda estão mudando com frequência.

Martin Berger
fonte
11
TPPPT
@babou Sim, isso está correto. Não conheço nenhum resultado formal da forma expressão regular composta com LL (k) sai de LL (k), ou similar. Além disso, o lexing geralmente não é feito com idiomas regulares, mas com algo mais poderoso, ou seja, idiomas regulares estendidos com as prioridades de correspondência mais longa e primeira palavra-chave. Não tenho certeza de qual classe de idioma exata é e quais são suas propriedades de fechamento.
Martin Berger
2
Se sua previsão envolver a leitura de um identificador, a composição exigirá uma previsão ilimitada, pois não há (em princípio) nenhum limite para o comprimento dos identificadores.
babou
@babou Não tenho certeza. Se a palavra-chave mais longa tiver 17 caracteres, qualquer sequência maior deverá ser um identificador ou ser lexicamente inválida.
Martin Berger
Mas você identificador, ou possivelmente uma string, número ou outro literal, é uma sequência com mais de 17 símbolos individuais, que pode estar diante do token que você realmente precisa. Esse é um grande olhar à frente, sem limites. Você pode acabar com uma linguagem não determinística.
babou