編譯原理-上下無關(guān)文法和文法分析-預(yù)覽頁
【正文】 42 A grammar that generates a string with two distinct parse trees is called an ambiguous grammar. Two Ways to Deal with Ambiguity 1. Disambiguating rule ? State a rule that specifies in each ambiguous case which of the trees is correct. ? It corrects the ambiguity without changing and plicating the grammar. ? Syntactic structure of the language is not given by the grammar alone. 2. Change grammar into a form that forces the construction of a correct parse tree. ? In both cases we must decide which of the trees are correct. Precedence ? Some operations have precedence over other operations. – Multiplication has precedence over addition. ? To handle the precedence of operations in the grammar, we group the operators into groups of equal precedence. ? We must write a different rule for each precedence. Example exp exp op exp | (exp) | number op + | | * exp exp addop exp | term addop + | term term mulop term | factor mulop * factor (exp) | number Associativity ? Some operation (like subtraction) are left associative. – A series of subtraction operations is performed from left to right. ? exp exp addop exp | term – Recursion on both sides of the operator allows either side to match repetitions of the operator in a derivation. ? exp exp addop term | term – The right recursion is replaced with the base case, forcing the repetitive matches on the left side – Left recursion makes addition and subtraction left associative. Example exp exp addop term | term addop + | term term mulop factor | factor mulop * factor (exp) | number 34 3* 42 has a unique parse tree exp exp addop term term term mulop factor factor factor * number number number Dangling else Problem ? if (0) if (1) other else other has two parse trees with two meaning if (0) if (1) other else other and if (0) if (1) other else other 1. Modify the grammar. 2. Disambiguating rule: the most closely nested rule. statement ifstmt | other ifstmt if (exp) statement | if (exp) statement else statement exp 0 | 1 Inessential Ambiguity ? Sometimes a grammar may be ambiguous and yet always produce unique abstract syntax trees. ? Example: ( a + b ) + c = a + ( b + c ) Extended BNF Notation ? { } repetitions A β { α } and A { α } β ? [ ] optional constructs statement ifstmt | other ifstmt if (exp) statement [ else statement ] exp 0 | 1 statement ifstmt | other ifstmt if (exp) statement | if (exp) statement else statement exp 0 | 1 Homework ? , , ,
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1