Please enable JavaScript.
Coggle requires JavaScript to display documents.
TOPIC 4A: Syntax & Semantic Analysis (Grammar (Classes of grammar…
TOPIC 4A: Syntax & Semantic Analysis
Pushdown Machine
Can be used for syntax analysis
Made up of:
A finite set of states, with one designated as starting state
A finite set of input symbols
An infinite stack and a finite set of stack symbols
(Which may be pushed on top or removed from top in a Last-In-First-Out(LIFO) manner
A state transition function which takes as arguments the current state, the current input symbols, and symbol currently on top of the stack
On each state transition, the machine may advance to next input symbol or retain input pointer
On each transition, the machine may perform the stack operations: push(X) or pop
A state transition may include an exit labeled as 'Accept' or 'Reject' to determine if input string is part of the specified language
Introduction
Input: streams of token from lexical analysis
Output: streams of atoms
Syntax analysis: second phase of compiler
Grammar
List of rules used to generate all strings of language and does not generate strings not in language
Consist of: terminal symbols, non-terminal symbols, & rewriting rules
Two grammars are said to be equivalent if they specify the same language
ex: L(G1) = L(G2)
Classes of grammar
Right linear
Context-free
Represented in Bakus-Naur Form(BNF)
Non-terminal = angle bracket <>
Rewrite arrow = double colons + equal sign ::=
Multiple definition can be written on one line using alternative vertical bar |
Context-sensitive
Unrestricted
Ambiguous Context Free Grammar
CFG is ambiguous when there is more than one derivation tree for a particular string
Derivation tree
A tree which:
Interior node: non-terminal in sentential form
Leaf node: terminal symbol in the derived string
Parsing Problem
Parsing algorithm: solves the parsing problem by using grammar
Context Free Grammar:
Top-down algorithm
Bottom-up algorithm