Processamento de Linguagens I

Aulas Teorico-Praticas
Matematica e Ciencias da Computacao

Engenharia de Sistemas e Informatica

Ano Lectivo 2004/2005
Downloading and Installing the LRC System
Library of Attribute Grammar Components
Example of Constructed Tools
Installing the AG_LIB and TOOLS
LRC Lecture Notes
Past Student Projects

This page includes information to support the laboratory classes of the course Processamento de Linguagens I (introduction to language processing) running in the scholar year 2004-2005 . Processamento de Linguagens I is a course of the 3rd year in the curriculum of the graduation on  Engenharia de Sistemas e Informatica) (Software Engineering) and Matematica e Ciencias da Computacao (Mathematics and Computer Science).

This page is being produced from an XML document by a tool DocProc (a tool generated by LRC) which uses the formal methods introduced in this course (e.g., regular expressions, finite automata, context-free grammars, attribute grammars, pretty printing, etc). From the XML document , both an HTML (this page) and a LaTeX document are automatically generated.


  • Jun 7: A prototype of a heap modelled in C-- is available in the new version of the [AG-LIB_DOC_TOOLS.tgz] , or as the source C-- file [heap.c--] and generated MSP file [heap.msp]
    • It includes list functions to create, cons, free, concat, elem, etc 
    • It does not check for heap overflow...
    • It is just a simple prototype that "seams" to work (altough is becoming too big for the winmsp interpreter...)
  • Jun 2: A new version of the tool MicroC is available. This version handles recursive functions. That is, it produces thr right MSP code for recursice functions in C--. It is available from the new distribution of the libs and tools at  [AG-LIB_DOC_TOOLS.tgz]
    • To see the difference between recursion and iteration , produce msp for the two versions of the factorial function defined (in the test directory) fac.c-- and facRec.c-- and run the two in winMSP. Note the difference in the number of stack operations...
    • Obviously, the (MicroC) compilers should optimize the generated code by eliminating (tail) recursion and thus producing code for the iterative version of the function. Any volunteer(s) to implement this optimization in MicroC (in the summer)?
  • May 30: The version of the LRC system that solves the bug of running the executables with a non-defined view is now available. Just install the new rpm [Fedora 3] or the new C sources [lrc.tgz] .
  • May 30: A new version of the library of attribute grammar components (AG_LIB) and the tools built on top of such libraries are available at [AG-LIB_DOC_TOOLS.tgz]
    • It includes a new README file for the MicroC to MSP tool
    • It is distributed with all SSL files, and do not depend on the noweb system
  • The binary distribution for Mac OS 10.4 is available at [Mac OS 10.4]
  • The WinMSP : an interpreter , visualizer of MSP (a simple assembly stack machine/language) is available at [WinMSP.tgz] . This is a window-based application. To run it under linux you may use wine an Open Source implementation of the Windows API on top of X and Unix availabable at [Wine homepage] .

The RPM for Fedora 3 is available at [Fedora 3]
A Haskell front-end (written in LRC) has been constructed and added to AG_LIB.
  • This front-end is used in the web registration system of the conference GTTSE 2005 . Indeed, the web system is totally constructed in LRC + Haskell!
Expat - a C library for parsing XML - has been incorporated to LRC.
  • This parser is now used as the front-end of some XML-based tools constructed with LRC (e.g., DocProc ).
  • The Expat library is available at Expat homepage

1- Downloading and Installing the LRC System

  • The homepage of the LRC system is Lrc Homepage

  • The LRC system can easily be installed from binaries (RPMs) distributions. There are RPMs availables for: 

  • The LRC system, some of the tools and libraries have been developed using the literate programming system noweb. To process such specifications we have to install the noweb system: [noweb]
  • To be able to visualize the graphical representation of the AST, we need to install the GraphViz library (to see ..).

2- Library of Attribute Grammar Components

The LRC system is distributed with a library - named AG_LIB - of attribute grammar generic components which can easily be plugged-into any attribute grammar specification. For example, the AG_LIB contains components
  • Combinators of HTML, XML, Documents
  • Powerful and Generic Pretty Printing combinators
  • A set of front-ends for languages such as SSL, (Micro) C, Dot, MSP, etc
  • Querying Combinators
  • Generic Attribute Grammar Component for Name Analysis

3- Example of Constructed Tools

These are the tools distributed with LRC:
  • BiBTeX: A bibliographic database processor
  • Block: Generic Name Analysis Algorithm
  • DocProc: An XML-based Document Processor
  • Gram2C: Tools to embed grammars in C
  • microC: Compiler for (subset of) C. Produces MSP
  • spreadsheet: Students Spreadsheet
  • WebSystem: GTTSE2005 Web System
  • Xml4Free: Embeds XML in LRC

4- Installing the AG_LIB and TOOLS

  • The AG_LIB , the documentation and tools are not being distributed with the RPMs. You may download these files from [AG-LIB_DOC_TOOLS.tgz]

5- LRC Lecture Notes

  • The LRC system accepts as input the attribute grammar specification language SSL. This language is described in the book "The Synthesizer Generator Reference Manual" (see bibliografia).
  • To start working with the LRC system we recommend:
    • To carefuly read the first exercise proposed below. This first exercise is defined in literate programming and it gives a short introdution to the LRC system. It includes a simple example (a processor of lists of integer numebrs) that can be directly processed by LRC.
    • To study and execute the Block processor as described in  [Block] . This problem is also included as one of the example tools.
    • [] describes some bugs detected in the system.
    • [] explains how to build an interactive interface (programming environment) in LRC.

  • Next, we present a set of exercises to be solved with LRC. Each exercise discusses one particular feature of the LRC system.
    • LRC: regular expressions, concrete and abstract grammar, and unparsing rules [1.tgz]
    • LRC: Desk Calculator [2.tgz]
    • LRC: Multiple View and Tree Transformations [3.tgz]
    • LRC: Structure Editors and Attribute Grammars [4.tgz]
    • LRC: Scope Rules for Block.structured Languages [5.tgz]
    • LRC: Component-based Attribute Grammar Programming [6.tgz]
    • LRC: Interactive Interfaces [7.tgz]

6- Past Student Projects

Next we present the studens projects proposed in previous instances. Possible solutions for such projects are available as well.

  • João Saraiva and Matthijs Kuiper Lrc - A Generator for Incremental Language-Oriented Tools 7th International Conference on Compiler Construction, CC/ETAPS'98, Kay Koskimies, LNCS 1383 1998
  • João Saraiva Component-based Programming for Higher-Order Attribute Grammars proceedings of the ACM SIGPLAN SIGSOFT Conference on Generative and Component-Based Software Engineering (GPCE/PLI'02), Pittsburgh, USA [PS] 2002
  • Doaitse Swierstra and Pablo Azero and João Saraiva Designing and Implementing Combinator Languages Third Summer School on Advanced Functional Programming, LNCS 1608 1998
  • João Saraiva and Doaitse Swierstra Data Structure Free Compilation 8th International Conference on Compiler Construction, CC/ETAPS'99, Stefan Jahnichen, LNCS 1575 1999
  • João Saraiva Purely Functional Implementation of Attribute Grammars 1999 [PS]
  • Thomas Reps and Tim Teitelbaum The Synthesizer Generator Reference Manual third edition Edicao Springer Verlag 1989

Pagina mantida por:

João Saraiva
Page produced by a Tool generated by LRC from the XML document pagina_pli.xml

Last Change on Tue Jun 7 09:08:00 2005