9. Bigloo -- Regular parsing

Browsing
Home: | Bigloo A ``practical Scheme compiler'' User manual for version 2.6b December 2003
Previous chapter: | Threads
Next chapter: | Lalr(1) parsing
Regular parsing
9.1 | A new way of reading
9.2 | The syntax of the regular parser
9.3 | The semantics actions
9.4 | Examples of regular grammar
| 9.4.1 | Word count
| 9.4.2 | Roman numbers
Chapters
| Acknowledgements
1. | Table of contents
2. | Overview of Bigloo
3. | Modules
4. | Core Language
5. | Standard Library
6. | Pattern Matching
7. | Object System
8. | Threads
9. | Regular parsing
10. | Lalr(1) parsing
11. | Errors and Assertions
12. | Eval and code interpretation
13. | Macro expansion
14. | Command Line Parsing
15. | Explicit typing
16. | The C interface
17. | The Java interface
18. | Bigloo Libraries
19. | Extending the Runtime System
20. | SRFIs
21. | DSSSL support
22. | Compiler description
23. | User Extensions
24. | Bigloo Development Environment
25. | Global Index
26. | Library Index
| Bibliography
| Programming languages have poor reading libraries since the lexical information that can be specified is directly tied to the structure of the language. For example, in C it's hard to read a rational number because there is no type rational. Programs have been written to circumvent this problem: Lex [Lesk75], for example, is one of them. We choose to incorporate in Bigloo a set of new functions to assist in such parsing. The syntax for regular parser of Bigloo 2.0 (the one described in this document) is not compatible with former Bigloo versions.
9.1 A new way of reading
There is only one way in Bigloo to read text, regular reading, which is done by the new form:
read/rp regular-parser input-port | bigloo procedure
The first argument is a regular parser and the second a Scheme port. This way of reading is almost the same as the Lex's one. The reader tries to match the longest input, from the stream pointed to by `input-port`, with one of several regular expressions contained in `regular-parser`. If many rules match, the reader takes the first one defined in the grammar. When the regular rule has been found the corresponding Scheme expression is evaluated. remark: The traditional `read` Scheme function is implemented as:
    (define-inline (read port)
       (read/rp scheme-grammar port))

*about-to-read* | bigloo variable
When this variable is bound to a function, then each time the reader has filled its buffer, this function is called with an `input-port` as its argument.

9.2 The syntax of the regular parser

A regular parser is built by the means of the form `regular-grammar`:

regular-grammar (binding ...) rule ... | bigloo syntax
The `binding` and `rule` are defined by the following grammar:
    <binding>  ==> (<variable> <re>)
    <rule>     ==> (<cre> <s-expression> <s-expression> ...)
                 | (<context> <re> <s-expression> <s-expresion> ...)
                 | (else <s-expression> <s-expression> ...)
    <cre>      ==> <re>
                 | (context <symbol> <re>)
                 | (when <s-expr> <re>)
                 | (bol <re>)
                 | (eol <re>)
                 | (bof <re>)
                 | (eof <re>)
    <re>       ==> <variable>
                 | <char>
                 | <string>
                 | (: <re> ...)
                 | (or <re> ...)
                 | (* <re>)
                 | (+ <re>)
                 | (? <re>)
                 | (= <integer> <re>)
                 | (>= <integer> <re>)
                 | (** <integer> <integer> <re>)
                 | (... <integer> <re>)
                 | (uncase <re>)
                 | (in <cset> ...)
                 | (out <cset> ...)
                 | (and <cset> <cset>)
                 | (but <cset> <cset>)
                 | (posix <string>)
    <variable> ==> <symbol>
    <cset>     ==> <string>
                 | <char>
                 | (<string>)
                 | (<char> <char>)
  Here is a description of each construction. `` `(context <symbol> <re>)` This allows us to protect an expression. A protected expression matches (or accepts) a word only if the parser has been set to the corresponding context. See The Semantics Actions, for more details. `` `(when <s-expr> <re>)` This allows us to protect an expression. A protected expression matches (or accepts) a word only if the evaluation of `<s-expr>` is `#t`. For instance,
      (define *g*
         (let ((armed #f))
            (regular-grammar ()
               ((when (not armed) (: "#!" (+ (or #\/ alpha))))
                (set! armed #t)
                (print "start [" (the-string) "]")
                (ignore))
               ((+ (in #\Space #\Tab))
                (ignore))
               (else
                (the-failure)))))

      (define (main argv)
         (let ((port (open-input-string "#!/bin/sh #!/bin/zsh")))
            (print (read/rp *g* port))))
  `` `(bol <re>)` Matches `<re>` at the beginning of line. `` `(eol <re>)` Matches `<re>` at the end of line. `` `(bof <re>)` Matches `<re>` at the beginning of file. `` `(eof <re>)` Matches `<re>` at the end of file. `` `<variable>` This is the name of a variable bound by a <binding> construction. In addition to user defined variables, some already exist. These are:
      all    <=> (out #\Newline)
      lower  <=> (in ("az"))
      upper  <=> (in ("AZ"))
      alpha  <=> (or lower upper)
      digit  <=> (in ("09"))
      xdigit <=> (uncase (in ("af09")))
      alnum  <=> (uncase (in ("az09")))
      punct  <=> (in ".,;!?")
      blank  <=> (in #" \t\n")
      space  <=> #\Space
  It is a error to reference a variable that it is not bound by a <binding>. Defining a variable that already exists is acceptable and causes the former variable definition to be erased. Here is an example of a grammar that binds two variables, one called `ident` and one called `number`. These two variables are used within the grammar to match identifiers and numbers.
      (regular-grammar ((ident  (: alpha (* alnum)))
                        (number (+ digit)))
         (ident  (cons 'ident (the-string)))
         (number (cons 'number (the-string)))
         (else   (cons 'else (the-failure))))
  `` `<char>` The regular language described by one unique character. Here is an example of a grammar that accepts either the character `#\a` or the character `#\b`:
      (regular-grammar ()
         (#\a (cons 'a (the-string)))
         (#\b (cons 'b (the-string)))
         (else (cons 'else (the-failure))))
  `` `<string>` This simple form of regular expression denotes the language represented by the string. For instance the regular expression `"Bigloo"` matches only the string composed of `#\B #\i #\g #\l #\o #\o`. The regular expression `".*["` matches the string `#\. #\* #\[`. `` `(: <re> ...)` This form constructs sequence of regular expression. That is a form `<re1> <re2> ... <ren>` matches the language construction by concatenation of the language described by `<re1>`, `<re2>`, `<ren>`. Thus, `(: "x" all "y")` matches all words of three letters, started by character the `#\x` and ended with the character `#\y`. `` `(or <re> ...)` This construction denotes conditions. The language described by `(or re1 re2)` accepts words accepted by either `re1` or `re2`. `` `(* <re>)` This is the Kleene operator, the language described by `(* <re>)` is the language containing, 0 or more occurrences of `<re>`. Thus, the language described by `(* "abc")` accepts the empty word and any word composed by a repetition of the `abc` (`abc`, `abcabc`, `abcabcabc`, ...). `` `(+ <re>)` This expression described non empty repetitions. The form `(+ re)` is equivalent to `(: re (* re))`. Thus, `(+ "abc")` matches the words `abc`, `abcabc`, etc. `` `(? <re>)` This expression described one or zero occurrence. Thus, `(? "abc")` matches the empty word or the words `abc`. `` `(= <integer> <re>)` This expression described a fix number of repetitions. The form `(= num re)` is equivalent to `(: re re ... re)`. Thus, the expression `(= 3 "abc")` matches the only word `abcabcabc`. In order to avoid code size explosion when compiling, `<integer>` must be smaller than an arbitrary constant. In the current version that value is `81`. `` `(>= <integer> <re>)` The language described by the expression `(>= int re)` accepts word that are, at least, `int` repetitions of `re`. For instance, `(>= 10 #\a)`, accepts words compound of, at least, 10 times the character `#\a`. In order to avoid code size explosion when compiling, `<integer>` must be smaller than an arbitrary constant. In the current version that value is `81`. `` `(** <integer> <integer> <re>)` The language described by the expression `(** min max re)` accepts word that are repetitions of `re`; the number of repetition is in the range `min`, `max`. For instance, `(** 10 20 #\a)`. In order to avoid code size explosion when compiling, `<integer>` must be smaller than an arbitrary constant. In the current version that value is `81`. `` `(... <integer> <re>)` The subexpression `<re>` has to be a sequence of characters. Sequences are build by the operator `:` or by string literals. The language described by `(... int re)`, denotes, the first letter of `re`, or the two first letters of `re`, or the three first letters of `re` or the `int` first letters of `re`. Thus, `(... 3 "begin")` is equivalent to `(or "b" "be" "beg")`. `` `(uncase <re>)` The subexpression `<re>` has to be a sequence construction. The language described by `(uncase re)` is the same as `re` where letters may be upper case or lower case. For instance, `(uncase "begin")`, accepts the words `"begin"`, `"beGin"`, `"BEGIN"`, `"BegiN"`, etc. `` `(in <cset> ...)` Denotes union of characters. Characters may be described individually such as in `(in #\a #\b #\c #\d)`. They may be described by strings. The expression `(in "abcd")` is equivalent to `(in #\a #\b #\c #\d)`. Characters may also be described using a range notation that is a list of two characters. The expression `(in (#\a #\d))` is equivalent to `(in #\a #\b #\c #\d)`. The Ranges may be expresses using lists of string. The expression `(in ("ad"))` is equivalent to `(in #\a #\b #\c #\d)`. `` `(out <cset> ...)` The language described by `(out cset ...)` is opposite to the one described by `(in cset ...)`. For instance, `(out ("azAZ") (#\0 #\9))` accepts all words of one character that are neither letters nor digits. One should not that if the character numbered zero may be used inside regular grammar, the `out` construction never matches it. Thus to write a rule that, for instances, matches every character but `#\Newline` including the character zero, one should write:
      (or (out #\Newline) #a000)
  `` `(and <cset> <cset>)` The language described by `(and cset1 cset2)` accepts words made of characters that are in both `cset1` and `cset2`. `` `(but <cset> <cset>)` The language described by `(but cset1 cset2)` accepts words made of characters of `cset1` that are not member of `cset2`. `` `(posix <string>)` The expression `(posix string)` allows one to use Posix string notation for regular expressions. So, for example, the following two expressions are equivalent:
      (posix "[az]+|x*|y{3,5}")

      (or (+ (in ("az"))) (* "x") (** 3 5 "y"))

string-case string rule ... | bigloo syntax
This form dispatches on strings. it opens an input on `string` a read into it according to the regular grammar defined by the `binding` and `rule`. Example:
    (define (suffix string)
       (string-case string
          ((: (* all) ".")
           (ignore))
          ((+ (out #\.))
           (the-string))
          (else
           "")))

9.3 The semantics actions

The semantics actions are regular Scheme expressions. These expressions appear in an environment where some ``extra procedures'' are defined. These procedures are:

the-port | bigloo rgc procedure
Returns the input port currently in used.

the-length | bigloo rgc procedure
Get the length of the biggest matching string.

the-string | bigloo rgc procedure
Get a copy of the last matching string. The function `the-string` returns a fresh copy of the matching each time it is called. In consequence,
    (let ((l1 (the-string)) (l2 (the-string)))
       (eq? l1 l2))
       => #f

the-substring start length | bigloo rgc procedure
Get a copy of a substring of the last matching string. Here is an example of a rule extracting a part of a match
    (regular-grammar ()
       ((: #\" (* (out #\")) #\")
        (the-substring 1 (-fx (the-length) 1))))

the-character | bigloo rgc procedure
Returns the first character of a match.

the-symbol | bigloo rgc procedure
Convert the last matching string into a symbol.

the-keyword | bigloo rgc procedure
Convert the last matching string into a keyword.

the-fixnum | bigloo rgc procedure
The conversion of the last matching string to fixnum.

the-flonum | bigloo rgc procedure
The conversion of the last matching string to flonum.

the-failure | bigloo rgc procedure
Returns the first char that the grammar can't match or the end of file object.

ignore | bigloo rgc procedure
Ignore the parsing, keep reading. It's better to use `(ignore)` rather than an expression like `(read/rp `grammar` `port`)` in semantics actions since the `(ignore)` call will be done in a tail recursive way. For instance,
    (let ((g (regular-grammar ()
                (")"
                 '())
                ("("
                 (let* ((car (ignore))
                        (cdr (ignore)))
                    (cons car cdr)))
                ((+ (out "()"))
                 (the-string))))
          (p (open-input-string "(foo(bar(gee)))")))
       (read/rp g p))
       => ("foo" ("bar" ("gee")))

rgc-context [context] | bigloo rgc procedure
If no `context` is provide, this procedure reset the reader context state. That is the reader is in no context. With one argument, `context` set the reader in the context `context`. For instance,
    (let ((g (regular-grammar ()
                ((context foo "foo") (print 'foo-bis))
                ("foo" (rgc-context 'foo) (print 'foo) (ignore))
                (else 'done)))
          (p (open-input-string "foofoo")))
       (read/rp g p))
       -| FOO
          FOO-BIS

the-context | bigloo rgc procedure
Returns the value of the current Rgc context.

9.4 Examples of regular grammar

The reader who wants to find a real example should read the code of Bigloo's reader. But here are small examples

### 9.4.1 Word count

The first example presents a grammar that simulates the Unix program `wc`.

    (let ((*char* 0)
          (*word* 0)
          (*line* 0))
       (regular-grammar ()
          ((+ #\Newline)
           (set! *char* (+ *char* (the-length)))
           (set! *line* (+ *line* (the-length)))
           (ignore))
          ((+ (in #\space #\tab))
           (set! *char* (+ *char* (the-length)))
           (ignore))
          ((+ (out #\newline #\space #\tab))
           (set! *char* (+ *char* (the-length)))
           (set! *word* (+ 1 *word*))
           (ignore))))

### 9.4.2 Roman numbers

The second example presents a grammar that reads Arabic and Roman number.

    (let ((par-open 0))
       (regular-grammar ((arabic (in ("09")))
                         (roman  (uncase (in "ivxlcdm"))))
          ((+ (in #" \t\n"))
           (ignore))
          ((+ arabic)
           (string->integer (the-string)))
          ((+ roman)
           (roman->arabic (the-string)))
          (#\(
           (let ((open-key par-open))
              (set! par-open (+ 1 par-open))
              (context 'pair)
              (let loop-pair ((walk (ignore)))
                 (cond
                    ((= open-key par-open)
                     '())
                    (else
                     (cons walk (loop-pair (ignore))))))))
          (#\)
           (set! par-open (- par-open 1))
           (if (< par-open 0)
               (begin
                  (set! par-open 0)
                  (ignore))
               #f))
          ((in "+-*\\")
           (string->symbol (the-string)))
          (else
           (let ((char (the-failure)))
              (if (eof-object? char)
                  char
                  (error "grammar-roman" "Illegal char" char))))))

This Scribe page has been generated by `scribeinfo`.
Last update Tue Dec 16 13:46:41 2003