From: PEM moderator
To:
Date: Mon, 24 May 2004 09:10:13 +0200
Subject: PEM meeting | 27.05.04 | F013

   Hi,

   You are invited to attend the following talk:

   This announcement can be found at <http://www.cwi.nl/~pem>

               The analysis of generalised parsing algorithms

   Date:    27.05.04
   Time:    10:00
   Venue:   F013
   Speaker: Rob Economopoulos
   Title:   The analysis of generalised parsing algorithms

   A parser is a function, associated with a grammar, that takes as input
   a  string  of  symbols  and produces a derivation for the input if the
   string  is  in  the  language  of  the  grammar  and  an error message
   otherwise.

   Masaru Tomita developed an efficient parsing algorithm that works on a
   large  subset  of the context free grammars, but fails to terminate on
   grammars  containing  hidden  left  recursion. Although several people
   claim  to  fix  this  problem,  their  modifications  result  in  less
   efficient  algorithms.  In  this talk we introduce the RNGLR algorithm
   which  correctly  parses  all  context  free  grammars without loss of
   efficiency.

   The extremely large structures constructed by these algorithms make it
   difficult  to  trace  their  behaviour by hand. It is useful to have a
   visual  representation  of an algorithm during a parse. We present the
   Parser  Animation  Tool  (PAT)  that  animates the construction of the
   necessary  data  structures  and  collects statistical data during the
   operation  of an algorithm. This tool has provided invaluable insights
   into the performance of several generalised parsing algorithms.
     _________________________________________________________________

   The  programming environment meetings are a forum for the presentation
   and  discussion  of  new  ideas,  ongoing and finished work. A typical
   meeting  addresses  a subject in the area of programming environments,
   program  generation, algebraic specification, term rewriting, parsing,
   etc.  A presentation ideally takes between 45 and 90 minutes. Meetings
   taking  longer  than 45 minutes are interrupted by a coffeebreak. Most
   Thursdays,  a  meeting is held which starts at 10:00 am. in one of the
   rooms at CWI/WINS. Exceptionally, dates or times may change.

   The    program    of    the    meetings    is    available   on   WWW:
   http://www.cwi.nl/~pem
     _________________________________________________________________