CS 345 slide 25 Spring 200521 January 2005An ambiguous expression grammar:E ::= E – E | E * E | ( E ) | num (G1)Two derivations:E E – E E – E * E …E E * E E – E * E …Two expressions, same string.Their parse trees:EE –3EE*4E5E*E5EE –3E4…and their abstract syntax trees–3*45*5–34CS 345 slide 26 Spring 200521 January 2005This ambiguity could be removed by either • adding a disambiguating rule or • revising the grammarWe revise the grammar:E ::= E – E | T (G2)T ::= T * T | ( E ) | numNow the only tree that corresponds to3 – 4 * 5isEE –3ET*4T5TTThe revised grammar G2 gives (*) a higher precedencethan (–).CS 345 slide 27 Spring 200521 January 2005But G2 is still ambiguous: Consider the expression3 – 4 – 5which can be derived two ways:E E – E 3 – E 3 – E – E 3 – 4 – E 3 – 4 – 5E E – E E – 5 T – E – 5 E – 4 – 5 3 – 4 – 5EE–EEE–345E–EE–E34E53 – (4 – 5)= 3 – (–1)= 4(3 – 4) – 5= –1 – 5= – 6In other words, (–) can be either right-associative orleft-associative —and so can (*).CS 345 slide 28 Spring 200521 January 2005Again we can revise the grammar, to eitherE ::= E – T | T (G3)T ::= T * F | F left-recursiveF ::= ( E ) | numorE ::= T – E | T (G4)T ::= F * T | F right-recursiveF ::= ( E ) | numUsing G3:EET–ET–43TF5FF Using G4: FT–E–453TETEFFSo… left-recursion yields left-associativity right-recursion yields right-associativity.CS 345 slide 29 Spring 200521 January 2005Alternative grammar notationsEBNF (Extended BNF) —one example: more meta-notation shorter productions• nonterminals begin with Uppercase letters(hence there’s no need for )• grouping uses ( )• alternatives are separated by |• repetitions (zero or more) are enclosed in { }(replacing many recursions)• options are enclosed in [ ]• terminals that are also grammar symbols (forexample, ‘[’ ) are enclosed in single quotes ‘ ’Example: integer expressions againExpression ::= Term { ( + | - ) Term }Term ::= Factor { ( * | / ) Factor }Factor ::= ‘(’ Expression ‘)’ | Name | NumeralName ::= Letter { Letter | Digit }Numeral ::= Digit { Digit }Letter ::= a | b | … | z | ‘A’ | … | ‘Z’Digit ::= 0 | 1 | 2 | … | 9CS 345 slide 30 Spring 200521 January 2005How is operators’ associativity specified in an EBNFgrammar?Example:E ::= T { + T }Does this make (+) left-associative or right-associative?Answer: Yes (i.e., it’s ambiguous).The {…} notation obscures operators’ associativity,so a grammar using it may need an “extra-syntactic”rule to eliminate the ambiguity.The conventional associativity rule for EBNF:E ::= T { + T } is understood to mean that (+) isleft-associativeE ::= { T + } T is understood to mean that (+) isright-associativeThe ambiguity can be avoided by using recursion:E ::= [ E + ] T (+) is left-associativeE ::= T [ + E ] (+) is right-associativeCS 345 slide 31 Spring 200521 January 2005Syntax charts (“railroad diagrams”)ExpressionTerm+–Each production a path through the chart.FactorExpressionNameNumeral( )…etc.How could syntax charts show associativity?Expression+–ExpressionTermCS 345 slide 32 Spring 200521 January 2005Context-sensitive grammarsIn a CFG, selection among a nonterminal’s produc-tions is unconstrained, but in a CSG, the selectionmay depend on the symbols on either side of thenonterminal.Example of a context-sensitive grammar:S ::= a b c | a X b cX b ::= b XX c ::= Y b c ca Y ::= a a | a a Xb Y ::= Y bNote the terminals appearing in some productions’left-hand sides. A derivation:S a X b c a b X c a b Y b c c a Y b b c c a a b b c cThis grammar generates a language of sequencescontaining equal numbers of a’s, b’s, and c’s, in thatorder. It has been shown that no CFG can producethis language.Although CSGs are more powerful than CFGs, thispower has not been found useful for defining thesyntax of programming
View Full Document
Unlocking...