¿En qué proceso se produce el error de sintaxis? (tokenización o análisis)

23

Estoy tratando de entender la compilación y la interpretación, paso a paso, descubriendo una imagen total. Entonces hice una pregunta mientras leía http://www.cs.man.ac.uk/~pjj/farrell/comp3.html este artículo

Dice :

La siguiente etapa del compilador se llama Analizador. Esta parte del compilador comprende la gramática del lenguaje. Es responsable de identificar los errores de sintaxis y de traducir un programa sin errores en estructuras de datos internas que se puedan interpretar o escribir en otro idioma.

Pero no pude entender cómo el tokenizador puede tokenizar correctamente la secuencia dada que tiene el error de sintaxis.

Debería estar atascado allí o proporcionar información incorrecta al analizador. Quiero decir, ¿no es la tokenización también una especie de traductor?

Entonces, ¿cómo acaba de superar las líneas de código léxicas corruptas mientras se tokeniza?

Hay un ejemplo de token dentro del enlace anterior en el encabezado The Tokenizer .

Según tengo entendido, la forma del token parece, si hay algo mal en el token de código también estaría dañado.

¿Podría por favor aclarar mi malentendido?

FZE
fuente

Respuestas:

32

Un tokenizer es solo una optimización de analizador. Es perfectamente posible implementar un analizador sin un tokenizador.

Un tokenizer (o lexer, o escáner) corta la entrada en una lista de tokens. Algunas partes de la cadena (comentarios, espacios en blanco) generalmente se ignoran. Cada token tiene un tipo (el significado de esta cadena en el idioma) y un valor (la cadena que forma el token). Por ejemplo, el fragmento de código fuente PHP

$a + $b

podría ser representado por los tokens

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

El tokenizer no considera si un token es posible en este contexto. Por ejemplo, la entrada

$a $b + +

produciría felizmente la secuencia de tokens

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

Cuando el analizador consume estos tokens, notará que dos variables no pueden seguirse, y tampoco dos operadores infijos. (Tenga en cuenta que otros lenguajes tienen diferentes sintaxis donde tal flujo de tokens puede ser legal, pero no en PHP).

Un analizador aún puede fallar en la etapa de tokenizer. Por ejemplo, puede haber un carácter ilegal:

$a × ½ — 3

Un tokenizador de PHP no podría hacer coincidir esta entrada con sus reglas y produciría un error antes de que comience el análisis principal.

Más formalmente, los tokenizadores se usan cuando cada token se puede describir como un lenguaje normal . Los tokens se pueden combinar de manera extremadamente eficiente, posiblemente implementado como un DFA. Por el contrario, la gramática principal suele estar libre de contexto y requiere un algoritmo de análisis más complicado y de menor rendimiento, como LALR.

amon
fuente
Por lo tanto, podríamos pensar que el tokenizador es parte del analizador sintáctico y el error de sintaxis puede ocurrir ya sea en el paso de tokenización o en el paso de análisis de acuerdo con el formulario de error de sintaxis. Gracias por la aclaración.
FZE
44
@FZE: Usted podría pensar de esa manera, pero es engañosa. Lexing no es "solo una optimización del analizador sintáctico". Por el contrario, lexing asigna una representación física (alguna secuencia de caracteres) en una representación lógica (los tokens representados por esos caracteres). Esto aísla el analizador de minucias como cómo se representa el final de una línea, o sea que decida representar una lógica -y como ando &&algo o de lo contrario. Es (principalmente) separado y diferente del análisis. La optimización (si la hay) es un efecto secundario casi accidental.
Jerry Coffin
@JerryCoffin gracias por la explicación adicional que tiene más sentido ahora.
FZE
2
@JerryCoffin, amon es correcto, esa es la diferencia no es fundamental. Puede crear una gramática coherente de BNF que cubra las partes "lexer" y "parser". Por lo general, clasificamos las reglas en bajo nivel (por ejemplo, número, operador de suma) y alto nivel (suma), pero la gramática en sí misma no hace tal distinción.
Paul Draper el
1
@PaulDraper No estoy seguro si separar un idioma regular como primera fase es la opción correcta. Por ejemplo, los pares coincidentes (no regulares) pueden ser necesarios para describir literales de cadena en algunos idiomas, sin embargo, aún tiene sentido manejarlos en la primera fase. Evitar / minimizar el retroceso parece una mejor guía.
CodesInChaos
16

Por lo general, esperaría que la mayoría de los errores de sintaxis provengan del analizador, no del lexer.

El lexer generaría un error si (y principalmente solo si) hay algo en la entrada que no puede ser tokenizado. Sin embargo, en muchos idiomas, casi cualquier secuencia de caracteres se puede convertir en fichas de algún tipo, por lo que los errores aquí son bastante inusuales.

El analizador generará un error si la entrada contiene tokens válidos, pero esos tokens no están organizados, por lo que forman declaraciones / expresiones válidas en el idioma de destino. Esto es mucho más común como regla.

Jerry Coffin
fuente
11

Tokenizer solo divide la secuencia de personajes en tokens. Desde el tokenizer POV esto es completamente válido:

1 * * 1

y se traduce en algo como: ["1", MULTIPLY, MULTIPLY, "1"] solo el analizador puede rechazar tales expresiones; sabe que el operador de multiplicación no puede seguir a otro operador de multiplicación. Por ejemplo, en JavaScript, esto produce:

Uncaught SyntaxError: Unexpected token *(…)

Hay errores que pueden ser detectados por el tokenizer. Por ejemplo literales de cadena: sin terminar "abco números no válidos: 0x0abcdefg. Sin embargo, aún podrían informarse como errores de sintaxis:

Uncaught SyntaxError: Unexpected token ILLEGAL

Sin embargo, tenga en cuenta que el token no se reconoció y se informa como ILLEGAL.

Banthar
fuente