Re: Lex, Yacc, and Lisp...

Ray Dillinger <bear@xxxxxxxxx> writes:

> I had a random thought the other day. Lisp could easily
> be the "back end" or "executable intermediate representation"
> for most language compilers.
>
> Consider this: some student in a CS course designs a language.
> He uses flex or lex to create a lexer, yacc or bison to parse
> the tokens into a syntax tree according to a grammar, and
> then does a traversal of the syntax tree where each node is
> preceded by an open-paren and the name of the node type (from
> the grammar), and followed by a close-paren.

Why not write the compiler in Lisp? There are parser generator
available. Besides, writing a recursive descent parser in Lisp is
straight-forward.


> The output of this traversal can be considered as a lisp
> expression. The final step in implementing the student's
> language is to implement lisp definitions (probably macros)
> for each grammar node type that perform the semantic action
> of that node type according to the language design.

Sounds like an elegant solution. However, doing a simple translation
from a tree-structured intermediate language to a lower level tends to
be pretty straight-forward. Using macros would allow you to avoid the
explicit case analysis, but the case analysis is the easy part, so you
wouldn't gain much.


> This seems like an easier method of implementing most
> languages, and Lisp, with its syntactic flexibility, is
> uniquely even more suited to being a "universal" target
> metalanguage than, say, the JVM or .NET to name a couple
> of the usual suspects.

>From a practical point of view, using Lisp as a backend has many
advantages. However, if we are talking about a compilers course and
one of the goals of the course is to teach how machine code is
generated, you would miss out on that.


> Have I missed important things?

You haven't explained why you want to do this :-)


> What would be hard to do with this approach?

If the goal is to implement an experimental language as easily as
possible, but with reasonable performance, then I think that a
translation to Lisp would be the easiest route. This is of course
under the assumption that the libraries you need may be accessed from
Lisp. (And if interfacing with the libraries is hard, then that might
be one of the main obstacles.)


Sven-Olof


--
Sven-Olof Nystrom
Comp Sci Dept, Uppsala University, Box 337, S-751 05 Uppsala SWEDEN
svenolof@xxxxxxxxx, http://www.csd.uu.se/~svenolof
phone: +46 18 471 76 91, fax: +46 18 51 19 25


.

Relevant Pages

  • Re: a dozen cpus on a chip
    ... No nontrivial language can ever be proven to be imposible to crash. ... compilers still available which implement ISO M2. ... It is a common misconception that Lisp is always interpretted. ... various X86 machines the hardware does exist that could allow the OS ...
    (sci.electronics.design)
  • Re: ILC2005: McCarthy denounces Common Lisp, "Lisp", XML, and Rahul
    ... >> the language should be available to users. ... In the design of Common Lisp, I asked Dave Moon (one of the architects ... Now, there are good kinds of low-level, like the way that floats are ...
    (comp.lang.lisp)
  • Re: CollabRx seeks brilliant engineers for an excellent e-science adventure
    ... belief that lisp programmers are smarter/better. ... Java or PHP programmers. ... a type of language that attracts a personality that meets my perceptions ...
    (comp.lang.lisp)
  • Re: Whats the best language to learn...
    ... on processors designed to run Lisp and Lisp OSes. ... byte-addressed memory, has native support for variable-sized value types, ... popular OO language, rather a language about like that of Delphi would have ... lisp, java, ruby, etc. ...
    (comp.programming)
  • Re: Program compression
    ... TM> supported by your favorite language (LISP) are good concepts. ... then call the Java compiler to compile that source file to a Class ... TM-STC> Since static type checking makes run-time type checks unnecessary, ...
    (comp.programming)