Parsing, also known as syntactic analysis, is the process of analyzing a sequence of tokens to determine the grammatical structure of a program. It takes the stream of tokens, which are generated by a lexical analyzer or tokenizer, and organizes them into a parse tree or syntax tree.
The parse tree visually represents how the tokens fit together according to the rules of the language’s syntax. This tree structure is crucial for understanding the program’s structure and helps in the next stages of processing, such as code generation or execution. Additionally, parsing ensures that the sequence of tokens follows the syntactic rules of the programming language, making the program valid and ready for further analysis or execution.
A parser performs syntactic and semantic analysis of source code, converting it into an intermediate representation while detecting and handling errors.
- Context-free syntax analysis: The parser checks if the structure of the code follows the basic rules of the programming language (like grammar rules).
- Guides context-sensitive analysis: Helps verify meaning-based rules, such as type checking.
- Constructs an intermediate representation: Helps verify meaning-based rules, such as type checking.
- Produces meaningful error messages: IIdentifies and reports syntax errors clearly.
- Attempts error correction: Tries to handle minor errors and continue parsing.
The parsing is divided into two types, which are as follows:
- Top-down Parsing
- Bottom-up Parsing
Method of building a parse tree from the start symbol (root) down to the leaves (end symbols). The parser begins with the highest-level rule and works its way down, trying to match the input string step by step.
Process:
- Starts from the start symbol.
- Expands non-terminals using production rules.
- Continues until the input string is matched.
Derivation:
- Uses leftmost derivation.
Other names:
- Recursive descent parsing
- Predictive parsing
Useful for simple languages and is often easier to implement. However, it can have trouble with more complex or ambiguous grammars.
With Backtracking
- Tries multiple production rules.
- If one fails, it backtracks and tries another.
- Advantage: Can handle more choices.
- Disadvantage: Slow and inefficient.
Without Backtracking
- Does not retry other rules once a choice is made.
- Faster and more efficient.
- Works only for suitable grammars (e.g., LL grammars).
Read more about classification of top-down parser.
Method of building a parse tree starting from the leaf nodes (the input symbols) and working towards the root node (the start symbol). The goal is to reduce the input string step by step until we reach the start symbol, which represents the entire language.
Process:
- Starts with the input string.
- Reduces substrings into non-terminals.
- Continues reducing until the start symbol is obtained.
Derivation:
- Uses rightmost derivation in reverse.
Also known as:
- Shift-Reduce Parsing
Efficient for handling more complex grammars and is commonly used in compilers. However, it can be more challenging to implement compared to top-down parsing.
LR Parsing (Shift-Reduce Parsing)
- LR(0)
- SLR(1)
- LALR
- CLR
Operator Precedence Parsing
- Used for operator grammars.
- No null productions allowed.
- No two non-terminals should be adjacent.
| Feature | Top-down Parsing | Bottom-up Parsing |
|---|---|---|
| Direction | Builds tree from root to leaves. | Builds tree from leaves to root. |
| Derivation | Uses leftmost derivation. | Uses rightmost derivation in reverse. |
| Efficiency | Can be slower, especially with backtracking. | More efficient for complex grammars. |
| Example Parsers | Recursive descent, LL parser. | Shift-reduce, LR parser. |
Read more about Difference Between Bottom-Up and Top-Down Parser.