DOC PREVIEW
UVA CS 415 - Parsing

This preview shows page 1-2-3-26-27-28 out of 28 pages.

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

Unformatted text preview:

In More Depth…ParsingOld Example“Standard Order”Common OrderingsTop-down vs. bottom-upSlide 7“Something Useful”Context-Free GrammarsStandard NotationsDerivation Relations (1)Derivation Relations (2)LanguagesReduced GrammarsAmbiguityExample: Ambiguous Grammar for Arithmetic ExpressionsExample (cont)Another exampleWhat’s going on here?Classic Expression GrammarCheck: Derive 2 + 3 * 4Check: Derive 5 + 6 + 7Check: Derive 5 + (6 + 7)Another Classic ExampleTwo derivations of if-elseSolving if AmbiguityParser Tools and OperatorsParser Tools and Ambiguous Grammars01/14/19 CS415 - Fall 2005 1In More Depth…•Grammars•Parsing(Slides copied liberally from Ruth Anderson, Hal Perkins and others)01/14/19 CS415 - Fall 2005 2Parsing•The syntax of most programming languages can be specified by a context-free grammar (CGF)•Parsing: Given a grammar G and a sentence w in L(G ), traverse the derivation (parse tree) for w in some standard order and do something useful at each node–The tree might not be produced explicitly, but the control flow of a parser corresponds to a traversal01/14/19 CS415 - Fall 2005 3OldExample a = 1 ; if ( a + 1 ) b = 2 ;program ::= statement | program statementstatement ::= assignStmt | ifStmtassignStmt ::= id = expr ;ifStmt ::= if ( expr ) stmtexpr ::= id | int | expr + exprId ::= a | b | c | i | j | k | n | x | y | zint ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9programprogramstatementstatementifStmtassignStmtstatementexprassignStmtexpr exprintidid exprintid exprintG w01/14/19 CS415 - Fall 2005 4“Standard Order”•For practical reasons we want the parser to be deterministic (no backtracking), and we want to examine the source program from left to right.–(i.e., parse the program in linear time in the order it appears in the source file)01/14/19 CS415 - Fall 2005 5Common Orderings•Top-down–Start with the root–Traverse the parse tree depth-first, left-to-right (leftmost derivation)–LL(k)•Bottom-up–Start at leaves and build up to the root•Effectively a rightmost derivation in reverse(!)–LR(k) and subsets (LALR(k), SLR(k), etc.)01/14/19 CS415 - Fall 2005 6Top-down vs. bottom-up•Consider the grammar (Scott, p. 49)–id_list -> id id_list_tail–id_list_tail -> , id id_list_tail–id_list_tail -> ;•And input text:–A, B, C;01/14/19 CS415 - Fall 2005 701/14/19 CS415 - Fall 2005 8“Something Useful”•At each point (node) in the traversal, perform some semantic action–Construct nodes of full parse tree (rare)–Construct abstract syntax tree (common)–Construct linear, lower-level representation (more common in later parts of a modern compiler)–Generate target code on the fly (1-pass compiler; not common in production compilers – can’t generate very good code in one pass)01/14/19 CS415 - Fall 2005 9Context-Free Grammars•Formally, a grammar G is a tuple <N,Σ,P,S> where–N a finite set of non-terminal symbols–Σ a finite set of terminal symbols–P a finite set of productions•A subset of N × (N U Σ )*–S the start symbol, a distinguished element of N •If not specified otherwise, this is usually assumed to be the non-terminal on the left of the first production01/14/19 CS415 - Fall 2005 10Standard Notations•a, b, c elements of Σ•w, x, y, z elements of Σ*•A, B, C elements of N•X, Y, Z elements of N U Σ, ,  elements of (N U Σ )*•A  or A ::=  if <A,  > in P01/14/19 CS415 - Fall 2005 11Derivation Relations (1) A  =>    iff A ::=  in P –derives•A =>* w if there is a chain of productions starting with A that generates w–transitive closure01/14/19 CS415 - Fall 2005 12Derivation Relations (2)•w A  =>lm w   iff A ::=  in P –derives leftmost A w =>rm   w iff A ::=  in P –derives rightmost•We will only be interested in leftmost and rightmost derivations – not random orderings01/14/19 CS415 - Fall 2005 13Languages•For A in N, L(A) = { w | A =>* w }•If S is the start symbol of grammar G, define L(G ) = L(S )01/14/19 CS415 - Fall 2005 14Reduced Grammars•Grammar G is reduced iff for every production A ::=  in G there is a derivation S =>* x A z => x  z =>* xyz –i.e., no production is useless•Convention: we will use only reduced grammars01/14/19 CS415 - Fall 2005 15Ambiguity•Grammar G is unambiguous iff every w in L(G ) has a unique leftmost (or rightmost) derivation–Fact: unique leftmost or unique rightmost implies the other•A grammar without this property is ambiguous–Note that other grammars that generate the same language may be unambiguous•We need unambiguous grammars for parsing01/14/19 CS415 - Fall 2005 16Example: Ambiguous Grammar for Arithmetic Expressionsexpr ::= expr + expr | expr - expr | expr * expr | expr / expr | intint ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9•Exercise: show that this is ambiguous–How? Show two different leftmost or rightmost derivations for the same string–Equivalently: show two different parse trees for the same string01/14/19 CS415 - Fall 2005 17Example (cont)•Give two leftmost derivations of 2+3*4 and show the parse treeexpr ::= expr + expr | expr - expr | expr * expr | expr / expr | intint ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 901/14/19 CS415 - Fall 2005 18Another example•Give two different derivations of 5+6+7expr ::= expr + expr | expr - expr | expr * expr | expr / expr | intint ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 901/14/19 CS415 - Fall 2005 19What’s going on here?•The grammar has no notion of precedence or associatively•Solution–Create a non-terminal for each level of precedence–Isolate the corresponding part of the grammar–Force the parser to recognize higher precedence sub-expressions first01/14/19 CS415 - Fall 2005 20Classic Expression Grammarexpr ::= expr + term | expr – term | termterm ::= term * factor | term / factor | factorfactor ::= int | ( expr )int ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 701/14/19 CS415 - Fall 2005 21Check: Derive 2 + 3 * 4•expr ::= expr + term | expr – term | term•term ::= term * factor | term / factor | factor•factor ::= int | ( expr )•int ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 701/14/19 CS415 - Fall 2005 22Check: Derive 5 + 6 + 7•Note interaction between left- vs


View Full Document

UVA CS 415 - Parsing

Download Parsing
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 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 Parsing 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?