CONTEXT-FREE GRAMMARS AND SYNTACTIC ANALYSIS
PRINCIPLES OF PROGRAMMING LANGUAGES
Norbert Zeh Winter 2021
Dalhousie University
1/4
PROGRAM TRANSLATION FLOW CHART
Source program (Character stream)
Scanner (lexical analysis)
Parser (syntactic analysis)
Semantic analysis and code generation
Machine-independent code improvement
Target code generation
Machine-specific code improvement
Token stream
Parse tree
Abstract syntax tree or other intermediate form
Target language (e.g., assembly)
Modified intermediate form
Modified target language
2/4
Back end Front end
Symbol table
SYNTACTIC ANALYSIS
Goal
Convert the token stream produced by the scanner into a parse tree representing the syntactic structure of the program.
3/4
SYNTACTIC ANALYSIS
kwClass identifier ‘{’ identifier identifier ‘;’ identifier identifier ‘;’
‘}’ ‘;’
Goal
Convert the token stream produced by the scanner into a parse tree representing the syntactic structure of the program.
3/4
SYNTACTIC ANALYSIS
kwClass identifier ‘{’ identifier identifier ‘;’ identifier identifier ‘;’
Goal
Convert the token stream produced by the scanner into a parse tree representing the syntactic structure of the program.
‘}’ ‘;’
kwClass
ClassDef
id ’{’ Fields
’}’ ’;’
Field
id ’;’ Field
id id ’;’ ε
id
Fields Fields
3/4
SYNTACTIC ANALYSIS
kwClass identifier ‘{’ identifier identifier ‘;’ identifier identifier ‘;’
Goal
Convert the token stream produced by the scanner into a parse tree representing the syntactic structure of the program.
‘}’ ‘;’
Tools
• Context-free grammars, LL(1)/LR(1) grammars
• (Deterministic) push-down automata, recursive-descent parsers
kwClass
ClassDef
id ’{’ Fields
’}’ ’;’
Field
id ’;’ Field
id id ’;’ ε
id
Fields Fields
3/4
ROAD MAP
• Parsing: Transform (tokenized) program text into parse tree
• Modelling programming languages: Context-free grammars and languages
• Capturing the syntactic structure of a program: Parse trees
• Types of parsers and types of grammars they can parse
• Grammars that describe programming languages and can be parsed
efficiently
• Construction of an LL(1) grammar
• Parsing LL(1) languages
• Push-down automata
4/4