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