Ox generalizes Yacc and Lex for attribute grammars

Tom Shields <thomas.evans.shields@gmail.com>
Wed, 6 Feb 2019 12:04:18 -0600

          From comp.compilers

Related articles
Ox generalizes Yacc and Lex for attribute grammars thomas.evans.shields@gmail.com (Tom Shields) (2019-02-06)
Ox generalizes Yacc and Lex for attribute grammars bischoff@cs.iastate.edu (Kurt Bischoff) (1993-11-16)
Re: Ox generalizes Yacc and Lex for attribute grammars a_tucker@paul.spu.edu (Andrew Tucker) (1993-11-16)
Re: Ox generalizes Yacc and Lex for attribute grammars wjw@eb.ele.tue.nl (1993-11-17)
Re: Ox generalizes Yacc and Lex for attribute grammars etxmow@garbo.ericsson.se (1993-11-17)
Re: Ox generalizes Yacc and Lex for attribute grammars bevan@cs.man.ac.uk (Stephen J Bevan) (1993-11-17)
Re: Ox generalizes Yacc and Lex for attribute grammars rad@cs.ucsb.edu (1993-11-18)
[2 later articles]
| List of all articles for this month |

From: Tom Shields <thomas.evans.shields@gmail.com>
Newsgroups: comp.compilers
Date: Wed, 6 Feb 2019 12:04:18 -0600
Organization: Compilers Central
Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="99956"; mail-complaints-to="abuse@iecc.com"
Keywords: yacc, attribute, available
Posted-Date: 06 Feb 2019 15:00:17 EST

I discovered the Ox (G1.04) back in 2004, while searching for an accessible
lex- & yacc-compatible attribute grammar evaluator generator. The Ox G1.04
skeleton code is highly dependent on the original AT&T Yacc skeleton
internals, and as I needed to use a more current parser generator with better
than LALR(1) capabilities, I proceeded to (slowly, as I had an unrelated day
job) refactor & upgrade Ox to eliminate the AT&T Yacc skeleton dependencies.

Based on an email exchange with Kurt Bischoff in January 2007, I repackaged Ox
under the GPL v3 license, with an exception similar to that found with Bison
allowing distribution of Ox-generated evaluator lever & parser specifications
under other licensing terms.

Unfortunately, I lost track of a working email address for Kurt sometime after
my last correspondence in April 2010, so he is probably not aware that I
finally finished my effort late last year. (Kurt: if you see this post, please
contact me, Tom).

I made the upgraded Ox (1.5) available via SourceForge
(sourceforge.net/projects/ox-attribute-grammar-compiler/) on Dec 8, 2018, and
released a minor update (1.5.1) on Feb 5, 2019.

Tom Shields

Here is the NEWS file:


* Noteworthy changes in release 1.5.1 (5 February 2019)

    Release was tested on the following platforms:

        macOS 10.14.2
        Ubuntu Linux 18.04.1 LTS
        Solaris x86 11.3 & 11.4
        Windows 10 w/ Cygwin & Msys2 2.11.2

    Release was tested with the following compilers & tools:

        macOS C/C++: 10
        Solaris C/C++: 5.14 (Studio 12.5) & 5.15 (Studio 12.6)
        GNU C/C++: 4.8, 5.5, 6.5, 7.3, 7.4, 8.2
        Clang C/C++: 3.9, 4.0, 5.0, 6.0, 7.0

        Lex & Yacc: from the Unix 4.3BSD (Reno) & 4.4BSD source release

        Flex: 2.5.35, 2.5.36, 2.5.39, 2.6.0, 2.6.1, 2.6.2, 2.6.3, 2.6.4

        Bison: 2.3, 2.4, 2.7.1, 3.0, 3.0.4, 3.0.5, 3.1, 3.2, 3.2.1, 3.2.2, 3.2.3,
                      3.2.4, 3.3, 3.3.1, 3.3.2

        Byacc (invisible-mirror.net/archives/byacc/):
          - compiled w/ backtracking: 20161202, 20170709, 20180525, 20180609
          - compiled w/o backtracking: 20180609

        Btyacc (github.com/ChrisDodd/btyacc): 3.0-5, 20181006, 20181215

        Msta (github.com/dino-lang/dino): 20160603 (w/ fix for LR(k>1) in issue

** Enhancements

    The GPPL compiler will now build with the Boehm-Demers-Weiser Conservative
    C/C++ Garbage Collector package (www.hboehm.info/gc), if specified in the

    Both Ox and the GPPL compiler will now build with the Dmalloc Debug Malloc
    Library (dmalloc.com), if specified in the configuration

** Bug fixes

    Corrected a memory leak in Ox-generated evaluators: semantic stack heap data,
    separate from the attributed AST tree node heap data, not reclaimed

    Corrected a minor memory leak in Ox: heap allocated file name string extracted
    from a "#line" directive not free'd in all cases

    Corrected a segfault in Ox (Linux): if Ox built with libgc w/o libcord, heap
    data allocated (with `malloc()') by the library function `vasprintf()' was
    passed to `GC_free()'

    Corrected a segfault in Ox (Solaris): heap allocatoin size `off by 1' error

** Test suite

    Portability improvements (removed use of `basename' in run script)

** Build system

    Added Dmalloc Debug Malloc Library (dmalloc.como) as a build option

    Improved robustness & generality (option consistency checking,
    option interactions)

** Attribute grammar evaluator skeleton

    The generated evaluator framework has been refactored to work with
    multiple Yacc compatible parser generators (`bison', `byacc', `btyacc',
    `msta') in addition to the original AT&T `yacc'. This includes support
    for the various non-LALR(1) parsing algorithms provided by these tools
    (LR(k>1), GLR, backtracking), the `byacc' and `bison' pure parser skeleton
    variants, and the `bison' push parser skeleton variant.

** Enhancements

    Incorporated patches from the Technical University of Vienna, Austria, by
    Martin K√∂gler, Florian G. Plug, and Mihai Ghete to build Ox using `flex'.

    Accept/pass-through (most) bison, byacc, btyacc, msta, and flex
    specification %-directives; recognize those that impact generated code.

    Accept C++ namespace IDs and template type specifiers in a `%token', etc,
    type tag.

    Accept a larger subset of the C/C++ type syntax in attribute declarations,
    including types and type qualifiers added in the C99 standard

    Allow properly nested parenthesized expressions in macro actual
    parameters, including C comma expressions, removing the requirement for
    a trailing comma.

    Generate `#line' directives in the Ox-generated lexer and parser
    specifications. Disable this functionality at configuration-time, or at
    run-time with a command-line option, if using lexer and/or parser
    generators that do not accept `#line' directives.

    Additional command-line options:
    - specify the prefix for Ox-generated external names, replacing the
        default "yyy" prefix, which enables linking multiple evaluators in a
        single application
    - specify output file name prefixes, replacing the default "oxout" prefix
    - specify that the lexer is intended for use with a bison or byacc pure
        parser skeleton, generating indirection references to yylval in leaf
        attribute evaluation code.
    - opt out of generating `#line' directives

    Eliminated fixed size tables in Ox and in Ox-generated evaluators.

    Provided the `yyyinit()' function, which must be called prior to the first
    call of the lexer by the parser to initialize Xwindows data structures if
    the Ox "-t" command-line option is used. Invocation of `yyyinit()' is
    added automatically to a generated Lex specification file, but must be
    invoked by user-written code for a generic (non-Lex) handwritten lexer.

** Bug fixes

    Corrected the Ox "-S" command-line option failure for generic (non-Lex)
    lexer specifications.

    Corrected multiple invocations of `fclose()' on a given output file; this
    caused a segmentation fault or an infinite loop within `fclose()' in
    different glibc Linux implementations.

    Added an `atexit()' handler to cleanup temporary files otherwise left
    dangling by an Ox abnormal exit from a C library function.

    Corrected missing parameter in invocation to `genImmCrefForAttrbRef()'
    exposed by the switch to use of Standard C function prototypes.

** Documentation

    Revised User Reference Manual and manpage to match the current release.

** Test suite

    Test cases were added that verify correctness of attribute evaluation with
    the various non-LALR(1) parsing algorithms (LR(k>1), GLR, backtracking)
    and the pure and push parser skeleton variants

    A test case was added to verify that the `#line' directive correctly
    tracks source lines from the original Ox input file in error messages.

** Build system

    Implemented a GNU Automake generated Autoconf Build system, with
    configure-time options to:
    - choose a specific Lex and/or Yacc compatible generator, rather than the
        tool found first by the configure script
    - build a version of Ox with debugging or profiling enabled
    - build a version of Ox with `#line' directives disabled
    - use the Boehm-Demers-Weiser Conservative Garbage Collector, if found
        by the configure script

    Tested build portability across the macOS, Linux, Windows (Cygwin, Msys),
    and Solaris development environments, including multiple version of
    various C/C++ compilers multiple version of lex, yacc, flex, bison, byacc,
    btyacc, and msta.

** Backward incompatible changes from release G1.04

    The approach adopted by Ox to work across multiple Yacc compatible parser
    generators via modification of the Yacc `%union' declaration (or
    generation of a `%union' declaration, if one is not present) enables
    portable use of the Yacc semantic value stack to manage the Ox semantic
    attribute stack.

    Since Ox uses the Yacc `%union' mechanism, the semantic value type
    definition mechanisms supported by Yacc in user-supplied code:
        (1) #define YYSTYPE <C_type_specifier> (default: `int')
        (2) typedef <C_type_specifier> YYSTYPE;
    are not suported. Yacc grammar specifications that make use of one of
    these two approaches to the definition of `YYSTYPE' will not work as-is
    with Ox, but must be first modified to include a Yacc `%union'
    declaration to make the semantic value type explicit.

    The requirement for a trailing comma in macro formal and actual parameter
    lists has been eliminated; trailing commas in these positions are no
    longer supported.

    The curses-based incremental tree construction display mechanism was
    removed. The lookahead processing in the various Yacc compatible
    variants - `msta' LR(k>1), `byacc' & `btyacc' backtracking, and `bison'
    GLR - can buffer more than a single lookahead token. The terminal node
    processing from release G1.04 only worked for the single token lookahead
    case. This capability may be reintroduced in a future version.

    Removed the `@prune' reserved word (the token wasn't actually passed from
    the lexer to the parser in release G1.04) and the associated
    implementation. The generated evaluator knows better than the author when
    pruning is feasible.

    Enabled the `@decorate' reserved word (the token wasn't actually passed
    from the lexer to the parser in release G1.04). The `@decorate' directive
    forces evaluation of attributes, which may be required for the
    implementation of interactive evaluators.

    Renamed `yyyerror()' to `yyyabort()'.

    These command-line options are no longer relevant and have been removed:
        "-aN" set structure-alignment size to N (no longer relevant)
        "-C" print Copyright statment
        "-I" ANSI/ISO C/C++ instead of K&R C source
        "-T" generate curses-based code to display tree construction
        "-U" print command-line usage summary (replaced by "--help")
        "-XaN" change the size of an internal table in Ox
        "-YaN" change the size of an internal table in the generated evaluator
        "-YY" enable "-YaN" command-line option in generated evaluator

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.