Expressing Programming Language Semantics (AST -> ASG)

Question

Do you have any pointers to information/research related to expressing computer language semantics in the same way, syntactical requirements are formalized using codified/markup notations (such as for example EBNF)?

Thanks

Answer 1

Wikipedia has information about formal semantics: http://en.wikipedia.org/wiki/Formal_semantics_of_programming_languages

Answer 2

There's a whole ton of literature on this problem. Peter Mosses wrote a book called Action Semantics. Peter Lee and Andrew Appel both did doctoral dissertations on generating a compiler from a formal description of semantics; I think Peter's came out as a book.

Bill Waite's group at Colorado did a compiler-construction toolkit called Eli that covered everything from lexing to parsing to semantics. Tom Reps's work on attribute grammars was aplied to language semantics among other things. There was also some European work using attribute grammars, but I can't remember the acronyms or the people.

Good places to dip your toe in might include

• Don Knuth's original paper on attribute grammars
• Peter Lee's dissertation
• Eli
• Maybe Peter Mosses's book, although I seem to rememeber I found it heavy going

Answer 3

Benjamin Pierce's book Types and Programming Languages is a good place to start. It uses "operational small step semantics" as a formal specification for programming languages.

Another good resource might be John Boyland's PHD thesis.

He developed a system called APS that can generate an entire compiler using attribute grammars.