Qiskit / qiskit / 28842348271

88%

Build Type

push

github

Committed by web-flow

Commit Message

Rewrite OpenQASM 2 expression parser as iterative (#16425)

* Rewrite OpenQASM 2 expression parser as iterative

The previous parser was just an extension of the recursive-descent
parsing of the outer structural parser, with extra operator-precedence
logic added in to resolve binding and associativity.  However, unlike
the outer OpenQASM 2 structure, the potential recursive depth of an
expression is unbounded; as an easy example, consider

    1.0 + (1.0 + (1.0 + ...))

where the brackets force the evaluation to proceed against the natural
associativity of the `+` operation.

Using a fully recursive parser here is pedagogically convenient for
describing the grammar, but rather less convenient for memory use in
deeply nested expressions; we're always going to end up limited by the
stack space allocated to our process, and in the worst case we'll
overflow it.

Instead, we can manually break the recursion into an iteration with our
new "stack" stored in a heap-allocated `Vec` instead.  We have to do a
little extra work to define an `enum` containing all possibilities of
the state we would otherwise have held over a recursive call, but with a
sufficiently simple grammar, that's not too onerous.  The actual parsing
logic is unchanged, just the memory-use / function-call patterns.

* Restore precedence on new subexpression

* Fix typos

* Enforce handling of `power_min`

---------

Co-authored-by: Miriyala Jeevan Kumar <miriyala.jeevan.kumar@ibm.com>

Coverage Stats

138 of 140 new or added lines in 1 file covered. (98.57%)

9 existing lines in 3 files now uncovered.

112897 of 128815 relevant lines covered (87.64%)

996143.9 hits per line