[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Fwd: my current project: new lalr module

From: Matt Wette
Subject: Fwd: my current project: new lalr module
Date: Wed, 03 Jun 2015 20:40:34 -0700

(Accidentally sent to guile-devel.)

Having fun with all the great code, and documentation, in guile 2. 

My current project is a lalr module. Last December I wanted to start working on an interpreter for modelica in guile.  Guile has a lalr parser generator (system base lalr).   When I started looking at it, I was not crazy about the input language. I looked to see if a better interface could be pasted on, but the code impenetrable for me.  So I started coding up my own LALR parser generator.  I was hoping it would take a month of nights/weekends but ended up taking me close to four months.  For now I am calling my implementation "lalr1".

A major difference between my lalr1 and lalr in guile is that the guile version is a translation of the C-coded bison tool and mine is a from-scratch implementation in Scheme based on algorithms from the Dragon Book.  (The bison implementation uses the DeRemer-Pennello algorithms, yacc does not.  I'd guess the bison-based implementation will generate a parser generator faster, but I think that is a minor advantage.)

Some features of lalr1:
0) It's implemented with syntax-rules and syntax-case (versus define-macro for lalr).

1) There is no specification of terminals.  Terminals are detected in rules (via fenders) as quoted symbols or characters.
    Example of terminals:  'number, #\+

2) Actions are specified as ($$ action ...).  (Identifiers beginning with $ are reserved.) 

3)  Mid-rule actions (Bison Manual section 3.4.8 ) are supported.  (Not supported by lalr in guile.)

4) Some handy "proxy" macros are included.  The macro _expression_ results in a generated symbol and additional productions.  Examples:
    ($? a b c) will generate symbol $Pk and production ($Pk () (a b c)) 
    ($* a b c) will generate symbol $Pk and production ($Pk () ($Pk a b c)) 
    ($+ a b c) will generate symbol $Pk and production ($Pk (a b c) ($Pk a b c))
   where $Pk will be $P0, $P1, ...

5) It can generate Bison and guile lalr input languages from lalr1 spec's.  (I have been using the Bison converter to debug lookahead generation.)

6) There is a macro to generate lalr1 input language from a lalr-parser specification.

7) Table compaction is optional.  (The current compaction procedure will generate a default action if max duplication is more than 3.)

8) The bulk of the code resides in one module of ~ 1500 lines of code and ~ 500 lines of comments.

Here is a partial specification from the C-parser I am working on.  It is being implemented with attributed-grammar semantics so that I can process code with functions from the SXML modules.  For example, I am using foldts to detect typedefs need to feed back to the lexer.)

(define clang-spec
   (start translation-unit-proxy)

    (translation-unit-proxy (translation-unit ($$ (tl->list $1))))

     (external-declaration ($$ (make-tl 'trans-unit $1)))
     (translation-unit external-declaration ($$ (tl-app! $1 $2)))
     (declaration-specifier init-declarator-list  ($$ (...)) #\;  ;; <=mid-rule action to capture typedef's
  ($$ (list 'decl (tl->list $1) (tl->list $2)))))
     (declaration-specifier #\;
          ($$ (list 'decl (tl->list $1))
     ('ident ($$ (list 'ident $1)))
     (#\( declarator #\) ($$ (list 'scope $2)))
     (direct-declarator #\[ constant-_expression_ #\] ($$ (list 'array $3 $1)))
     (direct-declarator #\[ #\] ($$ (list 'array $3 $1)))
     (direct-declarator #\( parameter-type-list #\) ($$ (list 'function $1 $3)))
     (direct-declarator #\( identifier-list #\) ($$ (list 'function $1 $3)))
     (direct-declarator #\( #\) ($$ (list 'function $1 $3)))


reply via email to

[Prev in Thread] Current Thread [Next in Thread]