Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

Compilers > Parser > Flashcards

Parser Flashcards

(67 cards)

Start Studying
1
Q

What does the parser do?

A

Group tokens into grammatical phrases
Discovers underlying structure of program
finds syntax errors

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is output of parser for legal program?

A

Abstract syntax tree (+ symbol table)
intermediate code
object code

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

terminal symbol

A

Tokens returned by scanner

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

productions

A

rules

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Production LHS

A

Single non-terminal

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Production RHS

A

Either epsilon or a sequence of one or more terminals and/or non-terminals

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

CFG 4-tuple (N, E, P, S)

A

N - set of nonterminals
E - set of terminals
P - set of productions
S - start non-terminals

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Leftmost derivation

A

The leftmost nonterminal is always chosen to be replaced

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Rightmost derivation

A

The rightmost nonterminal is always chosen to be replaced

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

How to construct a parse tree

A

Start with start non-terminal
Repeat: 1) choose a leaf nonterm X 2) choose a production X->alpha 3) The symbols in alpha become the children of X in the tree

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

The derived string is formed by reading leaf nodes from _______ to _______

A

The derived string is formed by reading the leaf nodes from left to right

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Ambiguous grammer

A

> 1 leftmost or > 1 right-most derivation or > 1 parse tree

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

How to write a grammer to express precedence

A

Use a different nonterminal for each precendence leve
Start by writing a rule for the operator with the lowest precedence
exp->

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What causes ambiguity?

A

Ill defined precedence and/or associativity

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

For left associativity, use

A

left recursion

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

For right associativity, use

A

right recursion

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

How to force left associativity?

A

exp->exp MINUS exp | term

exp->exp MINUS term | term

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Syntax directed translation

A

defined by augmenting the CFS: a translation rule is defined for each production

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

A translation rule defines the translation of the LHS non-terminal as a function of:

A

constants
the RHS nonterminal’s translations
the RHS tokens’ values

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

To translate an input string using syntax directed translation:

A
  1. Build the parse tree

2. Use the translation rules to computer the translation of each non-terminal in the tree, working bottom up

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Why work bottom up for syntax directed translation?

A

A non-terminal’s value may depend on the value of the symbols on the RHS so need to work bottom up so those values are available

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

AST vs. Parse Tree

A

AST: operators appear at internal nodes instead of leaves, chains of single productions are collapsed, listed a flattened, syntactic details are omitted

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Context Free Grammar

A

A set of recursive rewriting rules to generate patterns of strings

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

CFG in compiler

A

Start with a string and end with a parse tree for w if w exits in L(G)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
syntax directed translation
translate a sequence of tokens into a sequence of actions
26
For ASTS, when we execute an SDT rule:
we construct a new node object, which becomes the value of LHS.trans populate the node's fields with the translations of the RHS non-terminals
27
How to know if a string is in the language of the CFG?
Yes iff the string can be derived from the CFG's start non-terminal Yes iff we can build a parse tree for the string, with the CFG's start nonterminal at the root
28
CYK algorithm used for what?
Used to parse any CFG (to determine for any input whether that input is in the language of a given CFG)
29
CYK essentially does what?
Builds all of the possible parse trees for all (consecutive) fragments of the input, bottom up.
30
When does CYK accept input?
Iff it is able to build a complete a complete parse tree with the start non-terminal at the root and the entire input at the leaves.
31
Chomsky Normal Form
X->singular terminal X->2 non-terminals X->epsilon is not allowed unless the nonterminal is the start non-terminal If S->epsilon and S is the start non-term, then S cannot occur on the RHS of any rule
32
How to convert from CFG to CNF
1. Eliminate epsilon rules 2. Eliminate rules with exactly 1 non-terminal on the right (unit rules) 3. Fix remaining rules so all rules have single terminal or exactly two non-terminals on the right
33
how to eliminate epsilon for CNF?
A->epsilon Take any other rule that has A on the RHS and copy it with nothing F->(A) F->()
34
Idea of predictive parser
build parse tree top down, keep track of work to be done, use a parse table to decide how to do the parse
35
scanned tokens + stack contents correspond to what in predictive parser?
Leaves of the current (incomplete) parse tree
36
Rows of parse table are indexed by what?
indexed by nonterminals
37
columns of parse table are indexed by what?
columns are indexed by the tokens
38
Each element of the parse table is what?
Each element of the table for the row indexed by nonterminal X is either empty or contains the RHS of a grammar rule for X
39
What are the first two things pushed onto the stack for a predictive parser?
1) EOF terminal | 2) start nonterminal
40
What happens if top-of-stack symbol is a nonterminal X? | predictive parser
Use nonterminal X and the current token t to index into the parse table and choose a production with X on the LHS (RHS is in table[x][t] pop x from stack and push the chosen production's RHS
41
For nonterminal, which direction are chosen RHS pushed onto stack (predictive parser)
Push symbols from R to L
42
What happens if top-of-stack symbol is terminal (predictive parser)?
Match it with the current token; if it matches, pop it and call the scanner to get the next token
43
3 ways to terminate predictive parser?
Top of stack is non-terminal, and parse table entry is empty top-of-stack=terminal but doesn't match curr token stack is empty
44
When is predictive parser input accepted?
Stack is empty?
45
When is predictive parser input rejected
nonterminal and no parse table entry | terminal and doesn't match current token
46
Is it always possible to build a predictive parser given a CFG?
Only possible to build a predictive parser for CFG if CFG is LL(1)
47
Example of something not in LL(1) because LL(1) only allows 1 look ahead
S->(S)|()
48
How to know if grammar is LL(1)?
If build the parse table and no element of the table contains more than 1 grammar rule RHS, then LL(1)
49
2 properties that preclude grammar from being LL(1)
Left recursive grammar | Grammars that are not left factored
50
A nonterminal X is useless if:
1) you can't derive a sequence that includes X | 2) You can't derive a string (epsilon or a sequence of terminals) from X
51
Transform left recursion into non-left recursion | A->Aa|B
A->BA' | A'->aA'|epsilon
52
Meaning of left factored
A nonterminal has 2 productions whose RHS have a common prefix
53
Can a LL(1) grammar be left factored?
No
54
A grammar is not LL(1) if it is:
Left recursive | Not left factored
55
How to check if grammar is in LL(1)
Build the parse table; if any element in the table contains more than 1 grammar rule RHS, the grammar is not LL(1)
56
Idea of first sets
for a sequence a, FIRST(a) is the set of terminals that begin the strings derivable from a
57
Can grammar be LL(1) if a is current token | A->alpha, B->beta and a is in FIRST(alpha) and FIRST(beta)
No
58
FOLLOW sets are defined for what?
single non-terminals
59
Define FIRST sets for what?
RHS of each production | define FIRST sets for arbitrary sequences of terminals/non-terms/epsilon
60
Can epsilon be in a follow set?
No, epsilon can never be a follow set
61
What does the semantic stack hold?
Nonterminal's translations
62
When parse is finished, what does semantic stack hold?
Translation of the root nonterminal (translation of the whole input)
63
How are values pushed onto the semantic stack?
Add actions to grammar rules
64
Actions for a grammar rule must:
Pop the translations of all RHS nonterminals | compute and push the translation of the LHS nonterminal
65
Action numbers
part of RHS of grammar rules | Pushed onto normal stack, when action # is top of stack, popped and action carried out
66
When is action performed
not performed until all derivations of LHS are carried out
67
RHS nonterminals popped from semantic stack in which order?
Right to left because predictive parser does a leftmost derivation

Compilers (10 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2025 Bold Learning Solutions. Terms and Conditions