Ang pangunahing pagkakaiba sa pagitan ng top down at bottom up na pag-parse ay ang top down na parsing ay nagsasagawa ng pag-parse mula sa staring na simbolo hanggang sa input string habang ang bottom down na parsing ay nagsasagawa ng parsing mula sa input string hanggang sa panimulang simbolo. Higit pa rito, isa pang mahalagang pagkakaiba sa pagitan ng top down at bottom up parsing ay ang top down parsing ay gumagamit ng left most derivation at bottom down parsing ay gumagamit ng right most derivation.
Nakakatulong ang mga high-level na wika sa pagsulat ng mga computer program. Ang mga ito ay mas madaling maunawaan ng programmer ngunit hindi ng computer. Samakatuwid, ang mataas na antas na programa ay nagko-convert sa machine code. Ang gawain ng compiler ay i-convert ang nababasa ng tao na source code sa machine readable machine code. Dumadaan ang isang program sa ilang hakbang upang ma-convert sa machine code. Ang buong prosesong ito ay tinatawag na Language processing System. Isa na rito ang compilation. Ang syntax analyzer o ang parser ay nasa compiler, at ginagawa nito ang gawain sa pag-parse.
Ano ang Top Down Parsing?
Ang bawat programming language ay may set ng mga panuntunan upang kumatawan sa wika. Kinukuha ng syntax analyzer o ng parse ang input string at sinusuri kung ito ay ayon sa mga paggawa ng grammar. Sa madaling salita, dapat gawin ng grammar ang string na iyon gamit ang parse tree.
Sa top down parsing, ang pag-parse ay nangyayari mula sa panimulang simbolo at maaabot ang ibinigay na input string. Isaalang-alang ang sumusunod na mga tuntunin sa paggawa ng gramatika. Ang input string (w) ay cad.
S -> cAd
A -> ab /a
Ang parse tree pagkatapos magsagawa ng top down parsing ay ang mga sumusunod.
Figure 01: Parse Tree 1 gamit ang Top Down Parsing
Ang S ay gumagawa ng c A d at ang A ay gumagawa ng isang b. Ang string ay cabd. Hindi ito ang kinakailangang string. Kaya, kailangang gawin ang backtracking, na kung saan ay ang paggamit ng iba pang mga alternatibo.
Katulad nito, ang S ay gumagawa ng c A d. Ang paglalapat ng ibang opsyon para sa A ay magbibigay ng a. Ngayon ay nagbibigay ito ng kinakailangang string. Samakatuwid, tinatanggap ng parser ang input string na ito. Ang parse tree pagkatapos magsagawa ng top down parsing ay ang mga sumusunod.
Figure 02: Parse Tree 2 na may Top Down Parsing
Kapag ang input string (w) ay abbcde
Isaalang-alang ang sumusunod na mga panuntunan sa paggawa ng grammar.
S -> aABe
A -> Abc/b
B -> d
Sa itaas pababang pag-parse, S -> aABe (Pinapalitan ang A -> Abc)
S -> aAbcBe (Pinapalitan ang A -> b)
S -> abbcBe (Pinapalitan ang B ->d)
S -> abbcde
Ang pagpapalit ay nagsisimula sa kaliwang pinaka variable muna at pagkatapos ay sa susunod na kanang posisyon at iba pa. Samakatuwid, ito ay sumusunod sa isang kaliwang paraan ng derivation. Higit pa rito, mahalagang magpasya kung anong panuntunan sa produksyon ang pipiliin kapag may variable.
Ano ang Bottom Up Parsing?
In bottom up parsing nangyayari sa ibang paraan. Ang pag-parse ay nangyayari mula sa input string hanggang sa panimulang simbolo. Isaalang-alang ang sumusunod na mga panuntunan sa paggawa ng grammar at hayaang ang input string ay w ɛ cad
S -> cAd
A -> ab /a
Ang parse tree pagkatapos magsagawa ng bottom up parsing ay ang mga sumusunod.
Figure 03: Parse Tree na may Bottom Up Parsing
Ang ibinigay na string ay cad. Ang a ay nabuo ng A. Ang c, A at d ay nagsasama upang makuha ang panimulang simbolo na S.
Kapag ang input string(w) ay abbcde
Isaalang-alang ang sumusunod na mga panuntunan sa paggawa ng grammar.
S -> aABe
A -> Abc/b
B -> d
Sa bottom up parsing, S -> aABe (Pinapalitan ang B ->d)
S -> aAde (Pinapalitan ang A -> Abc)
S -> aAbcde (Substuting A -> b)
S -> abbcde
Ang pagpapalit ay nagsisimula sa pinakakanang pinakavariable muna at pagkatapos ay lilipat sa susunod na kaliwang posisyon at iba pa. Samakatuwid, ito ay sumusunod sa isang left mot derivation method.
Ano ang Pagkakaiba sa pagitan ng Top Down at Bottom Up Parsing?
Ang Top-down na pag-parse ay isang diskarte sa pag-parse na unang tumitingin sa pinakamataas na antas ng parse tree at ginagawa ito pababa sa parse tree sa pamamagitan ng paggamit ng mga panuntunan ng isang pormal na grammar. Ang Bottom up parsing ay isang diskarte sa pag-parse na unang tumitingin sa pinakamababang antas ng parse tree at gumagana sa parse tree sa pamamagitan ng paggamit ng mga panuntunan ng isang pormal na grammar. Ang pag-parse ay nangyayari mula sa panimulang simbolo hanggang sa input string, sa itaas pababa na pag-parse. Sa kabilang banda, nangyayari ang pag-parse mula sa input string hanggang sa panimulang simbolo, sa bottom up parsing.
Higit pa rito, ang pangunahing desisyon sa top down parsing ay ang piliin kung anong production rule ang gagamitin para mabuo ang string habang ang pangunahing desisyon sa bottom down parsing ay ang piliin kung kailan gagamit ng production rule para bawasan ang string sa makuha ang panimulang simbolo. Bukod dito, ang top down parsing ay gumagamit ng left most derivation at bottom down parsing ay gumagamit ng right most derivation.
Buod – Top Down vs Bottom Up Parsing
Ang pagkakaiba sa pagitan ng top down at bottom up na pag-parse ay ang top down na pag-parse ay nagsasagawa ng pag-parse mula sa staring na simbolo hanggang sa input string habang ang bottom down na pag-parse ay nagsasagawa ng pag-parse mula sa input string hanggang sa panimulang simbolo.
