The expression grammar E ==> E + E E ==> E *E E ==> ( E) E ==> NUM Lookahead + ( $ NUM ) could have the shift-reduce table at right: Here, "ACC" means "Accept" for a success, and "Err" means an error, since this combination cannot legally occur. Err -> Top stack terminal + 1 -> -> Err -> * * ** * * $ E * * X 4 So for example the expression 3* ( 4 + 5 ) would have a parse Stack Remaining input Comment $ 3 ( 4 + 5 ) $ $ so reduce $ E (E + 5 ) $ ( ) so reduce $ E (E+ E + ) so reduce $ E (E ( ) so shift (E) $ ) -> $ so reduce $ E * E $ -> $ so reduce $ E $ ACC $ so accept, done. * * * * * ) E * * 1b. Construct a shift-reduce table for the expressions in Atto-c. The terminals involved are $ high precedence binary operators + = == != 11 low precedence binary operator IDENT NUM (unary minus) ) ( You can treat the symbols on one row as a group, so your table will only need 14 rows and columns. The binary operators are listed in precedence order, so * / should be done before + - which are before = 6) && !( == 2) 1d. Operator precedence parsing: One way to compact a shift-reduce table into a convenient form is to assign numerical precedence levels to each symbol, an "F" precedence level to use for the stack terminal, and a "g" level to use for the lookahead symbol, so that I L is equivalent to f(T) > g(L) I = L is equivalent to f(T) g(L) Construct f and g values for your shift-reduce table (just put the values next to the symbols in your table). Don't worry about the Acc and Err entries. == Example: 8: 50 Lookahead 30 10 20 NUM + $ * 50 ( 2 ) f 1 $ ACC -> Err -> 11 + -> | + 1 | -> 1 (Err -> -> * 21 -> -> Err -> Err-> The expression grammar E ==> E + E E ==> E *E E ==> ( E) E ==> NUM Lookahead + ( $ NUM ) could have the shift-reduce table at right: Here, "ACC" means "Accept" for a success, and "Err" means an error, since this combination cannot legally occur. Err -> Top stack terminal + 1 -> -> Err -> * * ** * * $ E * * X 4 So for example the expression 3* ( 4 + 5 ) would have a parse Stack Remaining input Comment $ 3 ( 4 + 5 ) $ $ so reduce $ E (E + 5 ) $ ( ) so reduce $ E (E+ E + ) so reduce $ E (E ( ) so shift (E) $ ) -> $ so reduce $ E * E $ -> $ so reduce $ E $ ACC $ so accept, done. * * * * * ) E * * 1b. Construct a shift-reduce table for the expressions in Atto-c. The terminals involved are $ high precedence binary operators + = == != 11 low precedence binary operator IDENT NUM (unary minus) ) ( You can treat the symbols on one row as a group, so your table will only need 14 rows and columns. The binary operators are listed in precedence order, so * / should be done before + - which are before = 6) && !( == 2) 1d. Operator precedence parsing: One way to compact a shift-reduce table into a convenient form is to assign numerical precedence levels to each symbol, an "F" precedence level to use for the stack terminal, and a "g" level to use for the lookahead symbol, so that I L is equivalent to f(T) > g(L) I = L is equivalent to f(T) g(L) Construct f and g values for your shift-reduce table (just put the values next to the symbols in your table). Don't worry about the Acc and Err entries. == Example: 8: 50 Lookahead 30 10 20 NUM + $ * 50 ( 2 ) f 1 $ ACC -> Err -> 11 + -> | + 1 | -> 1 (Err -> -> * 21 -> -> Err -> Err->