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

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

6 Pages
Unlock Document

Computer Science (Sci)
COMP 302
Prakash Panangaden

______________________________________________________________ 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

Log In


Join OneClass

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

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.