UMD CMSC 330 - Context Free Grammars and Parsing (90 pages)

Previewing pages 1, 2, 3, 4, 5, 6, 42, 43, 44, 45, 46, 47, 85, 86, 87, 88, 89, 90 of 90 page document View the full content.
View Full Document

Context Free Grammars and Parsing



Previewing pages 1, 2, 3, 4, 5, 6, 42, 43, 44, 45, 46, 47, 85, 86, 87, 88, 89, 90 of actual document.

View the full content.
View Full Document
View Full Document

Context Free Grammars and Parsing

65 views

Lecture Notes


Pages:
90
School:
University of Maryland, College Park
Course:
Cmsc 330 - Organization of Programming Languages
Organization of Programming Languages Documents

Unformatted text preview:

CMSC 330 Organization of Programming Languages Context Free Grammars and Parsing CMSC 330 Spring 2011 1 Where We Are Programming language generalities Types of languages Compilers and interpreters Ruby An object oriented scripting language Text processing via regular expressions Theory of regular languages Regular expressions Finite automata deterministic nondeterministic CMSC 330 Spring 2011 2 Up Next Syntax of Prog Langs Structure of syntactic analyzers Scanning lexing Parsing Defining programming language syntax Via regular expressions and context free grammars CFGs Definition Derivations leftmost Parse tree Ambiguity Associativity precedence CMSC 330 Spring 2011 3 Programming Languages Syntax What a program looks like Needs to be very precise Semantics What a program means How different parts of a program behave CMSC 330 Spring 2011 4 Recall Architecture of Compilers Interpreters Parser Source Static Analyzer Intermediate Representation Front End Back End Compiler Interpreter CMSC 330 Spring 2011 5 Front End Source Static Analyzer Parser Parse Tree Intermediate Representation Front End Responsible for turning source code sequence of symbols into representation of program structure Parser generates parse trees which static analyzer processes CMSC 330 Spring 2011 6 Parser Architecture Source Scanner Token Stream Parser Parse Tree Parser Scanner lexer converts sequences of symbols into tokens keywords variable names operators numbers etc Parser yes a parser contains a parser converts sequences of tokens into parse tree CMSC 330 Spring 2011 7 Specifications of Syntax Tokens specified using regular expressions Valid sequences of tokens specified using context free grammars Automated tools e g lex yacc convert regular expressions grammars into scanners parsers CMSC 330 Spring 2011 8 Motivation for Grammars Programs are just strings of text But they are strings that have a certain structure Informal description of structure of a C program A C program is a list of



View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Context Free Grammars and Parsing and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Context Free Grammars and Parsing and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?