Repository: tweag/nickel
Pull request #180 (2020-10-26 16:59:57)

Migrate the lexer to use the Logos library
In #131, the implementation of string interpolation mandated to depart from LALRPOP's generated lexer, which is not able to handle such a usage. Some lexing libraries were reviewed, and none seemed to be able to do this simply by looking at the doc, so the decision was taken to implement a custom lexer.

After discussing with people from the LALRPOP community about a different subject, it turns out that one of the mentioned library is actually capable of implementing a modal lexer, by wrapping multiple simple lexers in a custom one: [Logos](https://github.com/maciejhirsz/logos). I should have looked better. In any case, even if implementing lexers is not a passion, I think it will be beneficial on the long term, in particular because we are working on the syntax right now, and the current hand-rolled custom lexer is much less easy to extend in a correct way than a generated one.

This PR migrates the lexer to use the Logos library.

## What it does
 - use Logos to generate lexers, and wrap them in a modal lexer which replace the previous custom one.
 - update the parser, tests and error handling code in consequence

## Changes

There a few differences with the previous behavior:
- previously, a dollar character needed to be escaped only if it was followed by a `{`, as in Nix. For example, this is was a valid string `"a$b\\${non interpolated}". Now, every dollar character must be escaped: "a\\$b\\${non interpolated}". This makes things simpler, as the underlying lexers don't have lookaheads, and it doesn't look like a big regression. However, it can become a problem if we have to be compatible with Nix strings. The old behavior can still be implemented on top of this lexer, if requested.
- the parser previously made an optimization on interpolated strings which was rightly deemed [prematured](https://github.com/tweag/nickel/pull/131#discussion_r482809778). This PR removes it. This piece of code had moreover nothing to do in the parser: we can very well implement this optimization, but it belongs to the program transformation phase.

[**Note**: the lexer has been put in a new file `lexer_new.rs`, to ease the review. Otherwise, if it replaces the old `lexer.rs`, git insists to make a diff even if the two files are totally distinct. It must be renamed back to `lexer.rs` before merging]


Patch:
diff --git a/Cargo.lock b/Cargo.lock
index b66e3d4d..5b6b7598 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -46,6 +46,11 @@ name = "autocfg"
 version = "0.1.7"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
+[[package]]
+name = "beef"
+version = "0.4.4"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
 [[package]]
 name = "bit-set"
 version = "0.5.1"
@@ -175,6 +180,11 @@ name = "fixedbitset"
 version = "0.1.9"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
+[[package]]
+name = "fnv"
+version = "1.0.7"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
 [[package]]
 name = "fuchsia-cprng"
 version = "0.1.1"
@@ -252,6 +262,28 @@ dependencies = [
  "cfg-if 0.1.10 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
+[[package]]
+name = "logos"
+version = "0.11.4"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "logos-derive 0.11.5 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "logos-derive"
+version = "0.11.5"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "beef 0.4.4 (registry+https://github.com/rust-lang/crates.io-index)",
+ "fnv 1.0.7 (registry+https://github.com/rust-lang/crates.io-index)",
+ "proc-macro2 1.0.24 (registry+https://github.com/rust-lang/crates.io-index)",
+ "quote 1.0.7 (registry+https://github.com/rust-lang/crates.io-index)",
+ "regex-syntax 0.6.12 (registry+https://github.com/rust-lang/crates.io-index)",
+ "syn 1.0.45 (registry+https://github.com/rust-lang/crates.io-index)",
+ "utf8-ranges 1.0.4 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
 [[package]]
 name = "memchr"
 version = "2.2.1"
@@ -271,6 +303,7 @@ dependencies = [
  "either 1.5.3 (registry+https://github.com/rust-lang/crates.io-index)",
  "lalrpop 0.16.3 (registry+https://github.com/rust-lang/crates.io-index)",
  "lalrpop-util 0.16.3 (registry+https://github.com/rust-lang/crates.io-index)",
+ "logos 0.11.4 (registry+https://github.com/rust-lang/crates.io-index)",
  "pretty_assertions 0.5.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "regex 0.2.11 (registry+https://github.com/rust-lang/crates.io-index)",
  "simple-counter 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -328,7 +361,7 @@ dependencies = [
 
 [[package]]
 name = "proc-macro2"
-version = "1.0.6"
+version = "1.0.24"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "unicode-xid 0.2.0 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -336,10 +369,10 @@ dependencies = [
 
 [[package]]
 name = "quote"
-version = "1.0.2"
+version = "1.0.7"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
- "proc-macro2 1.0.6 (registry+https://github.com/rust-lang/crates.io-index)",
+ "proc-macro2 1.0.24 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
@@ -495,9 +528,9 @@ name = "serde_derive"
 version = "1.0.102"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
- "proc-macro2 1.0.6 (registry+https://github.com/rust-lang/crates.io-index)",
- "quote 1.0.2 (registry+https://github.com/rust-lang/crates.io-index)",
- "syn 1.0.8 (registry+https://github.com/rust-lang/crates.io-index)",
+ "proc-macro2 1.0.24 (registry+https://github.com/rust-lang/crates.io-index)",
+ "quote 1.0.7 (registry+https://github.com/rust-lang/crates.io-index)",
+ "syn 1.0.45 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
@@ -542,8 +575,8 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "phf_generator 0.7.24 (registry+https://github.com/rust-lang/crates.io-index)",
  "phf_shared 0.7.24 (registry+https://github.com/rust-lang/crates.io-index)",
- "proc-macro2 1.0.6 (registry+https://github.com/rust-lang/crates.io-index)",
- "quote 1.0.2 (registry+https://github.com/rust-lang/crates.io-index)",
+ "proc-macro2 1.0.24 (registry+https://github.com/rust-lang/crates.io-index)",
+ "quote 1.0.7 (registry+https://github.com/rust-lang/crates.io-index)",
  "string_cache_shared 0.3.0 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
@@ -559,11 +592,11 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
 name = "syn"
-version = "1.0.8"
+version = "1.0.45"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
- "proc-macro2 1.0.6 (registry+https://github.com/rust-lang/crates.io-index)",
- "quote 1.0.2 (registry+https://github.com/rust-lang/crates.io-index)",
+ "proc-macro2 1.0.24 (registry+https://github.com/rust-lang/crates.io-index)",
+ "quote 1.0.7 (registry+https://github.com/rust-lang/crates.io-index)",
  "unicode-xid 0.2.0 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
@@ -666,6 +699,7 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 "checksum ascii-canvas 1.0.0 (registry+https://github.com/rust-lang/crates.io-index)" = "b385d69402821a1c254533a011a312531cbcc0e3e24f19bbb4747a5a2daf37e2"
 "checksum atty 0.2.13 (registry+https://github.com/rust-lang/crates.io-index)" = "1803c647a3ec87095e7ae7acfca019e98de5ec9a7d01343f611cf3152ed71a90"
 "checksum autocfg 0.1.7 (registry+https://github.com/rust-lang/crates.io-index)" = "1d49d90015b3c36167a20fe2810c5cd875ad504b39cff3d4eae7977e6b7c1cb2"
+"checksum beef 0.4.4 (registry+https://github.com/rust-lang/crates.io-index)" = "474a626a67200bd107d44179bb3d4fc61891172d11696609264589be6a0e6a43"
 "checksum bit-set 0.5.1 (registry+https://github.com/rust-lang/crates.io-index)" = "e84c238982c4b1e1ee668d136c510c67a13465279c0cb367ea6baf6310620a80"
 "checksum bit-vec 0.5.1 (registry+https://github.com/rust-lang/crates.io-index)" = "f59bbe95d4e52a6398ec21238d31577f2b28a9d86807f06ca59d191d8440d0bb"
 "checksum bitflags 1.2.1 (registry+https://github.com/rust-lang/crates.io-index)" = "cf1de2fe8c75bc145a2f577add951f8134889b4795d47466a54a5c846d691693"
@@ -685,6 +719,7 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 "checksum ena 0.11.0 (registry+https://github.com/rust-lang/crates.io-index)" = "f56c93cc076508c549d9bb747f79aa9b4eb098be7b8cad8830c3137ef52d1e00"
 "checksum fake-simd 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)" = "e88a8acf291dafb59c2d96e8f59828f3838bb1a70398823ade51a84de6a6deed"
 "checksum fixedbitset 0.1.9 (registry+https://github.com/rust-lang/crates.io-index)" = "86d4de0081402f5e88cdac65c8dcdcc73118c1a7a465e2a05f0da05843a8ea33"
+"checksum fnv 1.0.7 (registry+https://github.com/rust-lang/crates.io-index)" = "3f9eec918d3f24069decb9af1554cad7c880e2da24a9afd88aca000531ab82c1"
 "checksum fuchsia-cprng 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "a06f77d526c1a601b7c4cdd98f54b5eaabffc14d5f2f0296febdc7f357c6d3ba"
 "checksum generic-array 0.12.3 (registry+https://github.com/rust-lang/crates.io-index)" = "c68f0274ae0e023facc3c97b2e00f076be70e254bc851d972503b328db79b2ec"
 "checksum itertools 0.8.1 (registry+https://github.com/rust-lang/crates.io-index)" = "87fa75c9dea7b07be3138c49abbb83fd4bea199b5cdc76f9804458edc5da0d6e"
@@ -694,6 +729,8 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 "checksum lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "e2abad23fbc42b3700f2f279844dc832adb2b2eb069b2df918f455c4e18cc646"
 "checksum libc 0.2.65 (registry+https://github.com/rust-lang/crates.io-index)" = "1a31a0627fdf1f6a39ec0dd577e101440b7db22672c0901fe00a9a6fbb5c24e8"
 "checksum log 0.4.8 (registry+https://github.com/rust-lang/crates.io-index)" = "14b6052be84e6b71ab17edffc2eeabf5c2c3ae1fdb464aae35ac50c67a44e1f7"
+"checksum logos 0.11.4 (registry+https://github.com/rust-lang/crates.io-index)" = "b91c49573597a5d6c094f9031617bb1fed15c0db68c81e6546d313414ce107e4"
+"checksum logos-derive 0.11.5 (registry+https://github.com/rust-lang/crates.io-index)" = "797b1f8a0571b331c1b47e7db245af3dc634838da7a92b3bef4e30376ae1c347"
 "checksum memchr 2.2.1 (registry+https://github.com/rust-lang/crates.io-index)" = "88579771288728879b57485cc7d6b07d648c9f0141eb955f8ab7f9d45394468e"
 "checksum new_debug_unreachable 1.0.3 (registry+https://github.com/rust-lang/crates.io-index)" = "f40f005c60db6e03bae699e414c58bf9aa7ea02a2d0b9bfbcf19286cc4c82b30"
 "checksum opaque-debug 0.2.3 (registry+https://github.com/rust-lang/crates.io-index)" = "2839e79665f131bdb5782e51f2c6c9599c133c6098982a54c794358bf432529c"
@@ -703,8 +740,8 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 "checksum phf_shared 0.7.24 (registry+https://github.com/rust-lang/crates.io-index)" = "234f71a15de2288bcb7e3b6515828d22af7ec8598ee6d24c3b526fa0a80b67a0"
 "checksum precomputed-hash 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "925383efa346730478fb4838dbe9137d2a47675ad789c546d150a6e1dd4ab31c"
 "checksum pretty_assertions 0.5.1 (registry+https://github.com/rust-lang/crates.io-index)" = "3a029430f0d744bc3d15dd474d591bed2402b645d024583082b9f63bb936dac6"
-"checksum proc-macro2 1.0.6 (registry+https://github.com/rust-lang/crates.io-index)" = "9c9e470a8dc4aeae2dee2f335e8f533e2d4b347e1434e5671afc49b054592f27"
-"checksum quote 1.0.2 (registry+https://github.com/rust-lang/crates.io-index)" = "053a8c8bcc71fcce321828dc897a98ab9760bef03a4fc36693c231e5b3216cfe"
+"checksum proc-macro2 1.0.24 (registry+https://github.com/rust-lang/crates.io-index)" = "1e0704ee1a7e00d7bb417d0770ea303c1bccbabf0ef1667dae92b5967f5f8a71"
+"checksum quote 1.0.7 (registry+https://github.com/rust-lang/crates.io-index)" = "aa563d17ecb180e500da1cfd2b028310ac758de548efdd203e18f283af693f37"
 "checksum rand 0.6.5 (registry+https://github.com/rust-lang/crates.io-index)" = "6d71dacdc3c88c1fde3885a3be3fbab9f35724e6ce99467f7d9c5026132184ca"
 "checksum rand_chacha 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "556d3a1ca6600bfcbab7c7c91ccb085ac7fbbcd70e008a98742e7847f4f7bcef"
 "checksum rand_core 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)" = "7a6fdeb83b075e8266dcc8762c22776f6877a63111121f5f8c7411e5be7eed4b"
@@ -729,7 +766,7 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 "checksum string_cache_codegen 0.4.4 (registry+https://github.com/rust-lang/crates.io-index)" = "f0f45ed1b65bf9a4bf2f7b7dc59212d1926e9eaf00fa998988e420fd124467c6"
 "checksum string_cache_shared 0.3.0 (registry+https://github.com/rust-lang/crates.io-index)" = "b1884d1bc09741d466d9b14e6d37ac89d6909cbcac41dd9ae982d4d063bbedfc"
 "checksum strsim 0.9.2 (registry+https://github.com/rust-lang/crates.io-index)" = "032c03039aae92b350aad2e3779c352e104d919cb192ba2fabbd7b831ce4f0f6"
-"checksum syn 1.0.8 (registry+https://github.com/rust-lang/crates.io-index)" = "661641ea2aa15845cddeb97dad000d22070bb5c1fb456b96c1cba883ec691e92"
+"checksum syn 1.0.45 (registry+https://github.com/rust-lang/crates.io-index)" = "ea9c5432ff16d6152371f808fb5a871cd67368171b09bb21b43df8e4a47a3556"
 "checksum term 0.4.6 (registry+https://github.com/rust-lang/crates.io-index)" = "fa63644f74ce96fbeb9b794f66aff2a52d601cbd5e80f4b97123e3899f4570f1"
 "checksum termcolor 1.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "bb6bfa289a4d7c5766392812c0a1f4c1ba45afa1ad47803c11e1f407d846d75f"
 "checksum thread_local 0.3.6 (registry+https://github.com/rust-lang/crates.io-index)" = "c6b53e329000edc2b34dbe8545fd20e55a333362d0a321909685a19bd28c3f1b"
diff --git a/Cargo.toml b/Cargo.toml
index 9d808d2f..05b5d380 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -17,6 +17,7 @@ either = "1.5.3"
 simple-counter = "0.1.0"
 codespan = "0.9.5"
 codespan-reporting = "0.9.5"
+logos = "0.11.4"
 
 [dev-dependencies]
 pretty_assertions = "0.5.1"
diff --git a/src/error.rs b/src/error.rs
index 3fd07b86..32e4f6e7 100644
--- a/src/error.rs
+++ b/src/error.rs
@@ -175,8 +175,6 @@ pub enum ParseError {
     /// A closing brace '}' does not match an opening brace '{'. This rather precise error is detected by the because
     /// of how interpolated strings are lexed.
     UnmatchedCloseBrace(RawSpan),
-    /// An alphanumeric character directly follows a number literal.
-    NumThenIdent(RawSpan),
     /// Invalid escape sequence in a string literal.
     InvalidEscapeSequence(RawSpan),
 }
@@ -234,12 +232,12 @@ impl ParseError {
                 token: Some((start, _, end)),
                 expected,
             } => ParseError::UnexpectedToken(mk_span(file_id, start, end), expected),
+            lalrpop_util::ParseError::User {
+                error: LexicalError::Generic(start, end),
+            } => ParseError::UnexpectedToken(mk_span(file_id, start, end), Vec::new()),
             lalrpop_util::ParseError::UnrecognizedToken {
                 token: None,
                 expected,
-            }
-            | lalrpop_util::ParseError::User {
-                error: LexicalError::UnexpectedEOF(expected),
             } => ParseError::UnexpectedEOF(file_id, expected),
             lalrpop_util::ParseError::ExtraToken {
                 token: (start, _, end),
@@ -247,12 +245,6 @@ impl ParseError {
             lalrpop_util::ParseError::User {
                 error: LexicalError::UnmatchedCloseBrace(location),
             } => ParseError::UnmatchedCloseBrace(mk_span(file_id, location, location + 1)),
-            lalrpop_util::ParseError::User {
-                error: LexicalError::UnexpectedChar(location),
-            } => ParseError::UnexpectedToken(mk_span(file_id, location, location + 1), Vec::new()),
-            lalrpop_util::ParseError::User {
-                error: LexicalError::NumThenIdent(location),
-            } => ParseError::NumThenIdent(mk_span(file_id, location, location + 1)),
             lalrpop_util::ParseError::User {
                 error: LexicalError::InvalidEscapeSequence(location),
             } => ParseError::InvalidEscapeSequence(mk_span(file_id, location, location + 1)),
@@ -881,9 +873,6 @@ impl ToDiagnostic<FileId> for ParseError {
             ParseError::UnmatchedCloseBrace(span) => Diagnostic::error()
                 .with_message("Unmatched closing brace \'}\'")
                 .with_labels(vec![primary(span)]),
-            ParseError::NumThenIdent(span) => Diagnostic::error()
-                .with_message("Invalid character in a number literal")
-                .with_labels(vec![primary(span)]),
             ParseError::InvalidEscapeSequence(span) => Diagnostic::error()
                 .with_message("Invalid escape sequence")
                 .with_labels(vec![primary(span)]),
diff --git a/src/grammar.lalrpop b/src/grammar.lalrpop
index c34fcb0b..c53a9dd6 100644
--- a/src/grammar.lalrpop
+++ b/src/grammar.lalrpop
@@ -2,7 +2,7 @@ use crate::identifier::Ident;
 use crate::term::{BinaryOp, RichTerm, Term, UnaryOp, StrChunk};
 use crate::types::{Types, AbsType};
 use super::utils::{mk_span, mk_label};
-use super::lexer::{Token, LexicalError};
+use super::lexer::{Token, NormalToken, StringToken, LexicalError};
 use std::collections::HashMap;
 use either::*;
 use codespan::FileId;
@@ -75,7 +75,7 @@ Atom: RichTerm = {
             mk_label(ty, src_id, l, r), t)
         ),
     "Docstring(" <s: Str> "," <t: SpTerm<Term>> ")" => RichTerm::new(Term::Docstring(s, t)),
-    Num => RichTerm::new(Term::Num(<>)),
+    "num literal" => RichTerm::new(Term::Num(<>)),
     Bool => RichTerm::new(Term::Bool(<>)),
     <StrChunks>,
     Ident => RichTerm::new(Term::Var(<>)),
@@ -121,40 +121,49 @@ Pattern: Ident = {
 
 Ident: Ident = "identifier" => Ident(<>.to_string());
 
-Num: f64 = "num literal" => <>;
-
 Bool: bool = {
     "true" => true,
     "false" => false,
 };
 
-StrChunks : RichTerm = "\"" <chunks: StrChunk+> "\"" => {
-    // We transform generic string chunks to a simple string literal if
-    // possible, as this should be a fairly common case, and evaluating a string
-    // as chunks do incur a small overhead.
-    if chunks.len() == 1 {
-        match chunks.into_iter().next().unwrap() {
-            StrChunk::Literal(s) => RichTerm::new(Term::Str(s)),
-            chunk => RichTerm::new(Term::StrChunks(vec![chunk])),
-        }
-    }
-    else {
-        // Chunks are stored in reverse order (see the comment at the definition
-        // of Term::StrChunks).
-        // LALRPOP does not let us declare chunks as mutable, so we move it
-        // first.
-        let mut chunks_mut = chunks;
-        chunks_mut.reverse();
-        RichTerm::new(Term::StrChunks(chunks_mut))
-    }
-};
+StrChunks : RichTerm =
+  "\"" <fst: ChunkLiteral?> <chunks: (ChunkExpr+ChunkLiteral)*> <lasts:
+    ChunkExpr*> "\"" => {
+        let chunks: Vec<StrChunk<RichTerm>> = fst.into_iter()
+            .map(StrChunk::Literal)
+            .chain(chunks.into_iter()
+                .map(|(mut es, s)| {
+                    es.push(StrChunk::Literal(s));
+                    es
+                })
+                .flatten())
+            .chain(lasts.into_iter())
+            .rev()
+            .collect();
 
-StrChunk : StrChunk<RichTerm> = {
-    "str literal" => StrChunk::Literal(<>),
-    "${" <t: SpTerm<RichTerm>> "}" => StrChunk::Expr(t),
-};
+        RichTerm::new(Term::StrChunks(chunks))
+    };
+
+ChunkLiteral: String = 
+    <parts: ChunkLiteralPart+> => {
+        parts.into_iter().fold(String::new(), |mut acc, part| {
+            match part {
+                Either::Left(s) => acc.push_str(s),
+                Either::Right(c) => acc.push(c),
+            };
+
+            acc
+        })
+    };
+
+ChunkExpr: StrChunk<RichTerm> = "${" <t: SpTerm<RichTerm>> "}" => StrChunk::Expr(t);
 
-Str: String = "\"" <s: "str literal"> "\"" => s;
+Str: String = "\"" <s: ChunkLiteral> "\"" => s;
+
+ChunkLiteralPart: Either<&'input str, char> = {
+    "str literal" => Either::Left(<>),
+    "escaped char" => Either::Right(<>),
+};
 
 UOp: UnaryOp<RichTerm> = {
     "isZero" => UnaryOp::IsZero(),
@@ -226,17 +235,12 @@ Arrows: Types = {
 };
 
 BaseType: Types = {
-    "type" => {
-        match <> {
-            "Dyn" => Types(AbsType::Dyn()),
-            "Num" => Types(AbsType::Num()),
-            "Bool" => Types(AbsType::Bool()),
-            "Str" => Types(AbsType::Str()),
-            "List" => Types(AbsType::List()),
-            _ => panic!()
-        }
-    }
-}
+    "Dyn" => Types(AbsType::Dyn()),
+    "Num" => Types(AbsType::Num()),
+    "Bool" => Types(AbsType::Bool()),
+    "Str" => Types(AbsType::Str()),
+    "List" => Types(AbsType::List()),
+};
 
 subType : Types = {
     <BaseType>,
@@ -291,88 +295,94 @@ extern {
     type Error = LexicalError;
 
     enum Token<'input> {
-        "identifier" => Token::Identifier(<&'input str>),
-        "operator" => Token::BinaryOp(<&'input str>),
-        "type" => Token::Type(<&'input str>),
-        "str literal" => Token::StrLiteral(<String>),
-        "num literal" => Token::NumLiteral(<f64>),
-
-        "if" => Token::If,
-        "then" => Token::Then,
-        "else" => Token::Else,
-        "forall" => Token::Forall,
-        "in" => Token::In,
-        "let" => Token::Let,
-        "switch" => Token::Switch,
-
-        "true" => Token::True,
-        "false" => Token::False,
-
-        "," => Token::Comma,
-        ":" => Token::Colon,
-        "$" => Token::Dollar,
-        "=" => Token::Equals,
-        ";" => Token::SemiCol,
-        "." => Token::Dot,
-        ".$" => Token::DotDollar,
-        "$[" => Token::DollarBracket,
-        "${" => Token::DollarBrace,
-        "-$" => Token::MinusDollar,
-        "$=" => Token::DollarEquals,
-        "fun" => Token::Fun,
-        "import" => Token::Import,
-        "|" => Token::Pipe,
-        "->" => Token::SimpleArrow,
-        "=>" => Token::DoubleArrow,
-        "#" => Token::Hash,
-        "`" => Token::Backtick,
-        "_" => Token::Underscore,
-        "\"" => Token::DoubleQuote,
-
-        "tag" => Token::Tag,
-        "Assume(" => Token::Assume,
-        "Promise(" => Token::Promise,
-        "Default(" => Token::Deflt,
-        "Contract(" => Token::Contract,
-        "ContractDefault(" => Token::ContractDeflt,
-        "Docstring(" => Token::Docstring,
-
-        "isZero" => Token::IsZero,
-        "isNum" => Token::IsNum,
-        "isBool" => Token::IsBool,
-        "isStr" => Token::IsStr,
-        "isFun" => Token::IsFun,
-        "isList" => Token::IsList,
-        "isRecord" => Token::IsRecord,
-        "blame" => Token::Blame,
-        "chngPol" => Token::ChangePol,
-        "polarity" => Token::Polarity,
-        "goDom" => Token::GoDom,
-        "goCodom" => Token::GoCodom,
-        "goField" => Token::GoField,
-        "wrap" => Token::Wrap,
-        "unwrap" => Token::Unwrap,
-        "embed" => Token::Embed,
-        "mapRec" => Token::MapRec,
-        "seq" => Token::Seq,
-        "deepSeq" => Token::DeepSeq,
-        "head" => Token::Head,
-        "tail" => Token::Tail,
-        "length" => Token::Length,
-        "fieldsOf" => Token::FieldsOf,
-
-        "hasField" => Token::HasField,
-        "map" => Token::Map,
-        "elemAt" => Token::ElemAt,
-        "merge" => Token::Merge,
-
-        "{" => Token::LBrace,
-        "}" => Token::RBrace,
-        "[" => Token::LBracket,
-        "]" => Token::RBracket,
-        "(" => Token::LParen,
-        ")" => Token::RParen,
-        "<" => Token::LAngleBracket,
-        ">" => Token::RAngleBracket,
+        "identifier" => Token::Normal(NormalToken::Identifier(<&'input str>)),
+        "operator" => Token::Normal(NormalToken::BinaryOp(<&'input str>)),
+        "str literal" => Token::Str(StringToken::Literal(<&'input str>)),
+        "escaped char" => Token::Str(StringToken::EscapedChar(<char>)),
+        "num literal" => Token::Normal(NormalToken::NumLiteral(<f64>)),
+
+        "if" => Token::Normal(NormalToken::If),
+        "then" => Token::Normal(NormalToken::Then),
+        "else" => Token::Normal(NormalToken::Else),
+        "forall" => Token::Normal(NormalToken::Forall),
+        "in" => Token::Normal(NormalToken::In),
+        "let" => Token::Normal(NormalToken::Let),
+        "switch" => Token::Normal(NormalToken::Switch),
+
+        "true" => Token::Normal(NormalToken::True),
+        "false" => Token::Normal(NormalToken::False),
+
+        "," => Token::Normal(NormalToken::Comma),
+        ":" => Token::Normal(NormalToken::Colon),
+        "$" => Token::Normal(NormalToken::Dollar),
+        "=" => Token::Normal(NormalToken::Equals),
+        ";" => Token::Normal(NormalToken::SemiCol),
+        "." => Token::Normal(NormalToken::Dot),
+        ".$" => Token::Normal(NormalToken::DotDollar),
+        "$[" => Token::Normal(NormalToken::DollarBracket),
+        "${" => Token::Str(StringToken::DollarBrace),
+        "-$" => Token::Normal(NormalToken::MinusDollar),
+        "$=" => Token::Normal(NormalToken::DollarEquals),
+        "fun" => Token::Normal(NormalToken::Fun),
+        "import" => Token::Normal(NormalToken::Import),
+        "|" => Token::Normal(NormalToken::Pipe),
+        "->" => Token::Normal(NormalToken::SimpleArrow),
+        "=>" => Token::Normal(NormalToken::DoubleArrow),
+        "#" => Token::Normal(NormalToken::Hash),
+        "`" => Token::Normal(NormalToken::Backtick),
+        "_" => Token::Normal(NormalToken::Underscore),
+        "\"" => Token::Normal(NormalToken::DoubleQuote),
+
+        "Num" => Token::Normal(NormalToken::Num),
+        "Dyn" => Token::Normal(NormalToken::Dyn),
+        "Str" => Token::Normal(NormalToken::Str),
+        "Bool" => Token::Normal(NormalToken::Bool),
+        "List" => Token::Normal(NormalToken::List),
+
+        "tag" => Token::Normal(NormalToken::Tag),
+        "Assume(" => Token::Normal(NormalToken::Assume),
+        "Promise(" => Token::Normal(NormalToken::Promise),
+        "Default(" => Token::Normal(NormalToken::Deflt),
+        "Contract(" => Token::Normal(NormalToken::Contract),
+        "ContractDefault(" => Token::Normal(NormalToken::ContractDeflt),
+        "Docstring(" => Token::Normal(NormalToken::Docstring),
+
+        "isZero" => Token::Normal(NormalToken::IsZero),
+        "isNum" => Token::Normal(NormalToken::IsNum),
+        "isBool" => Token::Normal(NormalToken::IsBool),
+        "isStr" => Token::Normal(NormalToken::IsStr),
+        "isFun" => Token::Normal(NormalToken::IsFun),
+        "isList" => Token::Normal(NormalToken::IsList),
+        "isRecord" => Token::Normal(NormalToken::IsRecord),
+        "blame" => Token::Normal(NormalToken::Blame),
+        "chngPol" => Token::Normal(NormalToken::ChangePol),
+        "polarity" => Token::Normal(NormalToken::Polarity),
+        "goDom" => Token::Normal(NormalToken::GoDom),
+        "goCodom" => Token::Normal(NormalToken::GoCodom),
+        "goField" => Token::Normal(NormalToken::GoField),
+        "wrap" => Token::Normal(NormalToken::Wrap),
+        "unwrap" => Token::Normal(NormalToken::Unwrap),
+        "embed" => Token::Normal(NormalToken::Embed),
+        "mapRec" => Token::Normal(NormalToken::MapRec),
+        "seq" => Token::Normal(NormalToken::Seq),
+        "deepSeq" => Token::Normal(NormalToken::DeepSeq),
+        "head" => Token::Normal(NormalToken::Head),
+        "tail" => Token::Normal(NormalToken::Tail),
+        "length" => Token::Normal(NormalToken::Length),
+        "fieldsOf" => Token::Normal(NormalToken::FieldsOf),
+
+        "hasField" => Token::Normal(NormalToken::HasField),
+        "map" => Token::Normal(NormalToken::Map),
+        "elemAt" => Token::Normal(NormalToken::ElemAt),
+        "merge" => Token::Normal(NormalToken::Merge),
+
+        "{" => Token::Normal(NormalToken::LBrace),
+        "}" => Token::Normal(NormalToken::RBrace),
+        "[" => Token::Normal(NormalToken::LBracket),
+        "]" => Token::Normal(NormalToken::RBracket),
+        "(" => Token::Normal(NormalToken::LParen),
+        ")" => Token::Normal(NormalToken::RParen),
+        "<" => Token::Normal(NormalToken::LAngleBracket),
+        ">" => Token::Normal(NormalToken::RAngleBracket),
     }
 }
diff --git a/src/parser/lexer.rs b/src/parser/lexer.rs
index d6aaad66..3494e7ae 100644
--- a/src/parser/lexer.rs
+++ b/src/parser/lexer.rs
@@ -1,7 +1,9 @@
 //! The lexer, transforming an input string to a stream of tokens.
 //!
-//! A custom lexer is implemented in order to support arbitrary interpolated expressions, which is
-//! not possible using LALRPOP's generated lexer. To see why, consider the following string:
+//! A modal lexer is implemented on top of two standard
+//! [logos](https://github.com/maciejhirsz/logos) lexers in order to support arbitrary interpolated
+//! expressions, which is not possible using LALRPOP's generated lexer. To see why, consider the
+//! following string:
 //!
 //! ```
 //! "hello, I have 1 + ${ {a = "40"}.a } + 1 bananas."
@@ -9,678 +11,399 @@
 //!
 //! Once the `${` token is encountered, the lexer has to switch back to lexing expressions as
 //! usual. But at the end of the interpolated expression, `+ 1 bananas.` needs to be parsed as a
-//! string again, and not as program tokens. Since the interpolated expression is arbitrary, it can
-//! contains nested `{` and `}` (as here, with records) and strings which themselves have
+//! string again, and not as normal program tokens. Since the interpolated expression is arbitrary,
+//! it can contains nested `{` and `}` (as here, with records) and strings which themselves have
 //! interpolated expression, and so on.
 //!
-//! This is typically not lexable using only regular expressions. To handle this, the lexer
-//! maintains the following state:
-//!  - mode: a current mode, which can be either `Normal`, `Str` or `DollarBrace` (the latter being
-//!    a less important transitional mode, see the comments in [`str_literal`]()'s code).
-//!  - mode stack: a stack to save and restore modes.
+//! This is typically not lexable using only regular expressions. To handle this, we use a *modal*
+//! lexer. As hinted by the name, a modal lexer have several modes in which the same tokens can be
+//! parsed differently. Ours can be in *normal* mode or in *string* mode.
 //!
-//!  The two following operations are performed on the state:
-//!  - push-update: save the current mode on the stack, and switch to a new one.
-//!  - pop: restore the previous mode from the stack.
+//! It also maintains a stack of brace counters, required inside an interpolated expression to
+//! decide if a closing brace `}` belongs to the expression or is actually the closing brace of the
+//! interpolated expression, indicating that we should switch back to string mode.
 //!
-//! When entering a string, the `Str` mode is pushed. When a `${` is encountered in a string,
+//! When entering a string, the `Str` mode is entered. When a `${` is encountered in a string,
 //! starting an interpolated expression, the normal mode is pushed. At each starting `{` in normal
-//! mode, the normal mode is also pushed. At each closing '}', the previous mode is popped.
-//!
-//! When parsing an interpolated expression, the closing `}` (if any) matching the starting `${`
-//! will pop the `Str` mode from the stack. Then, the lexer knows that it should not try to lex the
-//! next tokens as normal Nickel expressions, but rather as a string.
-use std::fmt;
-use std::str::CharIndices;
-
-/// A token generated by the lexer.
-#[derive(Clone, PartialEq, Debug)]
-pub enum Token<'input> {
-    /// An identifier.
+//! mode, the brace counter is incremented. At each closing '}', it is decremented. When it reaches
+//! `0`, this is the end of the current interpolated expressions, and we leave the normal mode and
+//! go back to string mode. In our example, this is the second `}`: at this point, the lexer knows
+//! that the coming characters must be lexed as string tokens, and not as normal tokens.
+use logos::Logos;
+
+/// The tokens in normal mode.
+#[derive(Logos, Debug, PartialEq, Clone)]
+pub enum NormalToken<'input> {
+    #[regex("[ \r\t\n]+", logos::skip)]
+    #[error]
+    Error,
+
+    #[regex("_?[a-zA-Z][_a-zA-Z0-9]*")]
     Identifier(&'input str),
-    /// A binary operator.
+    #[regex("-?[0-9]*\\.?[0-9]+", |lex| lex.slice().parse())]
+    NumLiteral(f64),
+    #[regex("[+@=\\-<>\\.|#]+")]
     BinaryOp(&'input str),
-    /// A base type (Num, Str, etc.).
-    Type(&'input str),
 
-    /// A string literal (which does not contain interpolated expressions).
-    StrLiteral(String),
-    /// A number.
-    NumLiteral(f64),
+    #[token("Dyn")]
+    Dyn,
+    #[token("Num")]
+    Num,
+    #[token("Bool")]
+    Bool,
+    #[token("Str")]
+    Str,
+    #[token("List")]
+    List,
 
+    #[token("if")]
     If,
+    #[token("then")]
     Then,
+    #[token("else")]
     Else,
+    #[token("forall")]
     Forall,
+    #[token("in")]
     In,
+    #[token("let")]
     Let,
+    #[token("switch")]
     Switch,
 
+    #[token("true")]
     True,
+    #[token("false")]
     False,
 
+    #[token(",")]
     Comma,
+    #[token(":")]
     Colon,
+    #[token("$")]
     Dollar,
+    #[token("=")]
     Equals,
+    #[token(";")]
     SemiCol,
+    #[token(".")]
     Dot,
+    #[token(".$")]
     DotDollar,
+    #[token("$[")]
     DollarBracket,
+    #[token("$=")]
     DollarEquals,
+    #[token("${")]
     DollarBrace,
+    #[token("\"")]
     DoubleQuote,
+    #[token("-$")]
     MinusDollar,
+
+    #[token("fun")]
     Fun,
+    #[token("import")]
     Import,
+    #[token("|")]
     Pipe,
+    #[token("->")]
     SimpleArrow,
+    #[token("=>")]
     DoubleArrow,
+    #[token("#")]
     Hash,
+    #[token("`")]
     Backtick,
+    #[token("_")]
     Underscore,
 
+    #[token("tag")]
     Tag,
+    #[token("Assume(")]
     Assume,
+    #[token("Promise(")]
     Promise,
+    #[token("Default(")]
     Deflt,
+    #[token("Contract(")]
     Contract,
+    #[token("ContractDefault(")]
     ContractDeflt,
+    #[token("Docstring(")]
     Docstring,
 
+    #[token("isZero")]
     IsZero,
+    #[token("isNum")]
     IsNum,
+    #[token("isBool")]
     IsBool,
+    #[token("isStr")]
     IsStr,
+    #[token("isFun")]
     IsFun,
+    #[token("isList")]
     IsList,
+    #[token("isRecord")]
     IsRecord,
+
+    #[token("blame")]
     Blame,
+    #[token("chngPol")]
     ChangePol,
+    #[token("polarity")]
     Polarity,
+    #[token("goDom")]
     GoDom,
+    #[token("goCodom")]
     GoCodom,
+    #[token("goField")]
     GoField,
+
+    #[token("wrap")]
     Wrap,
+    #[token("embed")]
     Embed,
+    #[token("mapRec")]
     MapRec,
+    #[token("seq")]
     Seq,
+    #[token("deepSeq")]
     DeepSeq,
+    #[token("head")]
     Head,
+    #[token("tail")]
     Tail,
+    #[token("length")]
     Length,
+    #[token("fieldsOf")]
     FieldsOf,
 
+    #[token("unwrap")]
     Unwrap,
+    #[token("hasField")]
     HasField,
+    #[token("map")]
     Map,
+    #[token("elemAt")]
     ElemAt,
+    #[token("merge")]
     Merge,
 
+    #[token("{")]
     LBrace,
+    #[token("}")]
     RBrace,
+    #[token("[")]
     LBracket,
+    #[token("]")]
     RBracket,
+    #[token("(")]
     LParen,
+    #[token(")")]
     RParen,
+    #[token("<")]
     LAngleBracket,
+    #[token(">")]
     RAngleBracket,
 }
 
-/// The lexer mode.
-///
-/// See the general module description for more details.
-#[derive(Clone, Copy, PartialEq, Debug)]
-pub enum Mode {
-    Normal,
-    Str,
-    DollarBrace(usize),
-}
+/// The tokens in string mode.
+#[derive(Logos, Debug, PartialEq, Clone)]
+pub enum StringToken<'input> {
+    #[error]
+    Error,
 
-/// Lexing error.
-#[derive(Clone, PartialEq, Debug)]
-pub enum LexicalError {
-    /// A closing brace '}' does not match an opening brace '{'.
-    UnmatchedCloseBrace(usize),
-    /// A character does not match the beginning of any token.
-    UnexpectedChar(usize),
-    /// An alphanumeric character directly follows a number literal.
-    NumThenIdent(usize),
-    /// Invalid escape sequence in a string literal.
-    InvalidEscapeSequence(usize),
-    /// Unexpected end of input.
-    UnexpectedEOF(Vec<String>),
-}
-
-/// User for error reporting.
-impl<'input> fmt::Display for Token<'input> {
-    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        let repr = match self {
-            Token::Identifier(s) | Token::BinaryOp(s) | Token::Type(s) => {
-                return write!(f, "{}", s)
-            }
-            Token::StrLiteral(s) => return write!(f, "{}", s),
-            Token::NumLiteral(n) => return write!(f, "{}", n),
-
-            Token::If => "if",
-            Token::Then => "then",
-            Token::Else => "else",
-            Token::Forall => "forall",
-            Token::In => "in",
-            Token::Let => "let",
-            Token::Switch => "switch",
-
-            Token::True => "true",
-            Token::False => "false",
-
-            Token::Comma => ",",
-            Token::Colon => ":",
-            Token::Dollar => "$",
-            Token::Equals => "=",
-            Token::SemiCol => ";",
-            Token::Dot => ".",
-            Token::DotDollar => ".$",
-            Token::DollarBracket => "$[",
-            Token::DollarBrace => "${",
-            Token::MinusDollar => "-$",
-            Token::DollarEquals => "$=",
-            Token::Fun => "fun",
-            Token::Import => "import",
-            Token::Pipe => "|",
-            Token::SimpleArrow => "->",
-            Token::DoubleArrow => "=>",
-            Token::Hash => "#",
-            Token::Backtick => "`",
-            Token::Underscore => "_",
-            Token::DoubleQuote => "\"",
-
-            Token::Tag => "tag",
-            Token::Assume => "Assume(",
-            Token::Promise => "Promise(",
-            Token::Deflt => "Default(",
-            Token::Contract => "Contract(",
-            Token::ContractDeflt => "ContractDefault(",
-            Token::Docstring => "Docstring(",
-
-            Token::IsZero => "isZero",
-            Token::IsNum => "isNum",
-            Token::IsBool => "isBool",
-            Token::IsStr => "isStr",
-            Token::IsFun => "isFun",
-            Token::IsList => "isList",
-            Token::IsRecord => "isRecord",
-            Token::Blame => "blame",
-            Token::ChangePol => "chngPol",
-            Token::Polarity => "polarity",
-            Token::GoDom => "goDom",
-            Token::GoCodom => "goCodom",
-            Token::GoField => "goField",
-            Token::Wrap => "wrap",
-            Token::Unwrap => "unwrap",
-            Token::Embed => "embed",
-            Token::MapRec => "mapRec",
-            Token::Seq => "seq",
-            Token::DeepSeq => "deepSeq",
-            Token::Head => "head",
-            Token::Tail => "tail",
-            Token::Length => "length",
-            Token::FieldsOf => "fieldsOf",
-
-            Token::HasField => "hasField",
-            Token::Map => "map",
-            Token::ElemAt => "elemAt",
-            Token::Merge => "merge",
-
-            Token::LBrace => "{",
-            Token::RBrace => "}",
-            Token::LBracket => "[",
-            Token::RBracket => "]",
-            Token::LParen => "(",
-            Token::RParen => ")",
-            Token::LAngleBracket => "<",
-            Token::RAngleBracket => ">",
-        };
-        write!(f, "{}", repr)
-    }
-}
+    #[regex("[^\"$\\\\]+")]
+    Literal(&'input str),
 
-/// The lexer state.
-///
-/// It maintains one character look-ahead, which is currently sufficient to decide tokens without
-/// ambiguity.
-pub struct Lexer<'input> {
-    input: &'input str,
-    chars: CharIndices<'input>,
-    look_ahead: Option<(usize, char)>,
-    mode_stack: Vec<Mode>,
-    mode: Mode,
-}
-
-impl<'input> Lexer<'input> {
-    pub fn new(input: &'input str) -> Self {
-        let mut chars = input.char_indices();
-        let look_ahead = chars.next();
-        Lexer {
-            input,
-            chars,
-            look_ahead,
-            mode_stack: Vec::new(),
-            mode: Mode::Normal,
-        }
-    }
-}
-
-pub type Spanned<'input> = (usize, Token<'input>, usize);
-
-fn is_ident_start(chr: char, look_ahead: Option<char>) -> bool {
-    match chr {
-        'a'..='z' | 'A'..='Z' => true,
-        '_' => look_ahead.map(is_ident_char).unwrap_or(false),
-        _ => false,
-    }
+    #[token("\"")]
+    DoubleQuote,
+    #[token("${")]
+    DollarBrace,
+    #[regex("\\\\.", |lex| lex.slice().chars().nth(1))]
+    EscapedChar(char),
 }
 
-fn is_ident_char(chr: char) -> bool {
-    match chr {
-        '0'..='9' | '_' => true,
-        chr => is_ident_start(chr, None),
-    }
+/// The tokens of the modal lexer.
+#[derive(Debug, PartialEq, Clone)]
+pub enum Token<'input> {
+    Normal(NormalToken<'input>),
+    Str(StringToken<'input>),
 }
 
-fn is_op_char(chr: char) -> bool {
-    match chr {
-        '+' | '@' | '=' | '-' | '<' | '>' | '.' | '|' | '#' => true,
-        _ => false,
-    }
+pub enum ModalLexer<'input> {
+    Normal(logos::Lexer<'input, NormalToken<'input>>),
+    Str(logos::Lexer<'input, StringToken<'input>>),
 }
 
-fn is_whitespace(chr: char) -> bool {
-    match chr {
-        '\t' | '\n' | '\r' | ' ' => true,
-        _ => false,
-    }
-}
+// Wrap the `next()` function of the underlying lexer.
+impl<'input> Iterator for ModalLexer<'input> {
+    type Item = Token<'input>;
 
-// Digit can start with a heading '-'
-fn is_num_start(chr: char, look_ahead: Option<char>) -> bool {
-    match chr {
-        '-' => look_ahead.map(is_digit).unwrap_or(false),
-        chr => is_digit(chr),
+    fn next(&mut self) -> Option<Self::Item> {
+        match self {
+            ModalLexer::Normal(lexer) => lexer.next().map(Token::Normal),
+            ModalLexer::Str(lexer) => lexer.next().map(Token::Str),
+        }
     }
 }
 
-fn is_digit(chr: char) -> bool {
-    match chr {
-        '0'..='9' => true,
-        _ => false,
+// Wrap the `span()` function of the underlying lexer.
+impl<'input> ModalLexer<'input> {
+    pub fn span(&self) -> std::ops::Range<usize> {
+        match self {
+            ModalLexer::Normal(lexer) => lexer.span(),
+            ModalLexer::Str(lexer) => lexer.span(),
+        }
     }
 }
 
-fn escape_char(chr: char) -> Option<char> {
-    match chr {
-        '\'' => Some('\''),
-        '"' => Some('"'),
-        '\\' => Some('\\'),
-        '$' => Some('$'),
-        'n' => Some('\n'),
-        'r' => Some('\r'),
-        't' => Some('\t'),
-        _ => None,
-    }
+#[derive(Clone, PartialEq, Debug)]
+pub enum LexicalError {
+    /// A closing brace '}' does not match an opening brace '{'.
+    UnmatchedCloseBrace(usize),
+    /// Invalid escape sequence in a string literal.
+    InvalidEscapeSequence(usize),
+    /// Generic lexer error
+    Generic(usize, usize),
 }
 
-impl<'input> Iterator for Lexer<'input> {
-    type Item = Result<Spanned<'input>, LexicalError>;
-
-    /// Return the next token of the input.
-    fn next(&mut self) -> Option<Self::Item> {
-        // This is a special case to avoid two characters look-ahead for dollar brace. See the
-        // comments in str_literal()
-        if let Mode::DollarBrace(index) = self.mode {
-            assert!(self.pop_mode());
-            self.push_mode(Mode::Normal);
-            return Some(Ok((index, Token::DollarBrace, index + 2)));
-        }
-
-        // If we land here in Str mode, this means either:
-        // 1. The previous token is a string literal, and the next to come is the closing double
-        //    quote.
-        // 2. Or We started lexing a string literal, encountered a '${', lexed the interpolated
-        //    expression inside, and the previous token was the closing '}' which popped the Str
-        //    mode back from the stack.
-        // We peek one character to see if it is a closing double quote.
-        // If not, we call str_literal before actually consuming any character.
-        if self.mode == Mode::Str {
-            return match self.look_ahead {
-                Some((index, '"')) => {
-                    self.consume();
-                    assert!(self.pop_mode());
-                    Some(Ok((index, Token::DoubleQuote, index + 1)))
-                }
-                Some((index, _)) => Some(self.str_literal(index)),
-                None => None,
-            };
-        }
-
-        while let Some((index, chr)) = self.consume() {
-            let token = match chr {
-                ',' => Ok((index, Token::Comma, index + 1)),
-                ':' => Ok((index, Token::Colon, index + 1)),
-                ';' => Ok((index, Token::SemiCol, index + 1)),
-                '$' => match self.look_ahead {
-                    Some((_, '=')) => {
-                        self.consume();
-                        Ok((index, Token::DollarEquals, index + 2))
-                    }
-                    Some((_, '[')) => {
-                        self.consume();
-                        Ok((index, Token::DollarBracket, index + 2))
-                    }
-                    Some((_, '{')) => {
-                        self.consume();
-                        Ok((index, Token::DollarBrace, index + 2))
-                    }
-                    _ => Ok((index, Token::Dollar, index + 1)),
-                },
-                '{' => {
-                    self.push_mode(Mode::Normal);
-                    Ok((index, Token::LBrace, index + 1))
-                }
-                '}' => {
-                    if !self.pop_mode() {
-                        Err(LexicalError::UnmatchedCloseBrace(index))
-                    } else {
-                        Ok((index, Token::RBrace, index + 1))
-                    }
-                }
-                '[' => Ok((index, Token::LBracket, index + 1)),
-                ']' => Ok((index, Token::RBracket, index + 1)),
-                '(' => Ok((index, Token::LParen, index + 1)),
-                ')' => Ok((index, Token::RParen, index + 1)),
-                '#' => Ok((index, Token::Hash, index + 1)),
-                '`' => Ok((index, Token::Backtick, index + 1)),
-                '"' => {
-                    self.push_mode(Mode::Str);
-                    Ok((index, Token::DoubleQuote, index + 1))
-                }
-                chr if is_ident_start(chr, self.look_ahead.map(|(_, chr)| chr)) => {
-                    self.identifier(index)
-                }
-                '_' => Ok((index, Token::Underscore, index + 1)),
-                chr if is_num_start(chr, self.look_ahead.map(|(_, chr)| chr)) => {
-                    self.num_literal(index)
-                }
-                chr if is_op_char(chr) => self.operator(index),
-                // Ignore whitespaces
-                chr if is_whitespace(chr) => continue,
-                _ => Err(LexicalError::UnexpectedChar(index)),
-            };
-
-            return Some(token);
-        }
-
-        None
-    }
+pub struct Lexer<'input> {
+    // We are forced to use an `Option` in order to be able to switch mode without cloning the
+    // underlying lexer. Logos offers a `morph()` function for a in-place conversion between
+    // lexers, that we want to use to transform a normal mode lexer to a string mode lexer. But
+    // Rust's borrowing system won't let us take ownership of the underlying lexer without
+    // replacing it first by something else, whence the `Option`. `lexer` should never be none
+    // excepted in an non observable intermediate state during mode switching.
+    /// The modal lexer.
+    pub lexer: Option<ModalLexer<'input>>,
+    /// The current brace counter used to determine if a closing brace is the end of an
+    /// interpolated expression.
+    ///
+    /// This is always `0` in string mode.
+    pub brace_count: usize,
+    /// The stack of brace counters.
+    ///
+    /// As interpolated strings can be nested, we can start to lex a new string while we were
+    /// already inside an interpolated expression. In this case, once this string ends, we must
+    /// restore the original brace counter, which is what this stack is used for.
+    pub brace_stack: Vec<usize>,
 }
 
 impl<'input> Lexer<'input> {
-    /// Save the current mode on the stack, and then set it the `mode`.
-    fn push_mode(&mut self, mode: Mode) {
-        self.mode_stack.push(self.mode);
-        self.mode = mode;
-    }
-
-    /// Restore the previous mode from the stack. Return false if the stack was empty.
-    fn pop_mode(&mut self) -> bool {
-        if let Some(mode) = self.mode_stack.pop() {
-            self.mode = mode;
-            true
-        } else {
-            self.mode = Mode::Normal;
-            false
+    pub fn new(s: &'input str) -> Self {
+        Lexer {
+            lexer: Some(ModalLexer::Normal(NormalToken::lexer(s))),
+            brace_stack: Vec::new(),
+            brace_count: 0,
         }
     }
 
-    /// Take the next character from the stream.
-    fn consume(&mut self) -> Option<(usize, char)> {
-        std::mem::replace(&mut self.look_ahead, self.chars.next())
-    }
-
-    /// Check if the next character is equal to the given parameter without consuming.
-    fn look_ahead_is(&self, chr: char) -> bool {
-        match self.look_ahead {
-            Some((_, next)) if next == chr => true,
-            _ => false,
+    fn enter_str(&mut self) {
+        match self.lexer.take() {
+            Some(ModalLexer::Normal(lexer)) => {
+                self.brace_stack.push(self.brace_count);
+                self.brace_count = 0;
+                self.lexer.replace(ModalLexer::Str(lexer.morph()));
+            }
+            _ => panic!("lexer::enter_str"),
         }
     }
 
-    /// Consume the coming characters while they satisfy some predicate. Return the
-    /// position of the first character which does not satisfy `pred`, together with a slice of the
-    /// input starting at `start` until this character (excluded).
-    ///
-    /// # Example
-    /// In the following situation:
-    ///
-    /// ```
-    /// 1234.456 ab
-    /// ^    ^  ^
-    /// s    c  end
-    /// ```
-    ///
-    /// where `c` is the current position in the stream, then
-    /// `self.take_while(s, is_digit)` returns `(end, "1234.456")` and set the current position of
-    /// the stream to `end`.
-    fn take_while<F>(&mut self, start: usize, pred: F) -> (usize, &'input str)
-    where
-        F: Fn(char) -> bool,
-    {
-        let mut end = start;
-
-        while let Some((index, chr)) = self.look_ahead {
-            end = index;
-
-            if pred(chr) {
-                self.consume();
-            } else {
-                return (index, &self.input[start..index]);
+    fn enter_normal(&mut self) {
+        match self.lexer.take() {
+            Some(ModalLexer::Str(lexer)) => {
+                //brace_count must be zero, and we do not push it on the stack
+                self.lexer.replace(ModalLexer::Normal(lexer.morph()));
             }
+            _ => panic!("lexer::enter_normal"),
         }
-
-        end += 1;
-        (end, &self.input[start..end])
     }
 
-    /// Try to lex the next token as an identifier.
-    ///
-    /// If the identifier matches a reserved keyword, the associated token is returned instead.
-    pub fn identifier(&mut self, start: usize) -> Result<Spanned<'input>, LexicalError> {
-        let (mut end, slice) = self.take_while(start, is_ident_char);
-
-        // Reserved keywords are just special identifiers.
-        let is_next_lparen = self.look_ahead_is('(');
-        let token = match slice {
-            "if" => Token::If,
-            "then" => Token::Then,
-            "else" => Token::Else,
-            "forall" => Token::Forall,
-            "in" => Token::In,
-            "let" => Token::Let,
-            "switch" => Token::Switch,
-            "tag" => Token::Tag,
-            "fun" => Token::Fun,
-            "import" => Token::Import,
-            "true" => Token::True,
-            "false" => Token::False,
-            "Assume" if is_next_lparen => {
-                self.consume();
-                end += 1;
-                Token::Assume
-            }
-            "Promise" if is_next_lparen => {
-                self.consume();
-                end += 1;
-                Token::Promise
-            }
-            "Default" if is_next_lparen => {
-                self.consume();
-                end += 1;
-                Token::Deflt
+    fn leave_str(&mut self) {
+        match self.lexer.take() {
+            Some(ModalLexer::Str(lexer)) => {
+                // We can only enter string mode from normal mode, so the brace stack should not be
+                // empty
+                self.brace_count = self.brace_stack.pop().unwrap();
+                self.lexer.replace(ModalLexer::Normal(lexer.morph()));
             }
-            "Contract" if is_next_lparen => {
-                self.consume();
-                end += 1;
-                Token::Contract
-            }
-            "ContractDefault" if is_next_lparen => {
-                self.consume();
-                end += 1;
-                Token::ContractDeflt
-            }
-            "Docstring" if is_next_lparen => {
-                self.consume();
-                end += 1;
-                Token::Docstring
-            }
-            "isZero" => Token::IsZero,
-            "isNum" => Token::IsNum,
-            "isBool" => Token::IsBool,
-            "isStr" => Token::IsStr,
-            "isFun" => Token::IsFun,
-            "isList" => Token::IsList,
-            "isRecord" => Token::IsRecord,
-            "blame" => Token::Blame,
-            "chngPol" => Token::ChangePol,
-            "polarity" => Token::Polarity,
-            "goDom" => Token::GoDom,
-            "goCodom" => Token::GoCodom,
-            "goField" => Token::GoField,
-            "wrap" => Token::Wrap,
-            "embed" => Token::Embed,
-            "mapRec" => Token::MapRec,
-            "seq" => Token::Seq,
-            "deepSeq" => Token::DeepSeq,
-            "head" => Token::Head,
-            "tail" => Token::Tail,
-            "length" => Token::Length,
-            "unwrap" => Token::Unwrap,
-            "hasField" => Token::HasField,
-            "map" => Token::Map,
-            "elemAt" => Token::ElemAt,
-            "merge" => Token::Merge,
-            "fieldsOf" => Token::FieldsOf,
-            ty @ "Dyn" | ty @ "Num" | ty @ "Bool" | ty @ "Str" | ty @ "List" => Token::Type(ty),
-            id => Token::Identifier(id),
-        };
-
-        Ok((start, token, end))
+            _ => panic!("lexer::leave_str"),
+        }
     }
 
-    /// Try to lex the next token as a number literal.
-    pub fn num_literal(&mut self, start: usize) -> Result<Spanned<'input>, LexicalError> {
-        let (end, num) = self.take_while(start, is_digit);
-
-        // Take the fractional part into account, if there is one
-        let (end, num) = match self.look_ahead {
-            Some((_, '.')) => {
-                self.consume();
-                self.take_while(start, is_digit)
+    fn leave_normal(&mut self) {
+        match self.lexer.take() {
+            Some(ModalLexer::Normal(lexer)) => {
+                // brace_count must be 0
+                self.lexer.replace(ModalLexer::Str(lexer.morph()));
             }
-            _ => (end, num),
-        };
-
-        match self.look_ahead {
-            // Number literals must not be followed directly by an identifier character
-            Some((index, chr)) if is_ident_char(chr) => Err(LexicalError::NumThenIdent(index)),
-            _ => Ok((start, Token::NumLiteral(num.parse().unwrap()), end)),
+            _ => panic!("lexer::leave_normal"),
         }
     }
+}
 
-    /// Try the lex the next token as an operator.
-    ///
-    /// As for identifiers, if the operator correspond to a reserved symbol of the language, the
-    /// associated token is returned instead.
-    pub fn operator(&mut self, start: usize) -> Result<Spanned<'input>, LexicalError> {
-        let (mut end, op) = self.take_while(start, is_op_char);
-
-        let token = match op {
-            "." if self.look_ahead_is('$') => {
-                self.consume();
-                end += 1;
-                Token::DotDollar
-            }
-            "." => Token::Dot,
-            "-" if self.look_ahead_is('$') => {
-                self.consume();
-                end += 1;
-                Token::MinusDollar
-            }
-            "=" => Token::Equals,
-            "->" => Token::SimpleArrow,
-            "=>" => Token::DoubleArrow,
-            "<" => Token::LAngleBracket,
-            ">" => Token::RAngleBracket,
-            "|" => Token::Pipe,
-            op => Token::BinaryOp(op),
-        };
-
-        Ok((start, token, end))
-    }
+impl<'input> Iterator for Lexer<'input> {
+    type Item = Result<(usize, Token<'input>, usize), LexicalError>;
 
-    /// Try to lex the next token as a string literal.
-    pub fn str_literal(&mut self, start: usize) -> Result<Spanned<'input>, LexicalError> {
-        let mut eof = start + 1;
-        let mut acc = String::new();
+    fn next(&mut self) -> Option<Self::Item> {
+        use Token::*;
+
+        let lexer = self.lexer.as_mut().unwrap();
+        let mut token = lexer.next();
+        let span = lexer.span();
+
+        match token.as_ref() {
+            Some(Normal(NormalToken::DoubleQuote)) => self.enter_str(),
+            Some(Normal(NormalToken::LBrace)) => self.brace_count += 1,
+            Some(Normal(NormalToken::RBrace)) => {
+                if self.brace_count == 0 {
+                    if self.brace_stack.is_empty() {
+                        return Some(Err(LexicalError::UnmatchedCloseBrace(span.start)));
+                    }
 
-        loop {
-            if self.look_ahead_is('"') {
-                return Ok((start, Token::StrLiteral(acc), start + 1));
+                    self.leave_normal();
+                } else {
+                    self.brace_count -= 1;
+                }
             }
-
-            if let Some((index, chr)) = self.consume() {
-                eof = index + 1;
-                match chr {
-                    '\\' => {
-                        let (i, c) = self.consume().ok_or(LexicalError::UnexpectedEOF(vec![
-                            String::from("escape sequence"),
-                        ]))?;
-                        acc.push(
-                            escape_char(c).ok_or_else(|| LexicalError::InvalidEscapeSequence(i))?,
-                        );
-                    }
-                    '$' => {
-                        if self.look_ahead_is('{') {
-                            self.consume();
-
-                            // Instead of returning an empty string token, directly return the
-                            // dollar brace.
-                            if acc.is_empty() {
-                                self.push_mode(Mode::Normal);
-                                return Ok((index, Token::DollarBrace, index + 2));
-                            } else {
-                                // This is the only point where we would actually need to look two
-                                // characters ahead, to determine if the coming token is a '${'. We
-                                // can not, and had to consume the '$' of '${' to decide. To avoid
-                                // using a 2 chars look-ahead buffer just for this, we encode this
-                                // special case in Mode. Mode::DollarBrace indicates precisely that
-                                // we were lexing a string literal, and that we encountered and
-                                // consumed a "${", that should be returned without consuming
-                                // anything at the next call to next()
-                                self.push_mode(Mode::DollarBrace(index));
-                                return Ok((start, Token::StrLiteral(acc), index));
-                            }
-                        } else {
-                            acc.push('$');
-                        }
-                    }
-                    chr => acc.push(chr),
+            Some(Str(StringToken::DoubleQuote)) => {
+                self.leave_str();
+                // To make things simpler on the parser side, we only return one variant for
+                // `DoubleQuote`, namely the the normal one.
+                token = Some(Normal(NormalToken::DoubleQuote));
+            }
+            Some(Str(StringToken::DollarBrace)) => self.enter_normal(),
+            // Convert escape sequences to the corresponding character.
+            Some(Str(StringToken::EscapedChar(c))) => {
+                if let Some(esc) = escape_char(*c) {
+                    token = Some(Str(StringToken::EscapedChar(esc)));
+                } else {
+                    return Some(Err(LexicalError::InvalidEscapeSequence(span.start + 1)));
                 }
-            } else {
-                // We could fail here as we reached EOF while lexing a string, meaning the string
-                // is not terminated. However, we prefer to let the parser handle the problem
-                // instead of adding special cases in the lexer, as this is not the only code path
-                // which implies an unterminated string.
-                return Ok((start, Token::StrLiteral(acc), eof));
             }
+            // Early report errors for now. This could change in the future
+            Some(Str(StringToken::Error)) | Some(Normal(NormalToken::Error)) => {
+                return Some(Err(LexicalError::Generic(span.start, span.end)))
+            }
+            _ => (),
         }
+
+        token.map(|t| Ok((span.start, t, span.end)))
+    }
+}
+
+fn escape_char(chr: char) -> Option<char> {
+    match chr {
+        '\'' => Some('\''),
+        '"' => Some('"'),
+        '\\' => Some('\\'),
+        '$' => Some('$'),
+        'n' => Some('\n'),
+        'r' => Some('\r'),
+        't' => Some('\t'),
+        _ => None,
     }
 }


Test patch:
diff --git a/src/parser/tests.rs b/src/parser/tests.rs
index b2ae1713..619c001a 100644
--- a/src/parser/tests.rs
+++ b/src/parser/tests.rs
@@ -1,14 +1,16 @@
-use super::lexer::{Lexer, LexicalError, Token};
+use super::lexer::{Lexer, LexicalError, NormalToken, StringToken, Token};
 use crate::identifier::Ident;
 use crate::term::Term::*;
-use crate::term::{BinaryOp, RichTerm, UnaryOp};
+use crate::term::{BinaryOp, RichTerm, StrChunk, UnaryOp};
 use codespan::Files;
 
 fn parse(s: &str) -> Option<RichTerm> {
     let id = Files::new().add("<test>", String::from(s));
 
+    println!("Parsing {}", s);
     super::grammar::TermParser::new()
         .parse(id, Lexer::new(&s))
+        .map_err(|err| println!("{:?}", err))
         .ok()
 }
 
@@ -26,6 +28,11 @@ fn lex_without_pos(s: &str) -> Result<Vec<Token>, LexicalError> {
     lex(s).map(|v| v.into_iter().map(|(_, tok, _)| tok).collect())
 }
 
+/// Wrap a single string literal in a `StrChunks`.
+fn mk_single_chunk(s: &str) -> RichTerm {
+    StrChunks(vec![StrChunk::Literal(String::from(s))]).into()
+}
+
 #[test]
 fn numbers() {
     assert_eq!(parse_without_pos("22"), Num(22.0).into());
@@ -39,26 +46,26 @@ fn numbers() {
 fn strings() {
     assert_eq!(
         parse_without_pos("\"hello world\""),
-        Str("hello world".to_string()).into()
+        mk_single_chunk("hello world"),
     );
     assert_eq!(
         parse_without_pos("\"hello \nworld\""),
-        Str("hello \nworld".to_string()).into()
+        mk_single_chunk("hello \nworld")
     );
     assert_eq!(
         parse_without_pos("\"hello Dimension C-132!\""),
-        Str("hello Dimension C-132!".to_string()).into()
+        mk_single_chunk("hello Dimension C-132!")
     );
 
     assert_eq!(
         parse_without_pos("\"hello\" ++ \"World\" ++ \"!!\" "),
         Op2(
             BinaryOp::PlusStr(),
-            Str("hello".to_string()).into(),
+            mk_single_chunk("hello"),
             Op2(
                 BinaryOp::PlusStr(),
-                Str("World".to_string()).into(),
-                Str("!!".to_string()).into()
+                mk_single_chunk("World"),
+                mk_single_chunk("!!")
             )
             .into()
         )
@@ -231,51 +238,55 @@ fn string_lexing() {
     assert_eq!(
         lex_without_pos("\"Good\" \"strings\""),
         Ok(vec![
-            Token::DoubleQuote,
-            Token::StrLiteral(String::from("Good")),
-            Token::DoubleQuote,
-            Token::DoubleQuote,
-            Token::StrLiteral(String::from("strings")),
-            Token::DoubleQuote,
+            Token::Normal(NormalToken::DoubleQuote),
+            Token::Str(StringToken::Literal("Good")),
+            Token::Normal(NormalToken::DoubleQuote),
+            Token::Normal(NormalToken::DoubleQuote),
+            Token::Str(StringToken::Literal("strings")),
+            Token::Normal(NormalToken::DoubleQuote),
         ])
     );
 
     assert_eq!(
         lex_without_pos("\"Good\\nEscape\\t\\\"\""),
         Ok(vec![
-            Token::DoubleQuote,
-            Token::StrLiteral(String::from("Good\nEscape\t\"")),
-            Token::DoubleQuote,
+            Token::Normal(NormalToken::DoubleQuote),
+            Token::Str(StringToken::Literal("Good")),
+            Token::Str(StringToken::EscapedChar('\n')),
+            Token::Str(StringToken::Literal("Escape")),
+            Token::Str(StringToken::EscapedChar('\t')),
+            Token::Str(StringToken::EscapedChar('\"')),
+            Token::Normal(NormalToken::DoubleQuote),
         ])
     );
 
     assert_eq!(
         lex_without_pos("\"1 + ${ 1 } + 2\""),
         Ok(vec![
-            Token::DoubleQuote,
-            Token::StrLiteral(String::from("1 + ")),
-            Token::DollarBrace,
-            Token::NumLiteral(1.0),
-            Token::RBrace,
-            Token::StrLiteral(String::from(" + 2")),
-            Token::DoubleQuote,
+            Token::Normal(NormalToken::DoubleQuote),
+            Token::Str(StringToken::Literal("1 + ")),
+            Token::Str(StringToken::DollarBrace),
+            Token::Normal(NormalToken::NumLiteral(1.0)),
+            Token::Normal(NormalToken::RBrace),
+            Token::Str(StringToken::Literal(" + 2")),
+            Token::Normal(NormalToken::DoubleQuote),
         ])
     );
 
     assert_eq!(
         lex_without_pos("\"1 + ${ \"${ 1 }\" } + 2\""),
         Ok(vec![
-            Token::DoubleQuote,
-            Token::StrLiteral(String::from("1 + ")),
-            Token::DollarBrace,
-            Token::DoubleQuote,
-            Token::DollarBrace,
-            Token::NumLiteral(1.0),
-            Token::RBrace,
-            Token::DoubleQuote,
-            Token::RBrace,
-            Token::StrLiteral(String::from(" + 2")),
-            Token::DoubleQuote,
+            Token::Normal(NormalToken::DoubleQuote),
+            Token::Str(StringToken::Literal("1 + ")),
+            Token::Str(StringToken::DollarBrace),
+            Token::Normal(NormalToken::DoubleQuote),
+            Token::Str(StringToken::DollarBrace),
+            Token::Normal(NormalToken::NumLiteral(1.0)),
+            Token::Normal(NormalToken::RBrace),
+            Token::Normal(NormalToken::DoubleQuote),
+            Token::Normal(NormalToken::RBrace),
+            Token::Str(StringToken::Literal(" + 2")),
+            Token::Normal(NormalToken::DoubleQuote),
         ])
     );
 }
@@ -285,10 +296,10 @@ fn str_escape() {
     assert!(parse("\"bad escape \\g\"").is_none());
     assert_eq!(
         parse_without_pos(r#""str\twith\nescapes""#),
-        Str(String::from("str\twith\nescapes")).into(),
+        mk_single_chunk("str\twith\nescapes"),
     );
     assert_eq!(
-        parse_without_pos(r#""\$\${ }$""#),
-        Str(String::from("$${ }$")).into(),
+        parse_without_pos(r#""\$\${ }\$""#),
+        mk_single_chunk("$${ }$"),
     );
 }