# Lexer: what means "matches no string"?

**URL:** <https://racket.discourse.group/t/lexer-what-means-matches-no-string/2546>\
**Category:** Questions & Answers\
**Tags:** lexer\
**Created:** [November 27, 2023, 8:57pm UTC](https://racket.discourse.group/t/lexer-what-means-matches-no-string/2546 "2023-11-27T20:57:28Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![ceving](https://avatars.discourse-cdn.com/v4/letter/c/a3d4f5/32.png) [@ceving](https://racket.discourse.group/u/ceving)\
**Post date:** [November 27, 2023, 8:57pm UTC](https://racket.discourse.group/t/lexer-what-means-matches-no-string/2546/1 "2023-11-27T20:57:28Z")

</div>

> [nothing](https://docs.racket-lang.org/parser-tools/Lexers.html#%28form._%28%28lib._parser-tools%2Flex..rkt%29._nothing%29%29)  
> A lexer abbreviation that matches no string.

I am not sure if this means never or always.

If "no string" is an empty string, this would match always. In that case I would like to know how to stop endless recursion? Is it possible to create a stateful lexer?

If it matches never, I would like to know why this is useful?

---

<div class="post-metadata">

**Author:** ![sorawee](https://avatars.discourse-cdn.com/v4/letter/s/ea5d25/32.png) [@sorawee](https://racket.discourse.group/u/sorawee)\
**Post date:** [November 27, 2023, 9:42pm UTC](https://racket.discourse.group/t/lexer-what-means-matches-no-string/2546/2 "2023-11-27T21:42:38Z")

</div>

`nothing` interacts with `union` (or `:or` from the SRE library): the branches with `nothing` are discarded. So one possible use case (though I don’t know if it’s an intended use case) is to prune some branches that you don’t want away, especially within a regexp abstraction defined via `define-lex-trans`.

Here’s a concrete example.

```scheme
#lang racket

(require parser-tools/lex
         (prefix-in : parser-tools/lex-sre)
         (for-syntax syntax/parse))

(define-lex-trans option
  (syntax-parser
    [(_ re) #'(:or (:: "some " re) "none")]))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

((lexer
  [(option "abc") 'matched]
  ["" 'unmatched])
 (open-input-string "some abc")) ;=> matched

((lexer
  [(option "abc") 'matched]
  ["" 'unmatched])
 (open-input-string "some def")) ;=> unmatched

((lexer
  [(option "abc") 'matched]
  ["" 'unmatched])
 (open-input-string "none")) ;=> matched

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

((lexer
  [(option nothing) 'matched]
  ["" 'unmatched])
 (open-input-string "none")) ;=> matched

((lexer
  [(option nothing) 'matched]
  ["" 'unmatched])
 (open-input-string "some abc")) ;=> unmatched

```

The above code defines a regexp abstraction called `option`. So `(option "abc")` matches both `none` and `some abc`, but not `some def`.

But now, if I want to match only `none`, but not any `some`, I can give `nothing` as the regexp to `option`.

---

<div class="post-metadata">

**Author:** ![usao](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/usao/32/1375_2.png) [@usao](https://racket.discourse.group/u/usao)\
**Post date:** [November 28, 2023, 12:01am UTC](https://racket.discourse.group/t/lexer-what-means-matches-no-string/2546/3 "2023-11-28T00:01:41Z")

</div>

On the theoretical side: The empty regexp serves as the zero in the algebra of regular languages. If you consider the set of strings (i.e., the regular language) the regexp recognizes, the empty regexp is just the empty set. Concatenation corresponds to Cartesian product with string concatenation, so concatenation with empty always results in empty; union corresponds to set union, so empty is the identity element. In this sense, it is a zero, which is very important (although itself very trivial).