______________________________________________________________
March 9, 2017 (Lecture 23 // Week 9, Lecture 2)
Parsers (2)
Grammars don’t just generate strings; they generate tree structures called parse trees. The structure of the tree
tells you something about the grouping. In fact, many of the inadequacies in our standard linear languages is that
the linear structure doesn’t reveal grouping. That’s why we use parentheses to manifest grouping. The point of
parsing is to manifest algorithms based on a given grammar that allows you to take a string and:
1. Check if it is a valid string according to the rules of the grammar
2. Reconstruct a tree, which is the basis for code generation later on (next lecture)
The tree we looked at yesterday was ambiguous. Today we will fix that problem!
When a grammar produces 2 or more parse trees for a sequence, it is call ambiguous. We need to design
unambiguous grammars; but sometimes this is impossible. Here is how we do it for our expressions with
generation of numbers thrown in as well:
★ NT = {, , , , }
○ Non-terminals expand further (non leaves)
○ N = generates numbers.
○ D = generates digits.
○ E = generates expressions (last time we only had expressions).
○ F = generates factors
○ T = generates terms
The idea is that factors are things that can be multiplied and terms are things that are added.
★ Start Symbol is
★ Σ = {+, *, (, ), 0, 1, 2, 3, 4, ... 9 }
○ Terminal symbols
★ Rules of the grammar:
○ -> + |
■ Two different rules for E, written with a vertical bar between them as a space-saving
convention.
○ -> * |
■ Terms can be either a term times a factor, or just a factor.
○ -> () |
■ A factor can be a parenthesized expression, or a number.
○ -> |
■ A number can be a number followed by a digit or a single digit.
○ -> 0 | 1 | 2 | .... | 9
■ A digit is a numeral.
Focus on how the + and * interact. This is a different grammar but the same language as before.
Generate 3 + 4 * 5 : This was the string that was ambiguous last time. But it is perfect here! :)
Start with . Goal is to group 3 and 4 together, so * should be at the top level, as 3+4 are deeper. Use the rules to
work backwards.
Let us try to create the “wrong” grouping. We want to make the * appear at the top of the tree with the + nested
inside it. The ... lines

More
Less