Re: RM and abstract syntax trees

On Oct 29, 7:06 pm, David BL <davi..._at_iinet.net.au> wrote:

> The inappropriateness of the RM for ASTs is highlighted when we
> interpret tuples as propositions or facts. Consider the following
> expression
>
> (x + 1) * 3
>
> In order to state the fact that this expression consists of the
> product of subexpressions '(x+1)' and '3', one must clearly assign
> names to the things about which we want to state facts. No wonder the
> RM forces us to go on a naming spree.

And when you consider the above expression in the language theory you don't assign grammar symbols to each subexpression? In your example they clearly are:

number : 1 | 3;
expr : number | expr + expr | expr * expr | ( expr );

> By contrast, in LISP we may directly represent the above expression
> using the following S-expression
>
> (* (+ x 1) 3)
>

So? What power Lisp gives you in the realm of languages and grammars?

> There is an important philosophical difference : In LISP, Prolog or C
> we *directly* represent the AST as an entity that is *part of the
> abstract computational machine*.

AST is an implementation artifact of a particular parsing algorithm. In general case when you have a string of tokens and match it against a set of grammar rules, the result don't fit into AST (because of ambiguity).Some methods, like CYK don't produce AST, and yet you can still deduse many facts about the parsed string of tokens from the matrix that CYK outputs. Received on Wed Oct 31 2007 - 23:23:21 CET