Class Notes (835,007)
COMP 302 (61)
Lecture 23

# COMP 302 Lecture 23: March 9 (W9L2): Parsers, pt. 2 Premium

6 Pages
34 Views

School
Department
Computer Science (Sci)
Course
COMP 302
Professor
Semester
Winter

Description
______________________________________________________________ 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

Related notes for COMP 302
Me

OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.