[SOLVED] CS assembly CONTEXT-FREE GRAMMARS AND SYNTACTIC ANALYSIS

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