feat: lalrpop lexer prototype

[michaeljklein]

Description

Problem*

Resolves #4655

Summary*

NOTE: I've added CC0-1.0 to deny.toml. Its purpose is to release work to the public domain.

TL;DR

lalrpop generates a part of a parser for our grammar and the noirc_frontend/experimental_parser feature can be used to run it alongside the existing parser: when the existing chumsky parser succeeds, the lalrpop parser is run and the results compared.

Detail

Run with cargo test --features=noirc_frontend/experimental_parser

Originally investigating lalrpop for lexing, now for parsing:

• lalrpop doesn't handle string literals with escape characters well
  • this is due to how LR(1) parsers handle context
  • I realized this after discovering that all of the larger examples (solidity, python, etc) use the lexer to handle strings
• pivoted this PR to use our existing lexer
  • this entailed a version of Token without String so that e.g. Token::Str("hi") can be matched on. (which is essential to lalrpop)
  • currently using a shim to minimize impact to the rest of the code:
    • conversion to/from SpannedToken
    • lexing the whole input into a Vec and using iter() to feed token lifetimes to lalrpop
• current state:
  • WIP parsing use statements (missing support for recursive statements)
  • unit tests for use statements test lalrpop parser
  • feature flag experimental_parser enables running the experimental parser on every part of the AST that's successfully parsed with the existing chomsky parser

Changes:

• Now rejecting whitespace other than \t \n\r

Additional Context

Documentation*

Check one:

• No documentation needed.
• Documentation included in this PR.
• [For Experimental Features] Documentation to be submitted in a separate PR.

PR Checklist*

• I have tested the changes locally.
• I have formatted the changes with Prettier and/or cargo fmt on default settings.