DOC PREVIEW
Berkeley COMPSCI 164 - Lecture Notes

This preview shows page 1 out of 2 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

AdministrativeSyntactic AnalysisExample of Scanner OutputInternal representationsStrategy Overview for ScannerAdministrative• (Repeat) CS staff (not us!) will process the wait list as space be-comes available.• (Repeat) If you decide to drop, please inform TeleBEARS as soon aspossible to let others in.• Register with the course electr onically from your account (whetheror not enrolled yet)by Monday.• CSUA (Computer Science Undergraduates Association):– Web site: http://csua.berkeley.edu– Mon., Jan 24 at 5PM, 337 Soda: First General Meeting (+ freedinner)– Tue, Jan 25 at 6PM, 306 Soda: vi and emacs Help Session– Thu, Jan 27, 6PM, Wozniak Lounge (4th floor Soda): MentoringMeeting - Pair up with an UD major.Last modified: Fri Jan 21 12:40:30 2005 CS164: Lecture #2 1Syntactic Analysis• First part of the “front end” of compiler.• Purpose: convert string of characters (from file, editor input buffer ,etc.) into a tree or other intermediate form.• Like all phases of compiler:– Eliminates (or moves aside) information not needed by later phases.– Detects errors and substitutes something correct.– Gathers and converts other information to convenient form.• Traditionally divided i nto alexical analyzer(scanner) and(context-free) parser.• Scanner converts stream of character s into stream oftokens:moreconvenient chunks.Last modified: Fri Jan 21 12:40:30 2005 CS164: Lecture #2 2Example of Scanner Output• Original program might beif(i== j)z = 0; /* No work needed */elsez= 1;• Or as the translator sees it:\tif(i== j)\n\t\tz = 0; /* No work needed * /\n\telse\n\ t\tz= 1;• Scanner is intended to convert this to something like:IF, LPAR, ID("i"), EQUALS, ID ("j"), RPAR, ID("z"), ASSIGN,INTLIT("0"), SEMI, ELSE, ID("z"), A SSIGN, INTLIT("1" ), SEMI• That is, a sequence of objects, each with asyntactic category(IF,etc.) of interest to the parser, and poss ibly alexical valueof inter-est to later things.• May also add source-location information for error messages.Last modified: Fri Jan 21 12:40:30 2005 CS164: Lecture #2 3Internal representations• Syntactic categories (symbolic in example) can s i mply be membersof a finite set of integers or other discrete values:– (convenient for equality comparison or indexing tables)• The lexical value could be anything. In our example, it is thelexemeitself (the actual source characters).• So one might define:class Token {enum SyntacticCategory { IF, LPAR, ID, EQUALS, RPAR, ASSIGN, ... };SyntacticCategory syntax;Object value;Location sourcePosition;...}Last modified: Fri Jan 21 12:40:30 2005 CS164: Lecture #2 4Strategy Overview for Sc an ner•Regular expressionscan describe lexemes.•Finite-state automata(FSAs): abstract machines that can recog-nize languages.•Deterministic finite-state automata(DFAs): subset of FSAs easilyconverted into programs.• Can convert regular expressions to FSAs.• Any FSA can be converted to a DFA (i f not already there), and henceto program.• The total process from regular expression to program is automat-able (in our course, flex and jflex).Last modified: Fri Jan 21 12:40:30 2005 CS164: Lecture #2


View Full Document

Berkeley COMPSCI 164 - Lecture Notes

Documents in this Course
Lecture 8

Lecture 8

40 pages

Load more
Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes 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 Lecture Notes 2 2 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?