You can edit this page using wiki syntax for markup.

Article contents:[[tags:egg]] [[toc:]] == lalr LALR(1) parser generator written in Scheme. == Usage To generate the parser: (import lalr) ;; this will only work in the interpreter (lalr-parser grammar definition ... ) To use the parser: (include "parser.grm.scm") ;; file generated by lalr-parser macro (parser lexer parse-error) ;; parser is the function defined in the grammar file ;; lexer is a user-defined character-reading function ;; parse-error is a user-defined error function == Documentation {{lalr}} implements an efficient algorithm for computing lookahead sets, which is the same as the one used in Bison (GNU yacc): Efficient Computation of LALR(1) Look-Ahead Set, F. DeRemer and T. Pennello, TOPLAS, vol. 4, no. 4, october 1982. The official documentation for {{lalr}} can be found here: [[https://github.com/schemeway/lalr-scm]]. The following is taken from chapters 4 and 6 in the official documentation. === Defining a parser The file {{lalr.scm}} declares a macro called {{lalr-parser}}: (lalr-parser [options] tokens rules ...) To use this macro, you must first load {{lalr.scm}} in the Scheme interpreter via the {{include}} special form. The macro will not work in the compiler. This macro, when given appropriate arguments, generates an LALR(1) parser. The macro accepts at least two arguments. The first is a list of symbols which represent the terminal symbols of the grammar. The remaining arguments are the grammar production rules. === The grammar format The grammar is specified by first giving the list of terminals and the list of non-terminal definitions. Each non-terminal definition is a list where the first element is the non-terminal and the other elements are the right-hand sides (lists of grammar symbols). In addition to this, each right-hand side can be followed by a semantic action. For example, consider the following (yacc) grammar for a very simple expression language: e : e '+' t | e '-' t | t ; t : t '*' f : t '/' f | f ; f : ID ; The same grammar, written for the scheme parser generator, would look like this (with semantic actions): (define expr-parser (lalr-parser ; Terminal symbols (ID + - * /) ; Productions (e (e + t) : (+ $1 $3) (e - t) : (- $1 $3) (t) : $1) (t (t * f) : (* $1 $3) (t / f) : (/ $1 $3) (f) : $1) (f (ID) : $1))) In semantic actions, the symbol {{$n}} refers to the synthesized attribute value of the nth symbol in the production. The value associated with the non-terminal on the left is the result of evaluating the semantic action (it defaults to {{#f}}). ==== Operator precedence and associativity The above grammar implicitly handles operator precedences. It is also possible to explicitly assign precedences and associativity to terminal symbols and productions a la Yacc. Here is a modified (and augmented) version of the grammar: (define expr-parser (lalr-parser ; Terminal symbols (ID (left: + -) (left: * /) (nonassoc: uminus)) (e (e + e) : (+ $1 $3) (e - e) : (- $1 $3) (e * e) : (* $1 $3) (e / e) : (/ $1 $3) (- e (prec: uminus)) : (- $2) (ID) : $1))) The {{left:}} directive is used to specify a set of left-associative operators of the same precedence level, the {{right:}} directive for right-associative operators, and {{nonassoc:}} for operators that are not associative. Note the use of the (apparently) useless terminal {{uminus}}. It is only defined in order to assign to the penultimate rule a precedence level higher than that of {{*}} and {{/}}. The {{prec:}} directive can only appear as the last element of a rule. Finally, note that precedence levels are incremented from left to right, i.e. the precedence level of {{+}} and {{-}} is less than the precedence level of {{*}} and {{/}} since the formers appear first in the list of terminal symbols (token definitions). ==== Options The following options are available. * {{(output: name filename)}} - copies the parser to the given file. The parser is given the name name. * {{(out-tables: filename) }} - outputs the parsing tables in filename in a more readable format. * {{(expect: n)}} - don't warn about conflicts if there are {{n}} or less conflicts. * {{(driver: glr)}} - generates a GLR parser instead of a regular LALR parser. ==== Error recovery lalr implements a very simple error recovery strategy. A production can be of the form (rulename ... (error TERMINAL) : action-code) There can be several such productions for a single rulename.This will cause the parser to skip all the tokens produced by the lexer that are different than the given {{TERMINAL}}. For a C-like language, one can synchronize on semicolons and closing curly brackets by writing error rules like these: (stmt (expression SEMICOLON) : ... (LBRACKET stmt RBRACKET) : ... (error SEMICOLON) (error RBRACKET)) Conflicts in the grammar are handled in a conventional way. In the absence of precedence directives, Shift/Reduce conflicts are resolved by shifting, and Reduce/Reduce conflicts are resolved by choosing the rule listed first in the grammar definition. === Using the parser The parser generated by the {{lalr-parser macro}} is a function that takes two parameters. The first parameter is a lexical analyzer while the second is an error procedure. The lexical analyzer is zero-argument function (a thunk) invoked each time the parser needs to look-ahead in the token stream. A token is usually a pair whose {{car}} is the symbol corresponding to the token (the same symbol as used in the grammar definition). The {{cdr}} of the pair is the semantic value associated with the token. For example, a string token would have the {{car}} set to {{'string}} while the {{cdr}} is set to the string value "hello". The token may also be a plain symbol, such as {{'NEWLINE}}, if it has no need of a semantic value. Once the end of file is encountered, the lexical analyzer must always return the symbol{{'*eoi*}} each time it is invoked. The error procedure must be a function that accepts at least two parameters, a message and additional arguments to be printed. == Examples ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;; ;;; FILE: calc.grm ;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;; ;;; Parser for simple calculator in Scheme. ;;; ;;; To use, run the command: ;;; ;;; csi < calc.grm ;;; ;;; This will create file `calc.grm.scm'. Then, to compile the ;;; calculator program, run: ;;; ;;; csc calc.scm ;;; (import lalr) (define calc-parser (lalr-parser ;; --- Options ;; output a parser, called calc-parser, in a separate file - calc.yy.scm, (output: calc-parser "calc.yy.scm") ;; output the LALR table to calc.out (out-table: "calc.out") ;; there should be no conflict (expect: 5) ;; --- token definitions (ID NUM = LPAREN RPAREN NEWLINE COMMA (left: + -) (left: * /) (nonassoc: uminus)) (lines (lines line) : (display-result $2) (line) : (display-result $1)) ;; --- rules (line (assign NEWLINE) : $1 (expr NEWLINE) : $1 (NEWLINE) : #f (error NEWLINE) : #f) (assign (ID = expr) : (add-binding $1 $3)) (expr (expr + expr) : (+ $1 $3) (expr - expr) : (- $1 $3) (expr * expr) : (* $1 $3) (expr / expr) : (/ $1 $3) (- expr (prec: uminus)) : (- $2) (ID) : (get-binding $1) (ID LPAREN args RPAREN) : (invoke-proc $1 $3) (NUM) : $1 (LPAREN expr RPAREN) : $2) (args () : '() (expr arg-rest) : (cons $1 $2)) (arg-rest (COMMA expr arg-rest) : (cons $2 $3) () : '()))) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;; ;;; END FILE: calc.grm ;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;; ;;; FILE: calc.scm ;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (import (chicken port)) (import lalr-driver) ;; parser (include "calc.yy.scm") ;;; ;;;; The lexer ;;; (define (force-output) #f) (define (port-line port) (let-values (((line _) (port-position port))) line)) (define (port-column port) (let-values (((_ column) (port-position port))) column)) (define (make-lexer errorp) (lambda () (letrec ((skip-spaces (lambda () (let loop ((c (peek-char))) (if (and (not (eof-object? c)) (or (char=? c #\space) (char=? c #\tab))) (begin (read-char) (loop (peek-char))))))) (read-number (lambda (l) (let ((c (peek-char))) (if (char-numeric? c) (read-number (cons (read-char) l)) (string->number (apply string (reverse l))))))) (read-id (lambda (l) (let ((c (peek-char))) (if (char-alphabetic? c) (read-id (cons (read-char) l)) (string->symbol (apply string (reverse l)))))))) ;; -- skip spaces (skip-spaces) ;; -- read the next token (let loop () (let* ((location (make-source-location "*stdin*" (port-line (current-input-port)) (port-column (current-input-port)) -1 -1)) (c (read-char))) (cond ((eof-object? c) '*eoi*) ((char=? c #\newline) (make-lexical-token 'NEWLINE location #f)) ((char=? c #\+) (make-lexical-token '+ location #f)) ((char=? c #\-) (make-lexical-token '- location #f)) ((char=? c #\*) (make-lexical-token '* location #f)) ((char=? c #\/) (make-lexical-token '/ location #f)) ((char=? c #\=) (make-lexical-token '= location #f)) ((char=? c #\,) (make-lexical-token 'COMMA location #f)) ((char=? c #\() (make-lexical-token 'LPAREN location #f)) ((char=? c #\)) (make-lexical-token 'RPAREN location #f)) ((char-numeric? c) (make-lexical-token 'NUM location (read-number (list c)))) ((char-alphabetic? c) (make-lexical-token 'ID location (read-id (list c)))) (else (errorp "PARSE ERROR : illegal character: " c) (skip-spaces) (loop)))))))) ;;; ;;;; Environment management ;;; (define *env* (list (cons '$$ 0))) (define (init-bindings) (set-cdr! *env* '()) (add-binding 'cos cos) (add-binding 'sin sin) (add-binding 'tan tan) (add-binding 'expt expt) (add-binding 'sqrt sqrt)) (define (add-binding var val) (set! *env* (cons (cons var val) *env*)) val) (define (get-binding var) (let ((p (assq var *env*))) (if p (cdr p) 0))) (define (invoke-proc proc-name args) (let ((proc (get-binding proc-name))) (if (procedure? proc) (apply proc args) (begin (display "ERROR: invalid procedure:") (display proc-name) (newline) 0)))) ;;; ;;;; The main program ;;; (define (display-result v) (if v (begin (display v) (newline))) (display-prompt)) (define (display-prompt) (display "[calculator]> ") (force-output)) (define calc (lambda () (call-with-current-continuation (lambda (k) (display "********************************") (newline) (display "* Mini calculator in Scheme *") (newline) (display "* *") (newline) (display "* Enter expressions followed *") (newline) (display "* by [RETURN] or 'quit()' to *") (newline) (display "* exit. *") (newline) (display "********************************") (newline) (init-bindings) (add-binding 'quit (lambda () (k #t))) (letrec ((errorp (lambda (message . args) (display message) (if (and (pair? args) (lexical-token? (car args))) (let ((token (car args))) (display (or (lexical-token-value token) (lexical-token-category token))) (let ((source (lexical-token-source token))) (if (source-location? source) (let ((line (source-location-line source)) (column (source-location-column source))) (if (and (number? line) (number? column)) (begin (display " (at line ") (display line) (display ", column ") (display (+ 1 column)) (display ")"))))))) (for-each display args)) (newline))) (start (lambda () (calc-parser (make-lexer errorp) errorp)))) (display-prompt) (start)))))) (calc) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;; ;;; END FILE: calc.scm ;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; == About this egg === Author Dominique Boucher === Repository This egg is hosted on the CHICKEN Subversion repository: [[https://anonymous@code.call-cc.org/svn/chicken-eggs/release/5/lalr|https://anonymous@code.call-cc.org/svn/chicken-eggs/release/5/lalr]] If you want to check out the source code repository of this egg and you are not familiar with Subversion, see [[/egg-svn-checkout|this page]]. === Version history ; 2.5.0 : Updated to upstream version 2.5.0 ; 2.4.3 : Using (require-extension extras) in lalr.scm [thanks to Matt Gushee] ; 2.4.1 : Updated to upstream version 2.4.1; license updated to LGPL-3 ; 2.3.2 : Documentation converted to wiki format ; 2.3.1 : Bug fix in lalr-driver to clear the input variable every time a parser is called ; 2.3.0 : Updated to upstream version 2.3.0; functionality split in two modules ; 2.1.2 : Error-handler is now called with complete token ; 2.1.1 : Fixed missing syntax attribute in setup script === License This program is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. A full copy of the Lesser GPL license can be found at <http://www.gnu.org/licenses/>. Description of your changes:

I would like to authenticate

Spam control

What do you get when you subtract 11 from 1?