CPSC 323: 3.2 Syntax Analysis

3.1-3.3

Grammar

• The language of grammar G is the set of all sentences that can be generated by G and it is written L(G)

• 4 tuples G=(T,N,S,R)

Terminals(T)

• In programming: identifiers (id), operators (+, *), parentheses ((, )), keywords (if, else).

• Example: { id, +, *, (, ) }

• 1 of 4 tuples of grammar

• Written in lowercase.

  • EX: a,b,c

• Actual characters/lexemes of the language

Non-Terminals(N)

• Syntactic variables like E,T,F

• Get replaced by terminals or non-terminals

  • EX: E = expressions, T= term, F = factor

• Written with capital letters

• Represent syntactic variables

Start Symbol(S)

• Special non-terminal from which every derivation begins.

• Example: Start symbol E

Production Rules(R)

Tell us how non-terminals can be expanded

Context free(CFG)

• If each string a is a single nonterminal then the grammar is called this.

• The language of this is called a ___ language

Why is grammar needed?

•Source code is just a string of characters.

•A compiler must turn that string into a structured tree it can reason about.

•Without rules, id = id + id * id could be grouped multiple ways:

•(id = (id + id) id) vs (id = id + (id id)) have different meanings.

• Why is this important?

Same input string, two meanings.

Without rules, a compiler can’t know which one to pick → ambiguity.

• Programming languages must enforce operator precedence and associativity in their grammars to avoid such confusion.

•The formal contract that say which groupings are legal and which meaning wins.

•We need a formal way to describe programming language syntax.

BODMAS

Purpose for Chomsky’s Conventions in Grammars

• Makes grammar rules clear, general, and gives consistent notation.

• Helps distinguish between symbols when proving theorems, writing derivations, or doing automata theory.

  • A → aB | ab

  • B → b

• Using Chomsky’s convention:

  • A, B are non terminals (capitals).

  • a, b are terminals (lowercase).

  • aB is a terminal followed by a nonterminal.

Identify each term in S → AB

• S is a nonterminal (start symbol).

• A and B are nonterminals.

• AB means two nonterminals concatenated

Ways to represent productions in CFG

• BNF (Backus–Naur Form)

• Extended BNF (EBNF)

• Chomsky Normal Form (CNF)

• Syntax Diagrams (Railroad Diagrams)

BNF(Backus Naur Form)

• A formal notation for context-free grammars.

• Uses angle brackets < > for nonterminals.

• Uses ::= to mean “is defined as”.

• Alternatives are separated by |.

• The symbole | means “or”

• Compact and standardized, used in programming language specs such as Pascal and C

What are these an example of?

• <expr> ::= <expr> + <term> | <term>

• <term> ::= <term> * <factor> | <factor>

• <factor> ::= ( <expr> ) | id

• <expr>, <term>, <factor> → nonterminals.

• +, *, (, ) → terminals.

• id → terminal (identifier).

BNF(Backus- Naur Form)

Extended BNF(EBNF)

• Adds shortcuts to BNF to avoid repetition.

• Common notations:

  • {…} → repeat 0 or more times.

  • […] → optional.

  • (… | …) → choice between alternatives.

• Shorter than plain BNF

• More human readable, used in language docs like for Java

Example of Same Arithmetic Grammar in EBNF

Chomsky Normal Form(CNF)

• A restricted form of CFG useful in theory and parsing algorithms.

• Rules must be either:

• A → BC (two nonterminals), or

• A → a (a single terminal), or

• S → ε (start symbol to empty string, optional).

Syntax Diagrams(Railroad Diagrams)

• A graphical way to represent grammar rules.

• Looks like train tracks easy to follow visually.

• Widely used in manuals (e.g., SQL, JSON specs).

Syntax Diagram for (for<expr>)

• Start → <term> → [“+” <term> repeated] → End

• term: Non-terminal

Derivation

• The process of replacing one non-terminal symbol at a time (using grammar rules) until only terminal symbols remain.

• The result is a sentence (something the grammar recognizes, like valid code).

• Generally: <Expr> =>* a / (c-d), where =>* means “derives in zero or more steps.”

Derivation if a/(c-d)

• Step 4-5 is derivation

Sentential Form

• Any string that comes up during the process of derivation

• Can contain

  • Terminals: Symbols that appear in the final sentence, (ex: a,c,d)

  • Non-Terminals(symbols that still need

    expansion, ex:, <Expr>, <Term>)

Leftmost Derivation(LMD)

• When expanding, choose the leftmost nonterminal 1st

• Directly tied to top-down parsing(others include recursive descent, LL parsers)

• Follows this path

Rightmost Derivation(RMD)

• Choose the rightmost nonterminal 1st

• Tied to bottom-up parsing(like LR and shift-reduce parsers)

• Reconstructs the derivation in reverse corresponding to this type

Language of a CFG

• A Context-Free Grammar (CFG) defines a language.

• That language is the set of all strings that can be derived from the start symbol S.

• Mathematically:

  • L(G) = {x | S → * x}

  • S = start symbol

  • x = derived string (only terminals)

  • ⇒* = “derives in zero or more steps”

• So, if you can derive "a / (c - d)" starting from S, then it belongs to L(G)

Ambiguity in Context-Free Grammars (CFGs)

• For a single input there can be multiple valid interpretations

• A grammar is ambiguous if there exists at least one string in its language that can have two or more different parse trees.

• One of the largest issues in compiler design

Issues with Ambiguity and Compiler Design

• It leads to confusion about how to evaluate expressions.

• Ambiguous grammars cannot be parsed reliably by deterministic parsers (LL, LR).

• Typically, languages resolve ambiguity using Precedence and Associativity rules

Chomsky Hierarchy of Grammar

• Classifies grammars into 4 types based on restrictions on production rules

• The types define the expressive power of the language and the computational model needed

Type 0: Unrestricted Grammar

• A Type 0 grammar is the most general form of grammar in the Chomsky hierarchy.

• Production rules have the form α → β, where α and β can be any strings made of non-terminals (N) and terminals (T).

• There are no restrictions

Turing Machine

• Invented by Alan Turing

• Accepts/recognizes type 0 languages, it has the same power as the machine

• Mathematical model of computation

• Consists of an unlimited memory tape, a set of states or an FSM for logic control, a head for reading, moving, and writing, and transition rules to decide state changes.

• The head moves either left or right after writing (L | R)

• Captures class of recursively enumerable languages(Research this)

• Same power as type 0/unrestricted grammars

Unlimited tape

• Like a long strip of tape divided into cells

• Each cell has a alphabet symbol(listed in Σ)

• Functions as memory and input/output medium.

• Moves left or right along tape

FSM for Turing Machines

• Has a finite set of states

• Controls what happens based on the current state and the symbol being read from the tape

Read/Write Head

• Reads and writes symbols concerning the tapes

• Moves left and write

• Transition function

Transition functions for Turing machines

• N(q, a) → (qi, b ∈ Σ)

  • Meaning: If you are in state q and see symbol a on the tape:

  • Change to state qi,

  • Write symbol b on the tape.

• N(q, a) → (qi, {L, R})

  • After writing, the head moves either Left (L) or Right (R).

Type 1: Context Sensitive Grammar

• Productions are of the form α → β such that:

  • |β| ≥ |α| (the output is at least as long as the input, so no shrinking happens).

  • α and β are strings of terminals and non-terminals.

  • At most one non-terminal is replaced at a time.

• Unlike other types, this doesn’t allow productions that reduce string length, except for a special case allowing S → ε if ε is in the language

Type 2: Context Free Grammar

• Productions are of the form: A → β where:

  • A is a single non-terminal,

  • β is a string of terminals and/or non-terminals.

• This restriction makes CFGs more structured than Type 0 and Type 1 grammars.

Type 3: Regular Grammar

Productions are of the form:

• A → β where:

• A is a single non-terminal.

• β is either:

  • A string of only terminals (like a, b, aba), OR

  • A terminal string followed by at most one non-terminal (like aB, bA).

• Strict rules give this its name

Lexeme

• Raw substring in source code

• Ex: id = id + id * id → "id", "=", "+", "*"

Token

• Category/class of lexemes

• Examples:

  • "id" → IDENTIFIER

  • "=" → ASSIGN

  • "+" → PLUS

  • "*" → MULTIPLY

Chomsky’s Conventions in Grammars

• Serves the purpose of consistent notation

• Standard symbols to represent different categories in grammars

• Consists of:

  • Terminals(T)

  • Non-terminals(N)

  • Strings of terminals(S)

  • Mixtures of terminals and non-terminals written with greek letters

Identify the terms in A → aB

• A is a nonterminal (capital).

• a is a terminal (lowercase).

• B is a nonterminal.

• So aB means a terminal followed by a nonterminal.

Identify the terms in B → ab

• B: Nonterminals

• a: Terminal

• b: Terminal

• ab: String of 2 terminals

Identify terms in A → αBβ

• A: Nonterminals

• B: Nonterminal

• α & β: Mix of terminals/nonterminals

• A can be rewritten into some context α, followed by B,

  followed by β

What type of grammar is shown in the following rules?:

• E → E + T

• E → T

Chonsky Normal Form(CNF) with two non-terminals

Why is the string a/(<Expr> - <Term>) during the derivation of a/(c-d) a sentential form?

It still has non terminals

What type of derivation is this?

Leftmost derivation

What type of derivation is this?

Rightmost derivation

What do these different representations of the string w = a-b+c demonstrate?

Ambiguity in CFGs

What is this an example of?:

Production form: α → β where both α and β are any string of N and T

Unrestricted grammar

What does the form γ A δ → γ α δ mean?

This is a context sensitive grammar, A can be replaced by α, but only in the context of symbols γ (before) and δ (after)

What is the derivation of aabbcc using these rules?

• Start: S

• Apply R1: S → aSBC → aSBC

• Apply R2 (on inner S): aSBC → aabCBC

• Apply R3: aabCBC → aabBCC

• Apply R4: aabBCC → aabbCC

• Apply R5: aabbCC → aabbcC

• Apply R6: aabbcC → aabbcc

• Final string = aabbcc

• Language Generated

• This grammar generates strings of the form:

  • L(G) = { aⁿbⁿcⁿ∣ n ≥ 1 }

• That means: Equal numbers of a, b, and c.

• Examples: abc, aabbcc, aaabbbccc, etc.

Linear Bounded Automation(LBA)

• Restricted turing machine

  • Limited/bounded tape

  • Only as long as the input or a constant multiple

  • Head can’t move outside this bound/ends of input

• N(q,a)→ (qi,b ∈ Σ)

• After going to state qi, overwrite the tape symbol with b

• Move the head l or r

• N(q,a)→ (qi,{L,R})

Transition function for Context Sensitive Languages

With these rules what do the following productions fall under?

• S → aB → ab (String = ab)

• S →bA → ba (String = ba)

• S → aB → a(bS) →abA→aba(Can continue to form abab, etc.)

• S→ bA→b(aS)→baB - bab → balanced form

• Generates the grammar L(G) = { w|w has the same # of a’s and b’s}

  • EX: ab, ba, abab, aabb, aaabbb

Context free Grammar

For the grammar which generates strings like

• abab

• baba

• abababab

• babaababb

and expression L(G) = (abab | baba)*

What type of grammar and expression is this?

Type 3: Regular

In Chomsky’s Hierarchy of Grammars list the

Grammar type:

Grammar accepted:

Language Accepted:

Automation:

for the 1st level

• Type-0

• Unrestricted Grammer

• Recursively Enumerable Language

• Turing machine

In Chomsky’s Hierarchy of Grammars list the

Grammar type:

Grammar accepted:

Language Accepted:

Automation:

for the 2nd level

• Type-1

• Context Sensitive Grammar

• Context Sensitive Language

• Linear Bounded Automation

In Chomsky’s Hierarchy of Grammars list the

Grammar type:

Grammar accepted:

Language Accepted:

Automation:

for the 3rd level

• Type-2

• Context free Grammar

• Context free Language

• Pushdown Automation

In Chomsky’s Hierarchy of Grammars list the

Grammar type:

Grammar accepted:

Language Accepted:

Automation:

for the 4th level

• Type-3

• Regular Grammar

• Regular Language

• Finite State Automation

Push Down Automation(PDA)

• A way to implement a context free grammar in a similar way we design finite automata for regular expression

• A type of computational model that extends a Finite Automaton (FA) by adding a stack as extra memory.

• It is more powerful that FSM

• FSM has a very limited memory, but this has more

memory, more powerful

• __ = Finite State Machine with a stack

• A Finite Automaton (FA) can recognize regular languages.

• This can recognize a broader class of languages called Context-Free Languages (CFLs).

• The stack allows this to "remember" potentially unbounded information, such as matching parentheses or nested structures

Components of a PDA

• Defined as a 7-tuple

• M = (Q, Σ, Γ, δ, q₀, Z₀, F)

Q

• 1 of 7 PDA tuples

• Finite set of states

Σ

• 1 of 7 PDA tuples

• Input alphabet(symbols from the input string)

Γ

• 1 of 7 PDA tuples

• Stack alphabet (symbols you can push/pop onto stack).

δ

• 1 of 7 PDA tuples

• Transition Function

q₀

• 1 of 7 PDA tuples

• Initial state

Z₀

• 1 of 7 PDA tuples

• Intial Stack symbol

F

• 1 of 7 PDA tuples

• Set of accepting states

Transition function for a PDA

• δ: Q × (Σ ∪ {ε}) × Γ → P(Q × Γ*)

• This means:

  • Looks at the current state, current input symbol (or ε), and the top of the stack.

  • Based on this, it moves to a new state and can either push, pop, or replace symbols on the stack.

How PDAS accept input strings

• Final State Acceptance → If the machine ends in an accepting state after reading the input.

• Empty Stack Acceptance → If the stack becomes empty after reading the input.

• Some definitions use one or the other; both are equivalent in power.