The Fnc-2 Attribute Grammar System

Didier PARIGOT

Oscar Project

FNC-2 is a modern AG-processing system that aims at production-quality by providing the following qualities:

Efficiency

the generated evaluators, based on the visit-sequence paradigm, are completely deterministic; furthermore, this paradigm allows to apply very effective space optimization techniques. The evaluators are hence basically as efficient in time and space as hand-written programs using a tree as internal data structure.

Expressive power

this efficiency is not achieved at the expense of expressive power since FNC-2 accepts AGs in the very broad class of strongly non-circular AGs. Explore new formalisms allowing more comfortable use of AGs (generic AGs )[ LeBellec93, LeBellec93a Roussel95] or more expressive power (Dynamic AGs [Parigot96a] , which subsume circular AGs and allow to work on DAGs and maybe more general graphs).

Easiness of use

OLGA, the input language of FNC-2, enforces a high degree of programming safety, reliability and productivity. The input language containt the following sub-languages:

• attributed abstract syntaxes ASX;
• attribute grammars;
• declaration and definition modules.

Versatility

the generated evaluators can be interfaced with many other tools and produced in many variations

• Several attributes evaluators
  • exhaustive evaluator
  • incremental evaluator [Parigot88, Roudet94] ;
  • parallel evaluator[ Marmol90, Jourdan92, Jourdan94, Marmol94].
• Several implementation languages
  • C version;
  • Le_Lisp version on Centaur system[ Attali94, Roudet94, Rouzier93] ;
  • fSDL version on The CoSy Compilation System ();
  • ML version on The Caml system [LeBatard95]

Some applications

• FNC-2 itself with companion processors (70 000 lines)
• Pagode code generator generator on the COSY compiler (50 000 lines)
• A translator of E-LOTOS language [Vivien97] (20 000 lines)
• A generator of unparsers of attributed abstract trees (PPAT). See the complete list of Applications.

Companion processors

In addition, FNC-2 comes with a number of companion processors that help to build complete applications

• a generator of abstract tree constructors driven by parsers (ATC); two instantiations of ATC have been implemented, one on top of SYNTAX, and one on top of Lex and Yacc;[Zylberman90]
• a generator of unparsers of attributed abstract trees (PPAT), based on the TeX-like notion of nested boxes of text; [Jouve90]
• and a tool for describing the modules composing an application and managing their processing (MKFNC2)
• a interactive application descriptions (XFNC2)[Amilien92 ]
• a interactive circularity trace system (XVISU)[Amilien93 ]
• a descriptional composition of AGs, i.e. the construction, from two ``piped'' AGs, of a third one that performs the same computation without constructing the intermediate tree; this allows to take full advantage of modularity without hampering efficiency. [Roussel94a]
• Source-level optimizations of AGs resulting from descriptional composition [Roussel94a].

How to get the FNC-2 system

Publications

The principal articles on FNC-2 attribute grammar are:

• ``Design,implementation and evaluation of the FNC-2 attribute grammar system''
• ``Internals and Externals of the FNC-2 Attribute Grammar System''
• The list of publication.