An interactive exploration of parsing techniques, context-free grammars, and syntax tree visualization — the heart of every compiler.
function parseExpr() {
let node = parseTerm();
while (token === '+' || token === '-') {
let op = token;
advance();
node = { type: 'BinaryExpr',
op, left: node,
right: parseTerm() };
}
return node;
}Understanding the backbone of compiler design
Syntax analysis (parsing) is the second phase of a compiler. It takes a stream of tokens from the lexical analyzer and determines whether the token sequence can be generated by the grammar of the source language.
The parser constructs a parse tree (or syntax tree) that represents the hierarchical syntactic structure of the source program, verifying that the program follows the language's grammatical rules.
The syntax analyzer sits between the lexical analyzer (scanner) and the semantic analyzer in the compiler pipeline.
| Aspect | Lexical Analysis | Syntax Analysis |
|---|---|---|
| Phase | First phase | Second phase |
| Input | Character stream | Token stream |
| Output | Tokens | Parse tree / AST |
| Grammar | Regular expressions | Context-Free Grammar (CFG) |
| Errors | Invalid characters, malformed tokens | Structural errors, missing operators |
| Tool | Finite Automaton | Pushdown Automaton |
| Example | 123 → NUM(123) |
NUM + NUM → valid expression |
The formal rules our parser uses to validate expressions
A context-free grammar G = (V, Σ, P, S) where:
The grammar encodes precedence through its layered structure:
−x
^ (right-assoc)
*, Divide /
+, Subtract −
Enter an expression to see parsing in action — live tokenization, step-by-step parsing, and tree visualization
A top-down parser that uses a set of mutually recursive procedures — one for each non-terminal in the grammar. It processes input from left to right and constructs a leftmost derivation.
A table-driven predictive parser that reads input Left-to-right, produces a Leftmost derivation, and uses 1 token of lookahead. It uses FIRST and FOLLOW sets to build a parsing table.
A bottom-up parser that reads input Left-to-right and constructs a Rightmost derivation in reverse. Uses shift-reduce operations with a state stack.
Comprehensive testing with valid and invalid inputs
Where parsing powers the tools we use every day
Every programming language compiler (GCC, Clang, javac) uses syntax analysis as a core phase. The parser converts source code into ASTs that enable optimization and code generation.
VS Code, IntelliJ, and other IDEs use incremental parsers for syntax highlighting, auto-completion, code folding, and real-time error detection as you type.
Tools like ESLint, Prettier, and Black parse source code to enforce coding standards, detect potential bugs, and automatically format code to consistent styles.
SQL engines parse queries to build query execution plans. The parser validates syntax, resolves table references, and enables query optimization.
Browsers parse HTML, CSS, and JavaScript using specialized parsers. The HTML parser builds the DOM tree, CSS parser creates CSSOM, and JS parsers compile code to bytecode.
NLP systems use parsers to analyze sentence structure, extract meaning, and understand relationships between words — powering chatbots, translators, and voice assistants.
Key takeaways and future directions
This project demonstrated the design and implementation of a comprehensive syntax analysis detection system. We explored three major parsing techniques — Recursive Descent, LL(1), and LR(0) — all working with a well-defined context-free grammar for arithmetic expressions.
Key accomplishments include: