Parsare bottom-up

Parsarea bottom-up este o strategie de analiză de date necunoscute care încearcă să identifice mai întâi unitățile fundamentale, iar apoi să creeze structuri de ordin mai înalt din ele. Se încearcă construirea de arbori în sus, către simbolul de start. Această strategie apare și în limbajul natural, și în limbajele de programare. În informatică, parsarea bottom-up este cunoscută și ca "parsare deplasare-reducere".

Aceasta funcționează astfel:

1. Se începe cu propoziția de parsat drept formă propozițională inițială
2. Până când forma propozițională este simbolul de start execută:
   1. Scanează intrarea până când recunoști ceva care corespunde părții drepte a unei reguli de producție - acțiune numită deplasare
   2. Aplică o regulă de producție în sens invers (adică se înlocuiește partea dreaptă a unei reguli cu partea stângă a ei în forma propozițională - acțiune numită reducere)

La pasul 2.1 de mai sus "deplasăm" simbolurile de intrare pe stivă în timp ce le citim de pe bandă; de aceea parserul care operează aplicând pașii 2.1 și 2.2 se numesc parsere deplasare-reducere.

Un parser deplasare-reducere este implementat cel mai adesea folosind o stivă, unde se acționează în felul următor:

• se începe cu propoziția de parsat în vârful stivei
• operația de "deplasare" corespunde introducerii simbolului curent în stivă
• operația de "reducere" are loc când avem în vârful stivei partea dreaptă a unei reguli. Se șterge vârful stivei și se înlocuiește cu partea stângă a regulei corespunzătoare.

Figura 1.

 Fie limbajul:
 Propoziție   --> GrupSubstantival GrupVerbal
 GrupSubstantival --> Articol Substantiv
 GrupVerbal --> Verb | Adverb Verb
 Articol        --> un | o | ...
 Verb       --> latră | cântă | ...
 Substantiv       --> câine | pisică | ...

 Și intrarea:
 un câine latră

 Atunci parsarea bottom-up este:
Stivă                           Secvență de intrare
()                              (un câine latră)
(un)                            (câine latră)      DEPLASARE cuvânt pe stivă
(Articol)                       (câine latră)      REDUCERE folosind o regulă a gramaticii
(Articol câine)                 (latră)            DEPLASARE..
(Articol Substantiv)            (latră)            REDUCERE..
(GrupSubstantival)              (latră)            REDUCERE
(GrupSubstantival latră)        ()                 DEPLASARE
(GrupSubstantival Verb)         ()                 REDUCERE
(GrupSubstantival GrupVerbal)   ()                 REDUCERE
(Propoziție)                    ()                 SUCCES

Fie limbajul:
<Expresie> --> <Termen>
<Termen>       --> <Factor> | <Factor> * <Termen>
<Factor>     --> [ <Expresie ] | 0...9

()                       (2 * [ 1 + 3 ])  DEPLASARE
(2)                      (* [ 1 + 3 ])    REDUCERE
(<Factor>)               (* [ 1 + 3])     DEPLASARE
(<Factor> *)             ([ 1 + 3])       DEPLASARE
(<Factor> * [)           (1 + 3])         DEPLASARE
(<Factor> * [ 1)         (1 + 3])         REDUCERE (de 2 ori..)
(<Factor> * [ <Termen>)     (+ 3 ])         DEPLASARE (de 2 ori)
(<Factor> * [ <Termen> + 3) ( ])            REDUCERE (de 3 ori)
(<Factor> * [ <Termen> + <Expresie>) ( ]) REDUCERE
(<Factor> * [ <Expresie>) ( ])          DEPLASARE
(<Factor> * [ <Expresie> ]) ()          REDUCERE
(<Factor> * <Factor>)     ()              REDUCERE
(<Factor> * <Termen>)       ()              REDUCERE
(<Term>)                  ()              REDUCERE
(<Expresie>)            ()              SUCCES

Din punctul de vedere al deciziilor care trebuie luate, într-un parser top-down decizia principală este care regulă de producție trebuie aleasă. Într-un parser bottom-up, există două decizii:

1. Deplasăm un simbol nou sau reducem printr-o regulă?
2. Dacă reducem, prin ce regulă reducem?

• Parsare top-down