Coming soon! 



YACC / M
 
Yet Another Compiler-Compiler

An LR(1) Parser Generator for Java

By David R. Tribble
Revision 1.0, 2001-08-13 (TBD)

 

Introduction

YACC/M (pronounced "yak' em"), which stands for "Yet Another Compiler-Compiler / MLR(k)", is a parser generator, sometimes also known as a compiler-compiler. It takes a grammar specification for a user-defined language as input and produces a Java source code file that implements a parser for that language. Once compiled with the appropriate user-supplied driver methods, the resulting Java program is capable of parsing and recognizing sequences of tokens comprising valid sentences in the user-defined language.

 

Description

YACC/M is based on the theory of LR(k) bottom-up parsers, invented in the 1960s by Donald E Knuth. It is based in part upon the original YACC program written by Steven Johnson as part of the UNIX effort at Bell Labs in the early 1970s. YACC/M, in fact, is capable of translating most YACC source files with little or no modification. YACC/M differs from classic YACC, however, in a few important ways.

  • YACC/M generates Java code instead of C or C++ code.

  • The generated code uses a faster parsing algorithm.

  • The generated code is object-oriented. (Naturally, since the generated code is Java code.)

  • The generated code is coupled to the lexical analyzer (a.k.a. the lexer) in a different, more object-oriented manner.

  • Classic YACC produces parsers for LALR(1) grammars, while YACC/M is capable of producing parsers for full-blown LR(1) grammars, which comprise a larger and more powerful class of grammars.

  • The generated code is reentrant. This means that an application program can use more than one instance of the parser class simultaneously, with each instance operating independently of the others.

  • The parser itself is a library class, separate from the generated code (which is little more than static lookup tables). This means that an application program can use more than one parser for different grammars simultaneously, all sharing the same parser class code.

    • The YACC program is composed of two Java packages bundled as a single jar file.

    •  Package drt.io
    Generic I/O classes and interfaces.
    These are used by the generated class code, and also by the YACC/M program itself.

    •  Package drt.yaccm
    YACC/M classes.

    •  Class drt.yaccm.Yaccm
    The YACC/M command-line program.

    •  Class drt.yaccm.Gui
    A graphical user interface (GUI) front-end to the YACC/M program.

     

    Source Code and Executables

    [yaccm10.jar]
    A complete executable Java program.

    [yaccmlib10.jar]
    A complete Java runtime library for the generated parsers.

    [yaccmdoc10.jar]
    Complete javadocs for using the program.
    A good place to start reading is the UserGuide interface.

    [yaccmsrc10.jar]
    Complete source code.

    [yaccmsrcdoc10.jar]
    Complete javadocs for the source code.
    A good place to start reading is the ReadMe interface.

     

    Legal Restrictions

    The source code for YACC/M is copyrighted open source code. This means that although you are free to copy, use, and distribute the source code, you cannot claim it as your own creation, nor can you claim as your own any derivative works created by modifying the code.

    Generated code produced as a result of running the YACC/M program, however, is not subject to any copyright restrictions. Specifically, the generated code is not copyrighted except for the parts of the code that are included in the generated code that were originally written by the user - those parts may be copyrighted by the user who originally authored them. This also means that although the source to YACC/M is open source code, any parser code produced by it is not. Such generated source code can be used (and protected) any way the user sees fit, and he is not obligated to publish or make available to anyone such generated source code.

     

    Dedication

    This project is dedicated to the memory of Ed Felt, a former colleage of mine at BEA Systems, Inc. who was one of the victims of the terrorist hijacking of United Airlines Flight 93 on September 11, 2001.

    A few links mentioning Ed:

  • flight93.org/felt.html
  • www.911-remember.com/memberView/4d332e9a977003744d0891f39445ad50
  • www.hazlitt.org/united/whotheywere.html#EdwardFelt
  • www.bea.com/helping/nation.shtml
  • www.infoworld.com/articles/hn/xml/01/09/13/010913hntribute.xml
  • www.oasis-open.org/committees/business-transactions/documents/2002-04-22.BTP_draft_0.9.5.1.pdf
  • xml.coverpages.org/OASIS-BTP-Specification-DRAFT090.pdf
  • lists.oasis-open.org/archives/business-transaction/200109/msg00014.html

    • The author can be reached by email at david@tribble.com.
    The author's home web page is at david.tribble.com.

    Revision: 0.3, 2002-07-11.
    Copyright ©2001-2002, by David R. Tribble, all rights reserved.