5 ms·

There are many cases where parsing of Lisp code is necessary. A compiler will need to parse it. A compiler might even generate an internal AST representation (E

by lispm 8y ago

There are many cases where parsing of Lisp code is necessary. A compiler will need to parse it. A compiler might even generate an internal AST representation (Example: https://github.com/clasp-developers/clasp/blob/master/src/lisp/kernel/cleavir/ast.lisp https://github.com/clasp-developers/clasp/blob/master/src/li... ). An interpreter will need to understand the syntax, to be able to traverse code. A tool like a code walker will need to understand Lisp syntax and even may create an AST representation (https://gitlab.common-lisp.net/cl-walker/cl-walker/blob/master/src/handlers.lisp https://gitlab.common-lisp.net/cl-walker/cl-walker/blob/mast...).

kazinator 8y ago
Recovering an AST representation from the source code doesn't require parsing in general, only in some specific cases. By parsing I mean "recovering of nested syntactic units from a flat stream of tokens". E.g. when a compiler is processing let, it doesn't have to first process phrase structure rules to obtain let as a unit out of a stream of tokens, and identify its constituent pieces like the bindings and body. It has those pieces already in a fixed tree shape. In some constructs, the arguments of a form do have to be treated like tokens and subject to parsing actions to identify the constituent pieces, though usually nothing like a full blown LALR(1) grammar. loop has to parse its clauses; lambda lists have to be parsed; CL's defun needs some light parsing due to some design quirks in the syntax; formatter has to parse the format string and such. Identifying the optional declarations at the start of a body is a piece of light parsing.
- lispm 8y ago
  > fixed tree shape But it does not know what it is. It has to know the structure of the LET. The LET expression has no tagging of the parts. Is that list after the binding list a declaration or not? How many of them? Is the symbol in the list after a LET a variable? The s-expression does not say what a symbol is: a variable or not. We also don't know what the relationship of the declaration to this variable is: is there a declaration for this variable? The relatively simple syntax of LET: let ({var | (var [init-form])}) declaration form* We then see that the syntax for 'declaration' is quite a bit more complex. An AST will usually represent such information. > parsing I mean "recovering of nested syntactic units from a flat stream of tokens in Lisp this is: recovering of nested syntactic units from a nested list of tokens.
  - pflanze 8y ago
    This, together with taeric's question about tokenization made me realize that we can think of it this way: Macros are not receiving AST nodes [1]. They are not receiving tokens either, though. But something in-between: how many tokens it receives is strictly delimited (by the end paren which ends the macro form, but the macro doesn't see an end paren token, just doesn't get more items in the list, thus can't violate the scoping). Lisp forces open and end parens to be understood as hierarchical grouping indicators for (any kind of) syntax. This simple change over a stream of tokens seems to happen to simplify language creation via macros a lot. [1] quite definitely not before macro-expanding their arguments. After macro-expansion, by grouping the resulting s-expr with a context and a correct tree-walker, I guess it could be said to be one.
    - kazinator 8y ago
      Macros are expanded by a correct tree walker: the macro expander. It recognizes all special forms, and maintains an environment representing information about the lexical scope (at least in any Lisp dialect worth a damn, with lexical macros that can shadow lexical functions and variables and vice versa). Macros can also receive that environment as an argument, which provides the possibility that there can be an API by which macros can query the lexical environment. Furthermore, if macros are given an API for fully expanding an expression, with detailed information about what free references occur in that form, that creates a lot of possibilities for macros to do all sorts of clever things correctly, far beyond just "sticking pieces into a code template with a sprinkling of gensyms".
      - pflanze 8y ago
        I was talking about macro-expanding the form first so that the result to be walked consists of only "core" lisp forms. Do you mean that there are macro-expander APIs in CL that offer all ingredients to do the derivation as part of the macro-expansion step? (I'd welcome some pointer to study.)
        kazinator 8y ago

by lispm 8y ago

kazinator 8y ago

Recovering an AST representation from the source code doesn't require parsing in general, only in some specific cases. By parsing I mean "recovering of nested syntactic units from a flat stream of tokens". E.g. when a compiler is processing let, it doesn't have to first process phrase structure rules to obtain let as a unit out of a stream of tokens, and identify its constituent pieces like the bindings and body. It has those pieces already in a fixed tree shape. In some constructs, the arguments of a form do have to be treated like tokens and subject to parsing actions to identify the constituent pieces, though usually nothing like a full blown LALR(1) grammar. loop has to parse its clauses; lambda lists have to be parsed; CL's defun needs some light parsing due to some design quirks in the syntax; formatter has to parse the format string and such. Identifying the optional declarations at the start of a body is a piece of light parsing.

lispm 8y ago
> fixed tree shape But it does not know what it is. It has to know the structure of the LET. The LET expression has no tagging of the parts. Is that list after the binding list a declaration or not? How many of them? Is the symbol in the list after a LET a variable? The s-expression does not say what a symbol is: a variable or not. We also don't know what the relationship of the declaration to this variable is: is there a declaration for this variable? The relatively simple syntax of LET: let ({var | (var [init-form])}) declaration form* We then see that the syntax for 'declaration' is quite a bit more complex. An AST will usually represent such information. > parsing I mean "recovering of nested syntactic units from a flat stream of tokens in Lisp this is: recovering of nested syntactic units from a nested list of tokens.
- pflanze 8y ago
  This, together with taeric's question about tokenization made me realize that we can think of it this way: Macros are not receiving AST nodes [1]. They are not receiving tokens either, though. But something in-between: how many tokens it receives is strictly delimited (by the end paren which ends the macro form, but the macro doesn't see an end paren token, just doesn't get more items in the list, thus can't violate the scoping). Lisp forces open and end parens to be understood as hierarchical grouping indicators for (any kind of) syntax. This simple change over a stream of tokens seems to happen to simplify language creation via macros a lot. [1] quite definitely not before macro-expanding their arguments. After macro-expansion, by grouping the resulting s-expr with a context and a correct tree-walker, I guess it could be said to be one.
  - kazinator 8y ago
    Macros are expanded by a correct tree walker: the macro expander. It recognizes all special forms, and maintains an environment representing information about the lexical scope (at least in any Lisp dialect worth a damn, with lexical macros that can shadow lexical functions and variables and vice versa). Macros can also receive that environment as an argument, which provides the possibility that there can be an API by which macros can query the lexical environment. Furthermore, if macros are given an API for fully expanding an expression, with detailed information about what free references occur in that form, that creates a lot of possibilities for macros to do all sorts of clever things correctly, far beyond just "sticking pieces into a code template with a sprinkling of gensyms".
    - pflanze 8y ago
      I was talking about macro-expanding the form first so that the result to be walked consists of only "core" lisp forms. Do you mean that there are macro-expander APIs in CL that offer all ingredients to do the derivation as part of the macro-expansion step? (I'd welcome some pointer to study.)
      - kazinator 8y ago