Lalr example

From Gambit wiki

(Difference between revisions)
Jump to: navigation, search
(Created example, start of "how to run" steps.)
m (Aargh, list numbering resets between paragraphs. Changed numbers to bullets. Put example code in one big block.)
 
Line 9: Line 9:
I ran the example using these steps.  I used Mac OS 10.3.7, Lalr 2.1.0, and Gambit 4.2.4.  Lalr 2.3.0 is a [http://snow.iro.umontreal.ca/ Snow] package so the installation step is different, and other steps may need to be changed too.
I ran the example using these steps.  I used Mac OS 10.3.7, Lalr 2.1.0, and Gambit 4.2.4.  Lalr 2.3.0 is a [http://snow.iro.umontreal.ca/ Snow] package so the installation step is different, and other steps may need to be changed too.
-
# Download and unpack the Lalr sources.
+
* Download and unpack the Lalr sources.
-
# Change to the directory containing the unpacked sources.  Run <code>make gambit</code>.  Lalr is implemented in one file, <code>lalr.scm</code>.
+
* Change to the directory containing the unpacked sources.  Run <code>make gambit</code>.  Lalr is implemented in one file, <code>lalr.scm</code>.
-
# Put this code in a file, say <code>paren-depth.scm</code>.
+
* Put this code in a file, say <code>paren-depth.scm</code>.
  ;;; Read C source code, breaking it into the following types of tokens:
  ;;; Read C source code, breaking it into the following types of tokens:
Line 20: Line 20:
  ;;; newline characters) is never a token and may come between any two
  ;;; newline characters) is never a token and may come between any two
  ;;; tokens, before the first, or after the last.
  ;;; tokens, before the first, or after the last.
-
 
+
  ;;; Whenever the identifier ___P is seen, read a left parenthesis
  ;;; Whenever the identifier ___P is seen, read a left parenthesis
  ;;; followed by a body (zero or more tokens) followed by a right
  ;;; followed by a body (zero or more tokens) followed by a right
Line 27: Line 27:
  ;;; Count the deepest nesting level used in the body.  Count the maximum
  ;;; Count the deepest nesting level used in the body.  Count the maximum
  ;;; deepest level (of all the bodies seen so far).
  ;;; deepest level (of all the bodies seen so far).
-
 
+
  ;;; At the end of the file, print the maximum deepest level, or 0 if no
  ;;; At the end of the file, print the maximum deepest level, or 0 if no
  ;;; bodies were found.
  ;;; bodies were found.
-
 
+
-
 
+
  ;;; Global variables used by lexical analyzer and parser.
  ;;; Global variables used by lexical analyzer and parser.
  ;;; The lexical analyzer needs them to print the maximum level at the
  ;;; The lexical analyzer needs them to print the maximum level at the
  ;;; end of the file.
  ;;; end of the file.
-
 
+
  (define depth 0)
  (define depth 0)
  (define max-depth 0)
  (define max-depth 0)
-
 
+
  ;;; Lexical analyzer.  Passes tokens to the parser.
  ;;; Lexical analyzer.  Passes tokens to the parser.
-
 
+
  (define (paren-depth-lexer errorp)
  (define (paren-depth-lexer errorp)
   (lambda ()
   (lambda ()
-
 
+
     ;; Utility functions, for identifying characters, skipping any
     ;; Utility functions, for identifying characters, skipping any
     ;; amount of white space, or reading multicharacter tokens.
     ;; amount of white space, or reading multicharacter tokens.
-
 
+
     (letrec ((char-whitespace?
     (letrec ((char-whitespace?
               (lambda (c)
               (lambda (c)
Line 59: Line 59:
                       (begin (read-char)
                       (begin (read-char)
                               (loop (peek-char)))))))
                               (loop (peek-char)))))))
-
 
+
               (char-in-id?
               (char-in-id?
               (lambda (c)
               (lambda (c)
Line 74: Line 74:
                           ;; else
                           ;; else
                           'ID))))))
                           'ID))))))
-
 
+
       ;; The lexer function.
       ;; The lexer function.
-
 
+
       (skip-whitespace)
       (skip-whitespace)
       (let loop ((c (read-char)))
       (let loop ((c (read-char)))
Line 90: Line 90:
           ((char=? c #\))      'RPAREN)
           ((char=? c #\))      'RPAREN)
           (else                'CHAR))))))
           (else                'CHAR))))))
-
 
+
  ;;; Parser.
  ;;; Parser.
-
 
+
  (define paren-depth-parser
  (define paren-depth-parser
   (lalr-parser
   (lalr-parser
-
 
+
     ;; Options.
     ;; Options.
-
 
+
     (expect: 0) ;; even one conflict is an error
     (expect: 0) ;; even one conflict is an error
-
 
+
     ;; List of terminal tokens.
     ;; List of terminal tokens.
-
 
+
     (CHAR LPAREN RPAREN ID ___P)
     (CHAR LPAREN RPAREN ID ___P)
-
 
+
     ;; Grammar rules.
     ;; Grammar rules.
-
 
+
     (file      (newfile tokens))
     (file      (newfile tokens))
     (newfile    ()                      : (begin (set! depth 0)
     (newfile    ()                      : (begin (set! depth 0)
                                                 (set! max-depth 0)))
                                                 (set! max-depth 0)))
-
 
+
     (tokens    (tokens token)
     (tokens    (tokens token)
                 (token))
                 (token))
-
 
+
     ;; When not after a ___P, the structure of the file is unimportant.
     ;; When not after a ___P, the structure of the file is unimportant.
     (token      (CHAR)
     (token      (CHAR)
Line 118: Line 118:
                 (RPAREN)
                 (RPAREN)
                 (ID)
                 (ID)
-
 
+
     ;; But after a ___P, we start counting parentheses.
     ;; But after a ___P, we start counting parentheses.
                 (___P newexpr in LPAREN exprs RPAREN out)
                 (___P newexpr in LPAREN exprs RPAREN out)
                 (___P newexpr in LPAREN      RPAREN out))
                 (___P newexpr in LPAREN      RPAREN out))
     (newexpr    ()                      : (set! depth 0))
     (newexpr    ()                      : (set! depth 0))
-
 
+
     ;; Inside an expression, ___P is treated like all other identifiers.
     ;; Inside an expression, ___P is treated like all other identifiers.
     ;; Only parentheses do anything very interesting.  I'm assuming Lalr
     ;; Only parentheses do anything very interesting.  I'm assuming Lalr
     ;; will enforce the pairing of parentheses, so my in and out actions
     ;; will enforce the pairing of parentheses, so my in and out actions
     ;; don't check for too many or too few closing parens.
     ;; don't check for too many or too few closing parens.
-
 
+
     (exprs      (exprs expr)
     (exprs      (exprs expr)
                 (expr))
                 (expr))
-
 
+
     (expr      (CHAR)
     (expr      (CHAR)
                 (in LPAREN exprs RPAREN out)
                 (in LPAREN exprs RPAREN out)
Line 141: Line 141:
                                                   (set! max-depth depth))))
                                                   (set! max-depth depth))))
     (out        ()                      : (set! depth (- depth 1)))))
     (out        ()                      : (set! depth (- depth 1)))))
-
 
+
  ;;; Main program.
  ;;; Main program.
-
 
+
  (define paren-depth
  (define paren-depth
   (let ((errorp
   (let ((errorp
Line 151: Line 151:
     (lambda ()
     (lambda ()
       (paren-depth-parser (paren-depth-lexer errorp) errorp))))
       (paren-depth-parser (paren-depth-lexer errorp) errorp))))
-
 
+
  (paren-depth)
  (paren-depth)
-
# Gambit's <code>load</code> is useless on files containing macros, like <code>lalr.scm</code>.  Instead you must <code>include</code> the files.  This shell command generates and runs the parser:
+
* Gambit's <code>load</code> is useless on files containing macros, like <code>lalr.scm</code>.  Instead you must <code>include</code> the files.  This shell command generates and runs the parser:
  gsi -e "(include \"lalr.scm\")" paren-depth.scm < input.c
  gsi -e "(include \"lalr.scm\")" paren-depth.scm < input.c

Latest revision as of 10:30, 10 April 2008

Dominique Boucher ported the algorithms used in the Bison parser generator to several Scheme dialects including Gambit. His project, Lalr, is available here.

Lalr does the "behind-the-scenes" work of creating programs that recognize input described by a context-free grammar. You only need to give the grammar and some other things. All your input to Lalr has a very Scheme-like syntax. Lalr creates a Scheme function (the parser) which can call other Scheme functions at certain points in the parsing.

Unfortunately Lalr version 2.1.0 only comes wth one example. This page gives another example (although a special-purpose one) and describes using Lalr with Gambit.

See Creating tags from Gambit library C files for why this example was written, and User:dpeschel.

I ran the example using these steps. I used Mac OS 10.3.7, Lalr 2.1.0, and Gambit 4.2.4. Lalr 2.3.0 is a Snow package so the installation step is different, and other steps may need to be changed too.

  • Download and unpack the Lalr sources.
  • Change to the directory containing the unpacked sources. Run make gambit. Lalr is implemented in one file, lalr.scm.
  • Put this code in a file, say paren-depth.scm.
;;; Read C source code, breaking it into the following types of tokens:
;;; the identifier ___P, other identifiers, left and right parentheses,
;;; and any other non-spacing character.  White space (space, tab, and
;;; newline characters) is never a token and may come between any two
;;; tokens, before the first, or after the last.

;;; Whenever the identifier ___P is seen, read a left parenthesis
;;; followed by a body (zero or more tokens) followed by a right
;;; parenthesis.  If the body contains parentheses they must be properly
;;; paired.  Other tokens in the body, including ___P, have no effect.
;;; Count the deepest nesting level used in the body.  Count the maximum
;;; deepest level (of all the bodies seen so far).

;;; At the end of the file, print the maximum deepest level, or 0 if no
;;; bodies were found.


;;; Global variables used by lexical analyzer and parser.
;;; The lexical analyzer needs them to print the maximum level at the
;;; end of the file.

(define depth 0)
(define max-depth 0)

;;; Lexical analyzer.  Passes tokens to the parser.

(define (paren-depth-lexer errorp)
  (lambda ()

    ;; Utility functions, for identifying characters, skipping any
    ;; amount of white space, or reading multicharacter tokens.

    (letrec ((char-whitespace?
              (lambda (c)
                (or (char=? c #\space)
                    (char=? c #\tab)
                    (char=? c #\newline))))
             (skip-whitespace
              (lambda ()
                (let loop ((c (peek-char)))
                  (if (and (not (eof-object? c))
                           (char-whitespace? c))
                      (begin (read-char)
                             (loop (peek-char)))))))

             (char-in-id?
              (lambda (c)
                (or (char-alphabetic? c)
                    (char=? c #\_))))
             (read-___P-or-other-id
              (lambda (l)
                (let ((c (peek-char)))
                  (if (char-in-id? c)
                      (read-___P-or-other-id (cons (read-char) l))
                      ;; else
                      (if (equal? l '(#\P #\_ #\_ #\_))
                          '___P
                          ;; else
                          'ID))))))

      ;; The lexer function.

      (skip-whitespace)
      (let loop ((c (read-char)))
        (cond
         ((eof-object? c)      (begin (display "max depth ")
                                      (display max-depth)
                                      (newline)
                                      '*eoi*))
         ((char-whitespace? c) (begin (errorp "didn't expect whitespace " c)
                                      (loop (read-char))))
         ((char-in-id? c)      (read-___P-or-other-id (list c)))
         ((char=? c #\()       'LPAREN)
         ((char=? c #\))       'RPAREN)
         (else                 'CHAR))))))

;;; Parser.

(define paren-depth-parser
  (lalr-parser

   ;; Options.

   (expect: 0) ;; even one conflict is an error

   ;; List of terminal tokens.

   (CHAR LPAREN RPAREN ID ___P)

   ;; Grammar rules.

   (file       (newfile tokens))
   (newfile    ()                      : (begin (set! depth 0)
                                                (set! max-depth 0)))

   (tokens     (tokens token)
                (token))

   ;; When not after a ___P, the structure of the file is unimportant.
   (token      (CHAR)
                (LPAREN)
                (RPAREN)
                (ID)

   ;; But after a ___P, we start counting parentheses.
                (___P newexpr in LPAREN exprs RPAREN out)
                (___P newexpr in LPAREN       RPAREN out))
   (newexpr    ()                      : (set! depth 0))

   ;; Inside an expression, ___P is treated like all other identifiers.
   ;; Only parentheses do anything very interesting.  I'm assuming Lalr
   ;; will enforce the pairing of parentheses, so my in and out actions
   ;; don't check for too many or too few closing parens.

   (exprs      (exprs expr)
                (expr))

   (expr       (CHAR)
                (in LPAREN exprs RPAREN out)
                (in LPAREN       RPAREN out)
                (ID)
                (___P))
   (in         ()                      : (begin (set! depth (+ depth 1))
                                                (if (> depth max-depth)
                                                  (set! max-depth depth))))
   (out        ()                      : (set! depth (- depth 1)))))

;;; Main program.

(define paren-depth
  (let ((errorp
          (lambda args
            (for-each display args)
            (newline))))
    (lambda ()
      (paren-depth-parser (paren-depth-lexer errorp) errorp))))

(paren-depth)
  • Gambit's load is useless on files containing macros, like lalr.scm. Instead you must include the files. This shell command generates and runs the parser:
gsi -e "(include \"lalr.scm\")" paren-depth.scm < input.c

and this shell command generates and runs the parser on a series of input files:

for x in gambc-v4_2_5/lib/[cmos]*.c; do
  echo $x
  gsi -e "(include \"lalr.scm\")" paren-depth.scm < $x
done
Personal tools
documentation