Library

DPDA · Deterministic context-free

The syntax of an arithmetic expression

Tokens n, +, *, ( and ): is this a well-formed expression? The machine alternates between expecting an operand and expecting an operator, and the stack holds one P per open parenthesis. A parser’s first job, without the parse tree.

operandchecktopinner
The machine as drawn — 4 states, 9 transitions.

The author’s examples, run

n → acceptn+n*n → accept(n+n)*n → accept((n)) → acceptn*(n+(n*n)) → acceptn+ → reject(n → rejectn)(n → reject() → rejectnn → reject