Language Technologies Institute
11-712: Self-Paced Laboratory

Algorithms for NLP:
GLR Parsing Module

Objective: The Generalized LR Parser, implemented by Masaru Tomita and extended by other researchers, has been the basis for natural language analysis in several applied projects at CMU. In this module, you will work with the GLR parser to gain experience with basic issues which are typically addressed in each practical application.

To complete the module you will choose between two semantic representations: property lists, or knowledge bases written in the Scone Knowledge Representation. The Scone semantics option provides an opportunity for students interested in semantics to become familiar with a current Knowledge Representation project from CMU.

As part of this module, you will complete the following tasks:
  • Write a small syntactic lexicon;
  • Write a small semantic lexicon OR Scone Knowledge Base (not both);
  • Write lexical lookup functions for the lexicon;
  • Debug/extend a given grammar to extend its functionality;
  • Write a grammar callout function to implement semantic restrictions.
The Generalized LR Parser/Compiler Version 8.1: User's Guide, Masaru Tomita (ed.), Teruko Mitamura, Hiroyuki Musha and Marion Kee. CMT Technical Memo, April 1988.

"Coping With Ambiguity in a Large-Scale Machine Translation System", Baker, Franz, Jordan, Mitamura and Nyberg, Proceedings of COLING-94.

"The Scone User's Manual", Scott Fahlman. Online.

Copies of this material will be available in the LTI Library (NSH 4501).

  1. Read the first background reading to familiarize yourself with the GLR parser, especially the syntax of the grammar rules.
  2. Read Section 4 in the second background reading, to familiarize yourself with the notion of semantic restrictions on attachment during syntactic parsing.
  3. Read the third background reading to familiarize yourself with Scone, especially the syntax for writing knowledge bases.
  4. If you have any questions after reading the background materials, seek guidance from the instructor. Questions regarding Scone should be directed to Alicia Tribble (
  5. Choose your semantic representation and then follow the appropriate step-by-step instructions to complete your program and data files for the module.
    GLR with property list semantics, step-by-step instructions
    GLR with Scone semantics, step-by-step instructions
  6. Hand in your files by copying them to the directory corresponding to your userid under:


    These files should include (Note: Choose one of these lists, not both):
    GLR w/ property lists *OR* GLR w/ Scone
    glr-lexicon.lisp glr-scone-lexicon.lisp
    glr-semantics.lisp glr-scone-kb.lisp
    glr-grammar.gra glr-scone-grammar.gra
    glr-code.lisp glr-scone-code.lisp

    Also include a file called test-output.txt, containing of a transcript of your code running on the given test data (see the GLR instructions file or the GLR-SCONE instructions file for more details).

  7. Notify the instructor that your module is ready for evaluation. Please be sure to check that you have completed all the parts, and that you have created the 5 files mentioned above, with the precise names given, before handing in your work.

29-Oct-2006 update by
5-Nov-96 by