Parsing s-expressions is almost trivial. This is true for both automated processes (and thus implies ease of implementation of such processes) and for a human readers of printed s-expressions. It is the latter property that is the subject of this question.

The main cause for this simplicity is the one to one correspondence between certain tokens, and (types of) nodes in the AST. That is:

  • ( denotes the start of a list-expression,
  • ) the end of one,
  • whitespace separates atoms

That is: one can almost* look at an arbitrary substring of a printed s-expression and infer the structure of the associated AST.

Is there a name for this property of being able to infer the structure of a text locally, that is without any reference to the surrounding text, and using a 1-to-1 correspondence of certain tokens on screen and nodes in the AST?

I'm tempted to call this "explicitly structured", but that seems rather imprecise.

*"almost", because the parentheses might be quoted or part of a string literal; if we assume a mechanism of pretty-printing with relevant syntax highlighting for those cases, the qualification "almost" may be dropped.

  • $\begingroup$ I'm tempted to call it context free, but I'm not sure it's a total fit $\endgroup$ – ratchet freak Mar 28 '18 at 12:04
  • 1
    $\begingroup$ @ratchet: not a fit at all. $\endgroup$ – rici Mar 28 '18 at 14:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.