Re: Designing Lisp from scratch

On 23-Mar-07, at 8:22 AM, Shriram Krishnamurthi wrote:

>> I guess the main reason you may have a hard time finding lex/yacc
>> parsers for Lisp is that Lisp parsers are built into every Lisp  
>> system.
>> Thus, if you want to parse Lisp code, you just use Lisp and say  
>> (read).
>
> Bzzzt.
>
> READ does not *parse*.  Parsing is regarded as the process of
> distinguishing valid terms from invalid terms, accounting for the
> context-sensitive (and more) constraints of the language.

Is this the generally accepted definition?

For instance, it seems to also include type checking, or even more  
advanced forms of validation, all the way up to full theorem proving  
(to exclude "incorrect" programs.) The problem is the word "valid":  
it is too strong to be captured by the type of computation typically  
associated with parsers.

My impression is that in practice, "parsing" usually refers to the  
process of transforming text from a linear representation into a  
structured representation, with that structure conforming to a (more  
or less) context-free grammar. Subsequent stages of validation are  
usually classified as "semantic analysis", admittedly a vague term,  
but widely used.

The "Dragon Book" considers "parsing" and "syntax analysis" as  
synonyms, and defines both as "grouping the tokens of the source  
program into grammatical phrases that are used by the compiler to  
synthesize output."

In the more general context of formal languages, the term I always  
encountered was "acceptance", as in "this Turing machine accepts this  
language", without any reference to parsing.

> Of course, this is the same as the distinction between well-formedness
> and validity in XML.

But XML parsers just parse. If they also validate, that function is  
explicitly stated, as in  "XML validating parser". I take this as an  
argument for the view that the term "parser" when used unqualified  
denotes the weaker notion of turning linear input into trees.

--Florin