Ch5 Flashcards
(28 cards)
What is another name for syntax analysis?
Parser
what is the role of a syntax analyzer?
recombining tokens , created by the lexical analyzer, by creating a parse tree
what creates a syntactic structure of the given source program?
A syntax analzer
in a syntax tree, what represents tokens?
leaves
When can we say the the sequence is the same as input text?
when the leaves in a parse tree are read from left to right.
What role does syntax analysis play in rejecting invalid code?
In addition to finding the syntax structure of the input text, it rejects invalid code by reporting syntax errors
The syntax of a Programming Language is described by…
CFG (Context-Free-Grammar)
what is a BNF?
Backus Naur Form
a notation that describes CFG
How is the syntax analyzer related with CFG?
the syntax analyzer checks wether a given source program satisfies the rules implied by CFG or not.
if it satisfies, it creates a parse tree
if doesn’t, it returns an error message.
what is an initial phase of the design of a compiler?
The design of grammar
can a grammar be directly converted to a parser?
yes by some tools
Parser works on a …..
stream of tokens
what is the smallest unit of a parser?
token
How many categories are parsers categorized to an what are they?
2,
Top down parser
Bottom up parser
how do top-down and bottom-up parsers scan input?
from left to right (one symbol at a time).
Efficient top-down and bottom-up parsers can be implemented only for sub-classes of CFG.What are they?
LL for top-down parsing
LR for bottom-up parsing
what is a non terminal?
a grammatical symol that can be expanded into more symbols
what is a production?
a set of rules that explains how symbols are replaced (nonterminal)
: a sequence of applications of the rules of a grammar that produces a finished string of terminals.
Derivation or parse
what is a Start symbol?
a grammar that has a one non terminal in which all sentences are derived from this start state.
We formally define a grammar as a
4-tuple {S, P, N, T}.
what is A sentence
T derived from S using one or more applications of P
What is a Type 0 grammar?
A: Free or unrestricted grammars with no restrictions on production forms, except the left side must be non-empty
What is a Type 1 grammar?
A: Context-sensitive grammars where productions are of the form uXw → uvw, with v non-null and X a single nonterminal.
