Chapter 5
Bottom-Up
Parsing
Zhang Jing, Wang HaiLing
College of Computer Science & Technology
Harbin Engineering University
zhangjing@hrbeu.edu.cn
2
Shift-reduce parsing attempts to construct a parse tree for
an input string beginning at the leaves which can be
considered as bottom and working up towards the root,
know as top. We can think of this process as one of
reducing which reduce a string to the start symbol. At
each reduction step, a particular substring matches the
right side of production and is replaced by the symbol on
the left of the production. An easy-to-implement form of
shift-reduce parsing is operator-precedence parsing. A
much more general method of shift-reduce parsing is
LR(0) and SLR(1) parsing. The position of bottom-up
syntax analyzer in compiler is shown by Fig.5.1.
zhangjing@hrbeu.edu.cn
3
zhangjing@hrbeu.edu.cn
4
5.1 Operator-precedence Parsing
If a grammar has the property that has two
adjacent nonterminals, we can easily construct
efficient shift-reduce parsers by hand, the easy-to-
implement parsing technique called operator-
precedence parsing. The technique is described as
a manipulation on tokens without any reference to
any grammar. Once we finish building an
operator-precedence parser from a grammar, we
may efficiently ignore the grammar, using the
nonterminals on the stack only as placeholders for
attributes associated with the nonterminals.
zhangjing@hrbeu.edu.cn
5
5.1.1 Relation between pairs of
operator precedence
There are three relations between pairs of ope
rator precedence, “a” and “b” belongs to VT ,
U, V and R belong to VN ,
then their operator precedence are
