DOC PREVIEW
UT Arlington CSE 3302 - Syntax

This preview shows page 1-2 out of 5 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 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 5 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

1/22/20081CSE 3302 Programming LanguagesSyntax (cont )Chengkai Li, Weimin HeSpring 2008Syntax (cont.)Lecture 4 – Syntax (Cont.), Spring 2008 1CSE3302 Programming Languages, UT-Arlington ©Chengkai Li, Weimin He, Weimin He 2008What 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?i.e., is the string a legal program in the language?• In other words, to construct a parse tree for the token string.Lecture 4 – Syntax (Cont.), Spring 2008 2CSE3302 Programming Languages, UT-Arlington ©Chengkai Li, Weimin He, Weimin He 2008What’s 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 4 – Syntax (Cont.), Spring 2008 3CSE3302 Programming Languages, UT-Arlington ©Chengkai Li, Weimin He, Weimin He 2008Exampleexpr → expr + expr | expr ∗ expr | ( expr ) | numbernumber → number digit | digitdigit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9expreprparse treeleftmost derivationexprexprnumberdigit3*exprnumberdigit4exprnumberdigit5expr+numberdigit3numberdigit4numberdigit5exprexpr+*expr exprLecture 4 – Syntax (Cont.), Spring 2008 4CSE3302 Programming Languages, UT-Arlington ©Chengkai Li, Weimin He, Weimin He 2008What’s 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.)exprexpr1expr2+expr.val = expr1.val + expr2.val Lecture 4 – Syntax (Cont.), Spring 2008 5CSE3302 Programming Languages, UT-Arlington ©Chengkai Li, Weimin He, Weimin He 2008Relationship among language, grammar, parser• Chomsky Hierarchyhttp://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 parserA 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 parserLecture 4 – Syntax (Cont.), Spring 2008 6CSE3302 Programming Languages, UT-Arlington ©Chengkai Li, Weimin He, Weimin He 20081/22/20082Ambiguity• Ambiguous grammar: There can be multiple parse trees for the same sentence (program)– In other words, multiple leftmost derivations.Wh i i b d?•Why is it bad?– Multiple meaningsLecture 4 – Syntax (Cont.), Spring 2008 7CSE3302 Programming Languages, UT-Arlington ©Chengkai Li, Weimin He, Weimin He 2008Ambiguity• Was this ambiguous?number → number digit | digitdigit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9• How about this?expr → expr - expr | numberLecture 4 – Syntax (Cont.), Spring 2008 8CSE3302 Programming Languages, UT-Arlington ©Chengkai Li, Weimin He, Weimin He 2008Deal with Ambiguity• Unambiguous Grammar– Rewrite the grammar to avoid ambiguity.Lecture 4 – Syntax (Cont.), Spring 2008 9CSE3302 Programming Languages, UT-Arlington ©Chengkai Li, Weimin He, Weimin He 2008Example of Ambiguity: Precedenceexpr → expr + expr | expr ∗ expr | ( expr ) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9parse tree 1Two different parse tress for expression 3+4*5exprparse tree 2exprexpr3*expr4expr5expr+exprexpr5expr*+3expr4exprLecture 4 – Syntax (Cont.), Spring 2008 10CSE3302 Programming Languages, UT-Arlington ©Chengkai Li, Weimin He, Weimin He 2008Eliminating Ambiguity for Precedence• Establish “precedence cascade”: using different structured names for different constructs, adding grammar rules.– Higher precedence : lower in cascadeexpr → expr + expr | termterm → term ∗ term | ( expr ) | numberexpr → expr + expr | expr ∗ expr | ( expr ) | numberLecture 4 – Syntax (Cont.), Spring 2008 11CSE3302 Programming Languages, UT-Arlington ©Chengkai Li, Weimin He, Weimin He 2008Example of Ambiguity: Associativityexpr → expr - expr | ( expr ) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9exprparse tree 1Two different parse tress for expression 5-2-1exprparse tree 2expr.val = 4expr.val = 2expr5-expr2expr1expr-expr1expr--5expr2exprp- is right-associative, which is against common practice in integer arithmetic- is left-associative, which is what we usually assumeLecture 4 – Syntax (Cont.), Spring 2008 12CSE3302 Programming Languages, UT-Arlington ©Chengkai Li, Weimin He, Weimin He 20081/22/20083Associativity• Left-Associative: + - * /• Right-Associative: =What is meant by a=b=c=1?Lecture 4 – Syntax (Cont.), Spring 2008 13CSE3302 Programming Languages, UT-Arlington ©Chengkai Li, Weimin He, Weimin He 2008Eliminating Ambiguity for Associativity• left-associativity: left-recursionexpr→expr-term|termexpr → expr - expr | ( expr ) | numberexpr→exprterm| termterm → (expr) | number• right-associativity: right-recursionexpr → expr = expr | a | b | cexpr → term = expr | termterm → a | b | cLecture 4 – Syntax (Cont.), Spring 2008 14CSE3302 Programming Languages, UT-Arlington ©Chengkai Li, Weimin He, Weimin He 2008Putting Togetherexpr → expr - expr | expr / expr | ( expr ) | numbernumber → number digit | digitdigit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9We want to make - left-associative and /has precedence over -expr → expr - term | termterm → term / factor |factorfactor → ( expr )| numbernumber → number digit | digitdigit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9pLecture 4 – Syntax (Cont.), Spring 2008 15CSE3302 Programming Languages, UT-Arlington ©Chengkai Li, Weimin He, Weimin He 2008Example of Ambiguity: Dangling-Elsestmt → if( expr ) stmt| if( expr ) stmt else stmt| other-stmtTwo different parse trees for “if( expr ) if( expr ) stmt else stmt”parse tree 1parse tree 2stmtstmt(expr)ififstmt(expr)parse tree 1parse tree 2stmtelsestmt(expr)ififstmt(expr)stmtstmtelseLecture 4 – Syntax (Cont.), Spring 2008 16CSE3302 Programming Languages, UT-Arlington ©Chengkai Li, Weimin He, Weimin He 2008Eliminating Dangling-Elsestmt → matched_stmt| unmatched_stmtmatched_stmt → if( expr ) matched_stmt else matched_stmt| other-stmtunmatched_stmt → if( expr ) stmt|if()thd t tlthd t t| if(expr)matched_stmtelse unmatched_stmtLecture 4 – Syntax


View Full Document

UT Arlington CSE 3302 - Syntax

Documents in this Course
Smalltalk

Smalltalk

11 pages

Syntax

Syntax

5 pages

JAVA

JAVA

57 pages

Semantics

Semantics

41 pages

Control

Control

74 pages

Load more
Download Syntax
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 Syntax 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 Syntax 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?