Syntax Analysis Flashcards
What is top down parsing?
This is when we begin with the starting symbol of a grammar and always extend the left-most non-terminal symbol until we achieve a string that matches the input.
What is an ambiguous grammar?
This is a grammar that can generate the same string using multiple parse trees.
What is a left recursive grammar?
A grammar is left-recursive if it contains a non-terminal symbol A, which is replaced by Ax…
That is it is replaced by itself and some other symbols. This means we can generate an infinitely long parse tree, where we accumulate As on the left hand side.
E.g. A => Ab
A
Ab
Abb
Abbb ….
How can i eliminate the left recursion of the following grammar:
Sum => Sum + number | number
Sum => number Sum”
Sum” => +number Sum” | empty_symbol
What is the LL(1) property?
This is when all for all substitutions for a particular non-terminal symbol begin with different first terminal symbols.
For example:
A => aZ
A => bZ
They both start with different symbols, this allows us to look ahead one symbol in the input and make an informed choice about which rule to use.
How would we transform the following grammar so that it has the LL(1) property?
A => ax | ay | az
Factor out the a,
A => aF
F => x | y | z
Now all substitutions begin with a different symbol
What is bottom up parsing?
This is where we begin with the sentence, and try to come up with sequence of production rules that created it.
What is a handle in a string S?
A => b — rule to use
k — position
where b is a substring in S, and k is the position of b’s rightmost symbol in S.
What can cause a Top Down Parser to go into an infinite loop?
A Left Recursive Grammar
