OpenQASM 3 Parser

This project provides a compiler front end for OpenQASM 3 language (OQ3).

In this document, this parser is referred to as openqasm3_parser.

Differences with the OpenQASM reference parser are

• The parser in openqasm3_parser is much more performant. A crude test with large source files showed parse time reduced by a factor of 80.
• openqasm3_parser performs semantic analysis.

Crates (roughly one installable library per crate)

The first three crates are based on tools for rust and rust-analyzer.

• oq3_lexer -- A lightly modified version of the rustc (the rust compiler) lexer.
• oq3_parser -- Ingests output of oq3_lexer and outputs a concrete syntax tree.
• oq3_syntax -- Ingests output of oq3_parser and outputs an abstract syntax tree (AST). The rust-analyzer documentation sometimes refers to this AST by something like "typed AST". This can be confusing. It does not mean that semantic analysis has been performed and OQ3 types have been assigned to all expressions. It means that the rust type system is used to encode syntactic elements, in contrast to some lower representations in the same crate.
• oq3_semantics -- Performs semantic analysis and outputs an abstract semantic graph (ASG) There are other names for this structure. But "ASG" is convenient.
• oq3_source_file -- A higher-level interface to the syntactic AST. This sits beetween the syntactic AST and semantic ASG. This crate manages the main source file and incuded source files.

Warning !

Do not run cargo test. Rather use ./run_tests.sh or commands found therein. This is because codegen is implemented via the test system (you read correctly). If possible, we plan to change this to a more conventional approach.

Using this front end

A reminder: A front end is not of much use unless you have a back end. Examples showing the entry points and how to use them, can be found in ./crates/oq3_semantics/examples/semdemo.rs.

shell> export QASM3_PATH=./crates/semantics/examples/qasm/
shell> cargo run --example semdemo -- semantic scratch1.qasm

Replace scratch1.qasm with some file found in ./crates/oq3_semantics/examples/qasm/.

Search path

The environment variable QASM_PATH is a colon separated list of paths. Note that the name follows the venerable unix tradition of ending in PATH rather than PATHS. The code that retrives the paths uses routines std::path which may actually handle path specifications on other platforms.

Design

Code from rust-analyzer has been borrowed and modified for the lower levels of parsing. The developer documents for rust-analyzer are very relevant as the structure has not been changed in adapting to OQ3.

• Syntax
• Red/Green trees taken from the C# parser.
• Pratt parsing
  • Simple but Powerful Pratt Parsing
  • From Pratt to Dijkstra
  • Resilient parsing

Notes

Some of this code is modified from code found in rust-analyzer. It was taken at this commit:

commit d398ad3326780598bbf1480014f4c59fbf6461a7
Merge: 2f2cf21da 6990d0f26
Author: bors <bors@rust-lang.org>
Date:   Wed Aug 2 14:28:41 2023 +0000

    Auto merge of #15380 - HKalbasi:mir, r=HKalbasi

    Fix unsized struct problems in mir eval