UT Dallas CS 4337 - #Sebesta ch04 Parsing & LL & LR (58 pages)

Previewing pages 1, 2, 3, 4, 27, 28, 29, 30, 55, 56, 57, 58 of 58 page document View the full content.
View Full Document

#Sebesta ch04 Parsing & LL & LR



Previewing pages 1, 2, 3, 4, 27, 28, 29, 30, 55, 56, 57, 58 of actual document.

View the full content.
View Full Document
View Full Document

#Sebesta ch04 Parsing & LL & LR

31 views


Pages:
58
School:
University of Texas at Dallas
Course:
Cs 4337 - Organization of Programming Languages

Unformatted text preview:

Chapter 4 Lexical and Syntax Analysis Introduction Lexical Analysis The Parsing Problem Recursive Descent Parsing Bottom Up Parsing Syntax Analysis The syntax analysis portion of a language processor nearly always consists of two parts A low level part called a lexical analyzer mathematically a finite automaton based on a regular grammar A high level part called a syntax analyzer or parser mathematically a push down automaton based on a context free grammar or BNF BNF for syntax specification Copyright 2012 Addison Wesley All rights reserved 1 2 Advantages of Using BNF to Describe Syntax BNF example expr term term term factor factor factor id int constant expr Provides a clear and concise syntax description The parser can be based directly on the BNF Parsers based on BNF are easy to maintain Copyright 2012 Addison Wesley All rights reserved 1 3 Reasons to Separate Lexical and Syntax Analysis Simplicity less complex approaches can be used for lexical analysis separating them simplifies the parser Efficiency separation allows optimization of the lexical analyzer Portability parts of the lexical analyzer may not be portable but the parser always is portable Copyright 2012 Addison Wesley All rights reserved 1 4 Lexical Analysis A lexical analyzer is a pattern matcher for character strings is a front end for the parser Identifies substrings of the source program that belong together lexemes Lexemes match a character pattern which is associated with a lexical category called a token sum is a lexeme its token may be IDENT Copyright 2012 Addison Wesley All rights reserved 1 5 Lexical Analysis continued The lexical analyzer is usually a function which is called by the parser when it needs the next token Two approaches to building a lexical analyzer Write a formal description of the tokens and use a software tool that constructs a table driven lexical analyzer from such a description Design a state diagram that describes the tokens and write a program that implements the state diagram or hand construct a table driven implementation of the state diagram Copyright 2012 Addison Wesley All rights reserved 1 6 Lexical Analysis with State Diagram In many cases transitions can be combined to simplify the state diagram When recognizing an identifier all uppercase and lowercase letters are equivalent Use a character class that includes all letters When recognizing an integer literal all digits are equivalent use a digit class Reserved words and identifiers can be recognized together rather than having a part of the diagram for each reserved word Use a table lookup to determine whether a possible identifier is in fact a reserved word Copyright 2012 Addison Wesley All rights reserved 1 7 Lexical Analysis continued Convenient utility subprograms getChar gets the next character of input puts it in nextChar determines its class and puts the class in charClass addChar puts the character from nextChar into the place the lexeme is being accumulated lexeme lookup determines



View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view #Sebesta ch04 Parsing & LL & LR 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 #Sebesta ch04 Parsing & LL & LR 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?