Follow

I have trouble understanding this description of the shift-reduce parsing as given by Niklaus Wirth in his "Compiler Construction" book ethoberon.ethz.ch/WirthPubl/CB page 23.
The example does not seem to be logical at all. Is the process depicted correctly? Why the first term ends up being T and not E? @OCRbot

OCR Output (chars: 2041) 

@saper
43. Bottom-up Parsing

‘Bosh the wcusivedescet and tble-diven parsing shown hae re echnigues bse on the principe of
topedown parsing. The primary gol isto show tha the texto be analysed i derivable form te start
‘simbol Any sonicrmial synbols encomicred ate considered as aubgoas. The paring proces
onsets te syak e begining wih the tart syrbol a i ot, that he topo diction

However, iti abo posible to proceed aecrding to a complementary principe inthe botomup
sletion The txts fead witout pursuit ofa specifi gal Aer each step a et checks whether he
‘eal subsequence comesponds to soe senna erst ha, the right pat of a production this 5
the ease, the read subsequence is replaced by the coesponding novicninal symbol. The recopaion
process again consists of eonsecuive saps of which thereat wo distal Kinds

1. Shiting themes input sb

oa stack shit ep),
2 Reducing stacked Sequence of symbols ata single noatrmiaal symbol accnding to production
leeduce stp)

Parsing in the baton-up diction sao called shif-redace parsing. The syeactic const ate built
up and den educed: the sy tre grows fom the btn othe tp (Kau, 1968, Ao apd Ulla,
1577: Kasten, 190,

(Once asin, we demonsate the proces wih the example of simple expressions. Let the synthe as
fallow!

Es expression
Te tem
Fe factor

au let the sentence to be recopsizad be * (+2). onder to dla the proces, thers Source
texts show othe sgh, whetcas to the Lf the nly empy = sequence of ecogized comstucs
Tt. Ath ale he ets Sand Windia te Kind of step ake

xryta
s x syoa)
RF soo
ROT yon
sot won)
som yiay
Shy a
Rote 13
Ror ta
RTE +2
STE 2
S TEr2 ,
Ro OTMESE >
RO OTMEST ,
RTE ,
STM

ROT

Rot

RoE

A the end, the iil source txt is seduced tothe stat symbol E, which hee would beter be elle he
Stop symbol As mentioned eer, the intermediate store To the let stack

In analogy to this representation, the process of parsing the same input aesording to the top-down
principles showa blow. The wo kinds of ssp ate deote by M tach) abd (prac, expan) The
ut symbols

2

Sign in to participate in the conversation
Mastodon

Server run by the main developers of the project 🐘 It is not focused on any particular niche interest - everyone is welcome as long as you follow our code of conduct!