Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Compilers > Parser > Flashcards

Parser Flashcards

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
Q

syntax directed translation

A

translate a sequence of tokens into a sequence of actions

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

For ASTS, when we execute an SDT rule:

A

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

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

How to know if a string is in the language of the CFG?

A

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
Q

CYK algorithm used for what?

A

Used to parse any CFG (to determine for any input whether that input is in the language of a given CFG)

29
Q

CYK essentially does what?

A

Builds all of the possible parse trees for all (consecutive) fragments of the input, bottom up.

30
Q

When does CYK accept input?

A

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
Q

Chomsky Normal Form

A

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
Q

How to convert from CFG to CNF

A
  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
Q

how to eliminate epsilon for CNF?

A

A->epsilon
Take any other rule that has A on the RHS and copy it with nothing
F->(A) F->()

34
Q

Idea of predictive parser

A

build parse tree top down, keep track of work to be done, use a parse table to decide how to do the parse

35
Q

scanned tokens + stack contents correspond to what in predictive parser?

A

Leaves of the current (incomplete) parse tree

36
Q

Rows of parse table are indexed by what?

A

indexed by nonterminals

37
Q

columns of parse table are indexed by what?

A

columns are indexed by the tokens

38
Q

Each element of the parse table is what?

A

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
Q

What are the first two things pushed onto the stack for a predictive parser?

A

1) EOF terminal

2) start nonterminal

40
Q

What happens if top-of-stack symbol is a nonterminal X?

predictive parser

A

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
Q

For nonterminal, which direction are chosen RHS pushed onto stack (predictive parser)

A

Push symbols from R to L

42
Q

What happens if top-of-stack symbol is terminal (predictive parser)?

A

Match it with the current token; if it matches, pop it and call the scanner to get the next token

43
Q

3 ways to terminate predictive parser?

A

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
Q

When is predictive parser input accepted?

A

Stack is empty?

45
Q

When is predictive parser input rejected

A

nonterminal and no parse table entry

terminal and doesn’t match current token

46
Q

Is it always possible to build a predictive parser given a CFG?

A

Only possible to build a predictive parser for CFG if CFG is LL(1)

47
Q

Example of something not in LL(1) because LL(1) only allows 1 look ahead

A

S->(S)|()

48
Q

How to know if grammar is LL(1)?

A

If build the parse table and no element of the table contains more than 1 grammar rule RHS, then LL(1)

49
Q

2 properties that preclude grammar from being LL(1)

A

Left recursive grammar

Grammars that are not left factored

50
Q

A nonterminal X is useless if:

A

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
Q

Transform left recursion into non-left recursion

A->Aa|B

A

A->BA’

A’->aA’|epsilon

52
Q

Meaning of left factored

A

A nonterminal has 2 productions whose RHS have a common prefix

53
Q

Can a LL(1) grammar be left factored?

A

No

54
Q

A grammar is not LL(1) if it is:

A

Left recursive

Not left factored

55
Q

How to check if grammar is in LL(1)

A

Build the parse table; if any element in the table contains more than 1 grammar rule RHS, the grammar is not LL(1)

56
Q

Idea of first sets

A

for a sequence a, FIRST(a) is the set of terminals that begin the strings derivable from a

57
Q

Can grammar be LL(1) if a is current token

A->alpha, B->beta and a is in FIRST(alpha) and FIRST(beta)

A

No

58
Q

FOLLOW sets are defined for what?

A

single non-terminals

59
Q

Define FIRST sets for what?

A

RHS of each production

define FIRST sets for arbitrary sequences of terminals/non-terms/epsilon

60
Q

Can epsilon be in a follow set?

A

No, epsilon can never be a follow set

61
Q

What does the semantic stack hold?

A

Nonterminal’s translations

62
Q

When parse is finished, what does semantic stack hold?

A

Translation of the root nonterminal (translation of the whole input)

63
Q

How are values pushed onto the semantic stack?

A

Add actions to grammar rules

64
Q

Actions for a grammar rule must:

A

Pop the translations of all RHS nonterminals

compute and push the translation of the LHS nonterminal

65
Q

Action numbers

A

part of RHS of grammar rules

Pushed onto normal stack, when action # is top of stack, popped and action carried out

66
Q

When is action performed

A

not performed until all derivations of LHS are carried out

67
Q

RHS nonterminals popped from semantic stack in which order?

A

Right to left because predictive parser does a leftmost derivation

Compilers (10 decks)

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