Lexical analysis is the process of converting a sequence of characters in a source code file into a sequence of tokens that can be more easily processed by a compiler or interpreter. It is often the first phase of the compilation process and is followed by syntax analysis and semantic analysis.
- Non-terminal: This is a placeholder for a part of the language that can be further defined. It's like a variable in a mathematical equation.
- Terminal: This is the smallest unit of language, like a single character or word.
- Greedy Matching: The
* operator in the term and expression rules is greedy. It will consume as many factors as possible.
- Backtracking: If a part of the expression doesn't match, the parser backtracks to the previous position and tries a different path. For example
- Recursive Definitions: The
expression rule refers to itself indirectly through term and factor. This allows for nested expressions. For example, when parsing (1 + 2) * 3, the parser can recursively call the expression rule to parse the inner expression 1 + 2.
How Parsing Expressions Work:
- Success and Failure: When a parser processes a string, it tries to match the string to the grammar rules. If it can match, it's a success; if not, it's a failure.
- Atomic Expressions:
- Literal: Matches a specific character or string.
- Empty String: Always succeeds without consuming input.
- Non-terminal: Recurses to another part of the grammar.
- Sequence: Matches two expressions in order. Both must succeed.
- Choice: Tries to match the first expression. If it fails, tries the second.
- Repetition: Matches an expression zero or more times (), one or more times (
+), or zero or one times (?).
- And-predicate: Checks if an expression matches but doesn't consume input.
- Not-predicate: Checks if an expression doesn't match and doesn't consume input.
Key Concepts:
- “trial-and-backtrack”.
- the reader doesn’t operate on logical operators but on sequences, choices, and assembly instructions in the recipe book.
- non-terminals are instructions, and terminals are the simplest pieces used in those instructions.
parse tree. Each node in the tree represents a rule in the grammar, and the edges represent the application of that rule.