Em qual processo ocorre o erro de sintaxe? (tokenização ou análise)

23

Estou tentando entender compilação e interpretação, passo a passo, descobrindo uma imagem total. Por isso, fiz uma pergunta ao ler http://www.cs.man.ac.uk/~pjj/farrell/comp3.html este artigo

Diz :

O próximo estágio do compilador é chamado de analisador. Esta parte do compilador possui um entendimento da gramática da linguagem. Ele é responsável por identificar erros de sintaxe e por traduzir um programa sem erros em estruturas de dados internas que podem ser interpretadas ou gravadas em outro idioma.

Mas não consegui descobrir como o tokenizer pode tokenizar adequadamente o fluxo especificado que possui o erro de sintaxe.

Ele deve ficar preso ou fornecer informações erradas ao analisador. Quero dizer, o tokenizing também não é um tipo de tradutor?

Então, como ele simplesmente supera as linhas lexicais de código corrompidas ao usar token.

Há um exemplo de token dentro do link acima no cabeçalho do Tokenizer .

Pelo que entendi, parece que a forma do token, se houver algo errado no token de código, também estará corrompido.

Poderia, por favor, esclarecer meu mal-entendido?

FZE
fonte

Respostas:

32

Um tokenizer é apenas uma otimização de analisador. É perfeitamente possível implementar um analisador sem um tokenizador.

Um tokenizador (ou lexer ou scanner) divide a entrada em uma lista de tokens. Algumas partes da string (comentários, espaço em branco) geralmente são ignoradas. Cada token possui um tipo (o significado dessa string no idioma) e um valor (a string que compõe o token). Por exemplo, o trecho de código-fonte PHP

$a + $b

pode ser representado pelos tokens

Variable('$a'),
Plus('+'),
Variable('$b')

O tokenizer não considera se um token é possível nesse contexto. Por exemplo, a entrada

$a $b + +

alegremente produziria o fluxo de token

Variable('$a'),
Variable('$b'),
Plus('+'),
Plus('+')

Quando o analisador consome esses tokens, ele notará que duas variáveis ​​não podem se seguir e nem dois operadores de infixo. (Observe que outros idiomas têm sintaxes diferentes, onde um fluxo de token pode ser legal, mas não no PHP).

Um analisador ainda pode falhar no estágio do tokenizer. Por exemplo, pode haver um caractere ilegal:

$a × ½ — 3

Um tokenizador PHP seria incapaz de corresponder essa entrada às suas regras e produziria um erro antes do início da análise principal.

Mais formalmente, os tokenizadores são usados ​​quando cada token pode ser descrito como um idioma comum . Os tokens podem ser correspondidos com extrema eficiência, possivelmente implementados como um DFA. Por outro lado, a gramática principal geralmente é livre de contexto e requer um algoritmo de análise mais complicado e com menos desempenho, como o LALR.

amon
fonte
Portanto, podemos pensar que o tokenizer faz parte do analisador e o erro de sintaxe pode ocorrer na etapa de tokenização ou na etapa de análise de acordo com o formulário de erro de sintaxe. Obrigado pelo esclarecimento.
FZE 31/03
4
@FZE: Você poderia pensar assim, mas é enganador. Lexing não é "apenas uma otimização de analisador". Em vez disso, o lexing mapeia uma representação física (alguma sequência de caracteres) em uma representação lógica (os tokens representados por esses caracteres). Isso isola o analisador de minúcias, como a representação do final de uma linha ou se você decide representar uma lógica - e como andou &&ou qualquer outra coisa. É (principalmente) separado e diferente da análise. A otimização (se houver) é um efeito colateral quase acidental.
Jerry Coffin
@JerryCoffin obrigado pela explicação adicional que faz mais sentido agora.
FZE 31/03
2
@JerryCoffin, amon está correto, essa é a diferença não é fundamental. Você pode criar uma gramática BNF coesa que cubra as partes "lexer" e "parser". Geralmente, categorizamos as regras em baixo nível (por exemplo, número, operador de adição) e alto (soma), mas a gramática em si não faz essa distinção.
Paul Draper
1
@PaulDraper Não tenho certeza se a separação de um idioma comum como primeira fase é a escolha certa. Por exemplo, pares correspondentes (não regulares) podem ser necessários para descrever literais de strings em alguns idiomas, mas ainda faz sentido manipulá-los na primeira fase. Evitar / minimizar o rastreamento posterior parece uma orientação melhor.
CodesInChaos
16

Você normalmente espera que a maioria dos erros de sintaxe venha do analisador, não do lexer.

O lexer geraria um erro se (e principalmente somente se) houver algo na entrada que não possa ser tokenizado. Em muitos idiomas, no entanto, quase qualquer sequência de caracteres pode ser transformada em algum tipo de tokens; portanto, os erros aqui são bastante incomuns.

O analisador gerará um erro se a entrada contiver tokens válidos, mas esses tokens não estiverem organizados para formar declarações / expressões válidas no idioma de destino. Isso é muito mais comum como regra.

Jerry Coffin
fonte
11

O tokenizador apenas divide o fluxo de caracteres em tokens. No tokenizer POV, isso é completamente válido:

1 * * 1

e traduz para algo como: ["1", MULTIPLY, MULTIPLY, "1"] Apenas o analisador pode rejeitar essas expressões - ele sabe que o operador multiplicador não pode seguir outro operador multiplicador. Por exemplo, em JavaScript, isso produz:

Uncaught SyntaxError: Unexpected token *(…)

Existem erros que podem ser detectados pelo tokenizer. Por exemplo literais inacabadas string: "abcou números inválidos: 0x0abcdefg. Eles ainda podem ser relatados como erros de sintaxe:

Uncaught SyntaxError: Unexpected token ILLEGAL

Observe, no entanto, o token não foi reconhecido e é relatado como ILLEGAL.

Banthar
fonte