CSE 3302 Programming Languages - CSE SERVICES

CSE 3302 Programming Languages Syntax (cont.) Chengkai Li Fall 2007 Lecture 3 - Syntax, Fall 2007 CSE3302 Programming Languages, UT-Arlington Chengkai Li, 2007 1 Review of Lecture 3 Scanning and Parsing Lexical Structure: The structure of tokens (words) Syntactical Structure: The structure of programs regular expressio n charact er stream

Lecture 3 - Syntax, Fall 2007 scanner (lexical analysis) grammar token strea m parser (syntax analysis) CSE3302 Programming Languages, UT-Arlington Chengkai Li, 2007 pars e tree 2 Automatic Tools

regular expression description of the tokens (lex/flex) scanner of a language Example: Figure 4.1 (page 82) Context-Free Grammar (Yacc/Bison) parser Example: Figure 4.13 (page 112) Lecture 3 - Syntax, Fall 2007 CSE3302 Programming Languages, UT-Arlington Chengkai Li, 2007 3 Review of Lecture 3 Tokens: Reserved words (keywords) Literals/constants Special symbols Identifiers Principle of Longest Substring The longest possible string of characters is collected into a single

token. The principle requires that tokens are separated by white spaces. Lecture 3 - Syntax, Fall 2007 CSE3302 Programming Languages, UT-Arlington Chengkai Li, 2007 4 Review of Lecture 3 Context-Free Grammar (Backus-Naur Forms (BNF)) Grammar rules (productions): left-hand side: single nonterminal nonterminals (structured names) terminals (tokens) start symbol Language: the set of token strings that can be produced by derivation from the start symbol Derivation: number number digit number digit digit digit digit digit 2 digit digit 23 digit 234 Lecture 3 - Syntax, Fall 2007

CSE3302 Programming Languages, UT-Arlington Chengkai Li, 2007 5 Review of Lecture 3 Derivations: different derivations for the same syntactic structure. Parse trees: capture intrinsic structure, more intuitive, still tedious. Abstract Syntax Tress (Syntax Trees): Remove ``unnecessary symbols, meanwhile completely determine syntactic structure. number number number digit digit 3 4 3

2 page 91 2 Lecture 3 - Syntax, Fall 2007 4 digit CSE3302 Programming Languages, UT-Arlington Chengkai Li, 2007 6 Topics Today Topics: Ambiguities in Grammar Parsing Techniques Intuitive analysis and conclusion No formal theorems and rigorous proofs More details: compilers, automata theory Lecture 3 - Syntax, Fall 2007

CSE3302 Programming Languages, UT-Arlington Chengkai Li, 2007 7 What is Parsing? Given a grammar and a token string: determine if the grammar can generate the token string? i.e., is the string a legal program in the language? In other words, to construct a parse tree for the token string. Lecture 3 - Syntax, Fall 2007 CSE3302 Programming Languages, UT-Arlington Chengkai Li, 2007 8 Whats significant about parse tree? A parse tree gives a unique syntactic structure Leftmost, rightmost derivation

There is only one leftmost derivation for a parse tree, and symmetrically only one rightmost derivation for a parse tree. Lecture 3 - Syntax, Fall 2007 CSE3302 Programming Languages, UT-Arlington Chengkai Li, 2007 9 Example expr expr + expr | expr expr | ( expr ) | number number number digit | digit digit 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 parse tree expr expr leftmost derivation expr + number

expr digit number 3 * expr expr + expr number expr number

digit number digit digit 4 5 Lecture 3 - Syntax, Fall 2007 expr 3 CSE3302 Programming Languages, UT-Arlington Chengkai Li, 2007 * expr number

digit digit 4 5 10 Whats significant about parse tree? A parse tree has a unique meaning, thus provides basis for semantic analysis. (Syntax-directed semantics: semantics are attached to syntactic structure.) expr expr1 Lecture 3 - Syntax, Fall 2007 + expr.val = expr1.val + expr2.val

expr2 CSE3302 Programming Languages, UT-Arlington Chengkai Li, 2007 11 Relationship among language, grammar, parser Chomsky Hierarchy http://en.wikipedia.org/wiki/Chomsky_hierarchy A language can be described by multiple grammars, while a grammar defines one language. A grammar can be parsed by multiple parsers, while a parser accepts one grammar, thus one language. Should design a language that allows simple grammar and efficient parser For a language, we should construct a grammar that allows fast parsing Given a grammar, we should build an efficient parser Lecture 3 - Syntax, Fall 2007 CSE3302 Programming Languages, UT-Arlington Chengkai Li, 2007 12

Ambiguity Ambiguous grammar: There can be multiple parse trees for the same sentence (program) In other words, multiple leftmost derivations. Why it is bad? Multiple meaning Multiple derivation can be ok, but multiple leftmost derivation is the same as multiple parse tree. Lecture 3 - Syntax, Fall 2007 CSE3302 Programming Languages, UT-Arlington Chengkai Li, 2007 13 Ambiguity Was this ambiguous? number number digit | digit digit 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 How about this? expr expr + expr | number

Lecture 3 - Syntax, Fall 2007 CSE3302 Programming Languages, UT-Arlington Chengkai Li, 2007 14 Deal with Ambiguity disambiguating rules: Use semantics in determining which parse tree to construct or unambiguous grammar Rewrite the grammar to avoid ambiguity. Lecture 3 - Syntax, Fall 2007 CSE3302 Programming Languages, UT-Arlington Chengkai Li, 2007 15 Example of Ambiguity: Precedence expr expr + expr | expr expr | ( expr ) | 0 | 1 | 2 | 3 | 4 |

5|6|7|8|9 Two different parse tress for expression 3+4*5 parse tree 2 parse tree 1 expr expr expr 3 expr + * expr expr 5

expr 4 Lecture 3 - Syntax, Fall 2007 * expr 5 expr + 3 CSE3302 Programming Languages, UT-Arlington Chengkai Li, 2007 expr 4 16 Eliminating Ambiguity for

Precedence Establish precedence cascade: using different structured names for different constructs, adding grammar rules. Higher precedence : lower in cascade expr expr + expr | expr expr | ( expr ) | number expr expr + expr | term term term term | ( expr ) | number Lecture 3 - Syntax, Fall 2007 CSE3302 Programming Languages, UT-Arlington Chengkai Li, 2007 17 Example of Ambiguity: Associativity expr expr - expr | ( expr ) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |9 Two different parse tress for expression parse tree 1 expr expr 5

5-2-1 parse tree 2 expr expr.val = 2 expr.val = 4 expr - - expr expr 1 expr 2 - expr 1 - is right-associative, which is against

common practice in integer arithmetic Lecture 3 - Syntax, Fall 2007 expr - expr 5 2 - is left-associative, which is what we usually assume CSE3302 Programming Languages, UT-Arlington Chengkai Li, 2007 18 Associativity Left-Associative: + - * / Right-Associative: = What is meant by a=b=c=1? Lecture 3 - Syntax, Fall 2007

CSE3302 Programming Languages, UT-Arlington Chengkai Li, 2007 19 Eliminating Ambiguity for Associativity left-associativity: left-recursion expr expr - expr | ( expr ) | number expr expr - term | term term (expr) | number right-associativity: right-recursion expr expr= expr | a | b | c ? Lecture 3 - Syntax, Fall 2007 CSE3302 Programming Languages, UT-Arlington Chengkai Li, 2007 20 Putting Together

expr expr + expr | expr expr | ( expr ) | number number number digit | digit digit 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 We want to make + left-associative, and * has higher precedence than + ? Lecture 3 - Syntax, Fall 2007 CSE3302 Programming Languages, UT-Arlington Chengkai Li, 2007 21 Example of Ambiguity: Dangling-Else stmt if( expr ) stmt | if( expr ) stmt else stmt | other-stmt Two different parse trees for if( expr ) if( expr ) stmt else parse tree 1 parse tree 2 stmt stmt stmt

if if if (expr) (expr) Lecture 3 - Syntax, Fall 2007 stmt else (expr) stmt stmt stmt else stmt if

(expr) CSE3302 Programming Languages, UT-Arlington Chengkai Li, 2007 stmt 22 Eliminating Dangling-Else stmt matched_stmt | unmatched_stmt matched_stmt if( expr ) matched_stmt else matched_stmt | other-stmt unmatched_stmt if( expr ) stmt | if( expr ) matched_stmt else unmatched_stmt Lecture 3 - Syntax, Fall 2007 CSE3302 Programming Languages, UT-Arlington Chengkai Li, 2007 23

Recently Viewed Presentations

  • 1èrePARTIE: ORGANISATION DES EXAMENS

    1èrePARTIE: ORGANISATION DES EXAMENS

    Implication personnelle dans le développement du judo jujitsu justifiée par le candidat par attestation délivrée par le CORG et attestant d'au moins un titre ou une fonction depuis son dernier grade parmi : - Enseignant en exercice, - Commissaire sportif...
  • Status of States Alaska As of January 6,

    Status of States Alaska As of January 6,

    Alaska. California. Idaho. Oregon. Washington. Montana. Wyoming. Utah. Colorado. Arizona. New Mexico. Texas. Oklahoma. Kansas. Nebraska. South Dakota. North Dakota ...
  • Multiplying Decimals Using Models Alignment Lesson

    Multiplying Decimals Using Models Alignment Lesson

    Which base ten piece would you use to show one hundredth? Why? How many hundredths does a rod represent? How would you write 10 hundredths using decimal notation? Do 0.10 and 0.1 represent the same number? Explain why 0.10 and...
  • Market Structure - BioJuncture

    Market Structure - BioJuncture

    Abnormal profit. Q2. Because the model assumes perfect knowledge, the firm gains the advantage for only a short time before others copy the idea or are attracted to the industry by the existence of abnormal profit. If new firms enter...
  • Planning Strategically: How to Stay Competitive

    Planning Strategically: How to Stay Competitive

    Law Firm Finance: Is it Really a New Normal? ... many of the "old ways" may no longer work and firms need to become more entrepreneurial and flexible to take advantage of the new economy. Well, this line of thinking...
  • MILLENNIALS - WordPress.com

    MILLENNIALS - WordPress.com

    As Gerações do Séc XX E XXI - Breve análise. Esta é a época da globalização, da ida do homem à lua, do capitalismo e do consumismo mas também é aqui que nasce o movimento Hippie, a contestação política e...
  • Title Master style Arial Bold 34pt.

    Title Master style Arial Bold 34pt.

    The theme of "The Most Dangerous Game" is that people who appear to be civilized may really be savage and bloodthirsty. Theme vs. Moral The moral of a story is a rule of conduct or a practical lesson about life....
  • Metropolitan Golf Club Barn Owls Metropolitan Golf Club

    Metropolitan Golf Club Barn Owls Metropolitan Golf Club

    Metropolitan Golf Club Barn Owls Metropolitan Golf Club Barn Owls The trees to the right of the 6th Green is home to our new barn owls. The owls came from the Spier rehabilitation program.