Shift-reduce parser
શિફ્ટ-રિડ્યુસ પાર્સર એ કોમ્પ્યુટર ભાષાઓ અને વ્યાકરણ દ્વારા ઔપચારિક રીતે વ્યાખ્યાયિત અન્ય સંકેતો માટે કાર્યક્ષમ, ટેબલ-સંચાલિત બોટમ-અપ પાર્સિંગ પદ્ધતિઓનો વર્ગ છે. પ્રોગ્રામિંગ ભાષાઓને પદચ્છેદન કરવા માટે સૌથી વધુ ઉપયોગમાં લેવાતી પદચ્છેદન પદ્ધતિઓ, એલ. આર. પદચ્છેદન અને તેની વિવિધતાઓ, શિફ્ટ-રિડ્યુસ પદ્ધતિઓ છે. એલ. આર. પદચ્છેદનની શોધ પહેલાં ઉપયોગમાં લેવાતા પ્રાધાન્યતા પદચ્છેદન પણ સ્થળાંતર-ઘટાડાની પદ્ધતિઓ છે. બધા શિફ્ટ-રિડ્યુસ પાર્સર્સ સમાન બાહ્ય અસરો ધરાવે છે, વૃદ્ધિશીલ ક્રમમાં જેમાં તેઓ પાર્સ ટ્રી બનાવે છે અથવા ચોક્કસ આઉટપુટ ક્રિયાઓને કૉલ કરે છે. ઝાંખી શિફ્ટ-રિડ્યુસ પાર્સર બેક અપ લીધા વિના ટેક્સ્ટ પર એક ફોરવર્ડ પાસમાં ઇનપુટ ટેક્સ્ટને સ્કેન કરે છે અને પાર્સ કરે છે. પાર્સર અનુમાન લગાવ્યા વિના અથવા પીછેહઠ કર્યા વિના, પાર્સ ટ્રીને ક્રમશઃ, નીચેથી ઉપર અને ડાબેથી જમણે બનાવે છે. આ પાસના દરેક બિંદુ પર, પાર્સરે ઇનપુટ લખાણના સબટ્રીઝ અથવા શબ્દસમૂહોની સૂચિ એકઠી કરી છે જે પહેલાથી જ પાર્સ કરવામાં આવી છે. તે પેટા વૃક્ષો હજુ સુધી એક સાથે જોડાયેલા નથી કારણ કે પાર્સર હજુ સુધી વાક્યરચના પેટર્નના જમણા છેડા સુધી પહોંચ્યું નથી જે તેમને જોડશે. સ્ટ્રિંગ A = B + C * 2 નો વિચાર કરો. ઉદાહરણમાં પગલું 7 પર, ફક્ત "A = B +" નું પદચ્છેદન કરવામાં આવ્યું છે. પાર્સ વૃક્ષનો માત્ર છાયાવાળો નીચે-ડાબો ખૂણો અસ્તિત્વમાં છે. 8 અને તેનાથી ઉપરના ક્રમાંકિત પાર્સ ટ્રી નોડ્સમાંથી કોઈ પણ હજુ સુધી અસ્તિત્વમાં નથી. નોડ 1,2,6 અને 7 એ તમામ વસ્તુઓ 1.7 ને આવરી લેતા અલગ પેટા વૃક્ષોના મૂળ છે. નોડ 1 એ ચલ A છે, નોડ 2 એ સીમાંકન = છે, નોડ 6 એ સારાંશ B છે, અને નોડ 7 એ સંચાલક + છે. આ ચાર મૂળ ગાંઠો અસ્થાયી રૂપે પાર્સ સ્ટેકમાં રાખવામાં આવે છે. ઇનપુટ સ્ટ્રીમનો બાકીનો અનપરસ્ડ ભાગ "C * 2" છે. શિફ્ટ-રિડ્યુસ પાર્સર શિફ્ટ પગલાંઓ અને રિડ્યુસ પગલાંઓનું સંયોજન કરીને કામ કરે છે, તેથી આ નામ પડ્યું છે. ઇનપુટ સ્ટ્રીમમાં શિફ્ટ પગલું એક પ્રતીક દ્વારા આગળ વધે છે. તે સ્થાનાંતરિત પ્રતીક નવું સિંગલ-નોડ પાર્સ વૃક્ષ બની જાય છે. એક ઘટાડો પગલું તાજેતરના કેટલાક પાર્સ વૃક્ષો પર પૂર્ણ વ્યાકરણના નિયમને લાગુ કરે છે, જે તેમને નવા મૂળ પ્રતીક સાથે એક વૃક્ષ તરીકે જોડે છે. પાર્સર આ પગલાંઓ સાથે ત્યાં સુધી ચાલુ રાખે છે જ્યાં સુધી તમામ ઇનપુટનો વપરાશ ન થાય અને તમામ પાર્સ વૃક્ષોને એક જ વૃક્ષમાં ઘટાડી દેવામાં આવે જે સંપૂર્ણ કાનૂની ઇનપુટનું પ્રતિનિધિત્વ કરે. વૃક્ષ નિર્માણના પગલાં દરેક પાર્સ પગલામાં, સમગ્ર ઇનપુટ લખાણને પાર્સ સ્ટેક, વર્તમાન લુકહેડ પ્રતીક અને બાકી રહેલા બિન-સ્કેન કરેલા લખાણમાં વહેંચવામાં આવે છે. પાર્સરની આગામી ક્રિયા જમણી બાજુના સ્ટૅક પ્રતીક (ઓ) અને લુકહેડ પ્રતીક દ્વારા નક્કી થાય છે. આ ક્રિયા એક કોષ્ટકમાંથી વાંચવામાં આવે છે જેમાં સ્ટૅક અને લુકહેડ પ્રતીકોના તમામ વાક્યરચનાત્મક રીતે માન્ય સંયોજનો હોય છે. એક સરળ ઉદાહરણ માટે જુઓ. વ્યાકરણ એ ઇનપુટ ભાષા માટે પેટર્ન અથવા વાક્યરચના નિયમોનો સમૂહ છે. તે તમામ ભાષાના નિયમોને આવરી લેતું નથી, જેમ કે સંખ્યાઓનું કદ, અથવા સમગ્ર કાર્યક્રમના સંદર્ભમાં નામોનો સુસંગત ઉપયોગ અને તેમની વ્યાખ્યાઓ. શિફ્ટ-રિડ્યુસ પાર્સર્સ સંદર્ભ-મુક્ત વ્યાકરણનો ઉપયોગ કરે છે જે ફક્ત પ્રતીકોની સ્થાનિક પેટર્ન સાથે કામ કરે છે. A = B + C * 2 સાથે મેળ કરવા માટે સક્ષમ જાવા અથવા C ભાષાના નાના સબસેટ તરીકે એક ઉદાહરણ વ્યાકરણ હોઈ શકે છેઃ અસાઇન કરો 'ID' = 'sums sums' 'sums' + 'પ્રોડક્ટ્સ sums' 'પ્રોડક્ટ્સ' 'પ્રોડક્ટ્સ' 'વેલ્યુ પ્રોડક્ટ્સ' 'વેલ્યુ વેલ્યુ' 'int વેલ્યુ' 'ID વ્યાકરણના અંતિમ પ્રતીકો લેક્સિકલ સ્કેનર દ્વારા ઇનપુટ સ્ટ્રીમમાં મળેલા બહુ-અક્ષર પ્રતીકો અથવા' ટોકન્સ 'છે. અહીં આમાં કોઈપણ પૂર્ણાંક અચળાંક માટે = + * અને પૂર્ણાંક અને કોઈપણ ઓળખકર્તાના નામ માટે ઓળખ શામેલ છે. વ્યાકરણ પૂર્ણાંક મૂલ્યો અથવા ઓળખની જોડણી શું છે તેની કાળજી લેતું નથી, ન તો તે ખાલી જગ્યાઓ અથવા રેખા વિરામની કાળજી લે છે. વ્યાકરણ આ અંતિમ પ્રતીકોનો ઉપયોગ કરે છે પરંતુ તેમને વ્યાખ્યાયિત કરતું નથી. તેઓ હંમેશા પાર્સ વૃક્ષના તળિયે ઝાડીવાળા છેડે હોય છે. સમ જેવા કેપિટલાઇઝ્ડ શબ્દો બિન-અંતિમ પ્રતીકો છે. આ ભાષામાં વિભાવનાઓ અથવા પેટર્ન માટેના નામો છે. તેઓ વ્યાકરણમાં વ્યાખ્યાયિત કરવામાં આવે છે અને ઇનપુટ પ્રવાહમાં ક્યારેય પોતાને મળતા નથી. તેઓ હંમેશા પાર્સ વૃક્ષના તળિયાની ઉપર હોય છે. તેઓ માત્ર કેટલાક વ્યાકરણના નિયમો લાગુ કરતા પાર્સરના પરિણામે થાય છે. કેટલાક નોન-ટર્મિનલને બે અથવા વધુ નિયમો સાથે વ્યાખ્યાયિત કરવામાં આવે છે; આ વૈકલ્પિક પેટર્ન છે. નિયમો પોતાને પાછા સંદર્ભિત કરી શકે છે. આ વ્યાકરણ પુનરાવર્તિત ગણિત સંચાલકોને નિયંત્રિત કરવા માટે પુનરાવર્તિત નિયમોનો ઉપયોગ કરે છે. સંપૂર્ણ ભાષાઓ માટે વ્યાકરણ યાદીઓ, કૌંસબદ્ધ અભિવ્યક્તિઓ અને નેસ્ટેડ નિવેદનોને નિયંત્રિત કરવા માટે પુનરાવર્તિત નિયમોનો ઉપયોગ કરે છે. કોઈપણ કોમ્પ્યુટર ભાષાને વિવિધ વ્યાકરણ દ્વારા વર્ણવી શકાય છે. શિફ્ટ-રિડ્યુસ પાર્સર માટેનું વ્યાકરણ પોતે અસંદિગ્ધ હોવું જોઈએ, અથવા ટાઈ-બ્રેકિંગ અગ્રતાના નિયમો દ્વારા વધારવામાં આવવું જોઈએ. આનો અર્થ એ છે કે ભાષાના આપેલ કાનૂની ઉદાહરણ પર વ્યાકરણ લાગુ કરવાની માત્ર એક જ સાચી રીત છે, જેના પરિણામે એક અનન્ય પાર્સ ટ્રી અને તે ઉદાહરણ માટે શિફ્ટ/રિડ્યુસ ક્રિયાઓનો એક અનન્ય ક્રમ બને છે. ટેબલ-સંચાલિત પાર્સર પાસે પાર્સર કોષ્ટકો તરીકે ઓળખાતા અપરિવર્તનશીલ ડેટામાં એન્કોડ કરેલ વ્યાકરણ વિશેનું તેનું તમામ જ્ઞાન હોય છે. પાર્સરનો પ્રોગ્રામ કોડ એક સરળ સામાન્ય લૂપ છે જે ઘણા વ્યાકરણ અને ભાષાઓને અપરિવર્તિત રીતે લાગુ પડે છે. પ્રાધાન્યતા પદ્ધતિઓ માટે કોષ્ટકો હાથથી તૈયાર કરી શકાય છે. એલઆર પદ્ધતિઓ માટે, જટિલ કોષ્ટકો યાંત્રિક રીતે બાયસન જેવા કેટલાક પાર્સર જનરેટર ટૂલ દ્વારા વ્યાકરણમાંથી મેળવવામાં આવે છે. પાર્સર કોષ્ટકો સામાન્ય રીતે વ્યાકરણ કરતા ઘણા મોટા હોય છે. અન્ય પાર્સર્સ કે જે ટેબલ-સંચાલિત નથી, જેમ કે રિકર્સિવ ડિસેન્ટ, દરેક ભાષાની રચનાને એક અલગ સબરૂટિન દ્વારા પાર્સ કરવામાં આવે છે, જે તે એક રચનાના વાક્યરચના માટે વિશિષ્ટ છે. પાર્સર ક્રિયાઓ શિફ્ટ-ઘટાડો પાર્સર કાર્યક્ષમ છે કારણ કે તેમાં કોઈ બેકઅપ લેવાનો સમાવેશ થતો નથી. તેનો કુલ અમલ સમય ઇનપુટની લંબાઈ અને સંપૂર્ણ પાર્સ ટ્રીના કદ સાથે રેખીય રીતે માપવામાં આવે છે. અન્ય પાર્સર પદ્ધતિઓ કે જે બેકટ્રેક કરે છે તે જ્યારે ખરાબ રીતે અનુમાન કરે છે ત્યારે ઘાતાંકીય સમય લાગી શકે છે. અનુમાન લગાવવાનું ટાળવા માટે, શિફ્ટ-રિડ્યુસ પાર્સર ઘણીવાર અગાઉ સ્કેન કરેલા પ્રતીકો સાથે શું કરવું તે નક્કી કરતા પહેલા આગામી સ્કેન કરેલા પ્રતીક પર આગળ (ડાબેથી જમણે લખાણમાં જમણે) જુએ છે. લેક્સિકલ સ્કેનર બાકીના પાર્સરની આગળ એક પ્રતીક કામ કરે છે. દરેક પદચ્છેદન નિર્ણય માટે લુકહેડ પ્રતીકને 'જમણા હાથનો સંદર્ભ' પણ કહેવામાં આવે છે. (ભાગ્યે જ, બે અથવા વધુ લુકહેડ પ્રતીકોનો ઉપયોગ કરી શકાય છે, જો કે મોટાભાગના વ્યવહારુ વ્યાકરણ એક લુકહેડ પ્રતીકનો ઉપયોગ કરવા માટે ડિઝાઇન કરી શકાય છે.) શિફ્ટ-રિડ્યુસ પાર્સર ત્યાં સુધી રાહ જુએ છે જ્યાં સુધી તે સંયુક્ત રચના શું છે તે પ્રતિબદ્ધ કરતા પહેલા કોઈ રચનાના તમામ ભાગોને સ્કેન અને પાર્સ ન કરે. પાર્સર પછી વધુ રાહ જોવાને બદલે સંયોજન પર તરત જ કાર્ય કરે છે. ઉપરના પાર્સ ટ્રીના ઉદાહરણમાં, પાર્સ ટ્રીના તે ભાગોને ગોઠવવા માટે વધુ રાહ જોવાને બદલે, બી શબ્દસમૂહ મૂલ્યમાં ઘટાડો થાય છે અને પછી 3-6 પગલાંઓમાં પ્રોડક્ટ્સ અને સમમાં + દેખાય છે. બી ને કેવી રીતે હેન્ડલ કરવું તે નિર્ણયો જમણી બાજુએ ઘણી પાછળથી દેખાતી વસ્તુઓને ધ્યાનમાં લીધા વિના, પાર્સર અને સ્કેનર દ્વારા પહેલેથી જ જે જોવામાં આવ્યું છે તેના પર આધારિત છે. ઘટાડાઓ સૌથી તાજેતરમાં વિશ્લેષિત વસ્તુઓનું પુનર્ગઠન કરે છે, જે લુકહેડ પ્રતીકની ડાબી બાજુએ તરત જ હોય છે. તેથી પહેલેથી જ પદચ્છેદન કરેલી વસ્તુઓની સૂચિ એક ઢગલાની જેમ કાર્ય કરે છે. આ પાર્સ સ્ટૅક જમણી તરફ વધે છે. સ્ટેકનો આધાર અથવા તળિયો ડાબી બાજુએ હોય છે અને ડાબી બાજુનો સૌથી જૂનો પાર્સ ટુકડો ધરાવે છે. દરેક ઘટાડાનું પગલું માત્ર જમણી બાજુના, સૌથી નવા પાર્સ ટુકડાઓ પર જ કાર્ય કરે છે. (આ સંચયી પાર્સ સ્ટેક ટોપ-ડાઉન પાર્સર્સ દ્વારા ઉપયોગમાં લેવાતા આગાહીયુક્ત, ડાબી તરફ વિકસતા પાર્સ સ્ટેકથી ખૂબ જ વિપરીત છે.) જ્યારે વ્યાકરણનો નિયમ જેમ કે પ્રોડક્ટ્સ * પ્રોડક્ટ્સ * વેલ્યુ લાગુ કરવામાં આવે છે, ત્યારે સ્ટેક ટોપમાં પાર્સ વૃક્ષો હોય છે. "પ્રોડક્ટ્સ * વેલ્યુ". નિયમની જમણી બાજુના આ ઉદાહરણને હેન્ડલ કહેવામાં આવે છે. ઘટાડવાનું પગલું હેન્ડલ "પ્રોડક્ટ્સ * વેલ્યુ" ને ડાબી બાજુના નોન ટર્મિનલ દ્વારા બદલે છે, આ કિસ્સામાં મોટા ઉત્પાદનો. જો પાર્સર સંપૂર્ણ પાર્સ વૃક્ષો બનાવે છે, તો પછી આંતરિક ઉત્પાદનો માટે ત્રણ વૃક્ષો, *, અને મૂલ્યને મોટા ઉત્પાદનો માટે નવા વૃક્ષ મૂળ દ્વારા જોડવામાં આવે છે. નહિંતર, આંતરિક ઉત્પાદનો અને મૂલ્યમાંથી સિમેન્ટીક વિગતો કેટલાક પછીના કમ્પાઇલર પાસમાં આઉટપુટ થાય છે, અથવા સંયુક્ત થાય છે અને નવા ઉત્પાદનો પ્રતીકમાં સાચવવામાં આવે છે. પાર્સર જ્યાં સુધી તે ત્યાં વ્યાકરણના નિયમોના નવા પૂર્ણ થયેલા ઉદાહરણો શોધતું રહે ત્યાં સુધી પાર્સ સ્ટેકની ટોચ પર ઘટાડા લાગુ કરવાનું ચાલુ રાખે છે. જ્યારે કોઈ વધુ નિયમો લાગુ કરી શકાતા નથી, ત્યારે પાર્સર પછી લુકહેડ પ્રતીકને પાર્સ સ્ટેક પર ખસેડે છે, નવા લુકહેડ પ્રતીકને સ્કેન કરે છે અને ફરીથી પ્રયાસ કરે છે. શિફ્ટ-રિડ્યુસ પાર્સર્સના પ્રકારો પાર્સર કોષ્ટકો દર્શાવે છે કે ટોચના પાર્સ સ્ટેક પ્રતીકો અને લુકહેડ પ્રતીકના દરેક કાનૂની સંયોજન માટે આગળ શું કરવું. તે આગળની ક્રિયા અનન્ય હોવી જોઈએ; ક્યાં તો પાળી, અથવા ઘટાડો, પરંતુ બંને નહીં. (આ સ્પષ્ટ હોવા ઉપરાંત વ્યાકરણ પર કેટલીક વધુ મર્યાદાઓ સૂચવે છે.) કોષ્ટકની વિગતો વિવિધ પ્રકારના શિફ્ટ-રિડ્યુસ પાર્સર્સ વચ્ચે ખૂબ બદલાય છે. અગ્રતાના પદચ્છેદનમાં, હેન્ડલ્સનો જમણો છેડો અગ્રતાના સ્તર અથવા ટોચના સ્ટૅક પ્રતીકોની વ્યાકરણની ચુસ્તતાની સરખામણી લુકહેડ પ્રતીક સાથે કરીને જોવા મળે છે. ઉપરના ઉદાહરણમાં, સ્ટેટમેન્ટ ડિલિમિટરની સરખામણીમાં ઇન્ટ અને આઈડી આંતરિક વ્યાકરણના સ્તર સાથે સંબંધિત છે. તેથી પૂર્ણાંક અને આઈ. ડી. બંનેને; કરતા વધુ પ્રાધાન્ય માનવામાં આવે છે અને જ્યારે પણ અનુસરવામાં આવે ત્યારે તેને ઘટાડીને કંઈક બીજું કરવું જોઈએ. અગ્રતાના પદચ્છેદનની વિવિધ જાતો છે, દરેકમાં હેન્ડલનો ડાબો છેડો શોધવાની અને લાગુ કરવા માટે સાચો નિયમ પસંદ કરવાની વિવિધ રીતો છેઃ ઓપરેટર-પ્રેસીડેન્સ પદચ્છેદન, એક ખૂબ જ સરળ આંકડાકીય પદ્ધતિ છે જે અભિવ્યક્તિઓ માટે કામ કરે છે પરંતુ સામાન્ય પ્રોગ્રામ વાક્યરચના માટે નહીં. સરળ પ્રાધાન્યતા પાર્સર, જમણા અને ડાબા છેડા શોધવા માટે એક મોટા MxN કોષ્ટકનો ઉપયોગ કરે છે. પી. એલ. 360 માં વપરાય છે. સામાન્ય પ્રોગ્રામિંગ ભાષાઓનું સંચાલન કરતું નથી. નબળા અગ્રતા પાર્સર, માત્ર હેન્ડલ્સના જમણા છેડા શોધવા માટે અગ્રતા કોષ્ટકનો ઉપયોગ કરે છે. સરળ અગ્રતા કરતાં વધુ વ્યાકરણ સંભાળે છે. વિસ્તૃત અગ્રતાક્રમ પદચ્છેદન. મિક્સ્ડ સ્ટ્રેટેજી પ્રેસીડન્સ પાર્સર, જેનો ઉપયોગ એક્સ. પી. એલ. ના મૂળ સંસ્કરણ દ્વારા થાય છે. "ટ્રિપલ્સ" નો સમાવેશ કરવા માટે, કોઈપણ અગ્રતાક્રમ ઓળખકારમાં અંતર્ગત "ડબલ્સ" ને વિસ્તરે છે. એસએલઆર કરતાં ઓછી શક્તિશાળી. સામાન્ય રીતે XPL જેવી પ્રમાણમાં નાની ભાષાઓ માટે પણ ઘણા મોટા કોષ્ટકો હોય છે, કારણ કે તેમાં ઘણા બધા "ત્રિપલ" હોય છે, જે પ્રાધાન્ય પદ્ધતિઓ દ્વારા લાદવામાં આવેલી મર્યાદાની બહારના વ્યાકરણને ઓળખવા માટે જરૂરી હોય છે. પ્રેસીડેન્સ પાર્સર્સ તેઓ સંભાળી શકે તેવા વ્યાકરણમાં મર્યાદિત છે. નિર્ણયો લેતી વખતે તેઓ મોટાભાગના પાર્સ સ્ટેકની અવગણના કરે છે. તેઓ માત્ર સર્વોચ્ચ પ્રતીકોના નામોને જ ધ્યાનમાં લે છે, વ્યાકરણમાં તે પ્રતીકો હવે ક્યાં દેખાઈ રહ્યા છે તેના સંપૂર્ણ સંદર્ભને નહીં. પ્રાધાન્ય માટે જરૂરી છે કે સમાન દેખાતા પ્રતીક સંયોજનોનું વિશ્લેષણ કરવું જોઈએ અને સમગ્ર વ્યાકરણમાં સમાન રીતે તેનો ઉપયોગ કરવો જોઈએ, જો કે તે સંયોજનો સંદર્ભને ધ્યાનમાં લીધા વિના થાય છે. એલઆર પાર્સર્સ શિફ્ટ-રિડ્યુસ પાર્સિંગનું વધુ લવચીક સ્વરૂપ છે, જે ઘણા વધુ વ્યાકરણનું સંચાલન કરે છે. એલ. આર. પાર્સર પ્રોસેસિંગ એલ. આર. પાર્સર સ્ટેટ મશીનની જેમ કાર્ય કરે છે, જે દરેક પાળી માટે સ્ટેટ ટ્રાન્ઝીશન કરે છે અથવા ક્રિયા ઘટાડે છે. આ એક ઢગલાનો ઉપયોગ કરે છે જ્યાં વર્તમાન સ્થિતિને પાળી ક્રિયાઓ દ્વારા (નીચે) ધકેલી દેવામાં આવે છે. આ સ્ટૅક પછી ઘટાડો ક્રિયાઓ દ્વારા પૉપ (ઉપર) કરવામાં આવે છે. આ પદ્ધતિ એલ. આર. પાર્સરને તમામ નિર્ધારક સંદર્ભ-મુક્ત વ્યાકરણને સંભાળવાની મંજૂરી આપે છે, જે અગ્રતાના વ્યાકરણનો સુપરસેટ છે. એલ. આર. પાર્સર સંપૂર્ણ રીતે કેનોનિકલ એલ. આર. પાર્સર દ્વારા લાગુ કરવામાં આવે છે. લુક-હેડ એલઆર અને સિમ્પલ એલઆર પાર્સર્સ તેના સરળ સ્વરૂપોને અમલમાં મૂકે છે જેણે મેમરીની જરૂરિયાતોમાં નોંધપાત્ર ઘટાડો કર્યો છે. તાજેતરના સંશોધનોએ એવી પદ્ધતિઓ ઓળખી છે કે જેના દ્વારા કેનોનિકલ એલ. આર. પાર્સર્સને ક્નુથના ટેબલ-બિલ્ડિંગ અલ્ગોરિધમ પર નાટ્યાત્મક રીતે ઘટાડેલી ટેબલ જરૂરિયાતો સાથે અમલમાં મૂકી શકાય છે. એલ. આર., એલ. એ. એલ. આર. અથવા એસ. એલ. આર., મૂળભૂત સ્થિતિ મશીન સમાન છે; માત્ર કોષ્ટકો અલગ છે, અને આ કોષ્ટકો લગભગ હંમેશા યાંત્રિક રીતે ઉત્પન્ન થાય છે. વધુમાં, આ કોષ્ટકો સામાન્ય રીતે એવી રીતે લાગુ કરવામાં આવે છે કે REDUCE બંધ સબરૂટિનમાં કૉલમાં પરિણમે છે જે સ્ટેટ મશીનની બહાર છે અને જે એક કાર્ય કરે છે જે વ્યાકરણના નિયમના શબ્દાર્થ દ્વારા ગર્ભિત છે જે REDUCEd કરવામાં આવી રહ્યું છે. તેથી, પાર્સરને એક અપરિવર્તનશીલ સ્થિતિ મશીન ભાગ અને એક ભિન્ન સિમેન્ટિક્સ ભાગમાં વિભાજિત કરવામાં આવે છે. આ મૂળભૂત તફાવત ઉચ્ચ ગુણવત્તાના પાર્સર્સના વિકાસને પ્રોત્સાહન આપે છે જે અપવાદરૂપે વિશ્વસનીય છે. ચોક્કસ સ્ટૅક સ્થિતિ અને લુકહેડ પ્રતીકને જોતાં, ચોક્કસપણે ચાર સંભવિત ક્રિયાઓ છે, ભૂલ, શિફ્ટ, ઘટાડો અને સ્ટોપ (ત્યારબાદ રૂપરેખાંકનો તરીકે ઓળખવામાં આવે છે). રૂપરેખાંકનમાં બિંદુની હાજરી, ડોટની જમણી બાજુએ દર્શાવેલ લુકહેડ પ્રતીક (અને જે હંમેશા ટર્મિનલ પ્રતીકને અનુરૂપ હોય છે) સાથે વર્તમાન લુકહેડ સ્થિતિને રજૂ કરે છે, અને ડોટની ડાબી બાજુએ વર્તમાન સ્ટેક સ્થિતિ (અને જે સામાન્ય રીતે નોન-ટર્મિનલ પ્રતીકને અનુરૂપ હોય છે). ઉચ્ચ પ્રદર્શન સહિત વ્યવહારુ કારણોસર, કોષ્ટકો સામાન્ય રીતે કંઈક અંશે મોટા, બે-બીટ પ્રતીકોની સહાયક શ્રેણી દ્વારા વિસ્તૃત કરવામાં આવે છે, દેખીતી રીતે ચાર બે-બીટ પ્રતીકોમાં સંકુચિત થાય છે, એક બાઈટ, બાઈટ-લક્ષી મશીનો પર કાર્યક્ષમ ઍક્સેસ માટે, ઘણીવાર એનકોડ કરવામાં આવે છેઃ 00b એ ERROR 01b ને રજૂ કરે છે જે શિફ્ટ 10b ને રજૂ કરે છે જે REDUCE 11b ને રજૂ કરે છે જે STOP ને રજૂ કરે છે (STOP એ શિફ્ટનો વિશેષ કેસ છે). સમગ્ર એરેમાં સામાન્ય રીતે મોટે ભાગે ભૂલ રૂપરેખાંકનો, શિફ્ટ અને રીડ્યુસ રૂપરેખાંકનોની વ્યાકરણ-નિર્ધારિત સંખ્યા અને એક સ્ટોપ રૂપરેખાંકનનો સમાવેશ થાય છે. પ્રોગ્રામિંગ સિસ્ટમો કે જે ક્વાટર્નરી આંકડાકીય પ્રણાલી (આધાર 4, ક્વાટર્નરી અંક દીઠ બે બિટ્સ) માં મૂલ્યોના સ્પષ્ટીકરણને ટેકો આપે છે, જેમ કે એક્સ. પી. એલ., આને આ રીતે કોડેડ કરવામાં આવે છે, ઉદાહરણ તરીકેઃ "(2). 0". ભૂલને રજૂ કરે છે "(2). 1". શિફ્ટને રજૂ કરે છે "(2). 2". ઘટાડાનું પ્રતિનિધિત્વ કરે છે "(2). 3". સ્ટોપને રજૂ કરે છે અને રિડ્યુસ કોષ્ટકો એરેથી અલગથી લાગુ કરવામાં આવે છે. સહાયક શ્રેણી માત્ર વર્તમાન સ્થિતિ અને લુકહેડ પ્રતીક માટે "તપાસ" કરવામાં આવે છે. (સહાયક) એરે "પૂર્ણ" છે, જ્યારે (શિફ્ટ અને રિડ્યુસ) કોષ્ટકો ખરેખર ખૂબ જ "વિરલ" હોઈ શકે છે, અને તે શિફ્ટ અને રિડ્યુસ કોષ્ટકોના શ્રેષ્ઠ "વિઘટન" દ્વારા નોંધપાત્ર કાર્યક્ષમતા પ્રાપ્ત કરી શકાય છે (ભૂલ અને સ્ટોપને કોઈ કોષ્ટકોની જરૂર નથી). શિફ્ટ-રિડ્યુસ પાર્સરની મૂળભૂત વ્યાખ્યા પરથી શિફ્ટ અને રિડ્યુસ રૂપરેખાંકનો સ્પષ્ટ છે. STOP, પછી, એક રૂપરેખાંકનનું પ્રતિનિધિત્વ કરે છે જ્યાં સ્ટેકની ટોચ પરની સ્થિતિ અને લુકહેડ ટર્મિનલ પ્રતીક વિષય વ્યાકરણની અંદર હોય છે, અને પ્રોગ્રામના અંતને રજૂ કરે છેઃ δ <પ્રોગ્રામ> δ અંતિમ δથી આગળ સ્થળાંતર કરવું અશક્ય છે જેથી પહોંચવું, કલ્પનાત્મક રીતે δ <પ્રોગ્રામ> δ> ERROR, પછી, એક રૂપરેખાંકનનું પ્રતિનિધિત્વ કરે છે જ્યાં સ્ટેકની ટોચ પરની સ્થિતિ, અને લુકહેડ ટર્મિનલ પ્રતીક વિષય વ્યાકરણની અંદર નથી. આ ભૂલ પુનઃપ્રાપ્તિ પ્રક્રિયાને બોલાવવાની તક રજૂ કરે છે, કદાચ, તેના સૌથી સરળ સ્વરૂપમાં, લુકહેડ ટર્મિનલ પ્રતીકને કાઢી નાખવા અને આગામી ટર્મિનલ પ્રતીકને વાંચવા માટે, પરંતુ અન્ય ઘણી પ્રોગ્રામ કરેલી ક્રિયાઓ શક્ય છે, જેમાં સ્ટેકની કાપણી, અથવા લુકહેડ ટર્મિનલ પ્રતીકને કાઢી નાખવું અને સ્ટેકની કાપણીનો સમાવેશ થાય છે (અને પેથોલોજીકલ કિસ્સામાં, સામાન્ય રીતે જ્યાં <પ્રોગ્રામ> માં ફક્ત "નલ સ્ટેટમેન્ટ" નો સમાવેશ થાય છે). મોટા ભાગના કિસ્સાઓમાં, સ્ટેકને હેતુપૂર્વક પૂર્વ-લોડ કરવામાં આવે છે, એટલે કે, પ્રારંભ કરવામાં આવે છે, જેમાં પ્રારંભિક δ પહેલેથી જ ઓળખાયેલ હોવાનું માનવામાં આવે છે. આ, પછી, પ્રોગ્રામની શરૂઆતનું પ્રતિનિધિત્વ કરે છે, અને તેથી, એક અલગ START રૂપરેખાંકન રાખવાનું ટાળે છે, જે વિભાવનાત્મક રીતે એક વિશેષ સ્યુડો-ટર્મિનલ પ્રતીક છે જે યાંત્રિક રીતે વ્યાકરણમાં ઉમેરવામાં આવે છે, જેમ કે <પ્રોગ્રામ> એક વિશેષ સ્યુડો-નોનટર્મિનલ પ્રતીક છે જે યાંત્રિક રીતે વ્યાકરણમાં ઉમેરવામાં આવે છે (જો પ્રોગ્રામરે વ્યાકરણમાં સ્પષ્ટપણે <પ્રોગ્રામ> નો સમાવેશ કર્યો ન હોય, તો પછી <પ્રોગ્રામ> પ્રોગ્રામર વતી આપમેળે વ્યાકરણમાં ઉમેરવામાં આવશે). સ્પષ્ટપણે, આવા પાર્સર ચોક્કસપણે એક (ગર્ભિત) START રૂપરેખાંકન અને એક (સ્પષ્ટ) STOP રૂપરેખાંકન ધરાવે છે, પરંતુ તે કરી શકે છે, અને સામાન્ય રીતે તેમાં સેંકડો શિફ્ટ અને રીડ્યુસ રૂપરેખાંકનો અને કદાચ હજારો ભૂલ રૂપરેખાંકનો હોય છે. સંદર્ભો પાર્સિંગ અલ્ગોરિધમ્સ