created_at2024-05-06 01:25:15.170898
updated_at2024-06-01 21:14:47.60584
descriptionA zero-copy recursive-descent parser for WebGPU shading language
Danny McGee (dannymcgee)




WGSL Parser

A hand-rolled, zero-copy recursive-descent parser for WebGPU shading language, written with Gramatika.


Parsing a source file

use parser::{Parse, ParseStream, SyntaxTree};

const SOURCE_TEXT: &str = include_str!("path/to/some/shader.wgsl");

fn main() -> anyhow::Result<()> {
	let mut parser = ParseStream::from(SOURCE_TEXT);
	// The `SyntaxTree`
	let tree = parser.parse::<SyntaxTree>()?;
	// A tuple of `(ArcStr, Vec<Token>)`
	let (source, tokens) = parser.into_inner();


Tokenizing a source file without doing a full parse

use gramatika::Lexer as _;
use parser::Lexer;

const SOURCE_TEXT: &str = include_str!("path/to/some/shader.wgsl");

fn main() {
	let mut lexer = Lexer::new(SOURCE_TEXT.into());
	// `Vec<Token>`
	let tokens = lexer.scan();

Syntax tree representation

A SyntaxTree contains a vector of Decls representing the top-level syntax types defined by the WGSL grammar, e.g.:

  • Decl::Var(VarDecl { .. })

    @group(1) @binding(2)
    var<uniform> uniforms: Uniforms;
  • Decl::Const(VarDecl { .. })

    const FOO: u32 = 1u;
  • Decl::Struct(StructDecl { .. })

    struct Foo {
    	foo: mat3x4<f32>,
    	bar: vec2<u32>,
    	baz: array<mat4x4<f32>, 256u>,
  • Decl::Function(FunctionDecl { .. })

    fn sum(a: f32, b: f32) -> f32 {
    	return a + b;

The structures wrapped by those declarations can contain sub-declarations, e.g.:

  • Decl::Field(FieldDecl { .. }) inside of a StructDecl
  • Decl::Param(ParamDecl { .. }) inside of a FunctionDecl

The body of a FunctionDecl contains a vector of Stmts.

Stmt is an enum in a form similar to Decl, with variants indicating the kind of statement it represents, each wrapping an inner structure that describes the syntax in further detail, often recursively, e.g.:

// NOTE: This is not valid Rust code, just a pseudo-code example of what some
//       `Stmt` might look like on the inside

Stmt::If(IfStmt {
	else_branch: Some(ElseStmt {
		body: Arc(Stmt::Block(BlockStmt {
			stmts: Arc<[Stmt]>,

Finally, Expr is the "lowest" form of syntax in the tree, taking the same general form as Decl and Stmt above.

Inspecting a syntax tree

Each node of the syntax tree derives a bespoke Debug implementation, which prints the tree in a format that's a sort of cross between Lisp (a format commonly used for representing syntax trees) and Rust syntax.

That format looks like this:

max(4, 2) // The expression represented by the tree below
(Expr::Primary (PrimaryExpr
	expr: (Expr::FnCall (FnCallExpr
		ident: (IdentExpr::Leaf `max` (Function (1:1...1:4))),
		arguments: (ArgumentList
			brace_open: `(` (Brace (1:4...1:5)),
			arguments: [
				(Expr::Primary (PrimaryExpr
					expr: (Expr::Literal `4` (IntLiteral (1:5...1:6))),
				(Expr::Primary (PrimaryExpr
					expr: (Expr::Literal `2` (IntLiteral (1:8...1:9))),
			brace_close: `)` (Brace (1:9...1:10)),

Traversing a syntax tree

The package exports a Visitor trait which can be implemented to efficiently traverse the tree. Visitor defines a visit_ method for each type of syntax represented by the tree. visit_ methods for nodes that contain child nodes must return either FlowControl::Continue to traverse their children, or FlowControl::Break to stop traversing the current branch.

The default Visitor implementation returns FlowControl::Continue for every node, so you only need to actually implement the visit_ methods that your particular use case calls for:

use std::collections::HashMap;

use gramatika::{Substr, Token as _};
use parser::{
	expr::{IdentExpr, NamespacedIdent},
	traversal::{FlowControl, Visitor, Walk},
	ParseStream, SyntaxTree,

struct ReferenceCounter {
	counts: HashMap<Substr, usize>,

impl Visitor for ReferenceCounter {
	fn visit_var_decl(&mut self, decl: &VarDecl) -> FlowControl {
		self.counts.insert(decl.name.lexeme(), 0);

		if let Some(ref expr) = decl.assignment {


	fn visit_ident_expr(&mut self, mut expr: &IdentExpr) {
		if let IdentExpr::Leaf(name) = expr {
			if let Some(count) = self.counts.get_mut(&name.lexeme()) {
				*count += 1;

// Note: Not actually a robust implementation of a reference-counter,
//       but good enough for this toy example
pub fn count_references(tree: &SyntaxTree) -> HashMap<Substr, usize> {
	let mut visitor = ReferenceCounter::default();
	tree.walk(&mut visitor);

Commit count: 48

cargo fmt