3 releases (breaking)

0.3.0 Jul 12, 2023
0.2.0 Feb 23, 2023
0.1.0 Nov 10, 2022

#1596 in Parser implementations

36 downloads per month
Used in 4 crates (2 directly)

MIT license

610KB
14K SLoC

Parser

This crate contains the parser for AirScript.

The purpose of the parser is to parse the constraints written in the human-friendly AirScript language into an Abstract Syntax Tree.

Generating the Abstract Syntax Tree (AST)

The parser uses Logos to generate a custom lexer, which is then fed into the parser generated by LALRPOP.

To create an AST from a given AirScript module, pass your source to the public parse function, which will return the AST or an Error of type ScanError or ParseError.

The parse function will first tokenize the source using the lexer, then map the resulting tokens to new tokens accepted by the parser, which are of type (usize, Token, usize). Each invalid token will be stored as ScanError. Finally, if no ScanError occurred, parse feeds the tokens to the parser to generate a Result with the corresponding AST (or ParseError).

Example usage:

// parse the source string to a Result containing the AST or an Error
let ast = parse(source.as_str());

AST

The AirScript AST (Source) contains a vector of SourceSection, each of which contains the result of parsing a section in an AirScript module.

The SourceSection types are:

  • AirDef, which holds the name of the AIR.
  • Constant, which holds a named constant to be used to write constraints.
  • Trace, which contains the parsed trace column information for the main and auxiliary execution traces. Each column or group of columns is represented by its identifier and can be accessed in constraints using this identifier. These columns can also be accessed using the built-in variables $main[idx] and $aux[idx], where idx is the index of the column in the trace.
  • PublicInputs, which is a vector of all of the public inputs defined in the module. Each public input is represented by its identifier and a fixed size.
  • PeriodicColumns, which is a vector of all of the periodic columns defined in the module. Each periodic column is represented by its identifier and a vector containing the pattern of its repeated (periodic) values.
  • RandomValues, which is a vector of all of the random values provided by the verifier. Each random value or group of random values is represented by its identifier and can be accessed in constraints using this identifier. These random values can also be accessed using $rand[idx], where rand is the name of the random values array and idx is the index of the random value in that array.
  • BoundaryConstraints, which contains a vector of BoundaryStmt statements, each of which can be either a boundary constraint or an intermediate variable. Each boundary constraint is represented as an expression tree. Variables can be scalars, vectors or matrices containing expression trees.
  • IntegrityConstraints, which contains a vector of IntegrityStmt statements, each of which can be either an integrity constraint or an intermediate variable. Each integrity constraint is represented as an expression tree. Variables can be scalars, vectors or matrices containing expression trees.

Dependencies

~7–17MB
~199K SLoC