Re: [seweb-list] Re: Compiling with XSLT

Pete,

I was referring to the Chomsky hierarchy of grammars:

  1. Finite-state (or regular) grammars

  2. Context-free grammars

  3. Context-sensitive grammars

  4. Unrestricted phrase-strucure (or Turing) grammars

PK> I don't get what you mean by saying that XML is context-free.
 > do you mean just the base encoding syntax of '<' and '>' or the
 > tree which all the tools operate on(which has more context
 > available than most ASTs, as you can use .. in XPath to navigate
 > to the parent node)?

I agree that the parse tree is a very rich data structure.
But it is the result of parsing by means of a context-free
grammar in Chomsky's sense.  All common programming languages
use a context-free base grammar, but they also have context-
sensitive aspects that cannot be specified (or recognized)
by a C-F grammar.

Those C-S aspects are generally handled by means of some
auxiliary storage (such as a symbol table), which records
information about certain entities (such as the use or
declarations of variables).  The symbol table makes that
information available as needed during the compilation
(or interpretation) of the language.

A complete parse tree generated by a C-F parser would
contain all declarations and occurrences of variables.
As John Hanna said, it would, in principle, be possible
for a program to search the parse tree whenever it needed
information about some variable.  But I agree with John
that anybody who wrote such a program would either go
insane or produce code that would be extremely inefficient
in comparison to a program that merely checked a symbol
table for the information it needed.

In fact, if you have symbol tables (or the dictionary
or hash tables of many programming languages), it is not
necessary to save (or even generate) a parse tree since
the translation to some other language could be done with
locally available information together with information
from the symbol table.

John

Received on Friday, 18 June 2004 13:11:36 UTC