2 ms·
> Note that you also aren't using "token" in the usual way it appears in computer science I use the word such that we can talk about parsing, syntax, and synta
by lispm 8y ago
> Note that you also aren't using "token" in the usual way it appears in computer science
I use the word such that we can talk about parsing, syntax, and syntax trees at all. Lisp works different from most languages (the Lisp syntax is working over a data representation, syntax can depend on runtime state in the case of macros and a Lisp interpreter, ...), so I try to use related words to map that a bit.
We can look at the textual representation:
(let ((x '(* x x)))
(progv '(x) '(2)
(eval x)))
If we look at that code as text and/or as an S-expression, we have no idea what each X is. We have to construct that information by parsing or even by executing it. The s-expression is no AST (abstract SYNTAX tree), because it has no syntactic information represented, besides some structural information and on a textual level we can construct data objects from the tokens. Each token has a direct data representation (unless we have the reader re-programmed).
An AST OTOH has already been constructed as a tree, based on a syntax grammar for a programming language. To reach to an AST we need a parser + language syntax + a tree representation mechanism. The Lisp s-expression representation lacks the parser and the language syntax. All the s-expression represents is the data - internal and external. For an s-expression there is no difference between: (* x y) and (x y ). READ accepts externally represented data - it has no idea if the thing it successfully reads is a valid Lisp program or not. Only the parsing/interpretation of a that code snippet on the Lisp language level makes it possible to see if is a function or a variable. For that we need a grammar which says if that code is prefix, infix, postfix or something else. For Lisp it is much worse, since the interpretation of (foo (* x y)) depends on what foo actually does at runtime. In a Lisp interpreter, FOO could be a macro, which interprets the enclosed expression differently each time it gets executed.
If we look at an AST, we need to combine the s-expression + a syntax + plus something which acts similar to a parser to create an AST. Without that syntax, we can not generate that AST from the s-expression. IF we take a slightly different syntax, we are able to create different ASTs from an s-expression.
Note that the meaning of words like token, parser, lexer, scanner, ast, syntax has to be adjusted for Lisp. For example the ANSI CL standard contains EBNF-based syntax descriptions. But this syntax is actually over s-expressions (data - since we also need to be able what is a valid program as data) and not for textual representations of programs.
A token has two usual meanings: on the textual side it is the characters which form a basic element in the language, for example a number. In a representation, a scanner/lexer generates, it is then the data object which represents that thing. Think (defclass token () (text type ...)) and (defclass number-token (token) (numeric-value)). For Lisp the textual tokens are mapped to a more direct representation - each token gets translated into a typed data object (which has its type encode and which has a procedure to generate a textual representation back).