LEXICAL AND SYNTAX ANALYSIS

American Standard Code Information Interchange

ASCII

1. Assembly

2. Interpreter

3. Compiler

Language Translator

1. Preprocessor

2. Compiler

3. Assembler

4. Linker

Language Translator - Internal Architecture

1. Lexical Analysis

2. Syntax Analysis

3. Semantic Analysis

4. Intermediate Code Generator

5. Code Optimization

6. Target Code Generation

Compiler - Internal Architecture

1. Compilation

2. Pure Interpretation

3. Hybrid Implementation

Three Primary Approaches

involves translating high-level code into machine code using a compiler.

Compilation

Pure Interpretation

executes the original source code directly using an interpreter.

Hybrid Implementation

combines both methods. It translates high-level code into an intermediate representation, which is then interpreted.

Lexical Analysis

also known as scanning, is the first phase of processing source code. It converts the raw source code into tokens.

Syntax Analyzer

takes the generated tokens and verifies whether they follow the grammatical rules of the programming language.

Simplicity

Lexical analysis is less complex than syntax analysis. Separating them makes both processes easier to manage and maintain.

Efficiency

Since lexical analysis consumes a significant portion of compilation time, optimizing it separately improves overall performance without affecting syntax analysis.

Portability

Lexical analyzers handle platform-dependent elements, while syntax analyzers remain platform independent, making compilers more adaptable across different systems.

Lexical Analyzer

is essentially a pattern matcher that identifies tokens in a given string

• Serves as front end of the Syntax Analyzer

Lexemes

are the actual sequence of characters in the source code.

Tokens

are the classification or category assigned to a lexeme.

Finite Automata

Is used to recognize patterns in a regular language, determining which token category the sequence belongs to. (e.g. identifier, integer, or operator)

State Transition Diagram

A directed graph where each state represents a step in token recognition

parsing

is the act of determining if a set of words or symbols conforms to a set of grammar rules. In

sentential form

is a string with terminal and non-terminal symbols.

leftmost derivation

expands the leftmost non-terminal in each step.

LL Parser

are a family of top-down parsers

1. Left-to-right scan of the input.

2. Leftmost derivation.

The two L's stand for:

rightmost derivation

expands the rightmost non-terminal in each step.

Bottom-up parsing

reverses this process, reducing rightmost derivations

RECURSIVE-DESCENT PARSING

consists of a collection of subprograms, many of which are recursive, and produces a parse tree in top-down order.

EBNF

is a few simple extensions to BNF which make expressing grammars more convenient

PAIRWISE DISJOINTNESS TEST

test requires that the FIRST sets of each alternative are disjoint:

Left factoring

is a technique to transform the grammar to fix this issue.

BOTTOM-UP PARSING

is a technique used in syntax analysis of programming languages, where the parser starts with the input and works backward to reconstruct the parse tree

Rightmost Derivation

It means we always expand (replace) the rightmost non-terminal first at each step

Handle

is the specific part of the input that should be reduced next in bottom-up parsing.

Phrase

is any valid sequence of symbols in the input that folows the grammar rules.

Shift

The next input token is moved onto a stack.

Reduce

The top elements of the stack are replaced using a grammar rule.

Accept

Successful completion

Error

discover syntax mistake

PDA(pushdown automaton)

a theoretical computing model used to recognize context-free languages.

canonical LR

The most well-known bottom-up parsing algorithm is the ____________, introduced by Donald Knuth. LR

GOTO Table

Determines the next state after a reduction.

ACTION Table

Defines whether to shift, reduce, accept, or report an error based on the current state and input symbol.